Simulating the Denver Airport Automated Baggage System

The Denver International Airport Automated Baggage System (DIA ABS), first deployed in 1994, has been plagued by a series of highly publicized problems. Because of its great expense and troubled commencement, you can reasonably wonder whether or not the system -- which is typical of many large-scale, missioncritical system-integration efforts -- should have been built at all. To examine this question, I used David Betz's Xlisp to implement a computer simulation of the essential mechanism of the DIA ABS. You can use the techniques I describe here to simulate other large-scale system-integration projects.

According to R. deNeufville in "Baggage System at Denver: Prospects and Lessons" (Journal of Air Transport Management, December 1994), the DIA ABS is designed to deliver individual bags on a radio-monitored cart called a "destination-coded vehicle" (DCV). As Figure 1 illustrates, conveyor belts feed the central network of DCVs. The conveyor advances only when there is an empty cart available for the leading bag. The performance of the entire system depends on how quickly the empty "telecars" reach the conveyor belt.

All in all, there are 4000 DCVs on about 5.5 miles of conveyors and over 21 miles of track. Each track is designed to carry 60 DCVs a minute. The original projected cost for this project was supposed to be $195 million. As it turned out, the project cost in excess of $250 million, was delayed for several months, and continues to be unreliable.

Simulation Design

As illustrated in the enlarged portion of Figure 1, I simulated one concourse of the DIA ABS. The cart and track subsystem is the only controllable component of the system. Again, the conveyor is totally governed by the telecar system.

Every simulation consists of resources, transactions, and a scheduler. In this particular simulation:

• Airplanes arriving and departing, and luggage items loading and unloading, are transactions.
• Arrival gates and telecars are resources.
• The schedule is the arrival rate of airliners and terminal-side luggage items.

When the simulation executes, the transactions compete for the resources according to the schedule.

Driving the simulation are luggage items and airliners, which arrive at random intervals for processing by the event queue. I do this using the built-in Xlisp random-number generator. Since this random-number generator only provides values between 0.0 and 1.0, however, I can only obtain times between events/transactions of at most 1 second. To get around this limitation, and to control the rate at which each type of item arrives in the simulation, I use the negative logarithm of a random number generated by Xlisp. The result of this calculation is added to the arrival time of the preceding transaction to determine the arrival time of the current transaction.

Each arriving luggage item is paired with a telecar from the resource queue, assigned a destination gate number and an arrival time, and the resulting transaction is added to the event queue. Each arriving airliner is assigned a terminal gate and unloads 200 luggage items. At that time, 200 telecars are dispatched from the resource queue and assigned to the 200 luggage items. Arrival times are assigned to each telecar and the result is added to the event queue. After half an hour, each airplane departs its gate.

The simulation processes events on the event queue in time order according to the scenario. The simulation terminates when the time value associated with the next event is greater than eight hours (28,800 seconds) -- the duration of the simulation -- or when more telecars are requested than are available (a deadlock condition). System statistics are reported at each airliner arrival and departure and at the end of the simulation.

Implementation

My DIA ABS simulation is based on a design sketched in Adele Goldberg and Dave Robson's Smalltalk-80: The Language and Its Implementation (Addison-Wesley, 1983). Since I wanted to run the simulation on my Amiga, and there is no Smalltalk interpreter available for the Amiga, I used Xlisp instead. Since Xlisp has a built-in object-oriented programming capability that resembles Smalltalk, and is $1500 cheaper than any available Smalltalk software for the PC (Xlisp is free), I ported the Smalltalk simulation classes into Xlisp.

The simulation (see Listing One, comprises four concrete classes: simulation, exponential, resource, and arrival gates. Figure 2 lists the classes and their message-selector protocols. The design is completely parameterized so you can easily modify simulation variables.

The event queue (Figure 3) is the simulation scheduler and the primary data structure of the entire system. The simulation class owns and controls the event queue, as you can see in Figure 4, queuing transactions and allocating resources. The exponential class generates transactions that drive the simulation. There are two instances of this class, one for luggage from the terminal and another for airliner arrivals. The resource class manages the conveyor-head telecar holding area, and the arrivalGates class manages the arrival gates and their associated telecar holding areas.

Each transaction has an associated time value, determined by the time value of the previous transaction plus a random time interval. At a given instance, the queued transaction that has the lowest associated time value is dequeued. Upon reaching certain conditions, the simulation terminates: the equivalent of the baggage system failing.

If the transaction is a luggage item from the terminal, the simulation increments its time value by 600 seconds (10 minutes), assigns a destination gate and telecar, and requeues it as a new transaction. If the transaction is a destination gate, the associated telecar is added to the telecar-holding buffer associated with that gate, and no new transactions are added to the event queue. If the transaction is a "free gate" transaction, the gate status is reset. No new transactions are added to the event queue.

If the transaction is an arriving airplane, 200 telecar transactions (one for each luggage item) are added to the event queue. The simulation finds a free arrival gate and assigns it to the plane. That arrival gate becomes the destination gate for all arriving terminal-side luggage items. A "free gate" transaction with a time value of the current time, plus the 1800 seconds (30 minutes) that the airplane remains at the arrival gate, is added to the event queue. The gate status is then set to "busy." The simulation prints a report of the time of airliner arrival, the number of available telecars at the conveyor head, and each arrival gate. If 200 telecars are not available at the conveyor head, the simulation terminates.

When a transaction occurs, if its time value is greater than 28,800 seconds (8 hours) -- a large and arbitrarily chosen number -- the simulation terminates and reports the number of available telecars at the conveyor head and at each arrival gate.

Each plane's arrival and departure triggers the simulation:report method, which displays the current simulation time value together with the distribution of the telecars among the various holding areas. Any telecars that are not accounted for are in transit (on the eventqueue) and constitute unavailable resources. The final section is the system state at the end of the simulation.

Simulation Results

Figure 5 shows a sample of the simulation output. The first few lines are the system state at the start of the simulation, including the starting clock time.

The first event shown, likely a terminal-side luggage item, occurs 308 seconds (approximately 5 minutes) into the simulation. The simulation informs you that all the telecars are at the conveyor-head holding area.

The next simulation event is an airliner arrival at 650 seconds (11 minutes) into the simulation. The "active gate..." line informs you that the arriving airliner goes to gate one. At that time, 25 telecars are carrying terminal-side luggage items to the gate area. This is determined by subtracting the number of telecars showing in the report from 2000, the total number of telecars in the simulation.

The next event is the departure of the airliner from gate one. This is a purely deterministic event; it occurs exactly 1800 seconds (30 minutes) after the airliner arrival. At that time, 69 telecars are in transit between the conveyor-head holding area and the gate area.

The simulation continues relating airliner arrivals and departures together with reports of the number of telecars at each gate, at the conveyor head and, indirectly, in transit. Just before the simulation terminates (when the airplane departs gate three at simulated time 5616 seconds), the number of telecars at the conveyor head is critically low. Should another plane appear at this time, the simulated ABS would likely deadlock, since there are not enough available telecars to handle the airliner arrival.

This is the essence of the "empty car management" problem that the ABS system integrators describe. By using a simulation like the one presented here, the system designers could have anticipated this problem before construction ever began.

One final interesting observation from the output is that, in this particular example, actual machine clock time (found by subtracting the start run time from the end run time) roughly equaled simulation time (the time associated with the simulation termination). Both times were about an hour and a half. This provides a crude idea of the complexity of the system we are simulating.

Conclusion

This simulation demonstrates the feasibility of PC-hosted, object-oriented, flexible simulation of a complex, mission-critical system. The code for this particular simulation is 60 percent reusable, and could easily be placed on a web server for remote execution. The methods are general enough to apply to almost any given simulation.

This simulation does not capture every detail of the actual functioning DIA ABS. First, it runs at half the scale of the real system -- 2000 telecars as opposed to 4000 telecars. It doesn't factor in the reliability attributes of the actual ABS, such as the misdirection of cars, system outages due to communications overload, or other mechanical failures. These attributes could be incorporated in future versions.

This particular simulation revealed that the arbitrary initial placement of the telecars at the conveyor head was not a good idea. This flaw could have been solved by choosing a different initial placement, perhaps using a continuous-redistribution protocol that anticipated airplane arrival, or even a major redesign of the cart and track hardware.

The irony of the failure of the DIA ABS is that the original consulting firm did run a simulation of the ABS prior to the contract award. Because of the time lag between the simulation and the contract (over a year), the consultants did not report the simulation results directly to the contractor. Without reporting the results, they did recommend that the Denver Airport Authority not implement the single-bag-per-cart design. However, the city discounted the consultants' recommendations and went ahead with the single-bag-per-cart system. Consider how different things might have been had the city advised the contractor of the simulation findings and conclusions.

DDJ

Listing One

; <<<>>> Simulation of the Denver Airport Automated Baggage System; <<<>>> Programmer:  John Swartz     
; <<<>>> The design is a based on the design sketched in
; <<<>>> chapters 21, 22, 23 and 24 of Goldberg/Robson's 
; <<<>>> Smalltalk-80: The Language and Its Implementation.
(defun express (time chain) 
          (cond
               ((null chain) (print "exit function express"))
               (t (progn 
                    (setq cc (list time 'T (car  chain)))
;                   (print cc)
                    (denver :enqueue cc)
                    (express (1+ time) (cdr chain))
                    ))))
(defun service (item)     ;  <<<===   process events off the
event queue  !!!
          (case (cadr item)
               ( 'B    (subst (list (+ 600 (car item))  (denver:query) 
                    (car (telecarts :get 'bags))) item  item))
               ('"gateOne" (setq vv (car (last item)))
                    (gateOne :accept  vv )
                         ())
               ('"gateTwo" (setq vv (car (last item)))
                    (gateTwo :accept  vv )
                         ())
               ('"gateThree" (setq vv (car (last item)))
                    (gateThree :accept  vv )
                         ())
               ('"gateFour" (setq vv (car (last item)))
                    (gateFour :accept  vv )
                         ())
               ('"gateFive" (setq vv (car (last item)))
                    (gateFive :accept  vv )
                         ())
               ( 'A 
               (setq pp (list  '"Airliner arrival at system time " (car item)))
                    (print ())
                    (print pp)
                         (setq rr (denver :report))
                         (print (cadar rr))
                         (if (> 300 (cadar rr)) 
                    (print "Simulation terminating because of deadlock"))
                         (mapcar print rr)
                         (if (> 300 (cadar rr)) (exit))
                    (dotimes (x 400 t) ;  <<<===  send 500 carts to airplane
                         (setq zz
                         (list (+ 1200 (car item) x)
                              'T
                              (car (telecarts  :get 'bags))
                              ))
                         (denver :enqueue zz))
               (or  
                     (and (gateone :test) 
                          (gateone :set)
                           (print "active gate is gateOne")
                         (express (+ 600 (car item)) (gateOne:dispatch))
                         (gateOne :initialize)
;                        (mapcar print (denver :report))
                          (denver :assign '"gateOne")
                         (subst (list (+ 1800 (car item)) 'F
                         "gateOne") item item))
                    (and (gatetwo :test) 
                           (print "active gate is gateTwo")
                         (express (+ 600 (car item)) (gateTwo:dispatch))
                         (gateTwo :initialize)
;                        (mapcar print (denver :report))
                          (gatetwo :set)
                          (denver :assign '"gateTwo")
                         (subst (list (+ 1800 (car item)) 'F
                         "gateTwo") item item))
                    (and (gatethree :test) 
                          (gatethree :set)
                           (print "active gate is gateThree")
                         (express (+ 600 (car item)) (gateThree:dispatch))
                         (gateThree :initialize)
                          (denver :assign '"gateThree")
                         (subst (list (+ 1800 (car item)) 'F
                         "gateThree") item item))
                    (and (gatefour :test) 
                          (gatefour :set)
                           (print "active gate is gateFour")
                         (express (+ 600 (car item)) (gateFour:dispatch))
                         (gateFour :initialize)
                          (denver :assign '"gateFour")
                         (subst (list (+ 1800 (car item)) 'F
                         "gateFour") item item))
                    (and (gatefive :test) 
                          (gatefive :set)
                           (print "active gate is gateFive")
                          (denver :assign '"gatefive")
                         (subst (list (+ 1800 (car item)) 'F
                         "gateFive") item item))))
               (  'F  (setq pp (list '"Airliner departure from gate  "
                    (car (last item))  '"  at simulation time  " (car item)))
                    (print ())
                    (print pp)
                    (mapcar print (denver :report))
                    (case (caddr item)
                         ('"gateOne" (gateOne :reset))
                         ('"gateTwo" (gateTwo :reset))
                         ('"gateThree" (gateThree :reset))
                         ('"gateFour" (gateFour :reset))
                         ('"gateFive" (gateFive :reset))
                         )
                    ())
               (  'T  (telecarts :put 'bags (car (last item)))
                    ())
                    ))
(defun actuate (xactions)


</p>
;    locate next event on the eventQueue .... and move it to front of same.
     (cons      (assoc (apply 'min (mapcar car xactions)) xactions)
          (remove   (assoc (apply 'min (mapcar car xactions)) xactions)
               xactions)))
(expand 500)
(print (mem))
;(load "trace.lsp")
;(trace 'express)
;    Create classes
(setq simulation (class :new '(resources currentTime eventQueue activeGate)))
(simulation :answer :isnew '()
     '((setq resources nil) 
       (setq currentTime nil)
       (setq eventQueue nil)
       (setq activeGate "gateOne")  self))
(simulation :answer :enqueue '(event)
          '((setq eventQueue (cons event eventQueue) )  ))
(simulation :answer :abridge '()
          '((setq eventqueue
          (remove (assoc (apply 'min (mapcar car eventqueue)) eventqueue)
               eventqueue))
               ))
;         *******
;         this is the primary method of the simulation
;         ********
(simulation :answer :dequeue '(&aux tick)
          '((setq tick (car (actuate eventqueue)))
               ))
;            (self :abridge )))
(simulation :answer :revise '()
          '((setq eventqueue (cdr (actuate eventqueue))) self))
(simulation :answer :assign '(gate)
          '((setq activegate gate) self))
(simulation :answer :display '()
          '((mapcar print eventqueue) self))
(simulation :answer :query '(&aux active)
          '((setq active activegate)))
(simulation :answer :report '(&aux line)
          '((setq line 
          (list 
          (list '"telecarts at conveyorHead" (length (telecarts:get 'bags)))
               (list '"telecarts at  gateOne  " (gateone:display))
                (list '"telecarts at gateTwo  " (gatetwo:display))
               (list '"telecarts at gateThree  " ( gatethree:display))
               (list '"telecarts at gateFour   " (gatefour:display))
               (list '"telecarts at gateFive   " (gatefive:display))
               ))))
(load "resource.lsp")
;(print "\n simulation")
;(print (simulation :show))


</p>
(setq exponential (class  :new '(mu type)))
(exponential :answer :isnew '() 
     '((setq mu nil) 
          (setq type nil) self))
(exponential  :answer  :parameter  '(value)
          '((setq mu value) self ))
(exponential :answer :next '( &aux  time)
          '((setq time (* mu (- ( log (random 1.0)))))))
(print "\n exponential")
(print (exponential :show))
(print "resource")
; vvv  instantiate the simulation  v v v
(setq denver (simulation :new))
(setq terminalSide (exponential :new))
(terminalSide :parameter  '10)
(setq ss 0)
(do ((x (terminalside :next) (+ x (terminalside :next)))) ((> x 6000 )) 
          (if (zerop ss) (setq ss x))
           (setq a (list x 'B))
          (denver :enqueue a))
(setq flightSide (exponential :new))
(flightSide :parameter  '800 )
(do ((x (flightside :next) (+ x (flightside :next))))((> x
15000)) (setq a (list x 'A))
          (denver :enqueue a))
;    !!! process trasactions off the event queue  
(setq ww (list ' "Begin Denver International Airport Automated
Baggage System simulation at time   " ss))
(print ww)
(mapcar print (denver :report))
(dotimes (x 4000 t)
(setq ee (denver :dequeue))
(setq xx (service ee))
( if xx (denver :enqueue xx))
(denver :abridge)
)
(setq ww (list '"Automated Baggage System simulation terminated at time   "
          (car ee)))
(print ww)
(mapcar print (denver :report))


</p>
(print (mem))
(exit)
;    ***********
;    this is the *resource* module
;    ***********
;    Create classes
(setq resource (class :new   '() '(pending buffer 
amountAvailable)))
(resource :answer :isnew '()
     '((setq pending 0)
       (setq buffer ())
       (setq amountAvailable  0) self))
(resource :answer :initialize '(tag size)  
      '((setq a ())
        (dotimes (x size a)(setq a (cons x a)))
          (setq buffer
     (cons (cons tag  a) buffer))
          a))
;    ******
;create resource instance
;    *******
(setq telecarts (resource :new))
(telecarts :initialize 'bags '3000)
(print "shrink method  follows:")
(resource :answer :shrink '(tag)
     '((setq zz (cddr  (assoc tag  buffer)))
       (setq buffer ()) 
       (setq  buffer (cons (cons tag zz) buffer)) 
          zz))
(print "this is the :get function")
(resource :answer :get '(tag &aux entry)
     '((cond ((setq entry (assoc tag buffer))
          (cdr entry))
          (t ()))
          (self :shrink tag)))
(resource :answer :put '(tag entity)
     '((setq zz (assoc tag buffer))
       (setq buffer ())
       (setq zz (cons entity (cdr zz)))
       (setq buffer (cons (cons tag zz) buffer ))
               zz))
(setq arrivalGates (class :new  '(semaphore teleQueue)))
(arrivalGates :answer :isnew '()
     '((setq semaphore ())
       (setq teleQueue ()) self))
(arrivalGates :answer :accept '(tcart)
     '((setq telequeue (cons tcart telequeue)) self))
(arrivalGates :answer :set '()
          '((setq semaphore t)  self ))
;            (setq telequeue ()) 
(arrivalGates :answer :reset '()
          '((setq semaphore ()) self))
(arrivalGates :answer :test '(&aux flag)
          '((setq flag (not  semaphore))     
               ))
(arrivalGates :answer :display '(&aux val)
          '((setq val (length telequeue)) ))
(arrivalGates :answer :dispatch '(&aux train)
          '((setq train telequeue) ))
(arrivalGates :answer :initialize '()
            '((setq telequeue ()) self))
(setq gateOne (arrivalGates :new))
(setq gateTwo (arrivalGates :new))
(setq gateThree (arrivalGates :new))
(setq gateFour (arrivalGates :new))
(setq gateFive (arrivalGates :new))
(print "gateOne")
(print (gateOne :show))

Back to Article