16-Civ-A6 Highway Design, Construction, and Maintenance · December 2016

Question 2 of 7: Deterministic Queueing at a Toll Booth

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Examination, December 2016 — 98-Civ-A6, Transportation Planning & Engineering. Three hours, closed book (one two-sided aid sheet, approved calculator). Seven questions of equal value (20 marks each); any five constitute a complete examination. All seven are solved here, because the set is a study resource rather than a sat examination.

Reference texts. Mannering, Washburn & Kilareski, Principles of Highway Engineering and Traffic Analysis (Wiley) — traffic-stream models, deterministic queueing and shock waves; Papacostas & Prevedouros, Transportation Engineering and Planning (Prentice Hall) — the land-use/transport system and the four-step demand model; Ortuzar & Willumsen, Modelling Transport (Wiley) — trip generation, distribution, mode choice and traffic assignment; Sheffi, Urban Transportation Networks (Prentice Hall) — user-equilibrium assignment; Transportation Association of Canada, Geometric Design Guide for Canadian Roads — Canadian planning and design practice.

Question 2: Deterministic Queueing at a Toll Booth (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 toll booth with a constant arrival rate and a service rate that steps up once, fifteen minutes after the arrivals begin.

Given data — deterministic D/D/1 toll booth
Arrival rate, $\lambda$	40 veh/min, constant from 08:00
Service rate, $\mu_1$ (08:00–08:15)	20 veh/min
Service rate, $\mu_2$ (08:15 onward)	60 veh/min
Rate-change instant, $t_b$	15 min after 08:00
Queue discipline	first-in, first-out (FIFO)

Find. The cumulative arrival/departure diagram; the maximum queue length and the maximum time any vehicle spends waiting; and the total and average delay.

Queueing diagram for the toll booth. The vertical gap between the curves is the queue length (maximum 300 veh at 08:15), the horizontal gap is an individual vehicle's delay (maximum 7.5 min, for the vehicle arriving 08:07:30), and the enclosed area is the total delay of 4,500 veh-min.

Approach. Build the cumulative arrival curve $A(t)$ and cumulative departure curve $D(t)$ as piecewise-linear functions of time; then read the vertical gap as queue length, the horizontal gap as individual waiting time, and the enclosed area as total delay.

Write the two cumulative curves. Cumulative counts are the integrals of the rates, so each segment is a straight line whose slope is the rate in force: $$A(t)=40\,t \qquad\text{(veh, } t \text{ in min)}$$ $$D(t)=\begin{cases}20\,t, & 0\le t\le 15\\[2pt] 300+60\,(t-15), & t\gt 15\end{cases}$$ Because $\lambda=40\gt\mu_1=20$, the departure curve falls behind immediately and a queue exists from the first minute.
Locate the maximum queue. The queue is the vertical separation $Q(t)=A(t)-D(t)$. It grows at $\lambda-\mu_1=20$ veh/min while the slow service applies, and shrinks at $\mu_2-\lambda=20$ veh/min afterwards, so the maximum can only occur at the break: $$Q_{\max}=(\lambda-\mu_1)\,t_b=(40-20)(15)$$ $$\boxed{Q_{\max}=300\ \text{vehicles at 08:15}}$$ At that instant $A=600$ vehicles have arrived and $D=300$ have been served.
Find when the queue clears. Setting the 300-vehicle backlog against the surplus service rate, $$t_c=t_b+\frac{Q_{\max}}{\mu_2-\lambda}=15+\frac{300}{60-40}=30\ \text{min}$$ so the queue vanishes at 08:30, where both curves reach $A=D=1200$ vehicles. This is the right-hand end of the diagram above.
Identify the longest-waiting vehicle. Under FIFO the wait of the vehicle arriving at time $t$ is the horizontal gap, $w(t)=D^{-1}\!\big(A(t)\big)-t$. While that vehicle is served under $\mu_1$ the gap is $w(t)=40t/20-t=t$, which increases; once it is served under $\mu_2$ the gap is $w(t)=10-t/3$, which decreases. The switchover is the vehicle served exactly at the rate change, i.e. the 300th vehicle, which arrived at $$t^{*}=\frac{D(t_b)}{\lambda}=\frac{300}{40}=7.5\ \text{min}\quad(\text{08:07:30})$$ Its wait is therefore $15-7.5$ min: $$\boxed{w_{\max}=7.5\ \text{min}}$$ Notice that this vehicle is not the one that experiences the longest queue — the longest queue occurs 7.5 minutes later, at 08:15, the instant the booth switches to three times its initial service rate.
Total delay as the enclosed area. The region between the curves is two triangles meeting at 08:15: $$D_{\text{tot}}=\tfrac12(\lambda-\mu_1)\,t_b^{2}+\tfrac12 Q_{\max}\,(t_c-t_b)$$ $$D_{\text{tot}}=\tfrac12(20)(15)^{2}+\tfrac12(300)(15)=2250+2250$$ $$\boxed{D_{\text{tot}}=4500\ \text{vehicle-minutes}\;(=75\ \text{vehicle-hours})}$$
Average delay per vehicle. Every vehicle arriving before the queue clears is delayed, so the affected population is $N=\lambda\,t_c=40(30)=1200$ vehicles and $$\bar d=\frac{D_{\text{tot}}}{N}=\frac{4500}{1200}$$ $$\boxed{\bar d=3.75\ \text{min per vehicle}}$$ The average is only half the maximum, which is the usual signature of a triangular delay profile.

Final results — Question 2
Quantity	Value
Maximum queue length	300 vehicles (at 08:15)
Maximum waiting time in queue	7.5 min (vehicle arriving 08:07:30)
Time the queue clears	08:30 (30 min after arrivals begin)
Total vehicle delay	4,500 veh-min = 75 veh-h
Vehicles delayed	1,200
Average delay per vehicle	3.75 min

Topic. Deterministic (D/D/1) queueing analysis by cumulative arrival–departure curves.

Key relations. $Q(t)=A(t)-D(t)$ (vertical gap = queue length); $w(t)=D^{-1}(A(t))-t$ (horizontal gap = individual delay); total delay $=\int\!\big[A(t)-D(t)\big]\,dt$ (enclosed area); the queue clears where $A(t_c)=D(t_c)$; $\bar d = D_{\text{tot}}/\lambda t_c$.

Why this works. The cumulative-curve construction converts a queueing problem into plane geometry. Because both counts are monotone and the rates are piecewise constant, both curves are piecewise linear, and every quantity the question asks for is one of three geometric features: a vertical distance, a horizontal distance, or an area. The method needs no probability at all, which is why it is exact whenever arrival and service rates are genuinely deterministic and the demand is oversaturated — the regime in which random-queueing formulas such as M/M/1 break down entirely because they diverge as the volume-to-capacity ratio approaches unity.

Common pitfall. Reporting the maximum waiting time at the instant of the maximum queue. Those are different vehicles: the maximum queue is a vertical measurement at 08:15, the maximum wait is a horizontal measurement at a cumulative count of 300, and here they differ by a factor of two. The second pitfall is dividing the total delay by the vehicles in the queue at its peak (300) rather than by all vehicles that queued at all (1,200), which inflates the average four-fold.

Source. Mannering, Washburn & Kilareski, Principles of Highway Engineering and Traffic Analysis, Ch. 5 (queueing theory and traffic analysis, D/D/1 queues); Papacostas & Prevedouros, Transportation Engineering and Planning, Ch. 4.

← Question 1 Next: Question 3 →