Deterministic Queueing at a Parking Lot: 16-Civ-B7 Transportation Planning and Engineering, May 2017, Q2

Question 2: Deterministic Queueing at a Parking Lot (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A single service channel (the attendant) with a piecewise-constant arrival rate and a constant service rate, measured in minutes from 8:00 am.

Given data — arrival and service rates
Interval (from 8:00 am)	Clock time	Arrival rate $\lambda$ (veh/min)	Service rate $\mu$ (veh/min)
$0 \le t < 30$	8:00 – 8:30	12	6
$30 \le t < 45$	8:30 – 8:45	0	6
$t \ge 45$	from 8:45	3	6

Find. The time at which the queue clears, the maximum queue length and the maximum waiting time, and the total and average delay accumulated up to that time.

Figure 2.1 — Cumulative arrival and departure curves at the parking-lot booth. The vertical gap is the queue, the horizontal gap is an individual vehicle's wait, and the shaded area is the total delay of 6075 veh-min.

Approach. Build the cumulative arrival curve $A(t)$ and the cumulative departure curve $D(t)$ as piecewise-linear functions of time, then read every quantity off them geometrically: the queue clears where the curves meet, the queue length is the vertical gap, the waiting time is the horizontal gap, and the total delay is the enclosed area.

Steps 1 to 3 below construct the diagram and answer part (a); steps 4 and 5 answer part (b), the maximum queue length and the maximum waiting time; and steps 6 and 7 answer part (c), the total delay and the average delay per vehicle.

Construct the cumulative arrival curve. Cumulating each rate over its interval, $$A(t) = \begin{cases} 12t, & 0 \le t \le 30 \\ 360, & 30 \le t \le 45 \\ 360 + 3(t-45), & t \ge 45 \end{cases}$$ so that 360 vehicles have arrived by 8:30 and the curve is flat through the 15 minutes in which the access road was blocked.
Construct the cumulative departure curve. Because $\lambda > \mu$ from the first instant, a queue exists continuously and the attendant is never starved, so the server works at its capacity throughout: $D(t) = 6t$ for as long as the queue lasts.
Part (a) — locate the clearance point. The queue vanishes when the two cumulative curves meet. On the third arrival branch, $$360 + 3(t-45) = 6t \;\Longrightarrow\; 360 - 135 = 3t \;\Longrightarrow\; t = 75\ \text{min}$$ Both curves pass through 450 vehicles at that instant, confirming the intersection. Measuring 75 minutes from 8:00 am, $$\boxed{\text{the queue clears at } t = 75 \text{ min}, \text{ i.e. at } 9\text{:}15\text{ am}}$$ The check that matters is the sign of the queue on each branch: the queue grows at $12-6 = 6$ veh/min until 8:30, then falls at 6 veh/min while no vehicles arrive, then falls more slowly at $6-3 = 3$ veh/min after 8:45. It is still 90 vehicles at 8:45, so the queue survives into the third branch and the intersection was correctly sought there.
Part (b) — read the maximum queue length. The queue is the vertical distance $Q(t) = A(t) - D(t)$, which grows monotonically until 8:30 and shrinks thereafter, so its maximum occurs at the moment the arrivals stop: $$Q_{\max} = A(30) - D(30) = 360 - 180 = \boxed{180 \ \text{vehicles}}$$
Part (b) — read the maximum waiting time. Under first-in-first-out service, the wait of a vehicle is the horizontal distance between the curves at its own cumulative number. The vehicle arriving at $t = 30$ is the 360th; it is served when $D = 360$, that is at $t = 360/6 = 60$ min. Its wait is $$w_{\max} = 60 - 30 = \boxed{30 \ \text{minutes}}$$ That this is the worst case can be seen from the branches: a vehicle arriving at time $t \le 30$ waits $12t/6 - t = t$ minutes, which increases up to 30 minutes at $t = 30$; a vehicle arriving after 8:45 waits $15 - 0.5(t-45)$ minutes, which decreases from 15 minutes. The peak wait therefore belongs to the last vehicle to arrive before the access road closed — note that the longest wait and the longest queue occur at the same instant here, but they are different quantities and in general need not coincide.
Part (c)(1) — integrate the queue to obtain the total delay. The total delay is the area enclosed between the two curves, which splits into the three straight-sided regions visible on the diagram: $$D_{0-30} = \tfrac{1}{2}(6)(30)^2 = 2700 \ \text{veh-min}$$ $$D_{30-45} = \tfrac{1}{2}(180 + 90)(15) = 2025 \ \text{veh-min}$$ $$D_{45-75} = \tfrac{1}{2}(90)(30) = 1350 \ \text{veh-min}$$ Adding the three, $$\boxed{\text{total delay} = 2700 + 2025 + 1350 = 6075 \ \text{veh-min}}$$
Part (c)(2) — divide by the number of vehicles delayed. Every vehicle served up to clearance passed through the queue, and $D(75) = 450$ vehicles have been served, so $$\bar{d} = \frac{6075}{450} = \boxed{13.5 \ \text{minutes per vehicle}}$$

The results are internally consistent in a way worth checking on any queueing question: the average delay of 13.5 minutes is well under half of the 30-minute maximum, which is what one expects from a queue that builds sharply and drains slowly, and the average queue length over the 75 minutes, $6075/75 = 81$ vehicles, is less than half the peak of 180 for the same reason.

Final results — Question 2
Quantity	Value
Time the queue clears	$t = 75$ min after 8:00 am, i.e. 9:15 am
Maximum queue length (at 8:30 am)	180 vehicles
Maximum waiting time (vehicle arriving 8:30 am)	30 minutes
Total vehicle delay	6075 veh-min (101.25 veh-h)
Vehicles served to clearance	450
Average delay per vehicle	13.5 minutes

Topic. Deterministic (D/D/1) queueing analysis using cumulative arrival and departure curves.

Key relations. $Q(t) = A(t) - D(t)$ is the vertical gap; the individual delay under first-in-first-out is the horizontal gap; the total delay is the enclosed area $\int [A(t) - D(t)]\,dt$; the average delay is that area divided by the number of vehicles served. The queue clears where $A(t) = D(t)$ and, while a queue exists, $D(t) = \mu t$.

Why this works. When arrivals and departures are both treated as deterministic, the cumulative curves are exact, not statistical, so every performance measure reduces to a piece of plane geometry. Conservation of vehicles guarantees that the two curves start and finish together and that the enclosed area is precisely the sum of every vehicle's waiting time. The method is exact for oversaturated conditions, where the random-arrival models of queueing theory become unstable, which is why it is the standard tool for incident, work-zone and toll-plaza analysis.

Common pitfall. Dividing the total delay by the total number of vehicles that ever use the facility rather than by those served up to clearance, and confusing the vertical gap with the horizontal one — reporting the maximum queue in minutes or the maximum wait in vehicles. A third trap is to assume the service rate falls when arrivals stop; the attendant keeps working at 6 veh/min as long as anyone is queued, which is exactly why the queue drains during the blockage.

Source. Garber & Hoel, Traffic and Highway Engineering, 5th ed., Ch. 5 (traffic flow, queueing); Papacostas & Prevedouros, Transportation Engineering and Planning, 3rd ed., Ch. 5.

Question 2 of 7: Deterministic Queueing at a Parking Lot

Question 2: Deterministic Queueing at a Parking Lot (20 marks)