Lecture 5.2 Recap

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.

Minimum cost insertion, by hand

Asked in the review Lecture 5.2, Secs. 1 and 2, Ex. 3(a)

The questionHow minimum cost insertion works, and how to work the lecture's insertion and savings examples by hand.

Lecture Three shipments, and the costs between their locations

Six numbered locations: 1 and 2 along the middle, 3 and 4 above them, 5 and 6 below. Shipment 1 runs from location 1 to location 2, 300 miles; shipment 2 from 3 to 4, 250 miles; shipment 3 from 5 to 6, 275 miles. Short roads join 1 and 3 and 4 and 2, 30 miles each, and 1 and 5 and 6 and 2, 60 miles each.
The lecture's Fig. 1. “Three-shipment example. Each shipment (blue) travels from its origin to its destination; the dotted links (red) are the roads between the locations, with their miles.”

“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.”

\[ D = \begin{bmatrix} 0 & 300 & 30 & 280 & 60 & 335 \\ 300 & 0 & 280 & 30 & 335 & 60 \\ 30 & 280 & 0 & 250 & 90 & 340 \\ 280 & 30 & 250 & 0 & 340 & 90 \\ 60 & 335 & 90 & 340 & 0 & 275 \\ 335 & 60 & 340 & 90 & 275 & 0 \end{bmatrix} \tag{4} \]

Lecture A route, and its cost by hand

“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.”

\[ c ( R ) = \sum_{i = 1}^{2 n - 1} c_{x_{i} , x_{i + 1}} = 60 + 30 + 250 + 30 + 60 = 430 \tag{3} \]

“Constraint (c) is what defines a route: no segment of it has the truck empty.”

Lecture Where the new shipment can go

“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.”

Two tables of positions. (a) The route 1, 1 with shipment 2 placed at each of six positions; rows 1 and 6, which put shipment 2 entirely after or entirely before shipment 1, carry a red cross, and the other four carry costs c2 to c5, with c3, shipment 2 inside shipment 1, starred. (b) The route 1, 2, 2, 1 with shipment 3 placed at each of 15 positions; rows 14 and 15 carry a red cross and the rest costs c1 to c13, with c4, shipment 3 around the other two, starred.
The lecture's Fig. 3. “Minimum cost insertion, a • marking a stop of the route and a red × a position that is not a route, since the truck is empty between the shipments: (a) shipment 2 inserted into the route \((1, 1)\) at each of the six positions of its loading and unloading, four of them routes, at costs \(c_2\) to \(c_5\); (b) if \(c_3\) is the least (blue, starred), shipment 3 inserted into the route \((1, 2, 2, 1)\) at each of its 15 positions, 13 of them routes. If \(c_4\) is then the least (starred), the route found is \((3, 1, 2, 2, 1, 3)\).”

“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.”

Another view Fig. 3, one row at a time

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.

RowRouteCost

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.

The lecture’s answer: Ex. 3(a), every route the two insertions evaluate

“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 savings, by hand

Added by the instructor Lecture 5.2, Sec. 3, Ex. 5(a) and 6(a)

Lecture The procedure, and the example

“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:”

\[ C = \begin{bmatrix} 0 & 40 & 48 & 38 & 33 & 48 \\ 40 & 0 & 87 & 46 & 65 & 75 \\ 48 & 87 & 0 & 67 & 41 & 47 \\ 38 & 46 & 67 & 0 & 70 & 34 \\ 33 & 65 & 41 & 70 & 0 & 69 \\ 48 & 75 & 47 & 34 & 69 & 0 \end{bmatrix} \]

“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:”

\[ s_{ij} = 2c_{1i} + 2c_{1j} - \left(c_{1i} + c_{ij} + c_{j1}\right) = c_{1i} + c_{1j} - c_{ij} \tag{8} \]

Another view Fig. 7, one pair at a time

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 savings, in the order of the pairs, not of the savings.

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.

StepPairSavingRuleRoutes
Each pair clicked, in the order clicked, as Table 1 lists them.
The lecture’s answer: Table 1 and Fig. 7

“Determine the savings of every pair of customers, and the route the procedure builds from them, pair by pair.”

The lecture's Table 1. “Clarke-Wright on the five customers of Ex. 5, without capacity, pair by pair from the largest saving; the rule is the procedure’s (1) to (3), and “none” a pair already on one route.”
StepPair\(s_{ij} = c_{1i} + c_{1j} - c_{ij}\)RuleRoute
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.”

Five frames of the depot, node 1, and customers 2 to 6. (a) Each customer joined to the depot out and back by gray dotted lines. (b) Step 1 joins 4 and 6 into the route 1, 4, 6, 1. (c) Step 2 adds 3 after 6. (d) Step 3 adds 5 after 3. (e) Step 4 adds 2 before 4, giving the route 1, 2, 4, 6, 3, 5, 1. In each frame the route is blue and the pair joined red.
The lecture's Fig. 7. “Clarke-Wright on Ex. 5, the depot the tan square: (a) the starting state, each customer served out and back (gray, dotted); (b) to (e) a frame per join of Table 1, its step numbered as the table’s row is, the route in blue and the pair it joins in red.”

“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.”

Lecture Ex. 6(a): the same savings, with insertion

“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:”

The lecture's Table 2. “The pairwise savings of the three shipments, largest first.”
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:”

The lecture's Table 3. “The savings procedure on the three shipments, merge by merge.”
StepPairRoutes beforeMergeRoute afterCost
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.”