Queuing Systems: Lecture 5 Amedeo R. Odoni October 22, 2001 Quiz #1: October 29 ? Open book, 85 minutes (start 10:30) ? Chapter 4 coverage: Sections 4.1through 4.7 (inclusive); Section 4.9 (skim through 4.9.4) [Up to lecture of 10/22] ? Review Problem Set 3 ? Review some old quizzes ? Prof. Barnett: Quiz review today ? Odoni: Office Hours, Friday, 1:30-3:00 Lecture Outline ? Bounds for G/G/1 systems ? A numerical example ? Congestion pricing in transportation: the fundamental ideas ? Congestion pricing and queuing theory ? Numerical example ? Practical complications ? The LaGuardia Airport example A general upper bound for G/G/1 systems ? A number of bounds have been obtained for more general cases (see Section 4.9) ? A good example is an upper bound for the waiting time at G/G/1 systems: (7) where X and S are, respectively, the r.v.’s denoting inter- arrival times and service times ? Under some fairly general conditions, such bounds can be tightened and perform extremely well )1()1(2 )( 22 <?? +?≤ rrssl SXqW Better bounds for a (not so) special case ? For G/G/1 systems whose inter-arrival times have the property that for all non-negative values of t0, l 1]|[ 00 ≤>? tXtXE it has been shown that: )1()1(2 )(21 22 <?? +?=≤≤+? rrssllr SXq BWB (what does this mean, intuitively?) ? Note that the upper and lower bounds in (8) differ by, at most, 1/l and that the percent difference between the upper and lower bounds decreases as r increases! (8) 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 airports (and congested facilities, in general) 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 or difficult simulation is typically needed); (2) Determine equilibrium congestion tolls (trial- and error approach that may take long time to converge is used sometimes). ? Queuing theory has much to offer (especially with regards to the first problem) under certain conditions. Congestion pricing and queuing theory qq WccLC l== MC = dCdl = c Wq + cl dWqdl Consider a queuing facility with a single type of customer in steady-state. Let c = delay cost per unit time per customer C = total cost of delay per unit time incurred in the system at equilibrium and the marginal delay cost, MC , imposed by an additional (“marginal”) customer is given by: Congestion pricing and queuing theory (2) ? Note that the first term on the right is the “internal cost” experienced by the marginal customer and the second term is the “external cost” (s)he imposes! ? These ideas can be extended to cases with multiple types of customers and to systems with priorities. Generalizing to m types of users… l i l = l i i= 1 m Si mi -1 = E S i[ ] 1 m = E S[ ]= l i l · 1 m i ? ? i =1 m r = lm = ri i= 1 m = lim ii =1 m ci c = l il ci ? ? i= 1 m ? Facility users of type i: arrival rate ; service time with ; cost per unit of time in the system ? For entire set of facility users, we have Generalization (continued) C = cLq = clWq MC(i) = dCdl i = ciWq + cl dWqdl i ? As before: giving: ? When we have explicit expressions for Wq, we can also compute explicitly the marginal social cost MC(i), the internal (or private) cost and the external cost associated with each additional user of type i Issues that arise in practice -- Toll may vary in time and by location -- Facility users may be driven by “network” considerations -- “Social benefit” considerations -- What to do with the money? -- Politics Demand Profiles at LaGuardia Number of runway operations per hour ? Scheduled passenger flights reduced by 10% (from 1,348 to 1,216/day) Hour of the day (scheduled time of operation) E.g. 5 means 5:00 am – 5:59 am Sources: OAG and FAA, based on Monday schedules for Nov 13 and Feb 12 0 10 20 30 40 50 60 70 80 90 100 5 7 9 11 13 15 17 19 21 23 1 3 Nov 00 Feb 01 Capacity at 75 ops/hr Average delay at LaGuardia Minutes/flight ? Average delay reduced by >80% during evening hours ? >900 hrs per day saved Hour of the day Capacity = 75 operations/hr 0 20 40 60 80 100 120 5 7 9 11 13 15 17 19 21 23 1 3 Nov 00 Feb 01 Effect of reducing and spreading demand can be large at very congested airports Total delay (aircraft-hour) 1160 216 176 944 40 0 200 400 600 800 1000 1200 1400 Schedules in Nov, 00 Flights discontinued since Nov, 00 Schedules in Feb, 01 Redistributing remaining flights Resultant delays Reduction in delays Congestion delays as a result Demand profiles at LaGuardia Number of runway operations per hour ? Scheduled passenger flights reduced by 10% (from 1,348 to 1,216/day) Hour of the day (scheduled time of operation) E.g. 5 means 5:00 am – 5:59 am Sources: OAG and FAA, based on Monday schedules for Nov 13 and Feb 12 0 10 20 30 40 50 60 70 80 90 100 5 7 9 11 13 15 17 19 21 23 1 3 Nov 00 Feb 01 Capacity at 75 ops/hr Marginal delay caused by an additional flight Marginal delay caused by an additional flight operation at LaGuardia (aircraft-hours) 0 2 4 6 8 10 12 14 16 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 0 1 2 3 4 Nov 00 Feb 01 Hour of the day External delay costs are not reflected in weight-based landing fees: Feb 01 schedule Cost per average aircraft operation at LaGuardia (US$/extra operation) 0 1,000 2,000 3,000 4,000 5,000 6,000 7,000 5 7 9 11 13 15 17 19 21 23 1 3 Increase in total direct operating costs to all flights due to one extra operation Current charge ($300 per operation) Hour of the day Distribution of Aircraft Size at LaGuardia Frequency of operations ? Average aircraft size at LGA is 102 seats, or 52,000 kg MTOW, corresponding to about USD $1,600/hr of direct operating costs ? 4 aircraft-hours of delay translates to about $6,400 congestion cost per marginal operation Aircraft seating capacity (e.g. 40 = 21 - 40 seats) 0 20 40 60 80 100 120 140 20 40 60 70 80 100 120 140 160 180 200 220 240 260