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.
“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.”
| Stop | Travel time in (h) | Window (h) |
|---|---|---|
| 1, depot, departure | [6, 18] | |
| 2 | 1 | [8, 11] |
| 3 | 2 | [12, 14] |
| 4 | 1 | [15, 18] |
| 1, depot, return | 1 | [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
| Stop | Window | 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\) |
“The earliest finish of the forward scan and the latest start of the reverse scan give the least time of the route:”
“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.”
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\) |
|---|
| Stop | Window | Forward \(\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 questionThe notation of tactical routing: what each symbol of the time feasibility stands for, and how the quantities work together.
“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 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:”
“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}\),”
“Since stem travel occurs both outbound and inbound to the depot, total estimated stem distance is”
“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.”
“In order to be time feasible, vehicle routes must satisfy:”
“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.”
“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:”
“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”
“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\),”
“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.”
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.
| Symbol | What it is | Value | Unit | Solved |
|---|
| Term of Eq. 10 | What it is | With the numbers | Hours |
|---|
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.