Two simple construction procedures, mincostinsert and savings, along with the twoopt improvement of Lecture 5.1, can be used for most routing applications, including pickup and delivery routing, where each shipment has its own origin and destination. Pickup and delivery routing covers alternatives (d) and (e) of Fig. 1 in Lecture 5.1, in which each shipment is picked up at its own origin and delivered to its own destination, and the truck need not return to where it started.
Half a dozen other construction procedures for the TSP could easily be added, though there are few improvement procedures beyond 2-opt; the savings procedure works as well or better in most cases. It is also much more robust, since it makes no assumptions: many of the others work only for metric distances, or only under certain constraints on the TSP, and the savings procedure has none of those limitations. Like the older methods of routing, it works in all cases, where the more specialized procedures, though more efficient in particular cases, are in general not as robust. And it can handle the more general case of pickup and delivery routing. The classic TSP is peddling or collecting, two of the routing alternatives of Lecture 5.1, where a route is just the sequence of its stops, essentially a permutation. That representation does not carry over to interleaved routes, whose shipments have different origins and different destinations, though the savings procedure can fairly easily be adapted to them. What else is needed to handle that more complicated case is the subject of the sections that follow.
When each shipment can have its own origin and destination, a location sequence is no longer adequate to represent a route, as it was for a tour in Lecture 5.1, whose permutation \pi sufficed because every stop was a delivery from, or a pickup for, the depot. 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.
Show the code that draws this figure
# Code block 1: three shipments and the roads between their locationsP = [0.00.0; 4.00.0; 0.350.75; 3.650.75; # locations 1 to 60.35-1.1; 3.65-1.1]rn =0.17# location radius, data unitslinks = [(1, 2, 300), (3, 4, 250), (5, 6, 275), (1, 3, 30), (4, 2, 30), (1, 5, 60), (6, 2, 60)] # road links, with their miles# points along a curve from p to q, bowed toward ccurvepts(p, c, q; n =60) = [(1- s)^2.* p .+2(1- s) * s .* c .+ s^2.* q for s inrange(0, 1, length = n)]# the part of a curve outside the circles around a and b, cut on each# outlinefunctionclipnodes(pts, a, b; r = rn)ins(x, o) =hypot((x .- o)...) < rfunctioncross(u, v, o) # where u to v crosses the outline around o lo, hi =0.0, 1.0for _ in1:40 mid = (lo + hi) /2ins(u .+ mid .* (v .- u), o) ? (lo = mid) : (hi = mid)endreturn u .+ hi .* (v .- u)end i =findfirst(x -> !ins(x, a), pts) j =findlast(x -> !ins(x, b), pts)returnvcat([cross(pts[i-1], pts[i], a)], pts[i:j], [cross(pts[j+1], pts[j], b)])endfunctionarrowline!(ax, pts, col; lw =2.5) # its tip on the last pointlines!(ax, first.(pts), last.(pts); color = col, linewidth = lw) j =findlast(x ->hypot((pts[end] .- x)...) >0.25, pts) u, v = pts[j], pts[end]arrows2d!(ax, [u[1]], [u[2]], [v[1] - u[1]], [v[2] - u[2]]; color = col, shaftwidth = lw, tipwidth =11, tiplength =11)endfunctiondrawlink!(ax, i, j, d) # a road, dotted, with its miles p, q = P[i, :], P[j, :] seg =clipnodes(curvepts(p, (p .+ q) ./2, q), p, q)lines!(ax, first.(seg), last.(seg); color = redc, linestyle =:dot, linewidth =1.5) m, long = (p .+ q) ./2, abs(q[1] - p[1]) >1 side = m[1] <2 ? -1:1# a short link's miles beside ittext!(ax, m[1], m[2]; text =string(d), color = redc, fontsize =13, align = long ? (:center, :top) : (side <0 ? :right ::left, :center), offset = long ? (0, -4) : (6side, 0))endfunctiondrawshipment!(ax, b, e, label) # bowed above its road p, q = P[b, :], P[e, :] c = [(p[1] + q[1]) /2, p[2] +0.38]arrowline!(ax, clipnodes(curvepts(p, c, q), p, q), bluec) top = (p .+ q) ./4.+ c ./2# the curve's highest pointtext!(ax, top[1], top[2]; text = label, color = bluec, fontsize =13, align = (:center, :bottom), offset = (0, 3))endfunctiondrawnodes!(ax, idx) # locations, over everythingfor i in idxpoly!(ax, Circle(Point2f(P[i, 1], P[i, 2]), rn); color =:white, strokecolor = ink, strokewidth =1.5)text!(ax, P[i, 1], P[i, 2]; text =string(i), color = ink, fontsize =13, align = (:center, :center))endend# an arrowhead partway along each leg of a route through x, y, so its# direction shows; on a map, x and y are longitude and latitude, and# each leg is taken as the map's Mercator projection draws itmerc(φ) =log(tand(45+φ/2))functionlegarrows!(ax, x, y; color, onmap =false, at =0.55, size =12, every =1) Y = onmap ? merc.(y) : yfor i in1:every:length(x)-1 dx, dy = x[i+1] - x[i], Y[i+1] - Y[i] dx == dy ==0&&continue# a location visited twice xm, ym = x[i] + at * dx, Y[i] + at * dyscatter!(ax, [xm], [onmap ? 2atand(exp(ym)) -90: ym]; marker =:rtriangle, markersize = size, rotation =atan(dy, onmap ? deg2rad(dx) : dx), color = color isa AbstractVector ? color[i] : color)endend# the shipments loaded (L) and unloaded (U) at location i: (L1,2:U3)functionldlabel(i, sh) L, U =findall(==(i), sh.b), findall(==(i), sh.e) parts = [isempty(L) ? "":"L"*join(L, ","),isempty(U) ? "":"U"*join(U, ",")] s =join(filter(!isempty, parts), ":")returnisempty(s) ? "":"($s)"endlet fig =Figure(size = (560, 330)) ax =Axis(fig[1, 1]; aspect =DataAspect())hidedecorations!(ax); hidespines!(ax)foreach(l ->drawlink!(ax, l...), links)for (k, (b, e)) inenumerate([(1, 2), (3, 4), (5, 6)])drawshipment!(ax, b, e, "Shipment $k")enddrawnodes!(ax, 1:6)xlims!(ax, -0.5, 4.5); ylims!(ax, -1.5, 1.25) figend
Figure 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.
One route that carries all three shipments on one truck is described by its shipment, route and location sequences:
The TSP and the classic vehicle routing problem have a single origin and destination, the depot: all of the routes start at one point and end at one point. In practice many routing problems have no depot. A national trucking company, for example, might carry blood plasma that has passed its expiration date for transfusion from the clinics where it was donated to the medical facilities that use it as a raw material for drug products; its trucks start and stop all over the country, and routing code written for a depot does not work when each shipment has its own origin and destination. In Fig. 1, the three shipments all go in the same general direction. Done point to point, their cost is just the sum of their individual costs, whether distance or cost; but there are obvious savings if one truck could pick up all three shipments and drop each one off at its destination. The way a route was represented for the TSP does not map over. There a route was the sequence of customers starting at the depot, a permutation of their indices, and any permutation was a valid route, because everything delivered came from one location or, in collecting, everything picked up ended at one final destination. When the shipments have different origins and destinations, the representation has to change. 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. A minus sign on each drop-off is unnecessary, since the order from left to right tells which occurrence is the pickup and which the drop-off; and with a sign, moving the numbers around, as 2-opt improvement does, could put a drop-off before its pickup, which an unsigned route cannot. So there are three sequences. The shipment sequence lists the shipments being considered, here 1, 2 and 3, without saying in what order they are picked up and delivered; the route gives the actual sequence of pickups and deliveries; and the location sequence gives, for every element of the route, the location at which that pickup or delivery occurs. Here every pickup and delivery is at a distinct location, but the same location could be the pickup or the delivery of different shipments, and the representation handles that easily. Many of the construction and improvement procedures map over to it, changed a little but with the same basic logic. The route above costs 60 + 30 + 250 + 30 + 60 = 430, against 825 for the three shipments done independently point to point, a saving of almost 50%.
The procedure to determine the minimum cost route sequence takes the sequence L = \left(y_1,\ldots,y_n\right) of n shipments in a load as input and outputs a 2n-element route sequence R = \left(z_1,\ldots,z_{2n}\right), representing the sequence in which the loading and unloading of each shipment occurs, so as to minimize the total cost to travel from the loading of the first shipment to the unloading of the last shipment in the route. The first occurrence of z_j = y_i in R indicates the loading of shipment y_i, and the second occurrence of z_k = y_i indicates its unloading, where j < k. Each element z_i of route sequence R has a corresponding location x_i,X = \left(x_1,\ldots,x_{2n}\right), representing either the origin or destination location of the shipment. A 2n-element route R has 2n-1 segments, where each segment consists of a consecutive pair of elements in R,\left(z_i, z_{i+1}\right). The total cost of R is the sum of the cost of each of its segments. Given the costs c_{ij} between all pairs of locations i and j,
c(R)=\sum_{i=1}^{2n-1} c_{x_i,\,x_{i+1}}
\tag{2}
where
c(R)
=total cost of route R
x_i
=location at which element z_i of R is loaded or unloaded
c_{ij}
=cost between locations i and j.
Eq. 2 represents the cost of route R. 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.
In Fig. 1 the cost of each shipment can be taken as its distance, at $1 per mile, so shipment 1 costs 300 as an independent shipment, shipment 2 costs 250 and shipment 3 costs 275. Since the shipments do not all start from the same depot, each could always hire a carrier to pick it up and deliver it, and that is always an alternative. If the shipments are small enough to fit easily onto one truck, putting all of them on one truck makes sense if it saves total distance traveled, and the question is then which origin to start from, which shipment to load first, second and third, and how to deliver them. With n shipments the route sequence is twice as long, 2n, where a TSP of n stops had a sequence of n, or n + 1 with the depot, so the effort is essentially doubled. Each route is not entered by hand: a construction procedure creates it, since with shipments all over the place there are many alternatives, and the computer does the hard work of finding the best. As a freebie, the 2-opt procedure of Lecture 5.1, designed for a permutation, works just as well on a route, because each number appears twice and carries no sign: flipping the middle portion of a route still leaves each shipment loaded before it is unloaded, though Sec. 2 shows that it can leave the truck empty. The location sequence is like the tour of the TSP, the actual locations visited; but where a TSP has one depot and every other location a drop-off or a pickup, here shipment 2, for example, starts at location 3, its own warehouse, and is shipped to a customer at location 4. Procedures for routing have to deal with both sequences, where the TSP had only one, and that restriction is why the TSP handles only peddling or collecting, not mixtures of pickups and deliveries at different places, as most routing problems other than the classic TSP have, such as those of a trucking company with customers all over the place. What follows covers only the mechanics of constructing such routes, leaving the capacity of trucks and the other constraints, such as time windows, to the vehicle routing problem of Lecture 5.3. Constraints only reduce what is possible, so this is the best case, the unconstrained vehicle routing problem. Nor is it obvious that all three shipments always belong on one route: if shipment 3 were far away, it would probably be better off on its own truck, with the other two combined. Shipments clustered geographically are the ones worth combining, and the representation handles the cases where combining does not make sense. That is why the term independent shipment is used: a shipment is independent of a consolidated route, and it is shipped TL or LTL, whichever is cheaper, the choice of Lecture 3.2.
The route sequencing problem is a generalization of the traveling salesman problem and simple heuristics can be used to provide reasonably good solutions. In order to make the route sequencing procedure especially simple and fast, an online procedure is used that takes as input only the current route sequence and the shipment to be added to the sequence. This is opposed to a more time-consuming offline procedure that would use all of the shipments to construct the route sequence. While an offline procedure can sometimes produce better results and would make the resulting route independent of the order in which shipments are added to the route, it requires extra time.
Route sequencing is stated as a model in Model 1. It generalizes the TSP of Model 1 in Lecture 5.1, which is the case in which every shipment is loaded at one location, peddling, or unloaded at one, collecting, and a truck begins and ends its route there, as in Ex. 6(d), so that the route reduces to a permutation. It keeps the TSP’s leave and enter constraints, those of the linear assignment problem of Model 1 in Lecture 4.2, on the route’s stops, opens its single tour into a single route that need not return to its start, and adds precedence; Secs. 2 and 3 formulate its two construction procedures.
minimize: total cost of a tour through every nodeone route that loads and unloads every shipment of a load
solve for:
(a) tourroute, a sequence that visits each node exactly once and returns to its starting nodeof stops, the loading and the unloading of each shipment.
subject to:
(a) Leave: each nodestop is left exactly once, except the last;
(b) Enter: each nodestop is entered exactly once, except the first;
(c) Single tourroute: the arcs used form one connected cyclepath through all the nodesstops, not several, the truck carrying at least one shipment along each; (d) Precedence: each shipment is loaded before it is unloaded.
assumptions: (a) each shipment has its own origin and destination;
(b) arc costscosts between locations are given and need not be symmetric;
(c) cost of a tourroute is the sum of the costs of its arcs, including the return to the startsegments, from the loading of the first shipment to the unloading of the last.
Constraint (c) is what defines a route: no segment of it has the truck empty. A segment on which the truck is empty divides it into two routes; otherwise a truck traveling for months on the road, with long gaps of empty travel between its shipments, would all be one route. The point of view is also typically the shipper’s, not the carrier’s: only the carrier is concerned with minimizing deadhead, the empty travel between routes, and what happens between routes is a problem for the carrier, outside the focus of this course.
Example 1: Three shipments on one route
Determine the cost of the route (3, 1, 2, 2, 1, 3) for the three shipments of Fig. 1, by hand and in Julia, how it compares with shipping them as independent shipments, and the least costly of every route.
Example 1(a): By hand
Determine the route’s cost from its location sequence in Eq. 1 and the costs of Fig. 1.
With the location sequence X of Eq. 1, its cost by Eq. 2 is:
c ( R ) = \sum_{i = 1}^{2 n - 1} c_{x_{i} , x_{i + 1}} = 60 + 30 + 250 + 30 + 60 = 430
\tag{3}
The five segments of Eq. 3 add up to the route’s cost, and when Ex. 1(b) computes the same 430 in code, an independent route agrees with the hand sum, a Triangulate check of Lecture 1.2. Their total is also bounded on both sides, a Bounds check: the route carries shipment 1 from location 1 to location 2, so it cannot cost less than that shipment’s own 300, and it is worth having only if it costs less than the 300 + 250 + 275 = 825 of the three shipments done independently.
The route (3, 1, 2, 2, 1, 3) visits locations (5, 1, 3, 4, 2, 6) and costs 430, against 825 for the three independent shipments.
Example 1(b): In Julia
Determine the same location sequence and cost with Logjam’s isorigin, rte2loc and rteTC, from the costs D between the six locations.
The costs between the locations are the shortest distances on the links of Fig. 1:
=costs between the locations, its row i and column j the cost c_{ij} from location i to location j.
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. It then enters the shipments, each a row with its origin b and destination e, as Logjam’s routing functions read them:
# Code block 2: the costs between the six locations, and the shipmentsusingGraphs, SimpleWeightedGraphsi = [1, 3, 5, 1, 4, 1, 6] # one end of each roadj = [2, 4, 6, 3, 2, 5, 2] # its other endw = [300, 250, 275, 30, 30, 60, 60] # its milesg =SimpleWeightedGraph(i, j, w) # a network of two-way roadsD, _ =shortestpaths(g, weights(g), nv(g)) # from every locationD =Int.(D) # whole milessh =DataFrame(b = [1, 3, 5], e= [2, 4, 6]) # origin, destinationD
1
shortestpaths(g, weights(g), n) runs Dijkstra’s procedure from each of the first n nodes, here all six, and returns the shortest distances between them and the predecessors, of which only the distances are kept, as in Lecture 4.1; Int.(D) then gives the distances as the whole miles they are.
Code block 3 marks which elements of the route are loadings, the first occurrence of each shipment, translates the route into its location sequence, and computes the cost of each segment and the whole route:
# Code block 3: the route's loadings, location sequence and costR = [3, 1, 2, 2, 1, 3]@showisorigin(R) # true where a shipment is loaded@show X =rte2loc(R, sh) # the location of each element@showsegcost(X, D) # the cost of each segment@showrteTC(R, sh, D) # the route's cost@showsum(D[sh.b[k], sh.e[k]] for k in1:3); # three independent
rteTC is the sum of segcost over the location sequence rte2loc gives, which is Eq. 2.
Logjam’s rteTC gives the same 430, and the three independent shipments cost 825.
Example 1(c): Every route
Determine the least costly of every route of the three shipments, by brute force.
With only three shipments, the cost of every route can be computed, and the least costly of them is the optimum that the construction procedures of Secs. 2 and 3 are compared with. Each of the three shipments appears twice in a route, so there are 6!/(2!\,2!\,2!) = 90 distinct orderings of (1, 1, 2, 2, 3, 3), and with n shipments there are (2n)!/2^n; in each, the first appearance of a shipment is its loading. Not every ordering is a route, though: in 30 of the 90, such as (1, 1, 2, 2, 3, 3), the truck is empty on a segment, having unloaded every shipment it loaded before it loads the next, which by constraint (c) of Model 1 makes two or three routes, so 60 of the orderings are routes. Lecture 5.1 closed by expecting interleaved pickups and deliveries to need hard construction; written as this unsigned route vector, with no constraints, a route is still easy to construct, since loading every shipment before unloading any always gives one, so pickup and delivery is again a case of easy construction, and hard construction returns with the constraints of Lecture 5.3. The multiset_permutations function of the Combinatorics package lists exactly those orderings: given a collection in which elements repeat, here each shipment twice, it gives each distinct ordering of it once, where permutations would list all 6! = 720 orderings of the six elements, the same ordering eight times over. Code block 4 keeps the orderings that are routes, those on which the truck always carries a shipment, and finds the cost of each, one at a time, as Code block 19 of Lecture 5.1 does for every tour:
# Code block 4: all 60 routes by brute forceusingCombinatoricsrtesegsum(r, x) =cumsum(x[r] .*ifelse.(isorigin(r), 1, -1))[1:end-1]v = [1, 1, 2, 2, 3, 3]rtes = (r for r ∈multiset_permutations(v, 6)ifall(>(0), rtesegsum(r, ones(3))))TCᵒ, rᵒ =minimum((rteTC(r, sh, D), r) for r ∈ rtes)@showlength(multiset_permutations(v, 6)) # the orderings@showlength(collect(rtes)) # the routes@show TCᵒ # the cheapest of them@showcount(rteTC(r, sh, D) == TCᵒ for r ∈ rtes) # how many that cheaprᵒ # the cheapest route
1
rtesegsum gives the cumulative sum of a value of each shipment over each segment of a route: isorigin is true for each element that is a loading, the first appearance of its shipment, as Code block 10 shows, so the value is added at the shipment’s loading and subtracted at its unloading. With a 1 for each shipment it gives the number of shipments on the truck over each segment, and with each shipment’s weight it would give the weight on board.
2
multiset_permutations(v, 6) gives the distinct orderings of all 6 elements of v, each once, though shipments 1, 2 and 3 each appear twice in it: 90 of them, against the 720 of permutations(v). The parentheses make rtes a generator, which produces the routes one at a time as the next line finds their costs, rather than storing all 60 first.
3
The if keeps the 60 orderings on which the truck carries at least one shipment over every segment, the routes.
4
Each route is paired with its cost, and minimum compares the pairs by cost first, so it returns the cheapest cost together with its route, as Code block 5 of Lecture 5.1 does for tours.
The least costly of all 60 routes is the route of Ex. 1(a), (3, 1, 2, 2, 1, 3), at 430, and no other route costs as little.
The optimum of the 60 routes is (3, 1, 2, 2, 1, 3), at 430.
Location indices in a location vector should range from 1 to the number of unique locations. This allows correct indexing into a distance matrix. Code block 5, for example, shows how to convert shipment origin and destination zip codes into a location vector.
In many problems, the information about where the origins and destinations are has to be translated into location vectors, that is, into indices that range from 1 to the number of unique locations. The reason is that the routing procedures, trying all the different possible beginning and end points for a route, look up each segment in a matrix of distances or travel times, which needs an index for each location. The four shipments of Code block 5 have four origin and four destination zip codes, but because of duplication there are only four unique ones, so each zip code is mapped to its unique location. The origin and destination zip codes are put in one list, the unique zip codes in it are found, without the duplicates, and the location indices run from 1 to the number of unique zip codes; each shipment’s beginning point b and endpoint e is then the index of its zip code among them. The first shipment, for example, begins at location 2, zip code 27606, the second of the unique zip codes, and ends at location 4. This is almost the plumbing of routing, one of the low-level things, but there is no obvious way of doing it, and the code is worth keeping as an example. A function could hide it all on the assumption that the locations are always zip codes, but seeing it done this way makes it easier to adapt to other ways of representing points: if the origins and destinations were given by longitude and latitude to three digits of accuracy, say, two of them within some threshold distance of each other could be taken as the same location before the indices are assigned. From the routing procedure’s point of view, what matters is that with the beginning and end points as indices 1 through 4, a procedure trying different ways of inserting shipments into routes can look up the corresponding distance or travel time in the matrix.
As an example, four shipments are known only by the zip codes of their origins and destinations, as a shipper’s records might give them: from Raleigh, North Carolina (27606) to Detroit (48234), from Gainesville, Florida (32606) to Cary, North Carolina (27518), from Detroit to Gainesville, and from Gainesville to Detroit. Code block 5 puts the origin and destination zip codes of the four shipments in one list, keeps each zip code once, sorted, and gives each shipment’s origin and destination as its index b and e among them; the zip codes’ centroids then give the distance matrix the indices look into:
# Code block 5: zip codes to locations, and the distances between themshz =DataFrame(orig = [27606, 32606, 48234, 32606], dest = [48234, 27518, 32606, 48234])zips =sort(unique([shz.orig; shz.dest])) # each zip code onceloc =1:length(zips) # the location indicesshz.b =indexin(shz.orig, zips) # each origin's locationshz.e=indexin(shz.dest, zips) # each destination'sz =uszcta5()XY =Matrix(z[indexin(zips, z.ZCTA5), [:LON, :LAT]])Dz =dists(XY, XY, :mi) *1.2# road miles, circuity 1.2@showDataFrame(loc = loc, zip = zips)@show shzround.(Dz, digits =2)
The circuity factor of 1.2 is that of Lecture 2.2, Sec. 7.
A comparison of the same kind, three shipments first considered as three independent shipments and then combined on one route that uses the same truck, is the analysis a carrier or trucking company would make: it has three different shipments, for which it would at least initially task three different trucks, and it would also consider what happens if one truck carries several of the shipments at the same time.
Example 2: Three shipments across the Southeast
Determine the total distance of three shipments, from Raleigh to Athens, from Asheville to Jacksonville and from Savannah to Gainesville, shipped independently and consolidated on one route, for several routes.
Code block 6 finds the six cities by name and state in Logjam’s table of places and computes the road distances between them, as great circle distances times the circuity factor of 1.2 of Lecture 2.2, Sec. 7:
# Code block 6: the six cities, and the road distances between themCity = ["Raleigh", "Athens", "Asheville", "Jacksonville", "Savannah","Gainesville"]St = [:NC, :GA, :NC, :FL, :GA, :FL]loc = [loc2lonlat(c; state = s) for (c, s) inzip(City, St)]x, y = [r.LON for r in loc], [r.LAT for r in loc]D =dists(hcat(x, y), hcat(x, y), :mi) *1.2
Code block 7 gives each shipment its origin b and its destination e, the indices of its cities in City, and Code block 8 adds up their distances shipped independently, which Fig. 2 draws:
# Code block 9: the three independent shipments on a mapfig, ax =makemap(x, y; xexpand=0.3)resize!(fig, 600, 520)sh2ln(sh, x) =vcat(collect([x[b], x[e], NaN]for (b, e) inzip(sh.b, sh.e))...)# each city's name over the shipments loaded and unloaded there, one# label placed by hand clear of the lines, flush to its point's sidecitylabel(i, sh) = City[i] *"\n"*ldlabel(i, sh)lalign = [(:left, :center), (:right, :center), (:left, :top), (:left, :center), (:left, :top), (:center, :top)]loff = [(5, 0), (-5, 0), (9, -9), (19, 0), (8, -8), (0, -5)]lines!(ax, sh2ln(sh, x), sh2ln(sh, y), color=:red)for (b, e) inzip(sh.b, sh.e) # each shipment's direction, Code block 1legarrows!(ax, x[[b, e]], y[[b, e]]; color=:red, onmap=true)endscatter!(ax, x, y)text!(ax, x, y, text=citylabel.(eachindex(City), Ref(sh)); align = lalign, offset = loff)fig
Figure 2: The three shipments of Ex. 2 shipped independently, each from its origin to its destination.
For a route that picks up in Raleigh and Asheville, delivers in Athens, picks up in Savannah and then delivers in Gainesville and Jacksonville, Code block 10 marks which of its elements are loadings, the first occurrence of each shipment, Code block 11 translates it into its location sequence, Code block 12 picks out the distance of each segment from D, and Code block 13 does all three in one call of rteTC:
# Code block 10: which elements of a route are loadingsrte = [1, 2, 1, 3, 3, 2]isorigin(rte)
# Code block 13: the route's cost, in one callrteTC(rte, sh, D)
916.857351701912
The route of Code block 10 is not meant to be optimal; it is just a route to work with, and any route will do: a random route is essentially two random permutations mixed together, as the random tours of Lecture 5.1 were one. The first of the functions identifies which elements of a route are origins and which are destinations, since each shipment’s number appears twice: it gives the Boolean value true for the elements that are pickups, and its negation is then true for the deliveries. It uses Julia’s set data structure to keep track of which shipments have been seen: a shipment not yet seen is a pickup and is added to the set, and one already seen is a delivery. The next function does a lot of the work of the procedures: given a route, it translates it into its location sequence, using one of Julia’s most useful features, an ifelse that can be broadcast, so that for a pickup it takes the shipment’s beginning field b and otherwise its ending field e. This is critical, because whenever there is a route, its location sequence can immediately be found, and the location sequence is what is then used to look up the cost of each segment of the route. That is what the segment cost function does, the same segcost that Lecture 5.1 used for a tour, here given the location sequence: it picks out the element of the cost matrix for each segment of the route. Added up, they give 916.86, an improvement over the 1,006.18 of the three independent shipments, even though the route is not necessarily optimal.
The five segment costs of Code block 12 are numbers picked from the matrix: the first segment, from location 1 to location 3, is 264, the entry in row 1 and column 3. The matrix here is the distance matrix D, but in general it can be a cost, which is why the functions call it C, and it is given the distance matrix because here distance and cost are the same. Most realistically the cost of a routing problem is the travel time, written T; it is rarely dollars, because the same trucks are used and their cost per mile is about the same, so that distance is a good substitute, but time is usually what constrains a route: hours-of-service rules, for example, allow a truck driver no more than 11 hours of driving, and a route may also have a maximum distance. So generically the term is cost, but it is usually a time or a distance, not dollars. Route total cost, rteTC, puts route-to-location and segment cost together: from the route, the shipments and the cost matrix it finds the location sequence, computes its segment costs and sums them, 916.86 for this route. It is the main worker bee. Every constraint is put into the route total cost, so the 2-opt, savings and minimum cost insertion procedures need no change when constraints are added. Here it is unconstrained and only adds up the segments; but with a limit of, say, 1,000 miles on a route, it could return a cost of infinity for a route that exceeds the limit, and in the savings procedure, which looks only at positive savings, an infinite cost of consolidating gives a savings of minus infinity. It is the same idea as the infinite cost that the maximin location of Lecture 2.2, Sec. 4, gives a point outside the region it must stay in, used in a routing context, and none of the routing code has to change. To use it, Code block 14 defines a one-line function rTDh of the route alone, since the distance matrix and the shipments do not change; it locks in their current values, and the h, for handle, marks it as a one-line function that does a calculation. The single-shipment route of shipment 1, (1, 1), a pickup in Raleigh and a delivery in Athens, is a valid route whose cost is just the distance from location 1 to location 2 in the matrix, with nothing recalculated.
A route that interleaves the first two shipments, (1, 2, 1, 2), with shipment 3 on a single-shipment route beats shipping all three independently, and the route (1, 2, 1, 3, 3, 2) of Code block 10, which carries all three, is the cheapest of those tried. Which route is cheapest of all is what the construction procedures of Secs. 2 and 3 determine.
Shipped independently, the three shipments travel 1,006.18 mi; of the routes tried, (1, 2, 1, 3, 3, 2) is the shortest, at 916.86 mi.
2. Minimum cost insertion
There are two types of routing procedure, depending on the application. Most of the time these problems are thought of in an offline mode: all of the candidate shipments are available at one time, and from that group the best thing to do can be determined. But sometimes shipments come in with no advance knowledge of what will be available: the truck starts operating with one shipment, and while it is on the road a second shipment asks to be picked up, and before what to do with that one is determined a third arrives. The truck might be going off in a direction that, in retrospect, with all of the information available at the beginning, would have been done in a different order at less cost or less distance. Without that information, the procedure is an online procedure.
Online procedure: a procedure that adds a shipment to an existing route as it becomes available. Its example is Insert and Improve, which, for each shipment, inserts it where it has the least increase in cost for the route and then improves the route (mincostinsert → twoopt).
Offline procedure: a procedure that considers all shipments to determine the order in which each is added to the route. Its example is Savings and Improve, which, using all shipments, determines the insert ordering based on “savings,” and then improves the final route (savings → twoopt).
Minimum cost insertion is not only the online procedure: savings, the offline one, uses it to merge two routes, inserting each shipment of one into the other (Sec. 3), so it is needed even when every shipment is known at once.
Of the two techniques used here, the savings procedure works only offline, with all of the data available, since it is a way of selecting which shipments are the best ones to start a route with, as Sec. 3 shows. Minimum cost insertion works every time a new shipment is given for whatever the existing route is: it finds the best place in that route to add the one shipment, giving another route with the new shipment in it, and when another shipment comes minutes later it can be added the same way. It is like a greedy procedure, as in Lecture 4.1, always taking the next optimal step, so the route it finishes with is probably not as good as that of an offline procedure that has all of the data. These are two areas of application, and neither is better than the other.
Fig. 3 shows the procedure’s two steps, inserting a second shipment into a route and then a third:
Show the code that draws this figure
# Code block 15: the positions minimum cost insertion trieslet# set in the lecture math's serif, as is the route (1, 2, 2, 1) fig =Figure(size = (470, 542), figure_padding =4, fonts = (; regular = Makie.MathTeXEngine.texfont())) ax =Axis(fig[1, 1]; aspect =DataAspect())hidedecorations!(ax); hidespines!(ax) w, dy =0.78, 0.62# a column's width, a row's heightX(c) = c * w# position (i, j) loads the shipment in gap i, unloads it in gap j;# each gap has two columns, and the route's stops are at 3, 6, ...functionslots(i, j)sx(g, s) =3(g -1) + sreturn i == j ? (sx(i, 1), sx(i, 2)) : (sx(i, 2), sx(j, 1))end# a table's rules, its column rules, and its subcaption belowfunctionframe!(y0, yb, xr, cap; ncol =0.0)for yy in (y0 +0.5dy, y0 -0.5dy, yb)lines!(ax, [X(-1.25), xr], [yy, yy]; color = ink, linewidth =1)endlines!(ax, [X(-0.2), X(-0.2)], [y0 +0.5dy, yb]; color = ink, linewidth =1) ncol >0&&lines!(ax, [ncol, ncol], [y0 +0.5dy, yb]; color = ink, linewidth =1)text!(ax, (X(-1.25) + xr) /2, yb -0.12; text = cap, fontsize =15, color = ink, align = (:center, :top))end# bad: the rows that are not routes, a red × in place of their costfunctionpostable!(route, k, pos, y0, best, bad, cap) m =length(route) stops =X.(3.* (1:m)) ncol =X(3m +2.6) # the rule before the costs xr = ncol +1.25text!(ax, stops, fill(y0, m); text =string.(route), fontsize =16, color = ink, align = (:center, :center))for (r, (i, j)) inenumerate(pos) # one row per position y = y0 - r * dy r == best &&poly!(ax, Rect(X(-1.25), y - dy /2, xr -X(-1.25), dy); color = (bluec, 0.14)) # the leasttext!(ax, X(-0.7), y; text =string(r), fontsize =16, color = ink, align = (:center, :center))scatter!(ax, stops, fill(y, m); color = ink, markersize =6)text!(ax, X.(collect(slots(i, j))), [y, y]; text =fill("$k", 2), fontsize =16, color = ink, align = (:center, :center)) r in bad ?text!(ax, ncol +0.15, y; text ="×", fontsize =20, color = redc, align = (:left, :center)) :text!(ax, ncol +0.15, y; text = L"c_{%$r}", fontsize =17, color = r == best ? bluec : ink, align = (:left, :center)) r == best &&scatter!(ax, [ncol +0.95], [y]; marker =:star5, markersize =15, color = bluec)end yb = y0 - (length(pos) +0.5) * dyframe!(y0, yb, xr, cap; ncol)return ybend# rows 1 and 6 of (a), the end and the front, leave the truck empty pos2 = [(3, 3), (1, 3), (2, 2), (2, 3), (1, 2), (1, 1)] yb =postable!([1, 1], 2, pos2, 0.0, 3, [1, 6],"(a) Shipment 2 inserted into the route (1, 1)") pos3 = [(i, j) for i in1:5 for j in i:5 if (i, j) != (1, 1)]push!(pos3, (1, 1)) # the front last, as in (a) yb3 =postable!([1, 2, 2, 1], 3, pos3, yb -1.25, 4, [14, 15],"(b) Shipment 3 inserted into the route "*"(1, 2, 2, 1)") xr =X(3*4+2.6) +1.25# the right edge of (b)xlims!(ax, -1.4w, xr +0.1); ylims!(ax, yb3 -0.7, 0.5) figend
Figure 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 is in some sense like 2-opt, but it works on a route rather than on a permutation of integers, and whatever the actual costs are, the setup is the same. 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. The number of possibilities is a formula of the route’s length before the insertion; the count can be verified on a piece of paper by listing them. In practice the procedure is of order n^2, about the most that can realistically be dealt with in medium to large problems, so it is at the upper limit of what is feasible. It is in some sense brute force: it uses none of the geographic information that, looking at the routes, would show that many alternatives are not worth trying. But brute force is what works for almost anything: with time windows and other constraints, it is hard to find a higher-level view of the problem that could eliminate many alternatives. The procedure leaves out the alternatives in which the truck goes empty between shipments, for example the pickup and delivery of shipment 1 followed by the pickup of shipment 2: whenever the truck becomes empty, what follows is defined as a second route, which also reduces the possibilities quite a lot. The efficiency of the procedure can be improved by techniques from computer science, the main one being memoization: when a route is expensive to evaluate, as with time windows, where the route has to be scanned, its cost can be stored in a Julia dictionary with the route as its key, as infinity if it is infeasible, so that the next time the route is seen its cost is looked up rather than computed. Improving efficiency on the programming side, rather than with domain knowledge that applies only to one type of problem, is typically much more robust.
The pickup of the new shipment goes into one of the m + 1 gaps of a route of m stops, before its first stop, between two of its stops, or after its last, and the delivery into the same gap or a later one. Two of those positions are not routes: loading and unloading the new shipment before the first stop, or after the last, leaves the truck empty between it and the other shipments, and by constraint (c) of Model 1 that makes two routes. So the number of routes evaluated is
\frac{m(m + 3)}{2} - 1
\tag{5}
where
m
=number of stops on the route before the insertion, two per shipment.
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.
Given a load sequence L, the procedure insertimprove, formulated below, is used to construct a route R. Each shipment y in L is added to R using the subprocedure mincostinsert that determines where the loading and unloading of the shipment can be added with the minimum increase in cost.
Model 1 formulation: Minimum cost insertion
algorithm mincostinsert;{ input: shipment y; route R of m = 2n stops; cost c(R) }{ output: R with y loaded and unloaded at least cost, and its cost }begin TC := ∞; for i := 1 to m do { the gap y is loaded in } for j := max(2, i) to m + 1 do { the gap y is unloaded in } begin R′ := (z₁, …, zᵢ₋₁, y, zᵢ, …, zⱼ₋₁, y, zⱼ, …, zₘ); if c(R′) < TC then R* := R′, TC := c(R′); end; return R*, TC;end;
In mincostinsert, y is inserted between subsequences of R, where any subsequence \left(z_i,\ldots,z_j\right) where i > j corresponds to the empty sequence \left(\,\right); thus, for example, when i = 1 and j = 2,\left(z_1, z_0, y, z_1, z_1, y, z_2,\ldots,z_{|R|}\right) reduces to \left(y, z_1, y, z_2,\ldots,z_{|R|}\right), a route where the loading of the new shipment occurs before any of the other shipments in the sequence.
The implementation runs the loops above as written, evaluating only the routes counted by Eq. 5, as a function named apart from Logjam’s, mincostinsert_rte: Logjam’s mincostinsert, in the release the course’s environment pins, also tries i = j = m + 1, loading and unloading the new shipment after the last stop, which is not a route.
mincostinsert_rte (generic function with 1 method)
Example 3: Minimum cost insertion
Determine where minimum cost insertion loads and unloads shipment 2 in the route (1, 1), and then shipment 3 in the result, for the shipments of Fig. 1 and for those of Ex. 2.
Example 3(a): Three shipments on one route
Determine every route the two insertions evaluate for the shipments of Fig. 1, and the least costly of each.
Ex. 2 has reused the names D and sh, so Code block 16 finds Ex. 1’s costs again from the network g of Code block 2, which Ex. 2 left unchanged, and enters Ex. 1’s shipments again, as D1 and sh1:
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. Code block 18 makes the same two insertions with mincostinsert_rte, the implementation of the formulation above:
# Code block 18: the same two insertions, by the implementationr, TC =mincostinsert_rte(2, [1, 1], rTD1h)r, TC =mincostinsert_rte(3, r, rTD1h)@show r@show TC;
r = [3, 1, 2, 2, 1, 3]
TC = 430
The printing insertion and the implementation agree, a Triangulate check: two ways of computing the insertion reach the same routes.
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.
Example 3(b): Three shipments across the Southeast
Determine the same two insertions for the three shipments of Ex. 2, and the route they give.
Code block 19 makes the two insertions with rTDh, the route cost of Ex. 2’s shipments from Code block 14:
# Code block 19: the two insertions for Ex. 2's shipments# insert shmt 2 route into shmt 1 routerte12, TD12 =mincostinsert_prt(2, [1, 1], rTDh)@show rte12@show TD12# insert shmt 3 route into shmt 1&2 routerte123, TD123 =mincostinsert_prt(3, rte12, rTDh)@show rte123@show TD123;
The route loads shipment 1 in Raleigh and shipment 2 in Asheville, unloads shipment 1 in Athens, loads shipment 3 in Savannah, and then unloads shipment 2 in Jacksonville and shipment 3 in Gainesville, the route Fig. 4 draws.
Show the code that draws this figure
# Code block 20: the consolidated route on the maploc =rte2loc(rte123, sh)lines!(ax, x[loc], y[loc], color=:green)legarrows!(ax, x[loc], y[loc]; color=:green, onmap=true, at=0.4)fig
Figure 4: The route that minimum cost insertion builds for Ex. 2’s three shipments (green), over the three shipments shipped independently (red).
Inserted at least cost, Ex. 2’s shipments travel 849.11 mi on the route (1, 2, 1, 3, 2, 3), against 1,006.18 mi shipped independently.
The pseudocode is not meant to be understood in every detail; it gives the flavor of the procedures, and it is cleaner than the Julia code, which for these problems becomes messy enough to give little insight into what is happening, while mapping closely to what that code does. At the highest level, a routing procedure takes minimum cost insertion and the sequence L of the shipments the route is to be created from, and the order in which the shipments are considered gives different routes. Online, there is probably no control over that order: the shipments are taken in whatever order they appear, each is inserted at minimum cost, and the resulting route is passed to 2-opt. Offline, different orderings of the shipments would be tried, to see which is best. Minimum cost insertion itself is just two nested for loops, literally trying all of the possibilities, with c evaluating the cost of each route; though written as a function of R alone, c could be a complicated procedure, taking all kinds of capacity considerations into account.
After each shipment has been inserted into R, the pairwise exchange subprocedure twoopt is used to possibly improve the route by replacing nonconsecutive pairs of segments \left(z_{i-1}, z_i\right) and \left(z_j, z_{j+1}\right) in R with segments \left(z_{i-1}, z_j\right) and \left(z_i, z_{j+1}\right), and reversing the subsequence \left(z_i,\ldots,z_j\right) until a reduction in cost is found; if so, R is replaced with the improved route and the process restarts, continuing until no improvement is found for all pairs of segments.
The 2-opt of Lecture 5.1 never moves the first or the last element of the sequence it improves, which for a tour is the depot at both ends. On a route those are its first and last stops, and moving them is part of improving it, so the 2-opt of a route reverses any stretch (z_i, \ldots, z_j) of it, as described above, its first and last stops included. A reversal can also leave the truck empty between shipments, as (1, 2, 1, 2) reversed in its middle gives (1, 1, 2, 2), two routes, so a reversal that does is skipped; rtesegsum of Code block 4 gives the shipments on board over each segment:
Model 1 formulation: Modified two-opt
algorithm twoopt;{ input: route R = (z₁, …, zₘ) of m = 2n stops; cost c(R) }{ output: route Rᵒ that no 2-opt change improves, and its cost TCᵒ }begin Rᵒ := R, TCᵒ := c(R); { the start is the best so far } done := false; while not done do { until a scan improves nothing } begin done := true, i := 1; while done and i ≤ m − 1 do begin j := i + 1; while done and j ≤ m do begin R′ := R with zᵢ, …, zⱼ reversed; { a 2-opt change } if R′ carries a shipment over every segment and c(R′) < TCᵒ then { strictly better } Rᵒ := R′, TCᵒ := c(R′), done := false; j := j + 1; end; i := i + 1; end; R := Rᵒ; { scan again from the new route } end; return Rᵒ, TCᵒ;end;
Model 1 implementation: Modified two-opt
# Model: route sequencing, modified two-opt, the twoopt of a routefunctiontwoopt_rte(r, rTCh) rᵒ, TCᵒ =copy(r), rTCh(r) done =falsewhile !done done =truefor i =1:length(r)-1, j = i+1:length(r) r′ =vcat(r[1:i-1], reverse(r[i:j]), r[j+1:end])all(>(0), rtesegsum(r′, ones(maximum(r′)))) ||continue TC =rTCh(r′)if TC < TCᵒ rᵒ, TCᵒ = r′, TC done =falsebreakendend r =copy(rᵒ)endreturn rᵒ, TCᵒend
twoopt_rte (generic function with 1 method)
Insert and improve, the online procedure, is these two in turn, shipment by shipment in the order of L:
Model 1 formulation: Insert and improve
algorithm insertimprove;{ input: load sequence L of n shipments; cost c(R) }{ output: route R and its cost }begin R := (y, y), where y is the first shipment of L; for each later shipment y of L, in order, do begin R := mincostinsert(y, R); { minimum cost insertion } R := twoopt(R); { modified two-opt } end; return R, c(R);end;
Model 1 implementation: Insert and improve
# Model: route sequencing, insert and improvefunctioninsertimprove(L, rTCh) r = [L[1], L[1]]for k in L[2:end] r =mincostinsert_rte(k, r, rTCh)[1] r =twoopt_rte(r, rTCh)[1]endreturn r, rTCh(r)end
insertimprove (generic function with 1 method)
Infeasibility is handled the way it was in the location problems: there are more elegant ways of accounting for it, but whenever a route is not feasible its cost is set to infinity, and the computer does the work. The difficulty, as with location, is that in some cases just getting a feasible starting point is hard: a point picked at random is likely to be infeasible, and a search started there, like the Nelder-Mead search of Lecture 2.2, just spins its wheels, still reporting infinity, and gets nowhere. That is why it is important to have a good construction procedure, one that, whatever the problem, builds a solution piece by piece and keeps it feasible, which for complicated problems is the hardest thing. A small trucking company, for example, might care nothing about the optimality of its routes, since it already has its trucks, and want only routes that are feasible, because getting one by hand that does not violate any of its many constraints is already a struggle; feasibility can be much more of a priority than any notion of optimality. As each shipment is added, different shipment orders can result in different routes, and 2-opt improves each with the first improvement procedure of Lecture 5.1: as soon as a better route is found, it becomes the new route and the improvement starts again from it. The alternative, steepest descent, tries all possibilities and takes the best of them, then tries all possibilities again; first improvement tends to work better.
The total cost of each route created by the procedure is dependent on the order of the shipment sequence L. For example, referring to the three shipments shown in Fig. 1, there are six different possible sequences L.
Example 4: Insert and improve
Determine the routes that insert and improve builds for the three shipments of Fig. 1 from each of their six load orders, how they compare with the optimum of Ex. 1(c), and the route it builds for five shipments in North Carolina.
Example 4(a): Six load orders
Determine the route insert and improve builds from each load order L of the three shipments.
Code block 21 runs insertimprove from each of the six orders, with Ex. 1’s route cost rTD1h of Code block 16:
# Code block 21: insert and improve, from each of the six load ordersfor L inpermutations(1:3) r, TC =insertimprove(L, rTD1h)println(L, " => ", r, " = ", TC)end
Four of the six orders reach the route (3, 1, 2, 2, 1, 3) of Ex. 1, at 430. The two that insert shipment 2 last, (1, 3, 2) and (3, 1, 2), stop at (2, 1, 3, 3, 1, 2), at 455, which no 2-opt change improves: changing the load order shows the result depending on the order, as the route sequencing paragraph above says it does. Against the optimum of every route found by brute force in Ex. 1(c), insert and improve finds it from four of the six orders and stops 25 above it from the other two, a Landmark check.
Insert and improve builds (3, 1, 2, 2, 1, 3), at 430, the optimum of Ex. 1(c), from four of the six load orders, and (2, 1, 3, 3, 1, 2), at 455, from the two that insert shipment 2 last.
Example 4(b): Five shipments in North Carolina
Determine the route insert and improve builds for the five shipments of Fig. 5, loaded in the order (1, \ldots, 5).
In Fig. 5, five shipments are consolidated given the load sequence \left(1,\ldots,5\right). The published route and location sequences are \left(3,2,5,5,1,4,3,1,2,4\right) and \left(4,3,7,1,1,6,5,2,2,2\right).
Code block 23 builds the route from the load order (1, \ldots, 5) and compares it with the route of Eq. 6:
# Code block 23: insert and improve, loading in the order 1, ..., 5r5, TC5 =insertimprove(1:5, rTD5h)@show r5@show TC5@showrte2loc(r5, sh5) # its location sequence@showrTD5h([3, 2, 5, 5, 1, 4, 3, 1, 2, 4]) # the published routesum(rTD5h([k, k]) for k in1:5) # shipped independently
The route of Code block 23 differs from the published one only in the order in which shipments 1, 2 and 4 are unloaded at location 2, which costs nothing, so the two routes tie: both visit the location sequence of Eq. 6, at the same cost.
Show the code that draws this figure
# Code block 24: the five shipments and their route on a maplet x5 = X5[:, 1], y5 = X5[:, 2] fig5, ax5 =makemap(x5, y5; xexpand =0.25, yexpand =0.12, doRoadbkgd =false)# no base map: its one state line, at the top, read as a shipmentforeach(p -> p.visible =false, ax5.scene.plots)φ=sum(y5) /length(y5) # mid-latitude, for angles on the map# placed by hand, so no line runs along another or through a# location: each shipment bowed by bulge, bent at along of the way,# its arrow at ta of the way and its label at tl, above or below it bulge = [0.4, -1.0, 0.1, -0.1, 0.2] along = [0.9, 0.5, 0.9, 0.5, 0.5] ta = [0.3, 0.45, 0.35, 0.5, 0.5] tl = [0.35, 0.15, 0.15, 0.2, 0.65] above = [true, true, true, false, true]for (k, (b, e)) inenumerate(zip(sh5.b, sh5.e)) # each shipment p, q = [x5[b], y5[b]], [x5[e], y5[e]] nk = [-(q[2] - p[2]), q[1] - p[1]] ./hypot((q .- p)...) c = p .+ along[k] .* (q .- p) .+ bulge[k] .* nk pts =curvepts(p, c, q) # Code block 1's curvelines!(ax5, first.(pts), last.(pts); color = bluec, linewidth =2.5) j =round(Int, 1+ ta[k] *59) u, v = pts[j-2], pts[j+2] θ =atan((v[2] - u[2]) /cosd(φ), v[1] - u[1])scatter!(ax5, [pts[j][1]], [pts[j][2]]; marker =:rtriangle, rotation = θ, markersize =14, color = bluec) i =round(Int, 1+ tl[k] *59) a, z = pts[i-2], pts[i+2] θt =atan((z[2] - a[2]) /cosd(φ), z[1] - a[1])text!(ax5, pts[i][1], pts[i][2]; text ="Shmt $k", color = bluec, fontsize =13, rotation =abs(θt) >pi/2 ? θt +pi: θt, align = (:center, above[k] ? :bottom ::top), offset = (0, above[k] ? 5:-5))end loc5 =rte2loc(r5, sh5)lines!(ax5, x5[loc5], y5[loc5]; color = redc, linestyle =:dash, linewidth =2.5) # the route, over the shipmentslegarrows!(ax5, x5[loc5], y5[loc5]; color = redc, onmap =true) labs =ldlabel.(1:7, Ref(sh5)) # loaded and unloaded, Code block 1 al = [(:right, :center), (:left, :center), (:right, :center), (:right, :center), (:right, :bottom), (:right, :center), (:right, :center)] # each label, by hand of = [(-14, -2), (14, 0), (-14, 0), (-14, 0), (-10, 8), (-14, -6), (-14, 0)]scatter!(ax5, x5, y5; color =:white, strokecolor = ink, strokewidth =1.5, markersize =22)text!(ax5, x5, y5; text =string.(1:7), color = ink, fontsize =13, align = (:center, :center))for i in1:7text!(ax5, x5[i], y5[i]; text = labs[i], color = redc, fontsize =13, font =:bold, align = al[i], offset = of[i])end lim = ax5.finallimits[] # the figure fitted to the mapresize!(fig5, 600,round(Int, 600* lim.widths[2] / lim.widths[1]) +10) fig5end
Figure 5: Five shipments among seven locations in North Carolina (blue), and the route insert and improve builds for them (red, dashed). Each location is labeled with the shipments loaded (L) and unloaded (U) there.
Reproducing the published location sequence and its cost is a Source check of Lecture 1.2.
Loaded in the order (1, \ldots, 5), insert and improve visits the locations (4, 3, 7, 1, 1, 6, 5, 2, 2, 2) of Eq. 6, 299.59 mi, against 642.85 mi for the five shipped independently.
NoteCost allocation for routing
Cost allocation for routing arises when shipments from different firms share the same vehicle: how much should each shipment contribute to the total cost paid to the carrier? That is not the typical case in practice. Typically the carrier runs the whole show: it hires the truck, gets a variety of customers, determines how to combine and route their shipments, and determines what to charge each of them, whether a standard posted price or a price the shipper can take or leave. The scenario can be flipped, to a coalition of shippers that rents a vehicle for their transportation, and the question then is how to split its cost among them in a way that is fair. That question has applications well beyond routing, and there is no standard definition of what is fair: it depends on what is important. What makes the routing problem easier is that it has a natural reservation price, a shipment’s best alternative, which is its independent charge, TL or LTL. Since even a really small shipment can always ship LTL, no shipper would agree to be charged more than that, and the allocation is bounded by it. And unlike a manufacturer’s costs, which it seldom reveals, TL and LTL charges are largely public, at least as spot prices, which are the worst case, since a shipper with enough volume pays a negotiated discount off them. Two shipments, each a truckload over the same 300 miles at $1 per mile, cost $300 each shipped independently; if together they need no more than one truck’s maximum payload, they can share one truck and split its $300, while shipments that each fill a truck gain nothing by collaborating.
A mechanism for that flipped scenario uses publicly available information about the shipments to consolidate several of them into a single load. Its routes are built online: as each new shipper joins a coalition, an online route construction procedure with 2-opt improvement reconstructs the route, and the new transport charge is reallocated to each shipper, which lets a shipper determine its own share of the charge when it wants to be part of more than one consolidated load.1
That is insert and improve, used online in earnest: each shipper’s shipment is inserted at least cost as it joins, and the route is improved by 2-opt.
Which allocation is fair turns out to depend on the horizon. Of two allocation methods, Shapley and proportional, the Shapley allocation is the most equitable in the short term, when a fixed set of shipments is to be consolidated, since it charges each shipment a cost that closely matches its impact on the overall cost of the consolidated load; proportional allocation promotes efficiency in the long term, because it gives shippers an incentive to consolidate more.2
Equity and efficiency pulling apart is the trade-off of the apartment problem of Model 4 in Lecture 2.1, where the fair location cost the couple more travel in total than the efficient one, the price of fairness.
3. Savings
Lecture 5.1 defined the pairwise saving of two customers served from a DC, Eq. 8 in Lecture 5.1: the cost of serving them individually, by two round trips, less the cost of serving them together on one route. The savings procedures of this section are built on it, and on its generalization to two shipments that each have their own origin and destination.
Pairwise savings are what the offline procedures are built on, and of those the savings procedure is probably the best. It calculates the pairwise savings between shipments. For the two shipments 1 and 2 of Fig. 6, the separate costs are 300 and 250, and combined the cost is 30 + 250 + 30 = 310, the green route that carries 1 and 2 together. The pairwise saving is the cost of the two as individual point-to-point shipments less their cost shipped together, here 300 + 250 − 310 = 240. Most savings procedures calculate all of the pairwise savings and then construct a route by picking the largest. What subtracts from a saving is the extra distance traveled with fewer shipments on board: here, 30 miles to pick up the second shipment and, after dropping it off, another 30 to drop off the first. So savings are largest when two shipments have the same origin and the same destination, and none can do better than that; of such pairs, the procedure would start with the pair whose origin and destination are furthest apart, the pair most worth shipping together, and work back from it.
The pairwise savings between shipments i and j, and that of shipments 1 and 2, are:
=cost of the least costly route carrying shipments i and j together.
A saving is negative when the two shipments cost more together than apart, and the savings procedures list only the positive ones.
Show the code that draws this figure
# Code block 25: the pairwise saving of shipments 1 and 2let fig =Figure(size = (560, 260)) # with Code block 1's helpers ax =Axis(fig[1, 1]; aspect =DataAspect())hidedecorations!(ax); hidespines!(ax)# the roads among locations 1 to 4foreach(l ->drawlink!(ax, l...), links[[1, 2, 4, 5]])drawshipment!(ax, 1, 2, "Shipment 1")drawshipment!(ax, 3, 4, "Shipment 2") p1, p2, p3, p4 = (P[i, :] for i in1:4) # the route 1-3-4-2 (green) leg =clipnodes(curvepts(p1, (p1 .+ p3) ./2, p3), p1, p3)lines!(ax, first.(leg), last.(leg); color = dcc, linewidth =2.5)arrowline!(ax, clipnodes(curvepts(p3, [2.0, 2.05], p4), p3, p4), dcc)arrowline!(ax, clipnodes(curvepts(p4, (p4 .+ p2) ./2, p2), p4, p2), dcc)text!(ax, 2.0, 1.4; text ="Shipments 1 and 2", color = dcc, fontsize =13, align = (:center, :bottom), offset = (0, 3))drawnodes!(ax, 1:4)xlims!(ax, -0.6, 4.6); ylims!(ax, -0.4, 1.75) figend
Figure 6: The pairwise saving of shipments 1 and 2 of Fig. 1. Shipped independently (blue), they cost 300 and 250; on one route (green), which loads 1 and then 2 and unloads 2 and then 1, they cost 30 + 250 + 30 = 310.
The savings procedure this section ends with allows pickups and deliveries at different points, and puts a shipment anywhere in a route, because it uses minimum cost insertion, which is easy with today’s computers. In 1964, Clarke and Wright proposed a savings procedure that was computationally feasible for its time, by only adding shipments at the beginning or the end of a route: there was no way of putting a shipment in the middle of a route, since that is minimum cost insertion, which on the computers of the 1960s would not have been computationally feasible. Remarkably, it works really well, and even today it gives a pretty good solution, still computationally reasonable some 60 years later. It calculates the savings just as above, the same notion of a saving, and looks at them in decreasing order of value. The only difference is what it does with each pair i and j of a saving: one of three things. If neither is on a route, as with the first pair, since there are no routes at the start, the two form a new route. If i is not on a route and j is, i is considered for adding at either the beginning or the end of that route. And if i and j are on two different routes, the routes can only be combined if both are endpoints, each at the beginning or the end of its route; otherwise it is not possible. That third condition is where the procedure with minimum cost insertion differs: it can merge any two routes, inserting each shipment of the smaller route into the larger one by minimum cost insertion, as long as the route stays feasible. That is more complex, but for its time, Clarke-Wright was quite effective.
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.
Without capacity constraints, as in this lecture, no pair is refused for exceeding a capacity, and the three rules alone determine the routes; Lecture 5.3 adds the capacity. With a depot at node 1, the saving of customers i and j is the pairwise saving of Eq. 8 in Lecture 5.1, written with the costs c_{1i} from the depot in place of the distances d_i: 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:
=savings of serving customers i and j on one route
c_{ij}
=cost between nodes i and j, node 1 the depot.
Example 5: Clarke-Wright savings
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.
Example 5(a): By hand
Determine the savings of every pair of customers, and the route the procedure builds from them, pair by pair.
The costs between the nodes, which are symmetric, are:
Node 1 is the depot, and there are five customers, nodes 2 to 6. From the distances between them, the savings are calculated. The procedure starts with the largest, nodes 4 and 6, with a saving of 52: everything else being equal, they give the biggest bang. Since the costs here are distances, it can be seen visually that these two are the closest to each other, and that is the heuristic: customers close to each other are good candidates and probably have the largest savings. As two customers get closer together, their pairwise saving gets larger, and as they get further apart it gets smaller and smaller, until, far enough apart, it goes to zero or negative; two customers at the same point have the maximum saving. The saving takes the costs of going out to each customer and back, and subtracts from their sum the cost of serving the two on one route, out to one, on to the other and back to the depot; so as the angle of separation between two customers increases, the saving goes down and down. That is the picture to have of a savings procedure: for an array of customers, with distance to be minimized, it gives a good heuristic for which customers to cluster. Neither 4 nor 6 is on a route, so they form the first route, by condition 1, since there was no route. The next pair, 3 and 6, uses condition 2, because node 6 is on the route and node 3 is not, so 3 can be added to it.
Eq. 8 gives each pair’s saving from C, and the procedure then takes the pairs from the largest saving down, in Table 1:
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.
Step
Pair
\boldsymbol{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.
Figure 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.
Example 5(b): In Julia
Determine the same savings in Julia, and how the route compares with every tour from the depot.
Code block 26 computes the saving of every pair, largest first, as the rows (i, j, s_{ij}) of a matrix, and then computes the cost of all 120 tours from the depot one at a time, as Code block 4 computes the cost of every route:
# Code block 26: the savings, largest first, and all 120 toursCcw = [ 040483833484008746657548870674147384667070343365417006948754734690]iˢ = [i for i in2:6 for j in i+1:6] # the pairs (i, j), i < jjˢ = [j for i in2:6 for j in i+1:6]sˢ = [Ccw[1, i] + Ccw[1, j] - Ccw[i, j] for (i, j) inzip(iˢ, jˢ)]k =sortperm(sˢ, rev =true) # largest firstprt(hcat(iˢ[k], jˢ[k], sˢ[k]); cols = ["i", "j", "Saving"], row_title ="Pair")TCs = [sum(segcost([1; p; 1], Ccw)) for p ∈permutations(2:6)]@showlength(TCs) # the tours looked at@showminimum(TCs) # the cheapest of themsum(segcost([1, 2, 4, 6, 3, 5, 1], Ccw)) # the Clarke-Wright route
The savings and their order are those of Table 1, a Triangulate check of the hand working, and the route’s 241 is the least of all 120 tours, a Landmark check: here, without capacity, Clarke-Wright constructs the optimal tour.
In Julia, as by hand, the savings run from 52 down to 1, and the Clarke-Wright route, at 241, is the optimal tour.
What is remarkable is how effective the procedure is, some 60 years after Clarke and Wright proposed it in 1964. When the term savings is used for the vehicle routing problem (VRP), by default everybody thinks of the Clarke-Wright procedure; a paper on much more complex routing, calculating total logistics costs and shipment sizes with a more complex savings procedure, might draw a reviewer’s objection that the savings procedure is 60 years old. But Clarke-Wright is really just a simple version of the more complicated savings. The key thing the pairwise savings tell any savings procedure is which two nodes to start with, here nodes 4 and 6, with the largest saving, 52; the procedure then goes down the list. Node 1 is the depot and the other nodes are the customers, which is what the truck that starts and returns to Raleigh in Ex. 6(d) gives Logjam’s procedure. Each route has an empty leg that depends on whether it is peddling, where the truck loads at the depot, travels loaded and unloads at each customer, then returns empty, or collecting, where it leaves empty, makes its first, second and third pickups, and travels loaded back to the depot. Clarke-Wright cannot handle interleaved routing: it has to be collecting or peddling, the classic VRP.
The Clarke-Wright procedure of Ex. 5 has to be expanded to apply to routes with pickups and deliveries at different places. 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. If the two nodes being considered are in separate routes and combining them violates no capacity, the two routes can be merged into one larger route, but again only at their beginning or end points; and if that fails, a new route is started. Those are the options, and for a route of pickups and deliveries they would not create many routes, because most of them would not be feasible. So the savings procedure for such routes looks, instead of at just the beginning and end points, at all of the places a route could be inserted: a more brute-force approach.
Written out, the savings procedure starts every shipment on a route of its own, lists the pairs with a positive saving from the largest down, and for each pair whose shipments are still on different routes, inserts the shipments of the shorter route into the longer one by minimum cost insertion, one at a time. The minimum cost insertion of Sec. 2 is used inside savings: the savings determine which shipments to combine, and mincostinsert determines where each one goes in the route it joins. So even when every shipment is known at once and the construction is offline, minimum cost insertion is needed:
Model 1 formulation: Savings
algorithm savings;{ input: shipments 1, …, n; cost c(R), ∞ for an infeasible route }{ output: routes, each shipment on exactly one }begin Rₖ := (k, k) for each shipment k; sᵢⱼ := c(Rᵢ) + c(Rⱼ) − c(best route of i and j), each pair i < j; list the pairs with sᵢⱼ > 0 in decreasing order of sᵢⱼ; for each pair (i, j) in the list do if i and j are on different routes then begin S, T := the shorter and the longer of their two routes; R′ := T; for each shipment k on S do R′ := mincostinsert(k, R′); if c(R′) < ∞ then T := R′, S := ∅; { the merge kept } end; return the routes that are not empty;end;
Logjam exports it, with the pairwise savings as a function of its own, pairwisesavings, which lists the pairs and their savings in the order the procedure takes them.
Model 1 implementation: Savings
# Model: Route sequencing, savings construction# rteTCh: Function that calculates route cost: rteTCh(route) -> cost.# Should return Inf for infeasible routes (capacity, time windows,# etc.).# sh: Shipments DataFrame where each row is a shipment requiring pickup# and delivery.savings # (rteTCh, sh)
Example 6: Savings construction
Determine the route the savings procedure constructs for the three shipments of Fig. 1 by hand and in Julia, for the three shipments of Ex. 2, and for a tour from Raleigh to the other five cities of Ex. 2.
Example 6(a): By hand
Determine the pairwise savings of the three shipments of Fig. 1 and the routes the savings procedure merges, step by step, with the costs between their locations.
The costs between the locations, those of Code block 16, are:
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:
Table 2: The pairwise savings of the three shipments, largest first.
Pair \boldsymbol{(i, j)}
Least costly route of the two
\boldsymbol{c_{ij}}
\boldsymbol{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:
Table 3: The savings procedure on the three shipments, merge by merge.
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.
Savings merges shipments 1 and 2 first, at a saving of 240, then shipment 3, and constructs (3, 1, 2, 2, 1, 3), at 430, the optimal route.
Example 6(b): In Julia
Determine the same pairwise savings and route with Logjam’s pairwisesavings and savings, and compare them with Ex. 6(a).
Code block 27 lists each pair with a positive saving, as the rows (i, j, s_{ij}) of a matrix, largest first, and then constructs the routes:
The savings 240, 180 and 95 and the one route (3, 1, 2, 2, 1, 3) at 430 are those of Table 2 and Table 3, a Triangulate check of the hand working.
Logjam’s savings constructs the same route as Ex. 6(a), (3, 1, 2, 2, 1, 3), at 430.
Example 6(c): Three shipments across the Southeast
Determine the pairwise savings of the three shipments of Ex. 2 and the route savings constructs for them.
Ex. 3(b) inserted shipment 2 into (1, 1) as the route rte12 of Code block 19, the least costly route of shipments 1 and 2, so Code block 28 finds their pairwise saving from it:
# Code block 30: the savings route, and its cost@show r =savings(rTDh, sh)rTDh.(r)
r = savings(rTDh, sh) = [[1, 2, 1, 3, 2, 3]]
1-element Vector{Float64}:
849.1072994662491
Shipments 2 and 3 have the largest saving, so savings merges them first, then inserts shipment 1, and constructs (1, 2, 1, 3, 2, 3), the route minimum cost insertion built in Ex. 3(b). Code block 31 computes the cost of all 60 routes of the three shipments, one at a time, with the generator rtes of Code block 4:
# Code block 31: Ex. 2's 60 routes by brute forceTCᵒ, rᵒ =minimum((rTDh(r), r) for r ∈ rtes) # paired, as Code block 4@show TCᵒ # the cheapest of themrᵒ # the cheapest route
TCᵒ = 849.1072994662491
6-element Vector{Int64}:
1
2
1
3
2
3
The route is the optimum of all 60, a Landmark check, and savings and minimum cost insertion reach it by different orders of merging.
Savings constructs (1, 2, 1, 3, 2, 3), at 849.11 mi, the optimal route of Ex. 2’s three shipments and the route of Ex. 3(b).
Example 6(d): Tour from Raleigh
Determine the tour savings constructs from Raleigh to the other five cities of Ex. 2 and back, and its improvement by 2-opt.
Code block 32 gives each of the other five cities a shipment from Raleigh, and a truck tr that begins and ends its route at Raleigh, location 1; with the truck, the route’s location sequence starts and ends at Raleigh, shown as the shipment 0 in the first column:
# Code block 32: a shipment from Raleigh to each city, a truck, savingsshR =DataFrame(b =ones(Int, 5), e= [2:6;])tr = (b =1, e=1)rTDRh(rte) =rteTC(rte, shR, D, tr)rte =savings(rTDRh, shR)[1]@showrTDRh(rte)prt(hcat(vcat(0, rte, 0), rte2loc(rte, shR, tr)); cols = ["Shipment", "Location"], row_title ="Element")
With every shipment loaded at Raleigh, a route is a tour: loading the five shipments in the order of a permutation p and unloading them in the same order, the route (p, p), visits the cities in that order. Code block 36 computes the cost of all 5! = 120 such tours, one at a time, as Code block 4 computes the cost of the routes of Ex. 1:
# Code block 36: all 120 tours from Raleigh by brute forceTCs = [rTDRh([p; p]) for p ∈permutations(1:5)] # only the costs@showlength(TCs) # the tours looked atminimum(TCs) # the cheapest of them
length(TCs) = 120
1348.4042743937814
The tour 2-opt reaches is the cheapest of all 120, a Landmark check.
Savings constructs a tour from Raleigh of 1,377.63 mi, and 2-opt improves it to 1,348.4 mi, the optimal tour.
Example 7: Tour of North Carolina by savings
Determine the tour of the 100 NC counties that savings constructs, and its improvement by 2-opt, against the tours of Ex. 4 in Lecture 5.1.
Before the tour is constructed, Ex. 4 in Lecture 5.1 gives a Prior for it: its estimate of the length of the tour, from the number of counties and the area of the state, was 2,106.45 mi, and the optimal tour turned out to be 2,107.56 mi. Code block 37 gives every other county a shipment from county 1, with the truck tr of Code block 32 starting and ending there, and constructs the tour by savings. Its distances are great circle miles, without the circuity of Ex. 2, 4(b) and 8, as in Ex. 4 in Lecture 5.1, so that the two tours compare:
# Code block 37: the NC counties, a shipment from county 1 to eachdf =filter(r -> (r.STFIP ==st2fips(:NC)), uscounty())XY =hcat(df.LON, df.LAT)DN =dists(XY, XY, :mi)n =nrow(df)# Node 1 has same b,e so can be ignoredshN =DataFrame(b =ones(Int, n-1), e= [2:n;])rTDNh(rte) =rteTC(rte, shN, DN, tr)rteN =savings(rTDNh, shN)[1]rTDNh(rteN)
2443.412422738106
Show the code that draws this figure
# Code block 38: the savings tour on a mapfig, ax =makemap(df.LON, df.LAT; xexpand=0.05)loc =rte2loc(rteN, shN, tr)lines!(ax, df.LON[loc], df.LAT[loc], color=:red, linewidth=.5)# Code block 1's arrowheads, on every third leglegarrows!(ax, df.LON[loc], df.LAT[loc]; color=:red, onmap=true, size=7, every=3)lim = ax.finallimits[] # the figure fitted to the mapresize!(fig, 600, round(Int, 600* lim.widths[2] / lim.widths[1]) +10)fig
Figure 10: The tour of the 100 NC counties that savings constructs.
Fig. 10 draws the savings tour. With every shipment loaded at county 1, the route’s location sequence, county 1 and then each county once, is a tour, so Code block 39 improves it with the 2-opt of Lecture 5.1 and its tour cost πTCh, giving the tour of Fig. 11:
# Code block 39: the savings tour improved by 2-opt, as a tourloc =rte2loc(rteN, shN, tr)π= [1; loc[loc .!=1]; 1] # county 1, then each county onceπTCh(π) =sum(segcost(π, DN))π′, TD =twoopt(π, πTCh)TD
2169.0242211847944
Show the code that draws this figure
# Code block 40: the improved tour on a mapfig, ax =makemap(df.LON, df.LAT; xexpand=0.05)lines!(ax, df.LON[π′], df.LAT[π′], color=:red, linewidth=.5)# Code block 1's arrowheads, on every third leglegarrows!(ax, df.LON[π′], df.LAT[π′]; color=:red, onmap=true, size=7, every=3)lim = ax.finallimits[] # the figure fitted to the mapresize!(fig, 600, round(Int, 600* lim.widths[2] / lim.widths[1]) +10)fig
Figure 11: The savings tour of Fig. 10 improved by 2-opt.
Savings alone is well above the Prior, and 2-opt brings the tour to 2.9% above the optimum, a Landmark check: close to the 2,141.21 mi of the best of 5.1’s 100 random starts, from one deterministic start.
Savings constructs a tour of 2,443.41 mi, and 2-opt improves it to 2,169.02 mi, against Lecture 5.1’s estimate of 2,106.45 mi, its multi-start 2,141.21 mi and the optimal 2,107.56 mi.
Computing the pairwise savings in a function of its own, outside the savings procedure, makes it possible to do things to the savings rather than rely on one way of doing them. One use is diversity. The basic savings procedure always takes the savings in strictly decreasing order, so with the standard default it always constructs exactly the same route, and that route is not necessarily the optimal one; most of the time it will not be, which is why 2-opt improvement follows it. It would be nice to have the kind of randomness that picking a random starting point gave the alternating location–allocation algorithm of Lecture 2.3. To diversify the starting points, the pairwise savings are calculated, and then, going through the list, each savings value is moved to the end of the list with a probability of perhaps 5% or 10%. That makes slight changes in exactly how the route is constructed, an easy way, given the time, of getting a diverse set of constructed solutions to improve. Most of the time, though, the unchanged order probably gives the best route, so the change improves things perhaps 20 or 25% of the time: the savings procedure by itself is so good that tweaking it usually does not help, though every once in a while it does. Where a solution is needed in seconds, the order is best left alone; where there are hours of computer time, it is an easy way to let the computer explore more possibilities.
Randomized savings is a meta-heuristic, like the multi-start of Lecture 5.1: it constructs routes by savings from a randomly reordered list, improves them by 2-opt, and repeats, keeping the best. Logjam’s savings computes its list itself, so the implementation includes a savings that is given the list, Logjam’s code with that one change.
Model 1 formulation: Randomized savings
algorithm randsavings;{ input: shipments 1, …, n; cost c(R); probability p; N starts }{ output: best routes found, and their total cost }begin TCᵒ := ∞; S := the pairs with sᵢⱼ > 0, in decreasing order of sᵢⱼ; for k := 1 to N do begin S′ := S with each pair moved to its end with probability p; routes := savings, with S′ in place of S; { construction } improve each route by twoopt; { improvement } if their total cost < TCᵒ then keep them, TCᵒ := that cost; end; return the routes kept, TCᵒ;end;
Model 1 implementation: Randomized savings
# Model: route sequencing, randomized savingsfunctionrandreorder(ijs, p) # each pair moved with prob. p mv =rand(length(ijs[1])) .< preturnTuple([v[.!mv]; v[mv]] for v in ijs)endfunctionsavings_ijs(rteTCh, sh, ijs) # Logjam's savings, list given TC =nothing rte = [[i, i] for i in1:nrow(sh)] inr = [1:nrow(sh);] iˢ, jˢ = ijsfor (i, j) inzip(iˢ, jˢ)if inr[i] != inr[j] inr_src, inr_tgt =length(rte[inr[i]]) <length(rte[inr[j]]) ? (inr[i], inr[j]) : (inr[j], inr[i]) rte′ =copy(rte[inr_tgt]) idx_src =unique(rte[inr_src])for k in idx_src rte′, TC =mincostinsert(k, rte′, rteTCh)isinf(TC) &&breakendif !isinf(TC) rte[inr_tgt] = rte′ inr[idx_src] .= inr_tgt rte[inr_src] = []endendendreturnfilter!(!isempty, rte)endfunctionrandsavings(rteTCh, sh; p =0.1, nruns =30) ijs =pairwisesavings(rteTCh, sh) rteᵒ, TCᵒ =nothing, Inffor k =1:nruns rte =savings_ijs(rteTCh, sh, randreorder(ijs, p)) rte = [twoopt_rte(r, rteTCh)[1] for r in rte] TC =sum(rteTCh.(rte))if TC < TCᵒ rteᵒ, TCᵒ = rte, TCprintln(k, ": ", TCᵒ)endendreturn rteᵒ, TCᵒend
randsavings (generic function with 1 method)
Minimum cost insertion gives different results for different orderings of the shipments, different permutations of the sequence in which they are added to the route, so it too becomes a meta-heuristic, like randomized savings: randomized insertion runs insert and improve from random load sequences and keeps the best.
Model 1 formulation: Randomized insertion
algorithm randinsert;{ input: shipments 1, …, n; cost c(R); N starts }{ output: best route found, and its cost }begin TCᵒ := ∞; for k := 1 to N do begin L := a random permutation of 1, …, n; R, TC := insertimprove(L); if TC < TCᵒ then Rᵒ := R, TCᵒ := TC; end; return Rᵒ, TCᵒ;end;
Determine the least costly single route that carries 30 shipments among locations in North Carolina, each with its own origin and destination, by savings, randomized savings, random routes improved by 2-opt and randomized insertion.
In some cases, everything has to be routed: every shipment goes on one route, and the question is then just the least costly way of doing it. That is route sequencing, Model 1, for all 30 shipments at once. Whether each shipment should be on a route at all, or shipped independently, is a different problem, load formation, the subject of Sec. 4.
Code block 41 reads the 54 locations from the file shmtNC30-xy.csv, of which Code block 22 took seven, enters the origin b and destination e of each of the 30 shipments among them, and computes the road distances between all of the locations:
Fig. 12 draws the 30 shipments, each from its origin to its destination.
Show the code that draws this figure
# Code block 42: the 30 shipments on a mapfunctionbasemap(x, y) # makemap around the points, its borders in gray# close at the sides; tall enough to show the state's borders whole fig, ax =makemap(x, y; xexpand =0.02, yexpand =0.12, doRoadbkgd =false)for p in ax.scene.plots # the state borders p.color, p.linewidth = (ink, 0.45), 1.5endreturn fig, axendfunctionfitmap!(fig, ax) # the figure's height fitted to the map lim = ax.finallimits[]resize!(fig, 600,round(Int, 600* lim.widths[2] / lim.widths[1]) +10)return figendfunctionshmtmap(sh, X) # each shipment, origin to destination x, y = X[:, 1], X[:, 2] used =unique([sh.b; sh.e]) # its locations only fig, ax =basemap(x[used], y[used])for (b, e) inzip(sh.b, sh.e)lines!(ax, x[[b, e]], y[[b, e]]; color = redc, linewidth =0.8)legarrows!(ax, x[[b, e]], y[[b, e]]; color = redc, onmap =true, size =7)endscatter!(ax, x[used], y[used]; color = ink, markersize =4)fitmap!(fig, ax)return fig, axendfunctionmilabel!(ax, what, d) # a distance, at the map's lower left s =commas(round(d, digits =2)) s ="$what: $(rpad(s, findfirst('.', s) +2, '0')) mi"text!(ax, 0.02, 0.03; text = s, space =:relative, color = ink, fontsize =13, font =:bold, align = (:left, :bottom))endfig, ax =shmtmap(sh30, X30)TD30 =sum(rTD30h([k, k]) for k in1:nrow(sh30))milabel!(ax, "Each from origin to destination", TD30)fig
Figure 12: The 30 shipments of Ex. 8 among locations in North Carolina, each from its origin to its destination (red), its direction by its arrow, and the sum of their distances at the lower left.
Code block 43 constructs the routes by savings and improves each by 2-opt, then makes them one route: oneroute keeps the longest and inserts into it, at least cost, each shipment on another route, following each insertion with 2-opt, as insert and improve does:
# Code block 43: savings and 2-opt, then one route for all 30functiononeroute(R, rTCh) # one route: the longest, the rest inserted r = R[argmax(length.(R))]for k insetdiff(reduce(vcat, R), r) # each one not on it, r′ =mincostinsert_rte(k, r, rTCh)[1] # inserted at least cost, r =twoopt_rte(r′, rTCh)[1] # then improved by 2-optendreturn r, rTCh(r)endr30 = [twoopt_rte(r, rTD30h)[1] for r insavings(rTD30h, sh30)]@showlength.(r30) .÷2# shipments per routers30, TC30 =oneroute(r30, rTD30h)TC30
length.(r30) .÷ 2 = [1, 28, 1]
1716.5799667642218
Savings puts 28 of the shipments on one route and leaves shipments 4 and 20, which have no positive saving with any other shipment, on routes of their own; inserted into the long route, they make the one route for all 30 that Fig. 13 draws.
Show the code that draws this figure
# Code block 44: the route on a mapfunctionrtemap(R, sh, X) # the routes, a single-shipment route in red x, y = X[:, 1], X[:, 2] used =unique([sh.b; sh.e]) fig, ax =basemap(x[used], y[used]) # Code block 42for r in R loc, col =rte2loc(r, sh), length(r) >2 ? dcc : redclines!(ax, x[loc], y[loc]; color = col, linewidth =0.8)legarrows!(ax, x[loc], y[loc]; color = col, onmap =true, size =7, every =length(r) >2 ? 3:1)endscatter!(ax, x[used], y[used]; color = ink, markersize =4)fitmap!(fig, ax)return fig, axendfig, ax =rtemap([rs30], sh30, X30)milabel!(ax, "Savings, one route", TC30) # Code block 42fig
Figure 13: The route that savings constructs for the 30 shipments of Ex. 8, improved by 2-opt, with the two shipments it leaves on routes of their own inserted at least cost: one route that carries every shipment (green), each leg’s direction by its arrow, and its distance at the lower left.
Code block 45 runs randomized savings from 30 reorderings of its list, each pair moved to the end with probability 0.1, printing each improvement on the best so far, and then makes the best routes one route, as Code block 43 does:
# Code block 45: randomized savings, 30 starts, then one routeRandom.seed!(1234)rr30, _ =randsavings(rTD30h, sh30; p =0.1, nruns =30)rr30, TCr30 =oneroute(rr30, rTD30h)TCr30
Code block 46 starts instead from 30 random routes, each a random order of the shipments loaded and then unloaded in the same order, and improves each by 2-opt, as the multi-start of Lecture 5.1 does for a tour:
# Code block 46: 2-opt from 30 random routesRandom.seed!(1234)rteᵒ, TCᵒ =nothing, Inffor k =1:30 p =randperm(nrow(sh30)) rk, TCk =twoopt_rte([p; p], rTD30h) # load in order p, then unloadif TCk < TCᵒglobal rteᵒ, TCᵒ = rk, TCkprintln(k, ": ", TCᵒ)endendTCᵒ
Fig. 14 draws the best route that randomized insertion finds, one route that carries all 30 shipments.
Show the code that draws this figure
# Code block 48: the best route of randomized insertion, by rtemapfig, ax =rtemap([ri30], sh30, X30)milabel!(ax, "Randomized insertion, best of 30", TCi30)fig
Figure 14: The best route of 30 randomized insertions for the 30 shipments of Ex. 8, one route that carries every shipment (green), each leg’s direction by its arrow, and its distance at the lower left.
Reordering the list changes the routes little: most of the 30 randomized starts give back the routes of Code block 43 or worse ones, as the telling above expects, and the best is only slightly shorter. On these shipments, with no constraint on a route, the random routes improved by 2-opt, given 30 starts against the one run of savings, do better, 5.8% below savings, as random tours improved by 2-opt did for the tour of Lecture 5.1, and randomized insertion better still, 13.5% below savings, its first start alone shorter than savings and 2-opt. Lecture 5.1 closes on why: with no constraints, the improvement procedure does most of the work, and the construction matters more as constraints are added, as they are in the vehicle routing of Lecture 5.3.
On one route for all 30 shipments, savings and 2-opt travel 1,716.58 mi, the best of 30 randomized savings 1,715.31 mi, the best of 30 random routes improved by 2-opt 1,616.43 mi, and the best of 30 randomized insertions 1,484.07 mi, the least costly route of the four.
Table 4 sets the constructions of route sequencing side by side:
Table 4: The constructions of route sequencing and what distinguishes them, each but Clarke-Wright improved by 2-opt. Clarke-Wright adds a customer only at the beginning or end of a route, never inside it, which keeps it easy to solve by hand; a random route is constructed whole rather than a shipment at a time.
Construction
Needs a depot
Placed in a route
Online or offline
Number of runs
insert and improve
no
anywhere
online
single
Clarke-Wright savings
yes
ends only
offline
single
savings
no
anywhere
offline
single
randomized savings
no
anywhere
offline
multiple
randomized insertion
no
anywhere
offline
multiple
random routes
no
—
offline
multiple
The routes of Secs. 1 to 3 are built once, for the shipments at hand. When the same shipments repeat, periodically, the periodic shipments of Lecture 3.3 carry over to a route, with one difference, its load mixes, the mixes of shipments on board over different parts of the route, which Lecture 5.3 takes up with the truck’s capacity. Combining shipments that each have their own origin and destination into a route by minimizing their total logistics cost is a tactical solution, as opposed to traditional vehicle routing, which minimizes only the distance and the number of vehicles required.
4. Load formation
The basic idea is to handle the case where, for a set of shipments, multiple routes can be formed and some of the shipments can be independent. Even for a private company that owns all the shipments, it needs to be able to look at a situation and determine whether or not each shipment should be part of a consolidated load versus run as an independent shipment. The independent shipment is that of Lecture 3.2, a P2P TL shipment or an LTL shipment, which that lecture introduced as the alternative to a multi-stop consolidated load, with its independent transport charge c_0 of Eq. 16 in Lecture 3.2.
The key idea is that minimum cost insertion will always add a shipment to a route. That is good and bad. But the savings procedure, using the default of not inserting negative savings, typically stops after all the positive savings have been used to create a route or multiple routes. At that point, there can be shipments left. What this means is these shipments may be better off as independent shipments.
The savings procedure creates a set of routes of several shipments, and when it is run, some shipments can be left that are not beneficial to combine with any other shipment. A shipment from somewhere in Wyoming to somewhere in Montana, for example, might have no other shipment within hundreds of miles; there is no way it will be combined with any other, so every saving it has with another shipment is negative, and the savings procedure never includes it. So when the savings procedure finishes, a check is needed that no shipments are left waiting, on no route; any that are become single-shipment routes, a good housekeeping step that accounts for every shipment not on an existing route.
The next thing is that in the savings procedure, once the pairwise savings have been calculated, the shipments that do not appear in any of the positive savings pairs can be identified immediately as those that should be considered for independent shipment. Minimum cost insertion does not have that characteristic, and the cost of each shipment would have to be found as it is added. The sequencing would be dependent, so minimum cost insertion really does not work well for this. This is where the pairwise savings come into play.
Code block 49 defines two functions for that housekeeping step: sh2rte creates a route for each shipment not in the existing routes, the single-shipment route (k, k), and returns those shipments, and rte2idx gives the shipments on a route, its loadings. The routes of a set of shipments are then one vector of routes, each shipment on exactly one of them and a single-shipment route standing for a shipment shipped independently, and Lecture 5.3 keeps this form. The block applies sh2rte to five shipments, 1 and 2 on one route:
# Code block 49: rte2idx and sh2rte# a route's shipments, or those of each route of a vector of routesrte2idx(r::AbstractVector{<:Integer}) = r[isorigin(r)]rte2idx(R::AbstractVector{<:AbstractVector}) =rte2idx.(R)# a single-shipment route (k, k) for each shipment k on no routefunctionsh2rte(idx, R) idx1 =setdiff(idx, rte2idx(reduce(vcat, R; init =Int[])))return [R; [[k, k] for k in idx1]], idx1endR, idx1 =sh2rte(1:5, [[1, 2, 1, 2]])@show idx1 # on no routeR
1
:: restricts an argument to a type, so this definition, a method of rte2idx, applies only when r is a single route: AbstractVector is any one-dimensional array, and {<:Integer} requires its elements to be integers, <: reading “is a subtype of”. It returns the elements of the route that are loadings, its shipments in the order they are loaded.
2
A second method of the same function, for a vector whose elements are themselves vectors, a vector of routes, which {<:AbstractVector} requires. Julia runs the method that matches the type of the argument, the multiple dispatch of Lecture 1.2, so rte2idx of a route gives its shipments, and rte2idx of a vector of routes applies the first method to each route, by the dot, and gives the shipments of each.
Load formation is stated as a model in Model 2. It widens Model 1 from one route to the loads of a set of shipments, each shipment either on one of the routes or shipped independently. Its formulation is the savings procedure of Sec. 3, each route then improved by 2-opt, with the cost of a single-shipment route the shipment’s independent charge, so that the savings are those of Eq. 7, relative to the shipments shipped independently, and a shipment that savings leaves on a route of its own is shipped independently.
minimize: total cost of one route that loads and unloads every shipment of a loadthe routes and of the shipments shipped independently
solve for: (a) shipments shipped independently, and the load of each route; (a)(b) routeof each load, a sequence of stops, the loading and the unloading of each shipmenton it.
subject to:
(a) Leave: each stopof a route is left exactly once, except the last;
(b) Enter: each stopof a route is entered exactly once, except the first;
(c) Single route: the arcs usedby a route form one connected path through all theits stops, not several, the truck carrying at least one shipment along each;
(d) Precedence: each shipmenton a route is loaded before it is unloaded; (e) Independent or consolidated: each shipment is on exactly one route or is shipped independently.
assumptions:
(a) each shipment has its own origin and destination;
(b) costs between locations are given and need not be symmetric;
(c) cost of a route is the sum of the costs of its segments, from the loading of the first shipment to the unloading of the last; (d) one company owns every shipment; (e) each shipment shipped independently costs its independent transport charge; (f) each route’s truck has no capacity limit.
algorithm loadform;{ input: shipments 1, …, n; cost c(R), with c((k, k)) = c₀(k), }{ the independent charge of shipment k }{ output: routes, and the shipments shipped independently }begin routes := the routes of savings with more than one shipment, each then improved by twoopt; I := the shipments on none of the routes; add the route (k, k) for each shipment k in I; return the routes, and I, the shipments shipped independently;end;
Model 2 implementation: Load formation
# Model: load formationfunctionloadform(rteTCh, sh) R = [twoopt_rte(r, rteTCh)[1] for r insavings(rteTCh, sh) if length(r) >2] # multi-shipment routesreturnsh2rte(1:nrow(sh), R) # the others, single-shipment routesend
loadform (generic function with 1 method)
Example 9: Load formation for 30 shipments
Determine which of 30 shipments among the locations of Ex. 8, as one-time shipments of one company, are better shipped independently than on a route, and the charge of the loads formed.
Example 9(a): Independent charges
Determine each shipment’s independent transport charge as a P2P TL shipment.
The 30 shipments of Ex. 8 run all over the state, and savings put nearly all of them on one route. Here the origins and destinations of 30 shipments are paired differently among the same 54 locations: most of the shipments run within the Charlotte area, and the others within the area around Raleigh or the Triad, around Greensboro, but for two in other parts of the state.
A shipment shipped independently goes by itself as a P2P TL shipment, at the $2.00 per loaded mile of Lecture 3.2’s charge_tl, with its minimum charge. A single truckload is charged by its miles alone, so Code block 50 needs only the miles from each shipment’s origin to its destination. The independent charge here is the TL charge alone, not the lesser of the TL and LTL charges that c_0 is in Lecture 3.2: with no capacity limit on a route’s truck, an LTL charge would make a small shipment cheap to ship alone however close it is to the others, and that case, with capacity, is taken up in Lecture 5.3.
Fig. 15 draws the 30 shipments, each shipped independently.
Show the code that draws this figure
# Code block 51: the 30 shipments on a map, by Code block 42's shmtmapshmtmap(shL, X30)[1]
Figure 15: The 30 shipments of Ex. 9, each shipped independently from its origin to its destination (red), its direction by its arrow.
Example 9(b): Shipments on no route
Determine the pairwise savings of the 30 shipments, relative to their independent charges, and the shipments in no pair with a positive saving, which no route of more than one shipment carries.
A route’s charge is one truck’s, at the same $2.00 per loaded mile over the route’s miles, since the truck has no capacity limit; for a route of one shipment that is the shipment’s own independent charge, which the @assert in Code block 52 checks. So the pairwise savings of Eq. 7 on that charge are relative to the shipments shipped independently, c_i being the independent charge of shipment i. Code block 52 lists them with Logjam’s pairwisesavings, showing the five largest, and finds the shipments in no pair with a positive saving:
# Code block 52: route charge, and the pairwise savingsrTCLh(rte) =max(2.00*rteTC(rte, shL, D30), mincharge_tl())@assertall(rTCLh([k, k]) ≈ c₀[k] for k in1:nrow(shL))ijs =pairwisesavings(rTCLh, shL) # positive, largest firstprt(hcat(ijs...)[1:5, :]; cols = ["i", "j", "Saving"], row_title ="Pair") # the five largest@showlength(ijs[3]) # pairs with a positive savingidx1 =setdiff(1:nrow(shL), ijs[1], ijs[2]) # the shipments in none
Shipments 2 and 4 are in no pair with a positive saving, so savings never puts either on a route: they are the candidates for independent shipment.
Example 9(c): The loads
Determine the routes and the shipments shipped independently, and the charge of the loads.
Code block 53 runs load formation, savings on the route charge, each route then improved by 2-opt. Its routes are one vector, in the form of Code block 49, in which each shipment shipped independently is a single-shipment route at its independent charge, and the block prints that vector a route to a line, RL[i] being route i:
# Code block 53: load formation on the 30 shipmentsRL, indL =loadform(rTCLh, shL)@assert indL == idx1 # those in no positive savingfor i ineachindex(RL) # the vector of routesprintln("RL[$i] = [", join(RL[i], ","), "]")endTCload =sum(rTCLh.(RL)) # a single-shipment route at c₀
Shipments 2 and 4 are shipped independently: they are the shipments of Ex. 9(b) in no pair with a positive saving, which the @assert in Code block 53 checks, and savings leaves each on a route of its own. In RL, the routes of more than one shipment that savings constructs come first, routes 1 to 3, and the single-shipment routes that sh2rte adds come after them, routes 4 and 5, for shipments 2 and 4; each shipment appears twice in its route, at its loading and at its unloading.
Shipment 4 is not added to any route, and it is better left as an independent shipment: the additional cost of traveling to its origin, and then of delivering it, means it fits none of the existing routes. That additional cost made adding it not beneficial, so it is better kept as an independent shipment.
Some of the shipments left independent make sense on sight: a shipment outside all of the others is not worth combining with any of them, and keeping it as an independent shipment is more cost effective. That assumes a truck is available for it. A shipment in the middle of nowhere, out in Nome, Alaska, say, would realistically cost a lot even as an independent shipment; within North Carolina a truck can be assumed to show up anywhere, so modeling it as an independent shipment makes sense.
In the vector of routes that loadform returns, a shipment shipped independently is a single-shipment route, so the routing functions treat it as one more route. Fig. 16 draws the loads formed, each route labeled by its place in the vector, and a single-shipment route also by the shipment it carries, in parentheses: route 4 is the single-shipment route of shipment 2, and that shipment is shipped independently.
Show the code that draws this figure
# Code block 54: the loads on a map, by Code block 44's rtemapfunctionrtelabels!(ax, R, at) # each route's label, placed by handfor (i, lon, lat, al) in at one =length(R[i]) ==2# one shipmenttext!(ax, lon, lat; color = one ? redc : dcc, fontsize =13, font =:bold, align = al, justification =:center, text = one ? "Route $i\n(Shmt $(R[i][1]))":"Route $i")endendfig, ax =rtemap(RL, shL, X30)rtelabels!(ax, RL, [(1, -80.62, 35.25, (:left, :center)), (2, -79.33, 36.13, (:left, :center)), (3, -78.70, 35.37, (:center, :top)), (4, -77.54, 35.97, (:center, :bottom)), (5, -81.13, 35.91, (:left, :center))])fig
Figure 16: The loads formed for the 30 shipments of Ex. 9, each route labeled by its place in the vector of routes: three routes of more than one shipment (green) and two single-shipment routes (red), each a shipment shipped independently, its number in parentheses; each leg’s direction by its arrow.
The loads cost $1,232.64, against $1,814.74 with all 30 shipments shipped independently, 32.1% less.
Shipments 2 and 4 are shipped independently, and the other 28 are consolidated on 3 routes, at $1,232.64 in all, against $1,814.74 shipped independently.
But there could be examples online where things would need to be done one at a time. The procedure would look at the differential cost and then compare it to the independent one and make an online decision for each shipment taken in order.
The online case is more where there are different companies owning the shipments, but that then requires cost allocation, which this lecture leaves to the dropdown “Cost allocation for routing” at the end of Sec. 2.
The vehicle routing of Lecture 5.3 is where essentially the same thing done in this section will be repeated, but then in the context of adding constraints on capacity. The difference there is that there will be cases where it is not economic for a shipment that is even in the middle of a cluster of other shipments; it may actually be better off shipped independently just because of its density or other shipment characteristics.
Endnotes
B. B. Sarangi and M. G. Kay, “Shipper-driven consolidation mechanisms for freight transport,” International Journal of Intelligent Transportation Systems Research, 2026, https://doi.org/10.1007/s13177-026-00650-9.↩︎