Queuing Theory

TRANSPORTATION ENGINEERING
ASSIST. PROF. DR. M. ALI. MOSABERPANAH
Queuing
Theory
 Fundamentals of Queuing
Theory
Microscopic traffic flow
◦ Different analysis than theory of traffic flow
◦ Intervals between vehicles is important
◦ Rate of arrivals is important

Arrivals
Departures
Service rate
Activated
Upstream of bottleneck/server Downstream

Arrivals Departures

Server/bottleneck

Direction of flow
Not Activated

Arrivals Departures

server
Flow Analysis
Bottleneck active
◦ Service rate is capacity
◦ Downstream flow is determined by bottleneck service rate
◦ Arrival rate > departure rate
◦ Queue present
Flow Analysis
Bottle neck not active
◦ Arrival rate < departure rate
◦ No queue present
◦ Service rate = arrival rate
◦ Downstream flow equals upstream flow
 Fundamentals of Queuing
Theory
Arrivals
◦ Arrival rate (veh/sec)
◦ Uniform
◦ Poisson
◦ Time between arrivals (sec)
◦ Constant
◦ Negative exponential

Service
◦ Service rate
◦ Service times
◦ Constant
◦ Negative exponential
 Queuing Theory
FIFO - a family of models that use the principle of “first in first out”
LIFO - “last in first out”
a/d/N notation:
1. a - arrival type (either D- deterministic, or M-mechanistic)
2. d - departure type (either D- deterministic, or M-mechanistic)
3. N - number of “channels”
It could be shown as:

D/D/N M/D/N M/M/N

9
 Poisson Distribution
Good for modeling random events
Count distribution
◦ Uses discrete values
◦ Different than a continuous distribution

Pn  
t  n
e  t

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(n≥4) = 1 – P(n<4) = 1 - P(0) + P(1) + P(2) + P(3)

Amount of time between arrival of successive vehicles

P0  Ph  t  
t  0
e  t
 e t  e  qt 3600
0!
Queue Notation
Number of
Arrival rate nature service channels

X /Y / N
Popular notations: Departure rate nature
◦ D/D/1, M/D/1, M/M/1, M/M/N
◦ D = deterministic
◦ M = some distribution
Queuing Theory Applications
D/D/1
◦ Deterministic arrival rate and service times
◦ Not typically observed in real applications but reasonable for approximations

M/D/1
◦ General arrival rate, but service times deterministic
◦ Relevant for many applications

M/M/1 or M/M/N
◦ General case for 1 or many servers
Queue times depend on
variability
Queue Analysis – Graphical
D/D/1 Queue Departure
Rate
Delay of nth arriving vehicle Arrival
Rate
Maximum queue
Vehicles

Maximum delay

Total vehicle delay

Queue at time, t1

t1 Time Where is capacity?

 Steady state assumption

Queue Analysis – Numerical


M/D/1    1.0

◦ Average length of queue
2
Q
21   
◦ Average time waiting in queue

1   
w  
◦ Average time spent in system 2  1   

1 2 
t  
2  1   
λ = arrival rate μ = departure rate =traffic intensity
Queue Analysis – Numerical
   1.0
M/M/1 

◦ Average length of queue
2
Q
◦ Average time waiting in queue
1   
1  
w   
◦ Average time spent in system     

1
t
 
λ = arrival rate μ = departure rate =traffic intensity
Queue Analysis – Numerical

M/M/N   N  1.0

◦ Average length of queue
P0  N 1  1 
Q  2
N ! N  1   N  
◦ Average time waiting in queue

 Q 1
w 
◦ Average time spent in system  

 Q
t

λ = arrival rate μ = departure rate =traffic intensity
M/M/N – More Stuff

◦ Probability of having no vehicles 1   N  1.0
P0  
N 1
n N

c


n  0 nc !
c
N!1   N 
◦ Probability of having n vehicles

 P0
n  n P0
Pn  for n  N Pn  n N
for n  N
n! N N!
◦ Probability of being in a queue

P0  N 1
Pn  N 
N! N 1   N 
λ = arrival rate μ = departure rate =traffic intensity
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?

Pn  
0.20 veh min  t 
n
e  0.20veh min t

n!

From HCM 2000

 Example Calculations
Exactly 2: P2 
0.20  15  e  0.2015
2
 0.224  22.4%
2!
Less than 2: Pn  2  P0  P1  0.1992

P(0)=e-.2*15=0.0498, P(1)=0.1494

More than 2: Pn  2  1  P0  P1  P2  0.5768