Fundamentals of Transportation/Queueing
Queueing^{[1]} is the study of traffic behavior near a certain section where demand exceeds available capacity. Queues can be seen in many common situations: boarding a bus or train or plane, freeway bottlenecks, shopping checkout, exiting a doorway at the end of class, waiting for a computer in the lab, a hamburger at McDonald’s, or a haircut at the barber. In transportation engineering, queueing can occur at red lights, stop signs, bottlenecks, or any designbased or trafficbased flow constriction. When not dealt with properly, queues can result in severe network congestion or "gridlock" conditions, therefore making them something important to be studied and understood by engineers.
Contents
 1 Cumulative InputOutput Diagram (Newell Curve)
 2 Distributions
 3 Characterizing Queues
 4 Little's Formula
 5 Uncapacitated Queues (M/D/1) and (M/M/1)
 6 Uncapacitated queues (M/M/1) (random arrival and random service)
 7 Capacitated Queues (Finite)
 8 Real Life Causes of Queue Generation
 9 Examples
 10 Thought Question
 11 Sample Problems
 12 Variables
 13 Key Terms
 14 External Exercises
 15 Additional Questions
 16 Videos
 17 References and Notes
Cumulative InputOutput Diagram (Newell Curve)[edit]
Based on the departure rate and arrival rate pair data, the delay of every individual vehicle can be obtained. Using the inputoutput (I/O) queueing diagram shown in the side figure, it is possible to find the delay for every individual vehicle: the delay of the vehicle is time of departure  time of arrival (). Total delay is the sum of the delays of each vehicle, which is the area in the triangle between the arrival (A(t)) and departure (D(t)) curves.
Distributions[edit]
Arrival Distribution  Deterministic (uniform) OR Random (e.g. Poisson)
Service Distribution  Deterministic OR Random
Service Method:
 First Come First Served (FCFS) or First In First Out (FIFO)
 Last Come First Served (LCFS) or Last In First Out (LIFO)
 Priority (e.g. HOV bypasses at ramp meters)
Characterizing Queues[edit]
Queue Length Characteristics  Finite or Infinite
Number of Channels  Number of Waiting Lines (e.g. Ramps = 2, Supermarket = 12)
We use the following notation:
 Arrival Rate =
 Departure Rate =
Utilization Rate
Degree of Saturation[edit]
Oversaturated:
Undersaturated
Saturated
Little's Formula[edit]
Little's Formula:
This means that the average queue size (measured in vehicles) equals the arrival rate (vehicles per unit time) multiplied by the average waiting time (both delay time in queue plus service time) (in units of time). This result is independent of particular arrival distributions and, while perhaps obvious, is an important fundamental principle that was not proven until 1961.
See Wikipedia article for more applications.
Uncapacitated Queues (M/D/1) and (M/M/1)[edit]
It has been shown that queue sizes, waiting times, and delays differ between M/D/1 and M/M/1 queueing. These differences are represented in formulas and shown below. Note the minor differences between the two.
'  M/D/1  M/M/1 

E(w) (average waiting time)  
E(v) (average total delay)  
E(n) (expected number of units in the system (including vehicles being served)) 

Notes:
 Average wait time (E(w)) excludes service time.
 Average total delay (E(v)) is (wait time + service time). This is sometimes referred to average delay time due to the existence of the bottleneck.
 Expected number of units in the system (E(n)) includes customers currently being served (in number of units). According to Little's Law this is arrival rate multiplied by the average time spent in the system .
 Sometimes Expected number of units in the queue (E(m)) is requested, excluding customers being served, which is a different formula ( arrival rate multiplied by the average waiting time ), and obviously results in a small number.
Uncapacitated queues (M/M/1) (random arrival and random service)[edit]
In addition to the properties stated before, M/M/1 queueing have a few additional ones of which to take note.
'  M/M/1 

Probability of n units in the system  
Average waiting time of arrival, including queue and service  
Average waiting time in queue (excluding vehicles being served)  
Expected number of units in the system (including vehicles being served)  
Mean queue length (excluding vehicles being served)  
Probability of spending time t or less in system  
Probability of spending time t or less in the queue  
Probability of spending more than time t in the queue, given the queue is not empty  
Probability of more than N vehicles in queue 
Capacitated Queues (Finite)[edit]
Capacitated queues permit a maximum number of vehicles to wait, and thus have different properties than uncapacitated queues. For single channel undersaturated finite queues where the maximum number of units in system is specified as and with random arrivals and departures () we have:
'  M/M/1 

Probability of n Units in System  
Expected Number of Units in System 
Real Life Causes of Queue Generation[edit]
For Roads:
 Geometric Bottlenecks (lane drops, hard curves, hills)
 Accidents and Incidents
 Traffic Signals and Intersection Controls
 AtGrade Crossings with other Modes (Railroad crossings, drawbridges, etc.)
 Toll Booths
 Ramp Meters
 "Gawker" Effect
 Inclement Weather
For Trains and Transit:
 Platform Capacities
 Fare Gates
 Ticket Windows/Ticket Machines
 Minimum Safe Separation for Trains
 Security Checkpoints
 Efficiency of Trains Entering and Leaving Station (number of tracks, switches, etc.)
For Aviation and Airports:
 Runways
 Designated Minimum Safe Following Distances for Planes (by government)
 Physical Minimum Safe Following Distance for Planes (creation of turbulence, etc.)
 Available Airspace for Approaches and Departures
 Ticketing Counters/Checkin Procedures
 Security Checkpoints
 Baggage Systems
 Terminal Capacity for Planes
 Internal Terminal Capacity for Passengers
 Inclement Weather
For Water and Maritime:
 Locks and Dams
 Port Capacities
 Minimum "Safe" Distances (determined by government and physics)
 Inclement Weather
For Space Flight:
 Launch Capacity
 Minimum Spacings between Orbital Vehicles
 Inclement Weather on Earth
 Unfavorable Celestial Conditions
Examples[edit]
Example 1[edit]
At the KrustyBurger, if the arrival rate is 1 customer every minute and the service rate is 1 customer every 45 seconds, find the average queue size, the average waiting time, and average total delay. Assume an M/M/1 process.
To proceed, we convert everything to minutes.
Service time:
per customer. Alternatively, you can say the server can handle 60/45 = 1/0.75 = 1.33 customers per minute.
The arrival rate is 1 customer per minute.
The utilization rate Meaning the server is busy on average 75% of the time.
Average queue size (E(n)):
Little's Formula
Average wait time:
Average delay time:
Comparison:
We can compute the same results using the M/D/1 equations, the results are shown in the Table below.
'  M/D/1  M/M/1 

E(n) (average queue size (#))  1.875  3 
E(w) (average waiting time)  1.125  2.25 
E(v) (average total delay)  1.875  3 
As can be seen, the delay associated with the more random case (M/M/1, which has both random arrivals and random service) is greater than the less random case (M/D/1), which is to be expected.
Example 2[edit]
Example 3[edit]
Before he encounters the “pimply faced teen” who serves burgers, what is the likelihood that Homer waited more than 3 minutes?
Example 4[edit]
Thought Question[edit]
Problem
How does one minimize wait time at a queue?
Solution
Cutting in line always helps, but this problem will be answered without breaking any rules. Think about going out to dinner, only to find a long line at your favorite restaurant. How do you deal with that? Maybe nothing can be done at that time, but the next time you go to that restaurant, you might pick a new time. Perhaps an earlier one to avoid the lunch or dinner rush. Similar decisions can be seen in traffic. People that are tired of being in network queues on their way to work may attempt to leave earlier or (if possible) later than rush hour to decrease their own travel time. This typically works well until all the other drivers figure out the same thing and shift congestion to a different time.
Sample Problems[edit]
Sample Problem 1 : Queueing at a Tollbooth[edit]
Sample Problem 2 : Queueing at a Ramp Meter[edit]
Sample Problem 3 : Queueing at a Ramp Meter[edit]
Variables[edit]
 A(t) = λ  Arrival Rate
 D(t) = μ  Departure Rate
 1/μ  service time
 ρ = λ/ μ  Utilization
 Q  average queue size including customers currently being served (in number of units)
 w  average wait time
 t  average delay time (queue time + service time)
Key Terms[edit]
 Queueing theory
 Cumulative inputoutput diagram (Newell diagram)
 average queue length
 average waiting time
 average total delay time in system
 arrival rate, departure rate
 undersaturated, oversaturated
 D/D/1, M/D/1, M/M/1
 Channels
 Poisson distribution,
 service rate
 finite (capacitated) queues, infinite (uncapacitated) queues
External Exercises[edit]
The assignment seeks to provide students with the opportunity to gain a better understanding of two queuing theories: M/D/1 and M/M/1. Two preformatted spreadsheets have been made available for assistance in computing the values sought after in this exercise. While these spreadsheets provide the computations for these results, the formula is listed below for reference:
Where:
 : Average customer delay in the queue
 : Coefficient of variation (CV) of the arrival distribution
 : Coefficient of variation of the departure distribution
 : Standard deviation/mean; CV = (1/SqRt (mean)) for Poisson process and CV = 0 for constant distribution
 : Average departure rate
 : Average arrival rate
 : Utilization = Arrival rate/service rate
M/D/1 Queueing
Download the file for M/D/1 Queueing from the University of Minnesota's STREET website: M/D/1 Queue Spreadsheet
With this spreadsheet, run 5 simulations for each of the 10 scenarios, using the arrival and departure information listed in the table below. In other words, program the same data into the spreadsheet 5 different times to capture a changing seed and, thus, produce slightly different answers because of the model's sensitivity. A total of 50 simulations will be run.
Scenario  1  2  3  4  5  6  7  8  9  10 

Arrival Rate  0.01  0.025  0.05  0.1  0.2  0.3  0.4  0.5  0.6  0.7 
Service Rate  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5 
Also, find the utilization for all ten scenarios. Based on the utilization and the distribution variability, use the above equation to compute the average delays for all scenarios with utilization values of less than 1.
Finally, summarize the averagedelays obtained both from the simulation and from the WTq equation in the same delayutilization plot. Interpret your results. How does the average user delay change as utilization increases? Does the above equation provide a satisfactory approximation of the average delays?
M/M/1 Queueing
Download the file for M/M/1 Queueing from the University of Minnesota's STREET website: M/M/1 Queue Spreadsheet
With this spreadsheet, run 5 simulations for each of the 10 scenarios, using the arrival and departure information listed in the table below. In other words, program the same data into the spreadsheet 5 different times to capture a changing seed and, thus, produce slightly different answers because of the model's sensitivity. A total of 50 simulations will be run.
Scenario  1  2  3  4  5  6  7  8  9  10 

Arrival Rate  0.01  0.025  0.05  0.1  0.2  0.3  0.4  0.5  0.6  0.7 
Service Rate  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5  0.5 
Again, you need to use five different random seeds for each scenario. Summarize the results in a delayutilization plot. Interpret your results (You do NOT need to use the WTq equation given above to compute delays for the M/M/1 queue).
Additional Questions
 Finally compare the M/M/1 queue and the M/D/1 queue. What conclusion can you draw? (For the same average arrival rate, do users experience the same delays in the two queuing systems? Why or why not?).
 Provide a brief example where M/M/1 might be the appropriate model to use.
 Provide a brief example where M/D/1 might be the appropriate model to use.
Additional Questions[edit]
Videos[edit]
 Introduction to Queueing
 Deterministic Queues
 Stochastic Queues
 Stochastic Queueing  Probabilistic Distributions
 Queueing  Tollbooth Example
References and Notes[edit]
 ↑ A Note on Linguistics: American English tends to use “Queueing” (getting 302,000 Google hits), while British English uses “Queuing” (getting 429,000 Google hits) Queueing is the only common English word with 5 vowels in a row. It has been posited: Cooeeing  To call out “cooee,” which is apparently something done in Australia. The uncommon word: archaeoaeolotropic has 6 vowels  a prehistorical item that is unequally elastic in different directions  One suspects it is just made up to have a word with 6 vowels in a row though, and the “ae” is questionable anyway.