5.2: Pickup and Delivery Routing · ISE 754, Fall 2026 · in class 3 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 questionHow minimum cost insertion works, and how to work the lecture's insertion and savings examples by hand.
“Fig. 1 illustrates three such shipments. Shipped independently, shipment 1 travels 300 miles from its origin at location 1 to its destination at location 2, shipment 2 travels 250 miles from location 3 to 4, and shipment 3 travels 275 miles from location 5 to 6.”
“Code block 2 computes \(D\) of Eq. 4 as Lecture 4.1 computes the distances between cities on a road network: the seven roads of Fig. 1, each two-way, form a network of the six locations, and Dijkstra’s procedure, run from each location, gives its shortest distance to every other.”
“Instead of a permutation, a route is a vector in which each shipment is indicated by its number, which appears twice: the first time it is picked up, and the second time it is dropped off at its destination. The route (3, 1, 2, 2, 1, 3) picks up shipment 3 first, then shipment 1, then shipment 2, and then drops off shipments 2, 1 and 3.”
“For example, referring to Fig. 1, the route sequence \(\left(3,1,2,2,1,3\right)\) would correspond to travel from location 5 after loading shipment 3 to location 1 to load shipment 1, to location 3 to load 2, to 4 to unload 2, to 2 to unload 1, and to 6 to unload 3. The total cost of the route is 430, where \(c_{5,1} =\) 60, etc.”
“Constraint (c) is what defines a route: no segment of it has the truck empty.”
“Imagine a route that has just one shipment in it, the route \((1, 1)\), which is essentially an independent shipment, and a second shipment, 2, to be added: the alternatives are the places its pickup and its delivery can go, such as the pickup of 2, then the pickup of 1, then the delivery of 1, and so on, and the procedure picks the one with the minimum cost. Every time a shipment is added, the cost of the route either does not change or, more likely, increases, so all that is looked for is how to make that increase as small as possible: the cost goes up, and the procedure finds the least costly way for it to go up. If the third alternative, with cost \(c_3\), is the least, and another shipment, 3, comes along, the route \((1, 2, 2, 1)\) stays in place and the procedure tries shipment 3 at each position, starting with its pickup before that of shipment 1 and its delivery right after, through all the possibilities.”
“Minimum cost insertion does not try those two positions. Of the six positions for inserting shipment 2 into the route \((1, 1)\), four are routes, and of the 15 for inserting a third shipment into a route of two shipments, 13 are.”
Shipment 1 starts alone, on the route \((1, 1)\). Each row is one place shipment 2 can be loaded and unloaded, numbered as Fig. 3 numbers it. Click a row to draw its route on the six locations and add up its cost. Keep a row to insert shipment 3 into it next.
| Row | Route | Cost |
|---|
In a row, the new shipment's two numbers are blue. A red × is a row that is not a route: the truck runs empty between shipments, drawn as a red dashed segment.
“Determine every route the two insertions evaluate for the shipments of Fig. 1, and the least costly of each.”
Code block 17 prints each route as \((i, j)\), the gap the new shipment is loaded in and the gap it is unloaded in, then the route and its cost: shipment 2 into \((1, 1)\), then shipment 3 into the result.
1,2: [2, 1, 2, 1] = 340 1,3: [2, 1, 1, 2] = 360 2,2: [1, 2, 2, 1] = 310 2,3: [1, 2, 1, 2] = 340 rte12 = [1, 2, 2, 1] TD12 = 310
1,2: [3, 1, 3, 2, 2, 1] = 1015 1,3: [3, 1, 2, 3, 2, 1] = 550 1,4: [3, 1, 2, 2, 3, 1] = 490 1,5: [3, 1, 2, 2, 1, 3] = 430 2,2: [1, 3, 3, 2, 2, 1] = 955 2,3: [1, 3, 2, 3, 2, 1] = 610 2,4: [1, 3, 2, 2, 3, 1] = 550 2,5: [1, 3, 2, 2, 1, 3] = 490 3,3: [1, 2, 3, 3, 2, 1] = 515 3,4: [1, 2, 3, 2, 3, 1] = 610 3,5: [1, 2, 3, 2, 1, 3] = 550 4,4: [1, 2, 2, 3, 3, 1] = 955 4,5: [1, 2, 2, 3, 1, 3] = 1015 rte123 = [3, 1, 2, 2, 1, 3] TD123 = 430
“Of the four routes for shipment 2, the least is \((1, 2, 2, 1)\), at 310, row 3 of Fig. 3, which carries shipment 2 inside shipment 1; the two positions that leave the truck empty between the shipments, \((2, 2, 1, 1)\) and \((1, 1, 2, 2)\), are not routes, rows 1 and 6 of the figure, so the procedure does not try them. Of the 13 routes for shipment 3, the least is \((3, 1, 2, 2, 1, 3)\), at 430, the optimum of Ex. 1(c) and row 4 of the figure’s second table. Each insertion raised the cost, from 300 to 310 to 430, and never lowered it, a Bounds check of Lecture 1.2: no insertion can cost less than the route it starts from.”
“Shipment 2 goes inside shipment 1, \((1, 2, 2, 1)\) at 310 of the 4 routes evaluated; shipment 3 then goes around both, \((3, 1, 2, 2, 1, 3)\) at 430 of the 13.”
“Clarke-Wright is the first (1964), and still best, offline routing procedure if there are only vehicle capacity constraints. The pairs of shipments are ordered in terms of their decreasing (positive) pairwise savings. Given savings pair \(i\)-\(j\), without exceeding the capacity constraint, either: (1) create a new route if \(i\) and \(j\) are not in any existing route; (2) add \(i\) to a route only if \(j\) is at the beginning or end of the route; or (3) combine routes only if \(i\) and \(j\) are endpoints of each route. Rule (2) applies either way round: either shipment of the pair can be the one added, when the other is at an end of its route.”
“Determine the route the Clarke-Wright savings procedure constructs, without capacity constraints, from a depot at node 1 to customers at nodes 2 to 6, by hand and in Julia.”
“The costs between the nodes, which are symmetric, are:”
“serving them each out and back costs \(2c_{1i} + 2c_{1j}\), and serving both on one route, from the depot to \(i\), then to \(j\) and back, costs \(c_{1i} + c_{ij} + c_{j1}\), so for symmetric costs their saving is:”
First the savings. At the start each customer is served out and back from the depot, and every saving is blank. Click a pair, then click its three costs in \(C\), \(c_{1i}\), \(c_{1j}\) and \(c_{ij}\), and its saving by Eq. 8 is worked out. Do one pair, a few, or none: All the savings fills in the rest.
Then the routes. With all ten savings in, click the pairs one at a time, from the largest saving down. Each pair clicked is joined by the three rules and numbered in the order clicked, and the map draws the routes as they are built.
| Pair | \(s_{ij} = c_{1i} + c_{1j} - c_{ij}\) | Step |
|---|
The map draws only the routes, as the pairs are picked. Gray dotted: a customer served out and back. Blue: a route. Red: the pair just joined. In \(C\), orange: the costs clicked for the saving being found.
| Step | Pair | Saving | Rule | Routes |
|---|
“Determine the savings of every pair of customers, and the route the procedure builds from them, pair by pair.”
| Step | Pair | \(s_{ij} = c_{1i} + c_{1j} - c_{ij}\) | Rule | Route |
|---|---|---|---|---|
| 1 | \((4, 6)\) | \(38 + 48 - 34 = 52\) | (1) new | \((1, 4, 6, 1)\) |
| 2 | \((3, 6)\) | \(48 + 48 - 47 = 49\) | (2) add 3 | \((1, 4, 6, 3, 1)\) |
| 3 | \((3, 5)\) | \(48 + 33 - 41 = 40\) | (2) add 5 | \((1, 4, 6, 3, 5, 1)\) |
| 4 | \((2, 4)\) | \(40 + 38 - 46 = 32\) | (2) add 2 | \((1, 2, 4, 6, 3, 5, 1)\) |
| 5 | \((3, 4)\) | \(48 + 38 - 67 = 19\) | none | |
| 6 | \((2, 6)\) | \(40 + 48 - 75 = 13\) | none | |
| 7 | \((5, 6)\) | \(33 + 48 - 69 = 12\) | none | |
| 8 | \((2, 5)\) | \(40 + 33 - 65 = 8\) | none | |
| 9 | \((2, 3)\) | \(40 + 48 - 87 = 1\) | none | |
| 10 | \((4, 5)\) | \(38 + 33 - 70 = 1\) | none |
“Fig. 7 draws the starting state and the four joins. After step 4 every customer is on the one route, so the last six pairs change nothing: 2 and 5 are its two ends, and joining them would close the route without the depot.”
“The route costs \(40 + 46 + 34 + 47 + 41 + 33 = 241\). Serving each customer out and back would cost \(2(40 + 48 + 38 + 33 + 48) = 414\), and the four joins saved \(52 + 49 + 40 + 32 = 173\) of it, and \(414 - 173 = 241\), a Balance check of Lecture 1.2: the savings of the pairs joined account for the whole difference.”
“Without capacity constraints, Clarke-Wright joins customers 4 and 6, then adds 3, 5 and 2, and constructs the one route \((1, 2, 4, 6, 3, 5, 1)\), at 241.”
“Clarke-Wright only adds a node to the beginning or to the end of a route, never anywhere in between: once a node is in a route, the points inside the route are not candidates.”
“Each shipment shipped independently costs its own distance, \(c_1 = 300\), \(c_2 = 250\) and \(c_3 = 275\). The least costly route of each pair is found by inserting one shipment into the other’s route, as in Fig. 3, and Eq. 7 then gives each pair’s saving, in Table 2:”
| Pair \((i, j)\) | Least costly route of the two | \(c_{ij}\) | \(s_{ij} = c_i + c_j - c_{ij}\) |
|---|---|---|---|
| \((1, 2)\) | \((1, 2, 2, 1)\), locations \((1, 3, 4, 2)\) | \(30 + 250 + 30 = 310\) | \(300 + 250 - 310 = 240\) |
| \((1, 3)\) | \((1, 3, 3, 1)\), locations \((1, 5, 6, 2)\) | \(60 + 275 + 60 = 395\) | \(300 + 275 - 395 = 180\) |
| \((2, 3)\) | \((3, 2, 2, 3)\), locations \((5, 3, 4, 6)\) | \(90 + 250 + 90 = 430\) | \(250 + 275 - 430 = 95\) |
“The procedure takes the pairs in that order, starting from the routes \((1, 1)\), \((2, 2)\) and \((3, 3)\), in Table 3:”
| Step | Pair | Routes before | Merge | Route after | Cost |
|---|---|---|---|---|---|
| 1 | \((1, 2)\), 240 | \((1, 1)\), \((2, 2)\) | Shmt 2 inserted into \((1, 1)\) | \((1, 2, 2, 1)\) | 310 |
| 2 | \((1, 3)\), 180 | \((1, 2, 2, 1)\), \((3, 3)\) | Shmt 3 inserted into \((1, 2, 2, 1)\) | \((3, 1, 2, 2, 1, 3)\) | 430 |
| 3 | \((2, 3)\), 95 | \((3, 1, 2, 2, 1, 3)\) | none: 2 and 3 on one route |
“Its two merges are the two insertions of Ex. 3(a), so the procedure ends at the same route, \((3, 1, 2, 2, 1, 3)\), at 430. That is the optimum of all 60 routes found by brute force in Ex. 1(c), a Landmark check: savings constructs the optimal route here, in a single pass down its list. And the 825 of the three shipped independently less the 430 is 395, more than any one pairwise saving, since the route consolidates all three.”