Lecture 5.3 Recap

5.3: Vehicle Routing · ISE 754, Fall 2026 · in class 10 November 2026

A recap answers what students found most difficult in their pre-class review of the lecture, along with anything the instructor adds. Blue Lecture panels quote the lecture; orange Another view panels look at the same idea from another side.

The three scans of a route with time windows, one step at a time

Added by the instructor Lecture 5.3, Sec. 2, Ex. 4

Lecture What each scan finds

“With time windows, the route cost of Model 1 is a route’s least time, its travel, unloading and waiting, and infinity when no schedule meets every window. It is found by scanning the route. The forward scan, a, starts at the opening of the window of the route’s first stop, the depot, and finds the earliest each stop can be served, waiting where a window has not yet opened; the last stop’s gives the earliest the route can finish. The reverse scan, b, goes back from that finish and finds the latest each stop can be served, the first stop’s giving the latest the route can start. The forward scan again, c, from that latest start, is the schedule, and the route’s least time is its earliest finish less its latest start.”

“Determine the least time in which the route from the depot at node 1 to customers 2, 3 and 4, in that order, can be run within every time window, with the travel times and windows of Table 4, and when it should leave the depot, by hand and in Julia.”

The lecture's Table 4. “The route of Ex. 4, its stops in order: the travel time into each and its window.”
StopTravel time in (h)Window (h)
1, depot, departure[6, 18]
21[8, 11]
32[12, 14]
41[15, 18]
1, depot, return1[18, 24]

“Code block 29 gives scanTW the route’s data, in the order of Table 4, with no unloading time:”

t = [0, 1, 2, 1, 1]          # travel to each stop: DC, 2, 3, 4, DC
lo = [6, 8, 12, 15, 18]      # each stop's window opens
hi = [18, 11, 14, 18, 24]    # and closes

Lecture Table 5 and Fig. 10

The lecture's Table 5. “Ex. 4 by hand, the three scans with no unloading time (\(u_k = 0\)): the forward scan from the top, the reverse scan from the bottom, and the forward scan again from the top.”
StopWindow Forward \(\mathrm{a}_k = \max\lbrace\mathrm{a}_{k-1} + t_k, \ell_k\rbrace\) Reverse \(\mathrm{b}_k = \min\lbrace\mathrm{b}_{k+1} - t_{k+1}, h_k\rbrace\) Forward again \(\mathrm{c}_k = \max\lbrace\mathrm{c}_{k-1} + t_k, \ell_k\rbrace\)
1, depart\([6, 18]\)\(\mathrm{a}_1 = 6\)\(\min\{11 - 1, 18\} = 10\)\(\mathrm{c}_1 = \mathrm{b}_1 = 10\)
2\([8, 11]\)\(\max\{6 + 1, 8\} = 8\)\(\min\{14 - 2, 11\} = 11\)\(\max\{10 + 1, 8\} = 11\)
3\([12, 14]\)\(\max\{8 + 2, 12\} = 12\)\(\min\{17 - 1, 14\} = 14\)\(\max\{11 + 2, 12\} = 13\)
4\([15, 18]\)\(\max\{12 + 1, 15\} = 15\)\(\min\{18 - 1, 18\} = 17\)\(\max\{13 + 1, 15\} = 15\)
1, return\([18, 24]\)\(\max\{15 + 1, 18\} = 18\)\(\mathrm{b}_5 = \mathrm{a}_5 = 18\)\(\max\{15 + 1, 18\} = 18\)
Four frames of the route of Example 4, the depot a tan square and customers 2, 3 and 4, each with its window. (a) The route as given, with its travel times. (b) The forward scan from 6, each stop's start after the time it is reached where the two differ. (c) The reverse scan from 18. (d) The forward scan again from 10, the waits at customer 4 and at the depot.
The lecture's Fig. 10. “Ex. 4 by hand, a frame per scan, the depot the tan square with its departure window above it and its return window below: (a) the route as given; (b) the forward scan, from the earliest departure, each stop’s start after the time it is reached where the two differ; (c) the reverse scan, from the earliest finish, each stop’s latest start after the time it is reached going back; (d) the forward scan again, from the latest start, the waits as late as the windows allow. The arrow in the middle of each scan is its direction. Given values, the travel times and windows, are red; determined ones are blue.”

“The earliest finish of the forward scan and the latest start of the reverse scan give the least time of the route:”

\[ \begin{aligned} \text{Earliest Finish} - \text{Latest Start} = 18 - 10 &= 8 \text{ hr} \\ &= 5 \text{ travel} + 3 \text{ delay} \end{aligned} \tag{6} \]

“The 8 hours of Eq. 6 are the 5 of travel, the lower bound, and the 3 of waiting the windows force, an hour at customer 4 and two at the depot in the last scan: a Balance check of Lecture 1.2, the travel and the waits accounting for the whole route.”

Another view Table 5, one step at a time

The symbols of Table 5: the stops are numbered in route order, \(k = 1\) to 5, the depot both first and last; \(t_k\) is the travel time into stop \(k\), the t of Code block 29; and \(\ell_k\) and \(h_k\) are the opening and the closing of its window, its lo and hi. \(\mathrm{a}_k\), \(\mathrm{b}_k\) and \(\mathrm{c}_k\) are the times the three scans find for stop \(k\).

The route of Ex. 4, with its data from Table 4. Change any travel time or window to try another route, then Next step works the three scans one cell at a time. Each step writes out its column's rule from Table 5, then the same rule with the numbers in it.

Stop \(k\)Travel in, \(t_k\)Opens, \(\ell_k\)Closes, \(h_k\)

StopWindowForward \(\mathrm{a}_k\)Reverse \(\mathrm{b}_k\)Forward again \(\mathrm{c}_k\)

The cell just worked is shaded. Hours are hours of the day.

The notation of tactical routing

Asked in the review Lecture 5.3, Sec. 4, Eqs. 8 to 11 and Ex. 8

The questionThe notation of tactical routing: what each symbol of the time feasibility stands for, and how the quantities work together.

Lecture Estimates, not routes

“Most routing procedures are for operational decisions, which, given actual demands, determine actual routes; for tactical decisions, a procedure can only estimate routing performance.”

“Tactical vehicle routing can only estimate routing performance. There is no actual route sequence, but there are overall estimates of how many vehicles would be needed on average over time.”

Lecture The tour, Eq. 8, and the stem, Eq. 9

“Lecture 5.1, Sec. 4, estimated the length of a tour from a central DC through \(m\) customers spread uniformly over an area \(a\) as Eq. 13 in Lecture 5.1:”

\[ \hat{d}_m^{TSP} = \varphi\sqrt{ma} \approx 0.908\sqrt{ma} \tag{8} \]
\(\hat{d}_m^{TSP}\)
estimated length of a tour from a central DC through \(m\) customers (mi)
\(m\)
number of customers
\(a\)
area of the region (mi²)
\(\varphi\)
tour constant, fitted to the two-customer route = \(2(\sqrt{2} + 1)/(3\sqrt{\pi}) \approx 0.908\).

“Whenever a single tour is broken into several separate routes, there is additional travel to and from the depot termed stem travel. Assuming that the expected one-way stem distance is about the average distance from the center of a circle, the \(2r/3\) of Eq. 6 in Lecture 2.5 with \(r = \sqrt{a/\pi}\),”

\[ \hat{d}^{\,\text{stem}}_{\text{1-way}} = \frac{2r}{3} = \frac{2}{3}\sqrt{\frac{a}{\pi}} \]

“Since stem travel occurs both outbound and inbound to the depot, total estimated stem distance is”

\[ \hat{d}^{\,\text{stem}} = 2\hat{d}^{\,\text{stem}}_{\text{1-way}} = 2\left(\frac{2}{3}\sqrt{\frac{a}{\pi}}\right) = \frac{4}{3\sqrt{\pi}}\sqrt{a} = \kappa\sqrt{a} \tag{9} \]
\(\hat{d}^{\,\text{stem}}_{\text{1-way}}\)
estimated one-way stem distance, depot to first or last stop (mi)
\(\hat{d}^{\,\text{stem}}\)
estimated stem distance of a route, out and back (mi)
\(r\)
radius of a circle of area \(a\) (mi)
\(\kappa\)
stem constant = \(4/(3\sqrt{\pi}) \approx 0.752\).
A depot at the center of a circle of customers, with one route: a red stem out from the depot to the route's first customer and back from its last, and a blue tour through its customers.
The lecture's Fig. 20. “A route’s stem (red), out from the depot to its first customer and back from its last, and its tour (blue) through its customers.”

“The travel beyond what the optimal TSP tour would need, the distance out to a route’s first customer and back from its last, is called the stem distance, and the rest is the tour distance, so a route’s total distance is its stem plus its tour.”

“Just as \(\varphi\) wraps up the constant of the tour estimate, the Greek letter \(\kappa\) wraps up this one, which never changes and is almost exactly 0.75. The Greek letters are kept as a reminder that neither constant is an empirical result.”

Lecture The time feasibility, Eq. 10

“In order to be time feasible, vehicle routes must satisfy:”

\[ \begin{gathered} \begin{aligned} \begin{array}{r}\text{Stem time} + \text{Tour Time} \\ {} + \text{Service Time}\end{array} &\le \text{Vehicle-time capacity} \\ (N - 1)\frac{\hat{d}^{\,\text{stem}}}{v} + \frac{\hat{d}_m^{TSP}}{v} + m t_s &\le N t_{\max} \\ (N - 1)\frac{\kappa\sqrt{a}}{v} + \frac{\varphi\sqrt{ma}}{v} + m t_s &\le N t_{\max} \end{aligned} \\ \boxed{\;\left[\kappa(N - 1) + \varphi\sqrt{m}\right]\frac{\sqrt{a}}{v} + m t_s \le N t_{\max}\;} \end{gathered} \tag{10} \]
\(t_{\max}\)
maximum operating time of a vehicle (h)
\(m\)
number of customers
\(N\)
number of routes, one vehicle each
\(a\)
service area (mi²)
\(t_s\)
service time at each customer (h)
\(v\)
average vehicle speed (mph).

“It assumes no capacity constraints, the estimates \(\kappa \approx 0.752\) and \(\varphi \approx 0.908\) of Eq. 9 and Eq. 8, and that \(N - 1\) means no stem travel if there is one vehicle.”

“Time feasibility is where these results are used, and capacity feasibility follows it. With \(N\) routes, one vehicle each, and a maximum operating time \(t_{\max}\), the right-hand side of Eq. 10 is the total vehicle hours available: an eight-hour day and ten vehicles give 80 hours, and whatever is done to make all of the deliveries, its total time cannot exceed those 80 vehicle hours. On the left is the total time required. With one vehicle, or one route, it is just a TSP: \(N - 1 = 0\) cancels the stem, which is ignored, and what remains is the tour of Lecture 5.1. A distance divided by the travel speed gives a time, since miles over miles per hour leaves hours. Then \(m\) is the number of customers and \(t_s\) the service time at each, perhaps 2 or 3 minutes for a delivery van: the time it takes a driver to hop out of the van, put the delivery on the porch, take a photo, run back to the van and take off again. All of that added together has to be no more than the vehicle hours available, and with \(\kappa\) and \(\varphi\) the result is a fairly simple inequality that captures both the stem and the tour, each a multiple of \(\sqrt{a}/v\), plus the service time.”

Lecture Ex. 8: one equation, solved for whichever quantity is unknown

“Determine, from the time feasibility of Eq. 10 and without constructing any route, the minimum operating time of three vehicles, the number of deliveries one vehicle can make in eight hours, and the number of deliveries a firm with six trucks has to outsource, by hand and in Julia.”

“In the symbols of Eq. 10, \(N = 3\), \(m = 100\), \(a = 1{,}000\) mi², \(v = 30\) mph and \(t_s = 6/60\) h, the six minutes in hours, so that every term of the inequality is in hours, a Units check of Lecture 1.2. Dividing Eq. 10 through by \(N\) and setting it at equality gives the least \(t_{\max}\) the deliveries need:”

\[ t_{\min} = \frac{\sqrt{a}}{Nv}\left[\kappa(N - 1) + \varphi\sqrt{m}\right] + \frac{m}{N}t_s \]

“Three vehicles serving 100 customers need at least 7.05 h each.”

“With one vehicle, \(N = 1\), there is no stem, and Eq. 10 at equality is \(m t_s + \varphi\sqrt{ma}/v = t_{\max}\), a quadratic in \(\sqrt{m}\) whose root is”

\[ m = \frac{a\varphi^2 + 2t_{\max}t_s v^2 - \sqrt{a\varphi^2\left(a\varphi^2 + 4t_{\max}t_s v^2\right)}}{2t_s^2v^2} \tag{11} \]

“One vehicle can make 159 deliveries in eight hours.”

“What is nice is that where the customers are does not have to be known: their number is the unknown, and what is known is the total service area. With the known information put into the time feasibility for a maximum of eight hours, \(m\) is the only unknown, and solving for it gives 159.”

“Solving Eq. 10 for \(N\) instead, with \(m = 500\),”

\[ N \ge \frac{\varphi\sqrt{ma}/v + m t_s - \kappa\sqrt{a}/v}{t_{\max} - \kappa\sqrt{a}/v} \]

“Six trucks can make 308 of the 500 deliveries, so 192 have to be outsourced; seven trucks would outsource 134, eight 76, and ten none.”

“The same basic tool, time feasibility, answers dozens of mixes and matches of problems like these, but what it leaves off the table is capacity.”

Another view The time feasibility as a calculator: fill in what is known, solve for the rest

Eq. 10 at equality ties six quantities together. Fill in any five, leave one blank, and the blank one is solved for, with the formula and the numbers that give it. Leave two blank and one is shown as it changes with the other. Fill in all six and the plan is checked against the inequality. The examples load the givens of Ex. 8; the constants are those of Eq. 9 and Eq. 8, \(\kappa = 0.752\) and \(\varphi = 0.908\). The service time is entered in minutes, as a problem usually states it, and goes into Eq. 10 in hours.

Load:
SymbolWhat it isValueUnitSolved
Term of Eq. 10What it isWith the numbersHours

Each distance over a speed is miles over miles per hour, so hours; the service term is customers times hours a customer, so hours too. A whole number of customers is rounded down and a whole number of vehicles up, since “A fractional delivery cannot be made” and a fraction of a vehicle cannot be run.