Queuing Theory
CET 233
Outline
1.
2.
3.
4.
5.
Fundamentals
Poisson Distribution
Notation
Applications
Analysis
a. Graphical
b. Numerical
6. Example
Fundamentals of Queuing Theory
Microscopic traffic flow
Arrivals
Uniform or random
Departures
Uniform or random
Service rate
Departure channels
Discipline
First In First Out(FIFO) and Last In First Out(LIFO) are most
popular
FIFO is more prevalent in traffic engineering
Poisson Distribution
Count distribution
Uses discrete values
Different than a continuous distribution
t
P n
e
n!
P(n) = probability of exactly n vehicles arriving over time t
n = number of vehicles arriving over time t
= average arrival rate
t = duration of time over which vehicles are counted
Poisson Ideas
Probability of exactly 4 vehicles arriving
P(n=4)
Probability of less than 4 vehicles arriving
P(n<4) = P(0) + P(1) + P(2) + P(3)
Probability of 4 or more vehicles arriving
P(n4) = 1 P(n<4) = 1 - P(0) + P(1) + P(2) + P(3)
Amount of time between arrival of successive vehicles
t
P 0 P h t
e
0!
e t e qt 3600
Poisson Distribution Example
Vehicle arrivals at the Olympic National Park main gate are assumed
Poisson distributed with an average arrival rate of 1 vehicle every 5
minutes. What is the probability of the following:
1. Exactly 2 vehicles arrive in a 15 minute interval?
2. Less than 2 vehicles arrive in a 15 minute interval?
3. More than 2 vehicles arrive in a 15 minute interval?
0.20 veh min t
P n
0.20 veh min t
n!
From HCM 2000
Example Calculations
Exactly 2:
0.20 15 e 0.20 15
P 2
2!
0.224 22.4%
Less than 2:
P n 2 P 0 P 1
More than 2:
P n 2 1 P 0 P1 P 2
Example Graph
0.25
Probability of Occurance
0.20
0.15
0.10
0.05
0.00
0
10
11
12
13
Arrivals in 15 minutes
14
15
16
17
18
19
20
Example Graph
0.25
Mean = 0.2 vehicles/minute
Probability of Occurance
0.20
Mean = 0.5 vehicles/minute
0.15
0.10
0.05
0.00
0
10
11
12
13
Arrivals in 15 minutes
14
15
16
17
18
19
20
Example: Arrival Intervals
Probability of Excedance
1.0
0.9
Mean = 0.2 vehicles/minute
0.8
Mean = 0.5 vehicles/minute
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
0
10
12
14
Time Between Arrivals (minutes)
16
18
20
Queue Notation
Number of
service channels
Arrival rate nature
X /Y / N
Departure rate nature
Popular notations:
D/D/1, M/D/1, M/M/1, M/M/N
D = deterministic distribution
M = Markov/ exponential distribution
Queuing Theory Applications
D/D/1
Use only when absolutely sure that both arrivals and
departures are deterministic
M/D/1
Controls unaffected by neighboring controls
M/M/1 or M/M/N
General case
Factors that could affect your analysis:
Neighboring system (system of signals)
Time-dependent variations in arrivals and departures
Peak hour effects in traffic volumes, human service rate
changes
Breakdown in discipline
People jumping queues! More than one vehicle in a lane!
Time-dependent service channel variations
Grocery store counter lines
Queue Analysis Graphical
D/D/1 Queue
Vehicles
Delay of nth arriving vehicle
Maximum queue
Maximum delay
Total vehicle delay
Queue at time, t1
t1
Time
Departure
Rate
Arrival
Rate
Queue Analysis Numerical
M/D/1
2
Average length of queue Q 21
1
w
2 1
Average time waiting in queue
Average time spent in system
= arrival rate
1 2
t
2 1
= departure rate
1.0
Queue Analysis Numerical
M/M/1
2
Average length of queue Q 1
1
w
Average time waiting in queue
t
Average time spent in system
= arrival rate
= departure rate
1.0
Queue Analysis Numerical
N 1.0
M/M/N
P0 N 1
1
Average length of queue Q N ! N 1 N 2
Q 1
w
Average time waiting in queue
t
Average time spent in system
= arrival rate
= departure rate
M/M/N More Stuff
Probability of having no vehicles
P0
N 1.0
nc
N
N ! 1 N
nc 0 nc !
N 1
Probability of having n vehicles
Pn
P0
for n N
n!
n
n P0
Pn n N
for n N
N N!
Probability of being in a queue
Pn N
P0 N 1
N ! N 1 N
= arrival rate
= departure rate
Example 1
You are entering Bank of America Arena at Hec Edmunson Pavilion to
watch a basketball game. There is only one ticket line to purchase
tickets. Each ticket purchase takes an average of 18 seconds. The
average arrival rate is 3 persons/minute.
Find the average length of queue and average waiting time in queue
assuming M/M/1 queuing.
Example 2
You are now in line to get into the Arena. There are 3 operating
turnstiles with one ticket-taker each. On average it takes 3 seconds
for a ticket-taker to process your ticket and allow entry. The average
arrival rate is 40 persons/minute.
Find the average length of queue, average waiting time in queue
assuming M/M/N queuing.
What is the probability of having exactly 5 people in the system?
Example 3
You are now inside the Arena. They are passing out Harry the Husky
doggy bags as a free giveaway. There is only one person passing
these out and a line has formed behind her. It takes her exactly 6
seconds to hand out a doggy bag and the arrival rate averages
9 people/minute.
Find the average length of queue, average waiting time in queue, and
average time spent in the system assuming M/D/1 queuing.
Seatwork
There is a checkpoint along a one way
road. Police officers can examine a car in
3.25 minutes. The ratio of departure and
arrival rate is 1.11.
Determine the average length of queue,
average waiting time in queue, average
time spent in system
Exactly 2 vehicles in a 5 minute interval
Use M/D/1
Primary References
Mannering, F.L.; Kilareski, W.P. and Washburn, S.S. (2003).
Principles of Highway Engineering and Traffic Analysis, Third
Edition (Draft). Chapter 5
Transportation Research Board. (2000). Highway Capacity Manual
2000. National Research Council, Washington, D.C.