Queueing Systems: Lecture 6

Amedeo R. Odoni

November 6, 2006

Lecture Outline
• Congestion pricing in transportation: the
fundamental ideas
• Congestion pricing and queueing theory
• Numerical examples
• A real example from LaGuardia Airport
• Practical complications

Reference: Handout on “Congestion Pricing

and Queueing Theory” (on course website)
 Congestion pricing:

The basic observation

• The congestion costs due to any specific user

have 2 components:
(1) Cost of delay to that user (internal cost)
(2) Cost of delay to all other users caused by that user
(external cost)

• At congested facilities, this second component

can be very large

• A congestion toll can be imposed to force

users to experience this cost component (to
“internalize the external costs”)

Economic principle

Optimal use of a transportation facility cannot be

achieved unless each additional (marginal)
user pays for all the additional costs that this
user imposes on all other users and on the
facility itself. A congestion toll not only
contributes to maximizing social economic
welfare, but is also necessary to reach such a
result. (Vickrey, 1967, 1969; Carlin + Park,
1970)
 Two hard technical problems

• In practice it is very hard to:

(1) Estimate external marginal delay costs
(extensive data analysis and/or simulation
have been typically needed – subtle issues);

(2) Determine equilibrium congestion tolls (trial

and-error approach that may take long time to
converge)

• Queueing theory has much to offer (especially

with regard to the first problem) under certain
conditions.

Computing Internal and External

Costs

Consider a queueing facility with a single type of users in

steady-state. Let
c = delay cost per unit time per user
C = total cost of delay per unit time incurred in the system
Then: C = cLq = cλWq
and the marginal delay cost, MC , imposed by an
additional (“marginal”) user is given by:
dC dW q
MC = = c W q + cλ
dλ dλ

Marginal Internal External

cost cost cost
 Numerical Example

• Three types of aircraft; Poisson; FIFO service

_ Non-jets: λ1 = 40 per hour; c1 = $600 per hour
_ Narrow-body jets: λ2 = 40 per hour; c2 = $1,800 per hour
_ Wide-body jets: λ3 = 10 per hour; c3 = $4,200 per hour
_ Total demand is: λ = λ1 + λ2 + λ3 = 90 per hour

• pdf for service times is uniform

_ U[25 sec, 47 sec]
_ E[S] = 36 sec = 0.01 hour; μ = 100 per hour

22 2
σ S2 = = 40.33 sec 2 = 3.11213×10 −6 hours 2
12
• Note: We have a M/G/1 system

Numerical Example [2]

λ ⋅[E 2 [S] + σ S2 ] 90 ⋅[(0.01) 2 + 3.11213×10 −6 ]

Wq = = ≈ 0.0464 hours ≈ 167 sec
2 ⋅ (1 − ρ ) 2 ⋅ (1 − 90 /100)

λ1 λ λ
Define: c = c1 + c 2 2 + c3 3
λ λ λ
C = c ⋅ Lq = c ⋅ λ ⋅Wq = (c1 ⋅ λ1 + c 2 ⋅ λ2 + c3 ⋅ λ3 ) ⋅Wq = c ⋅Wq

Or: C = c ⋅Wq = ($138,000) ⋅ (0.0464) = $6,400

dWq E 2 [S] + σ S2 λ ⋅[E 2 [S] + σ S2 ] 1

= + ⋅ ≈ 5.1556 ×10 −6 hours ≈ 18.6 sec
dλ 2 ⋅ (1 − ρ ) 2 ⋅ (1 − ρ ) 2 μ
 Numerical Example [3]

dC dWq
= c1 ⋅Wq + c ⋅ ≈ $28 + $711 = $739
dλ1 dλ
internal external cost=
cost congestion toll

dC dWq
= c 2 ⋅Wq + c ⋅ ≈ $85 + $711 = $796
dλ2 dλ
dC dWq
= c3 ⋅Wq + c ⋅ ≈ $198 + $711 = $909
dλ3 dλ

Generalizing to m types of users…

• Facility users of type i: arrival rate λi ;

Si with μ i = E[Si ] ;
−1
service time

cost per unit of time in the system ci

• For entire set of facility users, we have

m
1 m ⎛ λi 1 ⎞⎟
λ = ∑ λi = E [S ] = ∑ ⎜⎝ λ ×
i= 1 μ i =1 μ i
⎠

λ m m

λ
m
⎛ λi ⎞
ρ = = ∑ ρi = ∑ μi c=∑ ci
μ i= 1 i =1 i ⎝
i= 1 λ
⎠
 Generalization (continued)

• As before: C = cLq = cλ W q

dC dW q
giving: MC(i) = = ci W q + c λ
dλ i dλ i

• When we have explicit expressions for Wq, we

can also compute explicitly the total marginal
delay cost MC(i), the internal (or private) cost
and the external cost associated with each
additional user of type i

Example

For an M/G/1 system:

λ
(1 − ρ )E[S i2 ] + E[S 2 ]
dC λ ⋅ E[S ]
2 μi
MC(i) = = ci + cλ
d λi 2(1 − ρ ) 2(1 − ρ ) 2

• Can extend further to cases with user priorities

 Finding Equilibrium Conditions
and Optimal Congestion Tolls!
We now generalize further: let xi be the total cost
perceived by a user of type i for access to a congested
facility and let λi (xi ) be the demand function for type i
users.
x i = IC i + CTi + K i
ICi = internal private cost; it is a function of the demand
rates, λi (xi )
CTi = congestion toll imposed; equal to 0 in absence of
congestion tolls; can be set arbitrarily or can be set as a
function of the λi (xi ) under congestion pricing schemes

Ki = any other charges that are independent of level of

congestion

Finding Equilibrium Conditions and

Optimal Congestion Tolls! [2]

• With m types of users, the equilibrium conditions for

any set of demand functions, can be found by solving

simultaneously the m equations:

⎛ m ⎞ dWq [λ̂ ( x̂ )]
⎜
( )
xi = ci ⋅Wq [λˆ ( xˆ )] + ⎜ ∑ c j ⋅ λ j x j ⎟ ⋅
⎟ dλ i ( x i )
+ Ki ∀i
⎝ j =1 ⎠
where λ̂ (x̂) = {λ1 (x1 ), λ2 (x2 ),..., λm (x m )} .

The missing piece: Demand functions can

only be roughly estimated, at best!

 An illustrative example from airports

Type 1 Type 2 Type 3

(Big) (Medium) (Small)
Service rate 80 90 100
(movements per hour)
Standard deviation of 10 10 10
service time (seconds)
Cost of delay time $2,500 $1,000 $400
($ per hour)

Hypothetical Demand Functions

λ1 (x1 ) = 40 − 0.001⋅ x1 − 0.00001⋅ x12

λ2 (x 2 ) = 50 − 0.003 ⋅ x 2 − 0.00002 ⋅ x22

λ3 (x3 ) = 60 − 0.01⋅ x3 − 0.00008 ⋅ x32

 40 50 60
0,001 0,003 0,01
Demand Functions for three types of users
0,00001 0,00002 0,00008
x lambda 1 lambda 2 lambda 3
0 40 50 60

Arriv al rate (Users/unit tim e)

70 100 39,8 49,5 58,2
200 39,4 48,6 54,8
60 300 38,8 47,3 49,8
400 38 45,6 43,2
50 500 37 43,5 35
600 35,8 41 25,2
700 34,4 38,1 13,8 Type 1
40 800 32,8 34,8 0,8
900 31 31,1 -13,8
Type 2
30 1000 29 27 -30 Type 3
1100 26,8 22,5 -47,8
20 1200 24,4 17,6 -67,2
1300 21,8 12,3 -88,2
10 1400 19 6,6 -110,8
1500 16 0,5 -135
0 1600 12,8 -6 -160,8
1700 9,4 -12,9 -188,2
0

1800 5,8 -20,2 -217,2

0

0
00

00

00

00

00

00
20

40

60

80
10

12

14

16

18

20
1900 2 -27,9 -247,8
2000 -36 -280
Total cost ($)

Case 1: No Congestion Fee

Type 1 Type 2 Type 3

No Congestion Fee
(1) Delay cost (IC) per aircraft $1,802 $721 $288
(2) Congestion fee $0 $0 $0
(3) Total cost of access $1802 $721 $288
[=(1)+(2)]
(4) Demand (no. of movements 5.7 37.4 50.5
per hour)
(5) Total demand (no. of 93.6
movements per hour)
(6) Expected delay per aircraft 43 minutes 15 seconds
(7) Utilization of the airport 99.2%
(% of time busy)
Case 2: Optimal Congestion Fee
Optimal Congestion Fee
(8) Delay cost (IC) per aircraft $135 $54 $22
(9) Congestion fee (CF) $853 $750 $670
(10) Total cost of access $988 $804 $692
[=(1)+(2)]
(11) Demand (no. of 29.2 34.6 14.9
movements per hour)
(12) Total demand (no. of 78.7
movements per hour)
(13) Expected delay per 3 minutes 15 seconds
aircraft
(14) Utilization of the airport 89.9%
(% of time busy)

Demand Functions for three types of users

Arrival rate (Users/unit time)

70
60
50
o
Type 1
40
o+ Type 2
30
20
+ Type 3

10
+ o No Fee

0
o + With Fee
0

00

00

00

00

00

00
0
20

40

60

80

10

12

14

16

18

20

Total cost ($)

 Important to note…

• The external costs computed in the absence

of congestion pricing give only an upper
bound on the magnitude of the congestion-
based fees that might be charged
• These are not necessarily “equilibrium
prices”
• Equilibrium prices may turn out to be
considerably lower than these upper
bounds
• Equilibrium prices are hard to estimate,
absent knowledge of demand functions

Case of LaGuardia (LGA)

• Since 1969: Slot-based High Density Rule (HDR)

_ DCA, JFK, LGA, ORD; “buy-and-sell” since 1985
• Early 2000: About 1050 operations per weekday at LGA
• April 2000: Air-21 (Wendell-Ford Aviation Act for 21st Century)
_ Immediate exemption from HDR for aircraft seating 70 or fewer pax
on service between small communities and LGA
• By November 2000 airlines had added over 300 movements per
day; more planned: virtual gridlock at LGA
• December 2000: FAA and PANYNJ implemented slot lottery and
announced intent to develop longer-term policy for access to LGA
• Lottery reduced LGA movements by about 10%; dramatic reduction
in LGA delays
• June 2001: Notice for Public Comment posted with regards to
longer-term policy that would use “market-based” mechanisms
• Process stopped after September 11, 2001; re-opened in 2004
 Scheduled aircraft movements at LGA
before and after slot lottery
120
Scheduled
100
movements Nov, 00
Aug, 01
per hour 80 81 flights/hour

60

40

20

0
5 7 9 11 13 15 17 19 21 23 1 3

Time of day (e.g., 5 = 0500 – 0559)

Estimated average delay at LGA

before and after slot lottery in 2001
100
Nov, 00
Average
Aug, 01
delay 80

(mins
60
per
movt) 40

20

0
5 7 9 11 13 15 17 19 21 23 1 3

Time of day
 LGA: Marginal delay caused by an
additional operation by time of day
16
Nov, 00
Marginal 14 Aug, 01
delay 12

(Aircraft 10
hours) 8

0
5 7 9 11 13 15 17 19 21 23 1 3

Time of day of incremental operation

(e.g., 5 = 0500-0559)

LGA: Marginal external delay cost per additional

movement vs. average landing fee per movement

$5,000
Marginal
$4,500 Aug, 01
delay cost $4,000
Landing fee
($ per $3,500

movt) $3,000
$2,500
$2,000
$1,500
$1,000
$500
$0
5 7 9 11 13 15 17 19 21 23 1 3

Time of day
 Issues that arise in practice

-- Toll may vary in time and by location

-- Facility users may be driven by “network”
considerations
-- “Social benefit” considerations
-- Political issues
-- What to do with the money?