Constraints turn a single traveling salesman problem (TSP) tour into several routes, the routes of a vehicle routing problem (VRP). When a potential route violates a constraint, e.g., a limit on total route distance, total route time, vehicle capacity, or delivery/pickup time windows, its cost can be set to infinity so that it is never selected.
The TSP of Lecture 5.1 can be thought of as the unconstrained routing problem. With no constraint, a tour such as Lecture 5.1’s through the 100 counties of North Carolina returns to its starting point wherever it starts, like a pilgrimage, and it does not matter how long it takes. In practice, once constraints are put on, a route can no longer travel any distance it likes. Each route may be limited by its distance, which would be one constraint, but more realistically by its total time. Truck drivers, by law or just in practice, do not want to be on the road more than about eight hours if they can help it: they want to be back home every day, and a carrier that can offer routes that leave and return to where they started within eight hours keeps more loyal drivers in a trade with a lot of turnover. One way to keep a driver’s day that short on a long haul is a truck relay. In a relay, a driver takes a trailer only part of the way to its destination and drops it off at a meeting point, which needs to be little more than a parking lot, where another driver hooks it up and takes it on, so that each driver drives one leg and can return home the same day. A small company being set up at the Port of Wilmington, for example, was looking at a relay for product delivered to the port and going on further south. Its drivers would take the trailers from Wilmington as far as Augusta, Georgia, park them there, and be back in Wilmington within an eight-hour day, while drivers coming from Savannah, Atlanta and points south would hook up the trailers and take them on to their destinations. Without the relay, one driver going from Wilmington to Atlanta would need at least an overnight stay, which attracts fewer people to the job. By law a driver can drive up to 11 hours, and with loading and unloading time that makes a day of 13 or 14 hours, so time is an important constraint. Vehicles are also physically limited in capacity when product is actually delivered. The TSP alone is appropriate when no cargo is carried, as in visiting every county seat in North Carolina, where any notion of capacity is irrelevant, but a vehicle with a finite capacity in weight and cube adds another constraint. The final constraint seen quite often is a delivery or pickup time window: a route cannot be planned to arrive whenever, but must arrive within a fairly tight window. Windows matter less in the United States, where land is cheap and a distribution center can have a dedicated loading dock for each store it serves. Europe has always been very constrained in space and has long had very tight delivery windows, and near a distribution center trucks can be seen parked beside the road, next to a field, having arrived early because of uncertainty and waiting an hour or two for a window of perhaps an hour, since there is no space to wait at the distribution center itself. There, time windows are a very important constraint.
The VRP is the TSP with vehicle constraints added. The constraints can be some combination of the following: capacity (weight, cube, etc.); maximum TC (hours of service, HOS: 11 hr max); time windows (with/without delay at customer), where the VRP uses absolute windows that can be checked by simple scanning, while project scheduling uses relative windows solved by shortest path with negative arcs, as in Lecture 4.1; and the maximum number of routes/vehicles, which is hard to enforce. Its criteria are the number of routes/vehicles and the TC (time or distance). A VRP solution can be one time or periodic: a one time (operational) VRP minimizes TC, and a periodic (tactical) VRP minimizes TLC, a route sometimes called a “milk run,” the case of Lecture 5.2.
The VRP is best thought of as the TSP plus additional vehicle constraints, or the TSP as the unconstrained version of the VRP. From a technical point of view the TSP is easy, since any permutation is a feasible tour; because of its additional vehicle constraints, the likelihood that a random permutation is feasible for a VRP approaches zero. So with the VRP most of the work is in constructing a feasible solution, whereas with the TSP most of the work is taking any solution and improving it, the easy and hard construction of Lecture 5.1, Sec. 3. For the TSP, 2-opt does most of the heavy lifting, and the improvement over a random start can be very large; for the VRP, the construction procedure typically gets most of the way, and improvement afterward usually adds no more than about 5%. The two are related problems of different types. The most common constraints are capacity, in weight, in cube or in both, the physical capacity of a truck, and a maximum total cost: with the cost of a route taken as its travel time, the hours of service of Lecture 3.2 can be modeled, under which a driver who has reached the driving limit cannot drive again until enough time off has passed, and drivers are very conscious of reaching it. Time windows are another type of constraint, and they differ from capacity and maximum distance or time, which are geographic: on a map of routes, if the routes do not cross each other, they are probably good with respect to capacity and maximum distance or time, but a time window cannot be seen in the sequence of a route’s stops, since time is not a dimension of the map. With windows, two routes may overlap in a way that would be poor geographically for minimizing distance and still make sense. Windows can be with or without delay at a customer. With a window opening at 3:00, before which the loading dock cannot be reached and within which the load is dropped off by 4:00, a truck arriving at 2:30 either waits 30 minutes, which is feasible with delay, or is infeasible, since without delay it must arrive at 3:00 exactly. No delay can have a physical reason, there being no place for the truck to wait, but it can also be computational: even when the vehicle could wait, enforcing no delay can give better solutions, since it eliminates the possibilities that arrive early and forces a harder look for ones that arrive right at the start of a window. In practice, because of the uncertainty in driving, no window can be hit exactly, and a route planned to arrive at 3:00 would aim to arrive at least 10 or 15 minutes early.
The one constraint that cannot be handled by setting the cost of a violation to infinity is a maximum number of routes. With a limit of four routes, the savings procedure of Lecture 5.2 may create five or six, each feasible with respect to every constraint except the limit on vehicles, because savings starts with a dedicated route for each shipment, 100 routes for 100 shipments, and narrows them down to the number needed to minimize cost; a maximum number of routes would take extra work to incorporate. As for the criteria, what dominates everything else is the number of vehicles: most companies would rather have routes that need four vehicles and a total of 1,000 miles than five vehicles and 800 or 900 miles, since an extra hour of driving is marginal, while another vehicle means another driver. Minimizing distance or time is the secondary criterion, and minimizing the number of vehicles the primary one. Routes and vehicles are not always the same: when routes are time based, as with time windows, one truck can run several of them, a morning route that ends by noon and then an afternoon route, so the number of vehicles is sometimes less than the number of routes, the subject of Sec. 3.
Another objective is minimizing the number of routes. It is not exactly the same as minimizing the number of vehicles, but in between that and the traditional objective, minimizing the total cost of all of the routes. Especially when trying to reduce the number of vehicles, it may be better to increase the number of routes, shorter routes that one vehicle can run one after another without overlap. Also, a problem can have a fixed number of vehicles, and then a set of routes is fine as long as it does not need more vehicles than that.
Most vehicle routing research gives little attention to minimizing the number of vehicles, which, given the many thousands of papers published, is a real gap in what is done in vehicle routing. One possible tool is the ability to estimate route distances: if every vehicle can carry, say, 20 packages and the number of stops is known, the distances can be estimated, and an estimate that at least six vehicles are needed allows a start with six vehicles, trying to reach as many customers as possible at minimum distance with them. The focus is then not on minimizing the number of vehicles, but on first calculating the number to use and then doing the best with those, a different way of approaching routing problems from the procedures of Lecture 5.2, and the subject of Sec. 4. The VRP itself can be a one-time operational problem, a single set of routes, or, just as with estimating the TSP in Lecture 5.1, a tactical problem in which the routes are run on a regular basis, a series of deliveries made to the same customers every week. Such a route is called a milk run: a vehicle might come to a supplier twice a week, say, to pick up product and carry it to a manufacturing facility. It works because the production process is fairly constant, so a standardized set of routes repeated on a regular basis makes sense. To find the best set of milk runs, the total logistics cost has to be considered, both inventory and transport cost, whereas the operational problem looks only at the distance or travel time, because the size of each load has already been determined. This is the routing version of what Lectures 3.2 and 3.3 did for freight transport, first one-time point-to-point shipments and then the periodic case, and the periodic version minimizes total logistics cost in the same way.
Routing from a depot
The VRP from a depot is stated as a model in Model 1. It is the TSP of Model 1 in Lecture 5.1 with its tour divided into routes, each beginning and ending at the depot and each feasible: within the vehicle’s capacity, and within any other constraint a single route must satisfy. What changes from Lecture 5.1’s model is highlighted. Its objective is the cost of the routes alone, not first the number of vehicles, as in the operational VRP of Model 3 in Lecture 1.1; the reason is taken up with Model 3, in Sec. 3.
minimize: total cost of a tour through every nodethe routes
solve for:
(a) tour, a sequence that visits each node exactly once and returns to its starting noderoutes, each a sequence of customers that begins and ends at the depot.
subject to:
(a) Leave: each nodecustomer is left exactly once;
(b) Enter: each nodecustomer is entered exactly once;
(c) Single tour: the arcs used form one connected cycle through all the nodes, not severalRoutes: the arcs used form cycles, each passing through the depot; (d) Feasible routes: each route satisfies every constraint on a single route, such as the vehicle’s capacity, a maximum distance or time, or time windows.
assumptions:
(a) arc costs are given and need not be symmetric;
(b) cost of a tourroute is the sum of the costs of its arcs, including the return to the startgiven by a route cost, the route’s distance or time when it is feasible and infinity when it is not.
The procedures of Lecture 5.2 solve a VRP with no change. Suppose a route being created is feasible with respect to whatever constraints there are, and one more shipment is considered for it. If adding that shipment would violate one of the constraints, the cost of the route, which would otherwise be its time or its distance, is simply set to infinity. When the pairwise savings procedure then tries to combine routes, the infinite cost of the combined route makes its saving negative infinity, and since the savings procedure considers only positive savings, every pair whose combination is infeasible is eliminated at once. The savings procedure uses the minimum cost insertion procedure, and the same holds there: when it tries an insertion that makes a route infeasible, the cost of that route comes back as infinity, and the insertion is never chosen. It is a simple way to account for constraints.
With a single capacity, as in Ex. 1, the route cost of Model 1 is a route’s total cost when the demand on it is within the capacity and infinity otherwise, so that no procedure minimizing cost ever selects it:
=route, a sequence of customers from the depot back to it
TC(r)
=total cost of route r, its distance or its time
q_i
=demand of customer i, in the units of the capacity
K
=capacity of the vehicle, in any unit: tons, cubic feet, cases or seats.
The formulation of Model 1 is then the savings procedure of Lecture 5.2, with the route cost as its c(R), whatever constraints the route cost holds:
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, as in Lecture 5.2, and Ex. 1(c) runs it with this route cost:
Model 1 implementation: Savings
# Model: Vehicle routing from a depot, 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)
A constraint special to a particular problem is added by defining a route total cost function of its own. Its first input is the route, followed by whatever other information the constraint needs, such as a maximum distance. It does not reinvent the wheel: it calls the route total cost function already in use, with whatever constraints that function already incorporates, to get the route’s total cost, and then a single if statement sets the total cost to infinity when it exceeds the maximum distance. Any constraint could replace the maximum distance: if there were a way of identifying a left turn, the cost of any route involving one could be set to infinity. This gives a great deal of flexibility to incorporate almost any type of constraint into a routing problem, and when the savings and improvement procedures are run, they see the infinite total cost and never make a route that violates the added constraint.
Every constraint on a single route enters Model 1 in the same way, by its route cost, and Table 1 lists those of this lecture. A constraint across routes, such as on the number of vehicles, is not a route cost and needs a model of its own.
Table 1: Route costs. A constraint on one route enters Model 1 by its route cost, infinity when the constraint is violated, so savings never selects the route; an objective, or a constraint across routes, needs a model of its own.
Determine the routes of Model 1 from a depot at node 1 to customers at nodes 2 to 6, with the costs of Ex. 5 in Lecture 5.2, customer demands of 8, 5, 4, 7 and 6, and a vehicle capacity of 15: the optimal routes by brute force, and the routes the Clarke-Wright savings procedure constructs, by hand and in Julia.
Example 1(a): By brute force
Determine the routes of least total cost that serve every customer within the capacity, by enumerating every way of dividing the customers among routes.
Node 1 is the depot, and nodes 2 to 6 are customers, with customer demands 8, 5, 4, 7 and 6, respectively, and the vehicle capacity is 15. The symmetric costs are those of Ex. 5 in Lecture 5.2. One listing of the example gives node 3 a demand of 3, where every other statement of it gives 5, which is used here; checking a number against the other statements of its data in this way is a Source check of Lecture 1.2, and the optimal routes are the same with either.
The demands are in units, which can be thought of as tons or cartons or whatever is delivered, and the vehicle can carry at most 15 units. The first step is to take the locations and put each customer’s demand next to it, so that it is easy to see, beside the costs between them.
and Fig. 1 draws the customers with their demands.
Show the code that draws this figure
# Code block 1: the depot, the customers and their demandsXYcw = [0.4630.478; 0.1180.671; 0.8960.273# where nodes 1 to 6 lie0.5420.846; 0.5070.148; 0.8640.738]qcw = [0, 8, 5, 4, 7, 6] # each node's demandfunctioncwnodes!(ax) # the nodes, and each demand away from the depotscatter!(ax, XYcw[2:end, 1], XYcw[2:end, 2]; color =:white, strokecolor = ink, strokewidth =1.5, markersize =22)scatter!(ax, [XYcw[1, 1]], [XYcw[1, 2]]; marker =:rect, color = colorant"#f2d9a0", strokecolor = ink, strokewidth =1.5, markersize =22) # the depottext!(ax, XYcw[:, 1], XYcw[:, 2]; text =string.(1:6), color = ink, fontsize =12, align = (:center, :center))for c in2:6 d = XYcw[c, :] .- XYcw[1, :] # away from the depot u = d ./hypot(d...)text!(ax, XYcw[c, 1] +0.075u[1], XYcw[c, 2] +0.075u[2]; text =string(qcw[c]), color = redc, fontsize =12, font =:bold, align = (:center, :center))endendlet fig =Figure(size = (280, 260), figure_padding =4) ax =Axis(fig[1, 1]; aspect =DataAspect())hidedecorations!(ax); hidespines!(ax)cwnodes!(ax)xlims!(ax, 0.02, 0.99); ylims!(ax, 0.05, 0.94) figend
Figure 1: The depot (tan square) and the five customers of Ex. 1, at the places of Fig. 7 in Lecture 5.2, each with its demand, a given number, in red beside it.
A set partition is a way of dividing a set of n items into non-empty, disjoint subsets whose union is the original set. For example, if the set is \{1, 2, 3\}, the possible partitions are:
The total number of distinct partitions of a set with n elements is given by the n-th Bell number, denoted B_n. For n = 3,B_3 = 5. Each partition of the customers is one way of dividing them among routes, a route for each subset.
With every constraint of Eq. 1 known from the start, the brute force is in the route cost itself: each way of dividing the customers among routes, each route visiting its customers in their least costly order, and the cost of a division in which some route is over capacity infinite. Code block 2 takes the divisions, the partitions of the customers, one at a time, keeps those in which every route fits, and ranks them by their total cost, the objective of Model 1:
# Code block 2: every partition into routes that fit, by brute forceusingCombinatoricsCcw = [ 04048383348# the costs of Ex. 5 of Lecture 5.24008746657548870674147384667070343365417006948754734690]K =15# the vehicle's capacitybesttour(S) =# a route's customers in their best orderminimum((sum(segcost([1; p; 1], Ccw)), [1; p; 1])for p inpermutations(S))BF =DataFrame(Vehicles =Int[], TC =Int[], Routes =String[])for P inpartitions(2:6)all(S ->sum(qcw[S]) <= K, P) ||continue# a route over capacity tours =besttour.(P) rs = ["("*join(r, ",") *")" for r inlast.(tours)] # as textpush!(BF, (length(P), sum(first.(tours)), join(rs, " ")))endsort!(BF, :TC) # least TC first@showlength(partitions(2:6)) # the partitions looked at@shownrow(BF) # those in which every route fitsprt(first(BF, 3))
1
Each order of a route’s customers is paired with its cost, and minimum compares the pairs by cost first, so it returns the least cost together with its order, as Code block 4 of Lecture 5.2 does for routes.
2
partitions(2:6), from the Combinatorics package, generates every partition of customers 2 to 6, one at a time. A partition divides a set into non-empty, disjoint subsets whose union is the set, so each P is one way of dividing the customers among routes, a vector of subsets such as [[2, 5], [3, 4, 6]], a route for each subset.
Of the 52 ways of dividing the five customers among routes, 28 fit the capacity. No single route can serve all five, whose demands total 30, so two vehicles is the fewest, and only one division into two routes fits: customers 2 and 5 on one route and 3, 4 and 6 on the other, each route’s load exactly 15. It is also the least costly division, at 305 against 313 for the next, with 3 vehicles.
By brute force, the optimal routes are (1, 2, 5, 1) and (1, 3, 6, 4, 1), two vehicles at a total cost of 305.
Example 1(b): By hand
Determine the routes Clarke-Wright constructs, pair by pair, refusing any join that would exceed the capacity.
The savings, by Eq. 8 in Lecture 5.2, are those of Table 1 in Lecture 5.2, taken in the same order, from 52 down to 1, by the same three rules of Lecture 5.2, Sec. 3, each now applied only without exceeding the capacity.
As without capacity, 4 and 6 form the first route by rule (1), and 3 and 6 are combined by rule (2), but every time a join is made, the route has to be checked to make sure it is still capacity feasible. The initial route of 4 and 6 has a total of 10, which is less than 15, so it is capacity feasible. When 3 is added, the route is right at 15, so it is essentially done: anything more would exceed the capacity of 15, and with the legs to and from the depot it is a finished route. The pair 3 and 5, the next greatest saving, is eliminated, since 3 is already on the finished route, and likewise 2 and 4, 3 and 4, 2 and 6, and 5 and 6. Not until 2 and 5, the only two left, with a saving of 8, is a route formed, and with nothing left, it is the second route.
Table 2 takes the pairs in that order, the load each join would make in its Load column:
Table 2: Clarke-Wright on the five customers of Ex. 1, with a capacity of 15, pair by pair from the largest saving; the rule is the procedure’s (1) to (3), “refused” a join whose load would exceed the capacity, and “none” a pair already on one route or with a customer inside a route.
Step
Pair
\boldsymbol{s_{ij} = c_{1i} + c_{1j} - c_{ij}}
Load
Rule
Routes
1
(4, 6)
38 + 48 - 34 = 52
4 + 6 = 10
(1) new
(1, 4, 6, 1)
2
(3, 6)
48 + 48 - 47 = 49
10 + 5 = 15
(2) add 3
(1, 4, 6, 3, 1)
3
(3, 5)
48 + 33 - 41 = 40
15 + 7 = 22 > 15
refused
4
(2, 4)
40 + 38 - 46 = 32
15 + 8 = 23 > 15
refused
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
8 + 7 = 15
(1) new
(1, 4, 6, 3, 1),(1, 2, 5, 1)
9
(2, 3)
40 + 48 - 87 = 1
15 + 15 = 30 > 15
refused
10
(4, 5)
38 + 33 - 70 = 1
15 + 15 = 30 > 15
refused
Fig. 2 draws the starting state and the three joins. The two routes are each loaded to exactly 15.
Figure 2: Clarke-Wright on Ex. 1, the depot the tan square and each demand, a given number, in red: (a) the starting state, each customer served out and back (gray, dotted); (b) to (d) a frame per join of Table 2, its step numbered as the table’s row is, the routes in blue and the pair each joins in red.
The routes cost 38 + 34 + 47 + 48 = 167 and 40 + 65 + 33 = 138, a total of 305. Serving each customer out and back would cost 2(40 + 48 + 38 + 33 + 48) = 414, and the three joins saved 52 + 49 + 8 = 109 of it, and 414 - 109 = 305, a Balance check: the savings of the pairs joined account for the whole difference. And 305 is the optimum of Ex. 1(a), a Landmark check: with capacity, as without it in Ex. 5 in Lecture 5.2, Clarke-Wright constructs the optimal routes here.
With a capacity of 15, Clarke-Wright joins customers 4 and 6 and adds 3, refuses every join that would exceed the capacity, and then joins 2 and 5, constructing the routes (1, 4, 6, 3, 1) and (1, 2, 5, 1), at 305, the optimum.
Example 1(c): In Julia
Determine the routes Logjam’s savings procedure constructs with the capacity in the route cost, and compare them and their savings with those of Ex. 1(a) and 1(b).
The functions Lecture 5.2 defined for routes are used here by the same names, and Code block 3 repeats them:
Show the functions of Lecture 5.2
# Code block 3: the route functions of Lecture 5.2rtesegsum(r, x) =# each segment's sum of x on boardcumsum(x[r] .*ifelse.(isorigin(r), 1, -1))[1:end-1]functiontwoopt_rte(r, rTCh) # 2-opt that keeps r a route 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ᵒendrte2idx(r::AbstractVector{<:Integer}) = r[isorigin(r)] # its shipmentsrte2idx(R::AbstractVector{<:AbstractVector}) =rte2idx.(R) # per route
rte2idx (generic function with 2 methods)
Each customer’s demand is a shipment from the depot, so shipment k is delivered to node k + 1, and a truck tr begins and ends each route at the depot, as in Ex. 6(d) in Lecture 5.2. Logjam’s rteTC computes a route’s cost but knows nothing of a capacity, so the capacity is added the way Sec. 1 adds any constraint, by a route cost of one’s own: Code block 4 computes a route’s cost with rteTC, and then sets the cost to infinity when the shipments on the route weigh more than the capacity K. It then constructs the routes by savings and improves each by 2-opt:
# Code block 4: savings, with the capacity in the route costshcw =DataFrame(b =ones(Int, 5), e= [2:6;], q = qcw[2:6])tr = (b =1, e=1)functionrTCcwh(rte) # its cost, or Inf if over capacity TC =rteTC(rte, shcw, Ccw, tr)returnsum(shcw.q[unique(rte)]) <= K ? TC :InfendR1 = [twoopt_rte(r, rTCcwh)[1] for r insavings(rTCcwh, shcw)]@showrTCcwh.(R1)[rte2loc(r, shcw, tr) for r in R1] # each route's location sequence
Each route’s location sequence starts at the depot once for each shipment loaded there, so the two routes visit nodes 5 and 2, and nodes 3, 6 and 4, the routes of Ex. 1(a) and 1(b). Code block 5 lists the pairwise savings that savings takes its merges in order of, each shipment written as the node it is delivered to:
# Code block 5: the pairwise savings, largest first, as nodesijs =pairwisesavings(rTCcwh, shcw)prt(hcat(ijs[1] .+1, ijs[2] .+1, ijs[3]); cols = ["i", "j", "Saving"], row_title ="Pair")
The savings and their order are those of Table 2, and the routes, at 138 and 167, those of the hand working and the brute force, a Triangulate check of the three. Logjam’s savings is not Clarke-Wright: it can insert a customer anywhere in a route, by minimum cost insertion, where Clarke-Wright joins only at a route’s ends; on these five customers the two arrive at the same routes. Table 3 sets the three methods side by side.
Table 3: The three methods of Ex. 1 on the same five customers and capacity.
Method
Construction
Vehicles
Total cost
Brute force, Ex. 1(a)
every partition, best order of each route
2
305
Clarke-Wright, Ex. 1(b)
joins at route ends only, by hand
2
305
Logjam’s savings, Ex. 1(c)
minimum cost insertion anywhere
2
305
Logjam’s savings, with the capacity in its route cost, constructs the routes (1, 5, 2, 1) and (1, 3, 6, 4, 1) at a total of 305, the routes of Ex. 1(a) and 1(b), the first in reverse.
A vehicle can have more than one capacity, and a route can have a limit of its own. With both, the route cost of Model 1 is:
=maximum total cost of a route, a distance or a time.
Savings takes it as its c(R) as it takes Eq. 1, and nothing else in Model 1 changes.
Example 2: Thirty NC customers
Determine the routes of Model 1 from a depot to 30 customers in North Carolina: (a) with no constraint, a single tour; (b) with a truck’s capacity in weight and in cube; (c) with the capacity and a maximum distance of 600 mi on each route, by a route cost of one’s own; and (d) with the same maximum by the truck’s own limit.
Example 2(a): No constraint
Determine the tour that savings and 2-opt construct from the depot through all 30 customers, and how it compares with the optimal tour.
The 30 shipments are those of Ex. 8 in Lecture 5.2, each with its own origin and destination.
To turn them into a TSP kind of problem, a depot is added: the ending location of shipment 1 is used as the depot for the problem, and the 30 shipments then have a total of 31 location points, the depot and the beginning points of the 30 shipments. That is the data set, with great circle distances as the distances.
Code block 6 reads the locations and the shipments, takes the ending location of shipment 1 as the depot and the beginning location of each shipment as a customer, and computes their road distances, great circle distances times the circuity factor 1.2 of Ex. 8 in Lecture 5.2; each customer’s delivery is then a shipment from the depot, and a truck tr begins and ends each route there. It prints the first five of the shipments: each is from the depot, b, to its customer, e, both numbered among the 31 points of X and D, with its weight q, in tons, and its density s, in lb/ft³:
# Code block 6: the depot and the 30 customers, and their distancesxy = CSV.read("data/shmtNC30-xy.csv", DataFrame) # the 54 locationssh0 = CSV.read("data/shmtNC30-sh.csv", DataFrame) # the 30 shipmentse1 = sh0.e[1] # shipment 1's destinationX =Matrix(xy[[e1; sh0.b], [:x, :y]]) # the depot, then customersD =dists(X, X, :mi) *1.2# road miles, circuity 1.2n =nrow(sh0) # 30 customerssh =DataFrame(b =ones(Int, n), e= [2:n+1;]) # a delivery to eachtr = (b =1, e=1) # each route from the depotprt(first(hcat(sh, sh0[:, [:q, :s]]), 5)) # the first 5 of 30
b e q s
──────────────────────
1 1 2 0.2603 1.17
2 1 3 0.6243 5.46
3 1 4 0.8902 15.23
4 1 5 0.5616 5.71
5 1 6 0.7178 13.82
# Code block 7: the depot and the customers on a mapfunctionbasemap(x, y; roads =false) # makemap around the points, its# borders in gray, and its interstates faded behind them if roads;# 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 = roads)for p in ax.scene.plots # the state borders, drawn opaque;to_color(p.color[]).alpha <1&&continue# the roads are faded p.color, p.linewidth = (ink, 0.45), 1.5endreturn fig, axendrtecols = [bluec, dcc, colorant"#c26a00", colorant"#7b3294", redc, colorant"#8c564b", colorant"#d6439a", colorant"#0f8f9e"]rtecol(k) = rtecols[mod1(k, length(rtecols))] # route k's colorfunctionrtelabels!(ax, R, sh, X, tr, lab) # each route's number at the# centroid of its stops, in its color; lab = (align, offset), one of# each a route, moves each clear of every line (placed by hand) n =length(R) al, off =something(lab, (fill((:center, :center), n),fill((0, 0), n))) # unplaced: centered c = [let loc =filter(!=(tr.b), rte2loc(r, sh, tr)) # not the depot (sum(X[loc, 1]) /length(loc), sum(X[loc, 2]) /length(loc))end for r in R]returntext!(ax, first.(c), last.(c); text =string.(1:n), color =rtecol.(1:n), font =:bold, fontsize =13, align = al, offset = off)endfunctionfitmap!(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 figendfunctionmilabel!(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"returntext!(ax, 0.02, 0.03; text = s, space =:relative, color = ink, fontsize =13, font =:bold, align = (:left, :bottom))endfunctiondepot!(ax, X) # the depot, a tan square over everythingreturnscatter!(ax, [X[1, 1]], [X[1, 2]]; marker =:rect, color = colorant"#f2d9a0", strokecolor = ink, strokewidth =1.5, markersize =13)endfunctionvrpmap(R, sh, X, tr; lab =nothing) # each route from the depot x, y = X[:, 1], X[:, 2] # and back, in its color fig, ax =basemap(x, y)for (k, r) inenumerate(R) loc =rte2loc(r, sh, tr)lines!(ax, x[loc], y[loc]; color =rtecol(k), linewidth =1.2)legarrows!(ax, x[loc], y[loc]; color =rtecol(k), onmap =true, size =7, every =2)endscatter!(ax, x[2:end], y[2:end]; color = ink, markersize =4)depot!(ax, X)fitmap!(fig, ax) tp =length(R) >1 ? rtelabels!(ax, R, sh, X, tr, lab) :nothingreturn fig, ax, tp # tp: the routes' numbersendfig, ax =basemap(X[:, 1], X[:, 2]; roads =true)scatter!(ax, X[2:end, 1], X[2:end, 2]; color = ink, markersize =5)depot!(ax, X)fitmap!(fig, ax)
Figure 3: The depot (tan square) and the 30 customers of Ex. 2 in North Carolina, the interstates faded behind them.
The shipments now make a proper TSP kind of data set, in which every shipment starts at the depot. It is peddling, because every shipment is loaded at the depot and then delivered to its point, and the only reason to go back to the depot is the truck itself: after it delivers the last product to the last customer, it travels empty back. Collecting would be the opposite, with the 1s in the ending locations: the truck would travel empty to the first customer and then collect all the way to the last. Which of the two locations is the depot distinguishes peddling from collecting. The data also give each shipment’s density, its value and its annual demand, so the same data set can be used for many different things, such as finding the minimum total logistics cost; for the classic vehicle routing problem, all that is used is the density and, when there is a capacity, the quantity to be shipped, the amount shipped, say, tomorrow, where the annual demand is what is expected over the whole year. First the problem is solved as a TSP, an unconstrained tour with a cyclic route, constructing the route by savings and improving it by 2-opt. The route vector has a length of 60, because each of the 30 shipments has a pickup and a delivery.
Code block 8 constructs the tour as Lecture 5.2 constructed routes, by savings, and improves it by 2-opt:
# Code block 8: savings, then 2-opt, with no constraintrTDh(rte) =rteTC(rte, sh, D, tr)r1 =twoopt_rte(savings(rTDh, sh)[1], rTDh)[1]@showlength(r1) # a pickup and a delivery for each shipmentTD1 =rTDh(r1)
length(r1) = 60
1143.4092909506198
With no constraint, the tour is a TSP tour through the depot and the 30 customers, so its distance can be judged against the optimal tour, which the formulation of Model 1 in Lecture 5.1 finds; Code block 9 repeats Lecture 5.1’s functions for it, and Code block 10 solves it, and computes the cost of the other extreme, every customer served out and back on a route of its own:
Show the functions of Lecture 5.1
# Code block 9: the TSP formulation of Lecture 5.1usingJuMP, HiGHSfunctionsubtours(succ) # the cycles of a successor vector S, seen =Vector{Vector{Int}}(), falses(length(succ))for k ∈eachindex(succ) seen[k] &&continue Sₖ, i =Int[], kwhile !seen[i] # follow the arcs back to k seen[i] =truepush!(Sₖ, i) i = succ[i]endpush!(S, Sₖ)endreturn SendfunctionTSP(c)size(c, 1) ==size(c, 2) ||# assumption (a): each pair's costerror("arc costs must be a square matrix") V =1:size(c, 1) model =Model(HiGHS.Optimizer)@variable(model, x[i ∈ V, j ∈ V; i ≠ j], Bin) # no arc i to i@objective(model, Min,sum(c[i, j] * x[i, j] for i ∈ V, j ∈ V if i ≠ j))@constraint(model, leave[i ∈ V],sum(x[i, j] for j ∈ V if j ≠ i) ==1) # (a)@constraint(model, enter[j ∈ V],sum(x[i, j] for i ∈ V if i ≠ j) ==1) # (b)set_silent(model)set_attribute(model, "mip_rel_gap", 0.0) rounds = []whiletrueoptimize!(model)termination_status(model) == JuMP.OPTIMAL ||error(termination_status(model)) succ = [findfirst(j -> j ≠ i &&value(x[i, j]) >0.5, V) for i ∈ V] # the node after each node S =subtours(succ)push!(rounds, (TC =objective_value(model), S = S))iflength(S) ==1# a single tour: donereturn (TC =objective_value(model), tour = [S[1]; S[1][1]], rounds = rounds)endfor Sₖ ∈ S # (c), for each subtour found@constraint(model,sum(x[i, j] for i ∈ Sₖ, j ∈ Sₖ if i ≠ j) ≤length(Sₖ) -1, base_name ="singletour")endendend
TSP (generic function with 1 method)
# Code block 10: the optimal tour, and every customer out and backTDᵒ =TSP(D).TC@show TDᵒ # the optimal tour@showsum(rTDh([k, k]) for k in1:n) # every customer out and backTD1 / TDᵒ -1# the tour, above the optimum
TDᵒ = 1131.6048332354517
sum((rTDh([k, k]) for k = 1:n)) = 5444.342353684332
0.010431607720706948
The tour of 1,143.41 mi is 1.0% above the optimal tour, a Bounds check of Lecture 1.2: any routes that serve every customer cost at least the optimal tour, and at most the routes out and back. Fig. 4 draws the tour.
Show the code that draws this figure
# Code block 11: the tour on a mapfig, ax =vrpmap([r1], sh, X, tr) # Code block 7milabel!(ax, "Savings and 2-opt, no constraint", TD1)fig
Figure 4: The tour from the depot (tan square) through the 30 customers that savings and 2-opt construct with no constraint (blue), each leg’s direction by its arrow, and its distance at the lower left.
With no constraint, savings and 2-opt construct a single tour of 1,143.41 mi through all 30 customers, against the optimal tour of 1,131.6 mi.
Example 2(b): Capacity
Determine the routes with a truck that carries at most 25 tons and 2,750 ft³, first by a route cost of one’s own and then by a route cost that reads the truck’s capacity, and each route’s weight and cube.
Each customer’s shipment has a weight q, in tons, and a density s, in lb/ft³, in the data, and the truck’s capacity is added to tr, as Lecture 3.2 writes it. In Eq. 2 the truck has m = 2 capacities, its weight capacity K_{wt} of 25 tons and its cube capacity K_{cu} of 2,750 ft³, and a customer’s demands in their units are its shipment’s weight q and its cube 2000q/s. Logjam’s rteTC, though, does not read a capacity: Code block 12 adds the two to the shipments and the truck, and finds the tour of Ex. 2(a) over the cube capacity, while rteTC still returns its distance as its cost:
# Code block 12: Logjam's rteTC does not read a truck's capacitysh.q, sh.s = sh0.q, sh0.s # each shipment's weight, densitytr = (b =1, e=1, Kwt =25, Kcu =2750)cu =2000sh.q ./ sh.s # each shipment's cube, ft³@showsum(sh.q[rte2idx(r1)]) # the tour's weight, t@showsum(cu[rte2idx(r1)]) # and cube: more than 2,750rteTC(r1, sh, D, tr) # a cost all the same
With a weight capacity of 25 tons, the sum of the weights of a route’s shipments is checked against the truck’s capacity, and if it is less than or equal to it, the route is weight feasible. Doing a similar thing for q/s, the shipment’s weight over its density, times 2,000 pounds per ton, gives the route’s total cube, and checking it against the cube capacity tells whether the route is cube feasible. The route cost then returns the distance if the route is both weight and cube feasible, and otherwise infinity. Applying the savings procedure gives two routes, and each route’s distance, weight and cube can then be looked at; for these shipments, routes typically cube out before they weigh out, which is the most typical scenario. The neat thing is that the route cost can be defined however is wanted, to include whatever kind of constraints, and they carry over into the procedure: it is a flexible tool. Time windows would be the same: if the scan of a particular route found it infeasible, the route cost would return infinity, and the routing procedure would never create that route.
Code block 13 is the route cost of one’s own, which computes a route’s cost by rteTC and returns infinity unless the route’s shipments are within both capacities; savings and 2-opt then use it unchanged:
# Code block 13: capacity in a route cost of one's ownfunctionrTDh(rte) rTD =rteTC(rte, sh, D, tr) idxsh =unique(rte) wtfeas =sum(sh.q[idxsh]) <= tr.Kwt cufeas =sum(2000sh.q[idxsh] ./ sh.s[idxsh]) <= tr.Kcureturn wtfeas && cufeas ? rTD :Infend@showrTDh(r1) # the tour: over capacityR2 = [twoopt_rte(r, rTDh)[1] for r insavings(rTDh, sh)]TD2 =rTDh.(R2)
1
A route exactly at the capacity is feasible: a route is infeasible only when its load exceeds the capacity.
Code block 14 tabulates each route’s distance, weight and cube:
# Code block 14: each route's distance, weight and cubeWt = [sum(sh.q[rte2idx(r)]) for r in R2]Cube = [sum(cu[rte2idx(r)]) for r in R2]prt(DataFrame(TD = TD2, Wt = Wt, Cube = Cube))
Both routes are much nearer the cube capacity than the weight capacity: the first route carries 8.81 of the 25 tons and 2,253.85 of the 2,750 ft³.
With the constraint’s code in view, the same capacities can be read from the truck itself by a route cost that knows them, rteTC_vrp, which implements the route cost of Eq. 2. It takes the arguments of Logjam’s rteTC; for each segment of a route on which a different set of shipments is on board, it checks the weight and cube of those shipments against tr.Kwt and tr.Kcu; it checks the route’s total cost against a maximum, tr.maxTC; and it scans the route’s time windows, the subject of Sec. 2. Besides the cost, it returns an exit flag, 1 for a feasible route and a negative number naming the constraint an infeasible one violates (−1 not a single route, −2 weight, −3 cube, −4 maximum total cost, −5 a time window), and a table of the route’s stops:
Show the route cost rteTC_vrp
# Code block 15: rteTC_vrp, a route's cost, exit flag and schedule, with# capacity, loading and unloading, a maximum cost and time windowsfunctionrte2ldmx(rte) # the shipments on board at each load mix isL, on, ld =isorigin(rte), Int[], Vector{Int}[]for i in1:length(rte)-1 isL[i] ? push!(on, rte[i]) :filter!(!=(rte[i]), on) isL[i] && !isL[i+1] &&push!(ld, copy(on)) # a load mixendreturn ldendfunctionrteTC_vrp(rte::AbstractVector{<:Integer}, sh, C, tr = (;))has(f) =hasproperty(sh, f) # a column of sh?col(f, v) =has(f) ? float.(sh[rte, f]) :fill(v, length(rte)) isL, istr =isorigin(rte), haskey(tr, :b) # truck's b and e? loc =rte2loc(rte, sh, istr ? tr : (b = [], e= [])) Xflg =1if istr && tr.b == tr.e# back at the truck's location early: k =filter(!=(0), diff(loc[2:end-1] .== tr.b)) # two routes (length(k) >2||length(k) ==2&& k != [-1, 1]) && (Xflg =-1)endif Xflg >0&&has(:q) # each load mix'sfor ld inrte2ldmx(rte) # weight and cubeifhaskey(tr, :Kwt) &&sum(sh.q[ld]) > tr.Kwt Xflg =-2; breakelseifhaskey(tr, :Kcu) &&2000sum(sh.q[ld] ./ sh.s[ld]) > tr.Kcu +0.01sqrt(eps()) # a rounding tolerance Xflg =-3; breakendendend Xflg <0&&returnInf, Xflg, DataFrame() t = [k ==1|| loc[k] == loc[k-1] ? zero(eltype(C)) : C[loc[k-1], loc[k]] for k ineachindex(loc)] # same place: 0 tLU =ifelse.(isL, col(:tL, 0.0), col(:tU, 0.0)) # load, unload istr && (tLU = [0; tLU; 0]) TC =foldl(+, t) +foldl(+, tLU) # added in order, left to righthaskey(tr, :maxTC) && TC > tr.maxTC &&returnInf, -4, DataFrame() R = istr ? [0; rte; 0] : rte tw = (:tbmin, :tbmax, :temin, :temax)if !any(f ->has(f) ||haskey(tr, f), tw) out =DataFrame(Rte = R, Loc = loc, Cost = t) # no windows (has(:tL) ||has(:tU)) && (out.LU = tLU)return TC, Xflg, outend lo =ifelse.(isL, col(:tbmin, -Inf), col(:temin, -Inf)) # windows hi =ifelse.(isL, col(:tbmax, Inf), col(:temax, Inf))if istr # the truck's, also at stops at its b and its e lo = [get(tr, :tbmin, -Inf); lo; get(tr, :temin, -Inf)] hi = [get(tr, :tbmax, Inf); hi; get(tr, :temax, Inf)] c = [1; findall(diff(loc) .!=0) .+1] # where location changes n =length(loc)for (ix, j) in ((2:c[2]-1, 1), (c[end]:n-1, n)) # stops at b, e lo[ix] =replace(lo[ix], -Inf=> lo[j]) hi[ix] =replace(hi[ix], Inf=> hi[j])endend TC, _, _, s =scanTW(t, tLU, lo, hi) # Sec. 2's scan, its cisinf(TC) &&returnInf, -5, DataFrame()isnan(TC) && (TC =sum(t) +sum(tLU)) # no window at all# the waits, from the schedule, none below 0 from rounding w =max.(0, [0; s[2:end] - s[1:end-1] - tLU[1:end-1] - t[2:end]]) out =DataFrame(Rte = R, Loc = loc, Cost = t, Arrive = [0; s[2:end] - w[2:end]], Wait = w, TWmin = lo, Start = s, LU = tLU, Depart = s + tLU, TWmax = hi, Total = t + w + tLU)return TC, Xflg, outendfunctionrteTC_vrp(R::AbstractVector{<:AbstractVector}, sh, C, tr = (;)) v = [rteTC_vrp(r, sh, C, tr) for r in R] # each route of Rreturnfirst.(v), getindex.(v, 2), last.(v)end
rteTC_vrp (generic function with 4 methods)
Code block 16 uses it as the route cost, with the capacities read from tr:
# Code block 16: the same, by the route cost that reads themrTDh(rte) =rteTC_vrp(rte, sh, D, tr)[1]@showrteTC_vrp(r1, sh, D, tr)[1:2] # the tour: Inf, -3, cube exceededR2b = [twoopt_rte(r, rTDh)[1] for r insavings(rTDh, sh)]R2b == R2 # the routes of Code block 13
(rteTC_vrp(r1, sh, D, tr))[1:2] = (Inf, -3)
true
The two route costs give the same routes, a Triangulate check: the raw code and the built-in implement the same constraint. Fig. 5 draws the routes.
Show the code that draws this figure
# Code block 17: the routes on a mapfig, ax =vrpmap(R2, sh, X, tr; # Code block 7 lab = ([(:center, :center), (:left, :center)], [(55, -60), (5, 0)])) # numbers clear of linesmilabel!(ax, "Capacity, $(length(R2)) routes", sum(TD2))fig
Figure 5: The routes from the depot (tan square) that savings and 2-opt construct with the truck’s capacity of 25 tons and 2,750 ft³, each in its own color and numbered near the center of its stops, each leg’s direction by its arrow, and their total distance at the lower left.
With the truck’s capacity, savings and 2-opt construct 2 routes of 1,166.62 mi in total, the same by the route cost of one’s own and by rteTC_vrp; the tour of Ex. 2(a) exceeds the cube capacity.
Example 2(c): Maximum distance by a route cost of one’s own
Determine the routes when, besides the capacity, no route may exceed 600 mi, by a route cost of one’s own around the route cost of Ex. 2(b).
The first constraint added to the unconstrained problem is a maximum route distance, and it is added by just redefining the route total cost. The route cost already defined calls the route total cost; to add a constraint, the new one calls it again, gets its value, and uses Julia’s ternary operator: if the value is within the maximum distance of 600 mi, it is returned, and if it exceeds 600, infinity is returned. That one change feeds into all of the pairwise savings and all of the procedures, and the infinity keeps them from creating any route that exceeds 600 mi: a route of three shipments might be combined at a total of 325 mi, but adding a fourth shipment in the middle could exceed 600, and the route cost then returns infinity. Passed to the savings procedure, the new route cost gives, almost by magic, routes that satisfy the constraint, without any change to the savings procedure itself: several routes instead of a single one. It is typical for most of the routes to be cut off at the constraint, and for the last to be a catch-all. Savings returns a vector of routes, a single route vector for the TSP but in general several for the VRP, while 2-opt is designed to operate on a single route, so 2-opt is called for each route in an array comprehension. Another type of improvement procedure, one not implemented here or used very much, would take the shipments of the route with the most slack, perhaps all of them, and put them in the other routes, eliminating a route; 2-opt only works on a single route, so it never reduces the number of routes, only the distance of each.
Code block 18 keeps the route cost of Ex. 2(b), with its capacity, as rTDh0, and wraps it in a route cost of one’s own that returns infinity for a route over the maximum distance:
# Code block 18: a maximum distance, by a route cost of one's ownrTDh0(rte) =rteTC_vrp(rte, sh, D, tr)[1] # capacity, as Ex. 2(b)maxdist =600functionrTDh(rte) # my VRP constraint TC =rTDh0(rte)return TC > maxdist ? Inf: TCendR3 = [twoopt_rte(r, rTDh)[1] for r insavings(rTDh, sh)]TD3 =rTDh.(R3)Wt = [sum(sh.q[rte2idx(r)]) for r in R3]Cube = [sum(cu[rte2idx(r)]) for r in R3]prt(DataFrame(TD = TD3, Wt = Wt, Cube = Cube))
There are now three routes, and the weights and cubes of each are nowhere close to their maximum amounts: the maximum distance is the binding constraint that forced the creation of a third route. The first route is cut off at 598.06 mi, just short of the 600 mi limit, and the last is the catch-all, at 175.14 mi; Fig. 6 draws the routes.
Show the code that draws this figure
# Code block 19: the routes on a mapfig, ax =vrpmap(R3, sh, X, tr; # Code block 7 lab = ([(:left, :center), (:left, :center), (:left, :bottom)], [(5, 0), (5, 0), (4, 4)])) # clear of linesmilabel!(ax, "Capacity and 600 mi, $(length(R3)) routes", sum(TD3))fig
Figure 6: The routes from the depot (tan square) with the truck’s capacity and a maximum of 600 mi on each route, each in its own color and numbered near the center of its stops, each leg’s direction by its arrow, and their total distance at the lower left.
With the capacity and a maximum of 600 mi, savings and 2-opt construct 3 routes of 1,299.73 mi in total, one more route than with the capacity alone.
Example 2(d): Maximum distance by the truck’s own limit
Determine the routes of Ex. 2(c) with the maximum distance given to the route cost as the truck’s own limit.
rteTC_vrp reads a maximum total cost for a route from tr.maxTC, so Code block 20 adds it to the truck and uses the route cost directly:
# Code block 20: the same limit, built intr = (tr..., maxTC =600)rTDh(rte) =rteTC_vrp(rte, sh, D, tr)[1]R4 = [twoopt_rte(r, rTDh)[1] for r insavings(rTDh, sh)]@show R4 == R3 # the routes of Code block 18r13 = [rte2idx(R4[1]); rte2idx(R4[3])] # routes 1 and 3's shipmentsrteTC_vrp([r13; r13], sh, D, tr)[1:2] # on one route
R4 == R3 = true
(Inf, -4)
The routes are those of Ex. 2(c), a Triangulate check of the wrapper against the built-in limit. The last line puts the shipments of the first and third routes on one route, within the capacity, and rteTC_vrp refuses it with the flag −4: its distance exceeds the maximum.
With the maximum distance read from the truck, rteTC_vrp gives the same 3 routes as the route cost of one’s own, at 1,299.73 mi.
Pickup and delivery
The more general situation than routing from a single depot is a route of pickups and deliveries. The one difficulty with such a route is what is on board. The first route of Fig. 7 picks up shipments 1, 2 and 3 and then drops off 3, 2 and 1, and the numbers beneath each segment are the shipments on board over it: after the first pickup just shipment 1, after the second 1 and 2, then all three, and then back to two and to one. There is just one peak, where all three shipments are on board, which is called a single load mix. The second route picks up 1 and 2, drops off 1, leaving 2 on board, picks up 3, leaving 2 and 3, and then has just 3 on board: there are two places with different mixes of loads, a first and a second load mix. With two load mixes, capacity cannot be looked at for all of the shipments as one aggregate. A different mix of shipments is on board over each, so the truck could be at capacity on one load mix and, because the shipments differ, at capacity a second time on the other, where all of the shipments together would be well past its capacity. So what has to be determined is which load mix reaches the maximum capacity, since the two are unlikely to be at capacity at the same time.
Show the code that draws this figure
# Code block 21: the load mixes of two routeslet# set in the lecture math's serif, as the insertion positions are fig =Figure(size = (380, 250), figure_padding =4, fonts = (; regular = Makie.MathTeXEngine.texfont())) ax =Axis(fig[1, 1]; aspect =DataAspect())hidedecorations!(ax); hidespines!(ax) dy =0.62# a row's height# a route's stops along a rule, beneath each segment the shipments on# board, and a box around each load mix: a loading followed by an# unloading, where what is on board peaksfunctionloadmix!(r, y0, cap) n, ld =length(r), isorigin(r)text!(ax, 2.0.* (0:n-1), fill(y0, n); text =string.(r), fontsize =16, color = ink, align = (:center, :center))lines!(ax, [-0.4, 2n -1.6], [y0 -0.45, y0 -0.45]; color = ink, linewidth =1)onboard(k) =sort(setdiff(r[1:k][ld[1:k]], r[1:k][.!ld[1:k]])) depth =maximum(length(onboard(k)) for k in1:n-1)for k in1:n-1# the segment after stop k s =onboard(k) ys = y0 -0.95.- dy .* (0:length(s)-1)text!(ax, fill(2k -1.0, length(s)), ys; text =string.(s), fontsize =16, color = ink, align = (:center, :center))if ld[k] && !ld[k+1] # a load mix, boxedpoly!(ax, Rect(2k -1.42, ys[end] -0.36, 0.84, y0 -0.2- ys[end] +0.36); color =:transparent, strokecolor = bluec, strokewidth =1.5)endend yb = y0 -0.95- dy * (depth -1) -0.5text!(ax, n -1.0, yb; text = cap, fontsize =15, color = ink, align = (:center, :top)) # its subcaptionreturn ybend yb =loadmix!([1, 2, 3, 3, 2, 1], 0.0, "(a) A single load mix") yb =loadmix!([1, 2, 1, 3, 2, 3], yb -1.3,"(b) A first and a second load mix")xlims!(ax, -0.6, 10.6); ylims!(ax, yb -0.6, 0.45) figend
Figure 7: Load mixes. Beneath each segment of a route are the shipments on board, and a box marks each load mix, where a loading is followed by an unloading: (a) the route (1, 2, 3, 3, 2, 1) has a single load mix; (b) the route (1, 2, 1, 3, 2, 3) has a first and a second load mix.
What is on board changes only at a stop: a loading adds its shipment and an unloading removes it, as rtesegsum of Code block 3, from Lecture 5.2, adds them up. So the load on board over each segment of a route is a running sum:
=size of shipment i, in the units of the capacity.
A load mix is what is on board at a peak of w, a segment k whose stop k is a loading and stop k + 1 an unloading. A shipment is on board over segment k when it was loaded at or before stop k and is unloaded after it, so the load mix at a peak k is the set of those shipments:
\ell_k = \{\, i : k_i^{+} \le k < k_i^{-} \,\}
\tag{4}
where
k_i^{+}
=stop of route r at which shipment i is loaded, where \delta = +1
k_i^{-}
=stop at which shipment i is unloaded, where \delta = -1.
Each shipment appears twice in a route, loaded where it first appears and unloaded where it appears again, and that gives each stop its sign \delta_k. For the second route of Fig. 7, r = (1, 2, 1, 3, 2, 3), with each q_i = 1,Eq. 3 counts the shipments listed beneath each segment of the figure, each w_k the one before it plus \delta_k, starting from 0:
A peak is a +1 followed by a -1, at segments 2 and 4. In Eq. 4, k_i^{+} and k_i^{-} are the two stops at which shipment i appears in r, and the condition reads: loaded at or before stop k,k_i^{+} \le k, and not yet unloaded, k < k_i^{-}. At each peak, each shipment is checked:
At the first peak, shipment 3 is not yet loaded, and at the second, shipment 1 has already been unloaded, so \ell_2 = \{1, 2\} and \ell_4 = \{2, 3\}, the two boxes of Fig. 7 (b). The first route, (1, 2, 3, 3, 2, 1), has w = (1, 2, 3, 2, 1) and one peak, at segment 3, with all three shipments on board: \ell_3 = \{1, 2, 3\}. The load of a load mix is \sum_{i \in \ell_k} q_i = w_k, the load on board at its peak. Since w rises only at a loading and falls only at an unloading, its largest values are at its peaks, so a route is within a capacity over every segment if and only if it is within it at each load mix.
A route from a depot, as in Ex. 1 and Ex. 2, loads every shipment before it unloads any, so it has a single load mix, and checking the weight and cube of all of a route’s shipments, as the route cost of one’s own of Ex. 2(b) does, is checking its one load mix. On a pickup and delivery route the two checks differ: rteTC_vrp checks each load mix, its function rte2ldmx listing the shipments on board at each peak.
The pickup and delivery problem, Model 2, is the load formation of Model 2 in Lecture 5.2 with a route cost, each shipment with its own origin and destination, and Model 1 is its special case in which every shipment is loaded at the depot. What changes from Lecture 5.2’s model is highlighted:
minimize: total cost of the routes and of the shipments shipped independently
solve for:
(a) shipments shipped independently, and the load of each route;
(b) route of each load, a sequence of stops, the loading and the unloading of each shipment on it.
subject to:
(a) Leave: each stop of a route is left exactly once, except the last;
(b) Enter: each stop of a route is entered exactly once, except the first;
(c) Single route: the arcs used by a route form one connected path through all its stops, not several, the truck carrying at least one shipment along each;
(d) Precedence: each shipment on a route is loaded before it is unloaded;
(e) Independent or consolidated: each shipment is on exactly one route or is shipped independently; (f) Feasible routes: each route satisfies every constraint on a single route, such as the vehicle’s capacity over each load mix.
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 lastgiven by a route cost, the route’s distance or time from the loading of its first shipment to the unloading of its last when it is feasible, and infinity when it is not;
(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.
With a capacity on each load mix, as in Ex. 3, the route cost of Model 2 is a route’s total cost when the shipments on board over each load mix are within the capacity and infinity otherwise:
c(r) = \begin{cases}
TC(r), & \text{if } \displaystyle\sum_{i \in \ell} q_i \le K \text{ for each load mix } \ell \text{ of } r \\[6pt]
\infty, & \text{otherwise}
\end{cases}
\tag{5}
where
r
=route, its loadings and unloadings, as in Lecture 5.2
\ell
=load mix of r,Eq. 4, the shipments on board at a peak of Eq. 3 (Fig. 7).
The other symbols are those of Eq. 3 and Eq. 1. The formulation of Model 2 is the savings procedure of Model 1, each route then improved by 2-opt, with the route cost as its c(R) and the cost of a route of one shipment its independent charge, so that a shipment that savings leaves on a route of its own is shipped independently; Ex. 3 finds its loads both by brute force and by savings.
The savings procedure is the one normally used for the pickup and delivery problem. The key idea is that the savings are calculated relative to two shipments being shipped independently: what is saved if they are consolidated together. It tends to work better than minimum cost insertion when there are lots of constraints; as was seen in Lecture 5.2, for the unconstrained problem, randomized insertion worked better than randomized savings.
Example 3: Southeast shipments with capacity
Determine the loads of Model 2 for the three shipments of Ex. 2 in Lecture 5.2, from Raleigh to Athens, from Asheville to Jacksonville and from Savannah to Gainesville, with a truck that carries at most 25 tons: (a) by hand, which routes of the three fit when each shipment weighs 10 tons; (b) by brute force and by savings, the least costly loads; and (c) the same when the shipments weigh 10, 14 and 12 tons.
The cities, their road distances and the three shipments are those of Ex. 2 in Lecture 5.2; each shipment now has a weight q, 10 tons, and the truck tr3 a weight capacity, 25 tons. Code block 22 enters them, with names of their own, so that the data of Ex. 2 stay as they are:
# Code block 22: the six cities and three shipments of Lecture 5.2's Ex. 2City = ["Raleigh", "Athens", "Asheville", "Jacksonville", "Savannah","Gainesville"]St = [:NC, :GA, :NC, :FL, :GA, :FL]loc3 = [loc2lonlat(c; state = s) for (c, s) inzip(City, St)]x3, y3 = [r.LON for r in loc3], [r.LAT for r in loc3]D3 =dists(hcat(x3, y3), hcat(x3, y3), :mi) *1.2# road milessh3 =DataFrame(b = [1, 3, 5], e= [2, 4, 6], q = [10, 10, 10])tr3 = (Kwt =25,) # a truck of 25 tons
# Code block 23: the three shipments on a mapfunctionldlabel(i, sh) # the shipments loaded (L) and unloaded (U) at i 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)"endsh2ln(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, as in Lecture 5.2citylabel(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)]fig, ax =makemap(x3, y3; xexpand=0.3)resize!(fig, 600, 520)lines!(ax, sh2ln(sh3, x3), sh2ln(sh3, y3), color=:red)for (b, e) inzip(sh3.b, sh3.e) # each shipment's directionlegarrows!(ax, x3[[b, e]], y3[[b, e]]; color=:red, onmap=true)endscatter!(ax, x3, y3)text!(ax, x3, y3, text=citylabel.(eachindex(City), Ref(sh3)); align = lalign, offset = loff)fig
Figure 8: The three shipments of Ex. 3, each of 10 tons, from its origin to its destination (red), and each city labeled with the shipments loaded (L) and unloaded (U) there, as in Lecture 5.2.
Example 3(a): By hand
Determine whether each route of Fig. 7 fits the truck, load mix by load mix, when each shipment weighs 10 tons.
Each route of the three shipments carries all three at some point, and they weigh 30 tons together, so a check of the whole route’s weight refuses every route. By Eq. 3, with q_i the weight of shipment i, the weights on board over the five segments of the two routes of Fig. 7 are found by adding each stop’s weight at a loading and subtracting it at an unloading:
The first route has one peak, at segment 3, where shipment 3 is loaded and then unloaded, and so one load mix, \{1, 2, 3\}; the second has two, at segments 2 and 4, \{1, 2\} and \{2, 3\}. Load mix by load mix, as in Eq. 5, with the capacity K the truck’s weight capacity K_{wt}, the two routes are:
The single load mix of the first route is over the capacity, and the route is infeasible; each of the two load mixes of the second fits, and the route is feasible, although the three shipments it carries weigh 30 tons in all.
At 10 tons each, the route (1, 2, 3, 3, 2, 1), with one load mix of 30 tons, does not fit a truck of 25 tons, and the route (1, 2, 1, 3, 2, 3), with two load mixes of 20 tons, does.
Example 3(b): By brute force and by savings
Determine how many of the 60 routes of the three shipments fit load mix by load mix, and the least costly loads, by brute force and by savings.
Code block 24 takes the 60 routes of Ex. 1 in Lecture 5.2 one at a time, listing them as Code block 4 of Lecture 5.2 does (its notes 2 and 3 explain how), and computes the cost of each with rteTC_vrp, which returns infinity for a route with a load mix over the capacity; it gives the weights on board of Ex. 3(a)’s second route by rtesegsum, counts the routes that fit load mix by load mix, by the route cost and again by the peaks of Eq. 3, and those that would fit by the whole route’s weight, and finds the least costly route:
# Code block 24: all 60 routes, each load mix within 25 tonsv = [1, 1, 2, 2, 3, 3]rtes = (r for r ∈multiset_permutations(v, 6) # the 60 routesifall(>(0), rtesegsum(r, ones(3))))rTD3h(r) =rteTC_vrp(r, sh3, D3, tr3)[1] # Inf if a load mix is over@showrte2ldmx([1, 2, 3, 3, 2, 1]) # its one load mix@showrte2ldmx([1, 2, 1, 3, 2, 3]) # its two load mixes@showrtesegsum([1, 2, 1, 3, 2, 3], sh3.q) # on board, by segment@showcount(isfinite(rTD3h(r)) for r ∈ rtes) # each load mix fits@showcount(maximum(rtesegsum(r, sh3.q)) <= tr3.Kwt for r ∈ rtes)@showcount(sum(sh3.q[unique(r)]) <= tr3.Kwt for r ∈ rtes) # all fitTC3ᵒ, r3ᵒ =minimum((rTD3h(r), r) for r ∈ rtes)@show TC3ᵒ # the cheapest router3ᵒ
The loads of Model 2 need not put all three shipments on one route: two can share a route with the third shipped independently, or all three can be shipped independently. Code block 25 computes the cost of those loads too, a shipment shipped independently at the cost of its own distance, as in Ex. 2 in Lecture 5.2. That is the cost of its route of one shipment, so savings run with rTD3h, each route then improved by 2-opt, is the formulation of Model 2 as it stands, and Code block 25 runs it and compares its loads with the brute force’s:
# Code block 25: two on a route and one alone, all alone, and savingsindep(k) =rTD3h([k, k]) # shipment k shipped alonefunctionpairplusone(i, j) # i and j on a route, k alone k =only(setdiff(1:3, [i, j])) rs = (r for r ∈multiset_permutations([i, i, j, j], 4)ifall(>(0), rtesegsum(r, ones(3))))returnminimum(rTD3h(r) for r ∈ rs) +indep(k)end@showsum(indep(k) for k in1:3) # all three aloneTC3p = [pairplusone(i, j) for (i, j) in [(1, 2), (1, 3), (2, 3)]]@show TC3p # 1 and 2, 1 and 3, 2 and 3R3 =[twoopt_rte(r, rTD3h)[1] for r insavings(rTD3h, sh3)] # savings@show R3R3 == [r3ᵒ] # the brute force's loads?
sum((indep(k) for k = 1:3)) = 1006.178484226333
TC3p = [942.8252075426478, 1371.3537094235853, 884.692087837174]
R3 = [[1, 2, 1, 3, 2, 3]]
true
24 of the 60 routes fit load mix by load mix, the same by the route cost and by the peaks, where a check of the whole route’s weight would refuse all 60, and the least costly of them is the route (1, 2, 1, 3, 2, 3) of Ex. 3(a), at 849.11 mi, the route Lecture 5.2 found optimal without a capacity, a Landmark check: at 10 tons each, the capacity changes nothing. It is less than any load with a shipment shipped independently, and savings constructs the same route, a Triangulate check: two procedures, one answer.
At 10 tons each, 24 of the 60 routes fit, and the least costly loads, by brute force and by savings, are all three shipments on the route (1, 2, 1, 3, 2, 3), at 849.11 mi.
Example 3(c): Heavier shipments
Determine the least costly loads when the shipments weigh 10, 14 and 12 tons.
Code block 26 gives the shipments their new weights and repeats the two searches and savings:
# Code block 26: shipments of 10, 14 and 12 tonssh3.q = [10, 14, 12]@showcount(isfinite(rTD3h(r)) for r ∈ rtes) # the routes that fitTC3ᵒ, r3ᵒ =minimum((rTD3h(r), r) for r ∈ rtes)@show TC3ᵒ # the cheapest route@show r3ᵒTC3p = [pairplusone(i, j) for (i, j) in [(1, 2), (1, 3), (2, 3)]]@show TC3p # 1 and 2, 1 and 3, 2 and 3R3 = [twoopt_rte(r, rTD3h)[1] for r insavings(rTD3h, sh3)] # savings@show R3sum(rTD3h.(R3)) ≈ TC3p[1] # the brute force's cost?
The route (1, 2, 1, 3, 2, 3) no longer fits: by Eq. 3 its weights on board are 10, 24, 14, 26 and 12 tons, so its first load mix weighs 10 + 14 = 24 \le 25 tons, but its second, 14 + 12 = 26 > 25. Of the routes that still fit, the least costly is (1, 2, 2, 3, 3, 1), at 1,416.94 mi, which keeps shipments 2 and 3 apart, but shipments 1 and 2 on a route with shipment 3 shipped independently cost less, 942.83 mi, and less than all three shipped independently. Which shipments go on a route and which are shipped independently is the load formation of Lecture 5.2, Sec. 4, and here the capacity of each load mix is what determines it. Savings constructs the same loads, shipment 3 left on a route of its own and so shipped independently. Fig. 9 draws those loads.
Show the code that draws this figure
# Code block 27: the loads on a map# the routes of shipments 1 and 2, and the least costly of themrs12 = (r for r ∈multiset_permutations([1, 1, 2, 2], 4)ifall(>(0), rtesegsum(r, ones(3))))r12 =argmin(rTD3h, rs12)fig, ax =makemap(x3, y3; xexpand=0.3)resize!(fig, 600, 520)loc12 =rte2loc(r12, sh3)lines!(ax, x3[loc12], y3[loc12], color=dcc)legarrows!(ax, x3[loc12], y3[loc12]; color=dcc, onmap=true, at=0.4)lines!(ax, x3[[5, 6]], y3[[5, 6]], color=redc) # shipment 3, alonelegarrows!(ax, x3[[5, 6]], y3[[5, 6]]; color=redc, onmap=true)scatter!(ax, x3, y3)text!(ax, x3, y3, text=citylabel.(eachindex(City), Ref(sh3)); align = lalign, offset = loff) # placed as in Code block 23text!(ax, 0.98, 0.03; space =:relative, color = ink, fontsize =13, font =:bold, align = (:right, :bottom), # over the ocean text ="1 and 2 on a route, 3 alone:\n"*"$(commas(round(TC3p[1], digits =2))) mi")fig
Figure 9: The least costly loads of Ex. 3 at 10, 14 and 12 tons: shipments 1 and 2 on one route (green) and shipment 3 shipped independently (red), each leg’s direction by its arrow, and their total distance at the lower right.
At 10, 14 and 12 tons, the least costly loads, by brute force and by savings, put shipments 1 and 2 on a route and ship shipment 3 independently, at 942.83 mi, against 1,416.94 mi for the best route of all three.
2. Time windows
Why a route would have time windows can be seen in a dial-a-ride service, in which a van picks people up at their homes, typically elderly or disabled people who cannot drive, and takes them to places such as a doctor’s appointment. To be efficient, the van is not dedicated to one person’s transport but runs a multi-stop route that combines pickups with drop-offs, and each pickup has a guaranteed time window, usually about two hours or perhaps an hour, within which the van arrives.
One consideration with time windows is whether a vehicle may arrive early. If the window opens at 1 p.m. and the vehicle arrives at noon, it is usually still feasible for it to wait an hour, but in some cases there can be no waiting: the window has to be hit, and arriving early is another constraint. The windows of the VRP are absolute, a time of day such as 1 p.m., and a time-window constraint of this kind can be checked by a simple scanning procedure, so including it is not computationally difficult. Project scheduling also has time windows, but they are relative: once a task is complete, the next has to be done within one hour, perhaps because of some chemical process, and when the first will be done is not known in advance. A relative window cannot be checked by scanning; it has to be solved by a shortest path procedure with negative arcs, where Dijkstra’s procedure does not work and the Floyd-Warshall procedure is used. Lecture 4.1, Sec. 3 introduced the relative windows, as the negative arcs of project scheduling that Dijkstra’s procedure cannot handle; the windows of vehicle routing are absolute instead, and a scan of the route checks them.
With time windows, the route cost of Model 1 is a route’s least time, its travel, unloading and waiting, and infinity when no schedule meets every window. It is found by scanning the route. The forward scan, a, starts at the opening of the window of the route’s first stop, the depot, and finds the earliest each stop can be served, waiting where a window has not yet opened; the last stop’s gives the earliest the route can finish. The reverse scan, b, goes back from that finish and finds the latest each stop can be served, the first stop’s giving the latest the route can start. The forward scan again, c, from that latest start, is the schedule, and the route’s least time is its earliest finish less its latest start.
Code block 28 does the three scans as scanTW, and rteTC_vrp of Ex. 2(b) calls it for any route with time windows:
# Code block 28: scanTW, the three scans of a route with time windowsfunctionscanTW(t, u, ℓ, h) # time-window scans: route time, a, b, c n =length(t) a =zeros(n); a[1] = ℓ[1] # forward: the earliest startfor k in2:n a[k] =max(a[k-1] + u[k-1] + t[k], ℓ[k]) # wait if early a[k] + u[k] > h[k] &&returnInf, a, a, a # its window closedend b =zeros(n); b[n] = a[n] # reverse: the latest startfor k in n-1:-1:1 b[k] =min(b[k+1] - t[k+1] - u[k], h[k] - u[k])end c =zeros(n); c[1] = b[1] # forward again: the schedulefor k in2:n c[k] =max(c[k-1] + u[k-1] + t[k], ℓ[k]) # waits made lateendreturn a[n] + u[n] - b[1], a, b, c # earliest finish less startend
scanTW (generic function with 1 method)
Example 4: Route with time windows
Determine the least time in which the route from the depot at node 1 to customers 2, 3 and 4, in that order, can be run within every time window, with the travel times and windows of Table 4, and when it should leave the depot, by hand and in Julia.
The route’s windows are in hours of the day, [0, 24] h; the loading/unloading time is 0; the vehicle’s capacity is \infty; and its lower bound, LB = 5 h, is the sum of its travel times. Its data are in Table 4.
Table 4: The route of Ex. 4, its stops in order: the travel time into each and its window.
Stop
Travel time in (h)
Window (h)
1, depot, departure
[6, 18]
2
1
[8, 11]
3
2
[12, 14]
4
1
[15, 18]
1, depot, return
1
[18, 24]
Example 4(a): By hand
Determine the earliest finish, the latest start and the schedule by the three scans.
The time-window constraint takes a little more work than capacity, but computationally it is not very difficult. The route has a depot at node 1 and three customers, with travel times of 1, 2, 1 and 1 hours on its legs. There is assumed to be no time for loading or unloading the vehicle, which could be added but would only make the example more complicated, and the vehicle’s capacity is infinite, so there is no limit on it. The constraints are the time windows. Each customer has one: delivery to customer 2 can occur any time between 8 and 11, to customer 3 between 12 and 2 p.m., and to customer 4 between 3 and 6 p.m. The route is already set up to be close to feasible: if one window came before another in the direction the route travels, it would be known immediately to be violated. The depot itself has two windows, a departure window, any time between 6 a.m. and 6 p.m., and a return window, between 6 p.m. and midnight. In practice the two do not overlap because of the distribution center itself: its loading docks are set up for receiving or for shipping out product, and there are many practical reasons not to mix the two. The question is the total time the route requires, and the objective is to minimize it. Its lower bound is 5 hours: with zero loading and unloading time, the lower bound is just the sum of the travel times, and even with no time windows the route would take at least 5 hours. With the windows, the question is the minimum time in which every customer can be served without violating a window, which may require the vehicle to pause when it arrives early until the window starts, as a truck waiting outside the customer’s location: arriving at 7 a.m. for a window that opens at 8 means waiting an hour. The route is solved by a series of scans. The first is a forward scan, which starts at the beginning of the departure window, 6 a.m., to give the best chance of realizing the minimum time. The vehicle arrives at customer 2 at 7 a.m. and, because of its window, waits one hour; with zero unloading time, at 8 it heads for customer 3, which takes two hours, arriving at 10 a.m., where the window starts at 12, so it waits two hours. At 12 it travels an hour to customer 4, arriving at 1 p.m., and waits two hours until 3; one hour back to the depot, it arrives at 4 and has to wait until 6 p.m. Were there a loading or unloading time, at a customer the unloading usually has to be within the window, while at the distribution center, for a peddling route, the loading can usually be done before the window starts, and unloading likewise outside it. What the first forward scan establishes is that the earliest the route can finish is 6 p.m., and that is not going to change. Starting at 6 a.m. and finishing at 6 p.m., though, the route spends twelve hours on the road, which is not as short as it could be. Since it has to finish by 6 p.m., the latest it can start is found by going in the backward direction. Reversing from 18, one hour back to customer 4 gives 17, within its window, so there is no waiting at that customer, which already saves time. One hour back to customer 3 gives 16, against a window that closes at 14, a two-hour wait; two hours back to customer 2 gives 12, against its close of 11, a one-hour delay; and one hour back to the depot gives 10. That is the latest start.
Fig. 10 draws the three scans, and Table 5 gives the equation of each step:
Figure 10: Ex. 4 by hand, a frame per scan, the depot the tan square with its departure window above it and its return window below: (a) the route as given; (b) the forward scan, from the earliest departure, each stop’s start after the time it is reached where the two differ; (c) the reverse scan, from the earliest finish, each stop’s latest start after the time it is reached going back; (d) the forward scan again, from the latest start, the waits as late as the windows allow. The arrow in the middle of each scan is its direction. Given values, the travel times and windows, are red; determined ones are blue.
Table 5: Ex. 4 by hand, the three scans with no unloading time (u_k = 0): the forward scan from the top, the reverse scan from the bottom, and the forward scan again from the top.
The 8 hours of Eq. 6 are the 5 of travel, the lower bound, and the 3 of waiting the windows force, an hour at customer 4 and two at the depot in the last scan: a Balance check of Lecture 1.2, the travel and the waits accounting for the whole route. Read scan by scan:
The first forward scan takes 18 - 6 = 12 hours, with 7 hours of wait, so 18 is the minimum finish time. The backward scan takes 18 - 10 = 8 hours, with 3 of wait, so 10 is the maximum start time, and 18 - 10 = 8 is the minimum total time for the route. The second forward scan has the same time and waits, but with the waits shifted to the end of the route, which is better in case something changes during route delivery.
The forward and reverse scans give exactly the information wanted: the route needs 3 hours of delay, and in the reverse scan’s schedule the delay is one hour at customer 2 and two hours at customer 3, with none at customer 4. Suppose the two scans are coded for a trucking company whose scheduler has been routing a dozen trucks by hand on a big piece of paper in a conference room, and with two or three dozen trucks can no longer keep track of them, its windows more complex than these, some customers served every Monday and others every second Monday. Given feasible, optimal routes, a scheduler can answer that they are really good, but that no truck would ever be routed like that. Nothing is wrong with the time: no route can do better than 8 hours. A third scan, a second forward scan, fixes it. The forward scan gave the earliest finish, 18; starting from it, the reverse scan gave the latest start, 10; the last forward scan, starting at 10, moves the delays from the beginning of the route to its end. The truck reaches customer 2 at 11 and customer 3 at 13 with no delay, and has only one hour of delay at the last customer and two hours back at the depot. Delays are better late, because something can happen, a truck breaking down, say; delays held for later are a safety stock of delay, and with them as late as possible, the windows are still satisfied if anything goes wrong. Taking them early is like eating all of a trip’s food in the first hour and hoping to arrive on time, where it is better to keep a sandwich or two in the backpack in case of a delay. Practicality is as important as optimality: a perfectly deterministic world does not map to the real world, where things happen, and showing a solution to someone who actually does the work, to see whether it passes the smell test as feasible, is how such knowledge is found.
The route takes at least 8 hours, 5 of travel and 3 of waiting: it leaves the depot at 10 and returns at 18, waiting an hour at customer 4 and two hours at the depot.
Example 4(b): In Julia
Determine the same scans with scanTW, and the route’s schedule with rteTC_vrp.
Code block 29 gives scanTW the route’s data, in the order of Table 4, with no unloading time:
# Code block 29: the route of Ex. 4, its three scanst = [0, 1, 2, 1, 1] # travel to each stop: DC, 2, 3, 4, DClo = [6, 8, 12, 15, 18] # each stop's window openshi = [18, 11, 14, 18, 24] # and closesTC, a, b, c =scanTW(t, zeros(length(t)), lo, hi) # no unloadingprt(hcat(a, b, c); cols = ["a: forward", "b: reverse", "c: again"], row_title ="Stop")TC
Code block 30 computes the cost of the same route with rteTC_vrp: a time matrix T5 with the travel times of the route’s legs, a shipment from the depot to each customer with its delivery window, temin to temax, and a truck tr5 that leaves the depot within tbmin to tbmax and returns within temin to temax:
TC5 is 8.0 and Xflg5 is 1, a feasible route. The Start column where the truck moves, rows 1 and 5 to 8, is the c row of Code block 29, and the Total column sums to 8: the hand scans, scanTW and the route cost agree, a Triangulate check of Lecture 1.2.
In code, the same route needs a time matrix, just like a distance matrix, since it deals with time instead of distance: a 4 × 4 matrix with the known travel times put in. The shipments all begin at location 1, the depot, and end at locations 2, 3 and 4. The unloading time is 0, and the windows are given as the earliest and the latest time for delivery to each customer, 8, 12 and 15 and 11, 14 and 18. The truck carries over the truck of freight transport, but instead of its rate it uses fields for its beginning and end points, here both the depot; they carry over to multi-stop routes, in which a truck can start at any location and end at any other. A customer has just one window, an ending window, since it wants its delivery during a window, but the depot has both a beginning and an ending window, 6 to 18 and 18 to 24. The route is fixed in advance: shipments 1, 2 and 3 are dropped off in turn. Since ending windows are given for the customers, the example is peddling: every item is on the truck when it leaves the depot, and the three are dropped off at the customers. For collecting, the truck would leave the depot empty, pick up the three items and return them to the depot, and beginning windows would be given, since the pickup begins a shipment at a particular time. Whether the beginning or the ending windows are given shows whether a route is peddling or collecting. The route cost is called with the route, the shipment and truck information and the time matrix, which it uses to determine the total time of the route. Its second output is a flag giving the feasibility of the route, and its third a table of everything that happens on the route. Its route vector has a 0 at both ends for the depot, and in its location vector every shipment starts at location 1, the depot, and is delivered, which again shows a peddling route; for collecting, the end of the location vector would be all 1s. With no unloading time, a vehicle departs as soon as it arrives unless a window delays it. The route cost implements the forward scan, the reverse scan and then the forward scan again, putting the delays as far toward the end of the route as possible: an hour at the last customer and two hours back at the depot, the same as by hand. The route’s total time is the sum of the last column, 8, the total cost the route cost returns. The route cost does all the heavy lifting, and this is for just one route.
Of the six orders in which the three customers could be served, Code block 31 computes the cost of each, one at a time:
# Code block 31: every delivery order, one at a timeP6 =DataFrame(order =String[], TC =Float64[], Xflg =Int[])for p inpermutations(1:3) # deliver to the stops in order p TCp, Xflgp =rteTC_vrp([p; p], sh5, T5, tr5)[1:2]push!(P6, (join(p, ", "), TCp, Xflgp))endprt(P6)
Only the order of the route is feasible, and every other is refused for a window (flag −5). The data of Ex. 4 give travel times only on the legs of its route, but no others are needed: its three windows do not overlap, so no route can satisfy them in any other order, whatever the other legs take.
In Julia, as by hand, the route takes 8 hours, leaving at 10 and returning at 18, its waits an hour at customer 4 and two at the depot; it is the only order of the three customers that satisfies every window.
Example 5: Thirty NC customers with time windows
Determine the routes of Model 1 from the depot of Ex. 2 to its 30 customers, the first 15 with a delivery window from 7 a.m. to 5 p.m. and the other 15 from 1 p.m. to 11 p.m., at 50 mph with five minutes of positioning at each stop and 30 minutes of unloading a ton, within the windows, the truck’s capacity and the hours of service of Lecture 3.2, and the schedule of each.
Example 5(a): Windows, unloading and capacity
Determine the routes and schedules that the route cost with the windows, unloading times and capacity gives, and whether each is within the hours of service.
The depot and the customers are those drawn in Fig. 3.
The same can be done for the 30 shipments of Ex. 2. A travel time matrix is defined just as for the route of Ex. 4: the distance matrix, in miles, is converted to time at an average travel speed, and a positioning time is added at each stop, the time for the truck to get into position to make a pickup or delivery, beyond the time it is moving, here five minutes. The unloading time at each customer is proportional to the size of its shipment, 30 minutes a ton, so that it recognizes the amount delivered. The first 15 customers have daytime delivery, any time between 7 a.m. and 5 p.m., and the other 15 evening delivery, any time between 1 p.m. and 11 p.m. The truck itself has no time windows, so there is no restriction on when it can leave the depot or return to it; it has only its beginning and end points and its capacity. The routing is peddling, with deliveries only at the customers, and the same code as before solves it, the shipment and truck information encoded in the route cost. The schedule of each route gives when its vehicle departs the depot, when it arrives at each customer, any waiting time, and so on. Of particular interest in judging the quality of a routing solution is the waiting time, and here no route requires its vehicle to wait for a window, because the windows are very wide, basically the daylight hours against the evening; with narrow windows of an hour or two, positive waiting would likely be required, and quite different solutions would result.
Code block 32 converts Ex. 2’s distances to travel times at 50 mph with five minutes at each stop, gives each customer an unloading time of 30 minutes a ton and its window, and constructs and improves the routes with the truck’s capacity, as in Ex. 2(b):
# Code block 32: windows, unloading and capacity, from the depotT = D/50.+5/60# 50 mph, and 5 min at each stopsh.tU = sh.q *30/60# 30 min a ton to unloadsh.temin = [fill(7, 15); fill(13, 15)] # daytime, then eveningsh.temax = [fill(17, 15); fill(23, 15)]tr = (b =1, e=1, Kwt =25, Kcu =2750)rTTh(rte) =rteTC_vrp(rte, sh, T, tr)[1]R6 = [twoopt_rte(r, rTTh)[1] for r insavings(rTTh, sh)]TT6 =rTTh.(R6)
The first route leaves the depot after noon, its customers all but one with evening windows, and the depot’s rows carry no window, the truck having none. Code block 34 sums each route’s day from its schedule:
# Code block 34: each route's day, from its scheduleprt(DataFrame(Start = [o.Start[1] for o in out6], # leaves the depot Finish = [o.Start[end] for o in out6], # back at the depot Drive = [sum(o.Cost) for o in out6], # 5 min a stop Unload = [sum(o.LU) for o in out6], Wait = [sum(o.Wait) for o in out6], TT = TT6))
No route waits at all, and each route’s time is its driving and its unloading. Fig. 11 draws the routes.
Show the code that draws this figure
# Code block 35: the routes on a mapfunctiontwmap(R, TT; lab =nothing) # depot routes, each its color and x, y = X[:, 1], X[:, 2] # number, hours at the left col =rtecol.(eachindex(R)) # Code block 7 fig, ax =basemap(x, y) # Code block 7for (i, r) inenumerate(R) # each route, depot to depot loc =rte2loc(r, sh, tr)lines!(ax, x[loc], y[loc]; color = col[i], linewidth =1.2)legarrows!(ax, x[loc], y[loc]; color = col[i], onmap =true, size =8)end# the daytime customers filled, the evening ones openscatter!(ax, x[2:16], y[2:16]; color = ink, markersize =6)scatter!(ax, x[17:31], y[17:31]; color =:white, strokecolor = ink, strokewidth =1.2, markersize =6)depot!(ax, X) # Code block 7fitmap!(fig, ax)rtelabels!(ax, R, sh, X, tr, lab) # Code block 7hrs(v) ="$(round(v, digits =2)) h"for (i, h) inenumerate(TT)text!(ax, 0.02, 0.03+0.065* (length(TT) - i +1); text ="Route $i: "*hrs(h), space =:relative, color = col[i], fontsize =13, align = (:left, :bottom))endtext!(ax, 0.02, 0.03; text ="Total: "*hrs(sum(TT)), space =:relative, color = ink, font =:bold, fontsize =13, align = (:left, :bottom))return figendtwmap(R6, TT6; lab = ([(:left, :center), (:left, :center), (:right, :center)], [(5, 0), (5, 0), (-5, 0)])) # clear of lines
Figure 11: The routes of Ex. 5(a) from the depot (tan square), each in its own color and numbered near the center of its stops, its direction by its arrows; the customers with daytime windows filled and those with evening windows open; each route’s time and the total at the lower left.
A published solution of the same example has four routes, at 41.98 hours; Code block 36 computes their cost with the same route cost:
Its four routes take 42.0 hours on the distances of Ex. 2, against the published 41.98, the small difference coming from distances computed with a slightly different radius of the earth; against them, the 40.95 hours here take one route fewer. Both are feasible, and the difference is the construction, not the cost, a Triangulate check of the route cost. The first of those routes is also on duty for 15.61 hours.
Routes 2 and 3 here are on duty for 16.83 and 17.91 hours, and drive 13.56 and 13.45 of them, the driving here including the five minutes of positioning at each stop. The hours-of-service rule of Lecture 3.2 allows up to 11 hours of driving within a 14-hour on-duty window, a truck driver’s limit on the time of a route, so neither route can be driven by one driver in a day.
With the windows, unloading times and capacity, savings and 2-opt construct 3 routes taking 40.95 hours, none of them waiting, but two of them break the hours of service.
Example 5(b): Hours of service by a route cost of one’s own
Determine the routes and schedules when, besides the windows, unloading and capacity, each route is within the hours of service.
The route cost has no hours-of-service limit, so it is added by a route cost of one’s own, as in Sec. 1: Code block 37 calls rteTC_vrp, reads the driving time from its schedule, and sets the cost to infinity when the driving exceeds 11 hours or the route’s time on duty exceeds 14:
# Code block 37: hours of service, a wrapper that reads the schedulefunctionrTTh(rte) # hours of service (Lecture 3.2) TT, _, out =rteTC_vrp(rte, sh, T, tr)isinf(TT) &&returnInf drive =sum(out.Cost) # time at the wheelreturn drive >11|| TT >14 ? Inf: TT # 11 h in a 14 h dayendR6h = [twoopt_rte(r, rTTh)[1] for r insavings(rTTh, sh)]TT6h =rTTh.(R6h)
1
out.Cost is the travel time into each stop, and the travel times T of Code block 32 carry the five minutes of positioning at each stop, so the 11 hours of driving include that positioning as well as the time the wheels are turning.
Every route now drives at most 10.78 hours and is on duty at most 13.45; Fig. 12 draws the routes.
Show the code that draws this figure
# Code block 38: the routes within the hours of service, on a maptwmap(R6h, TT6h; # Code block 35 lab = ([(:left, :center), (:right, :center), (:center, :top), (:left, :center)], [(5, 0), (-5, 0), (0, -5), (5, 0)])) # clear of lines
Figure 12: The routes of Ex. 5(b), within the hours of service, drawn as in Fig. 11.
Within the windows and the trucks’ capacity alone, 3 routes take 40.95 hours, but two of them break the hours of service; within the hours of service as well, 4 routes take 42.54 hours.
3. Routes to vehicles
In practice, as in the operational VRP of Model 3 in Lecture 1.1, the VRP minimizes the number of vehicles first. It is stated so in Model 3, which differs from Model 1 in its objective alone, highlighted:
minimize:first the number of vehicles used, then, among the solutions that use the fewest, the total cost of the routes
solve for:
(a) routes, each a sequence of customers that begins and ends at the depot.
subject to:
(a) Leave: each customer is left exactly once;
(b) Enter: each customer is entered exactly once;
(c) Routes: the arcs used form cycles, each passing through the depot;
(d) Feasible routes: each route satisfies every constraint on a single route, such as the vehicle’s capacity, a maximum distance or time, or time windows.
assumptions:
(a) arc costs are given and need not be symmetric;
(b) cost of a route is given by a route cost, the route’s distance or time when it is feasible and infinity when it is not.
No procedure in this lecture solves Model 3. Savings, Clarke-Wright among them, is a construction, and 2-opt then improves each route only within itself: nothing tries to reduce the number of routes once they are constructed, and the number of vehicles is only a byproduct of how many routes savings constructs. So Model 3 is neither formulated nor implemented here. What is solved instead is the simpler Model 1, whose objective is the cost of the routes alone, and this section minimizes the number of vehicles only for routes already constructed.
Any kind of commercial package would minimize the number of vehicles. A more complicated type of improvement heuristic would typically be used, which goes beyond what this lecture takes up. The better approach in practice is the randomization of Lecture 5.2: the routes are constructed and improved by 2-opt many times, each time differently, in the hope of different results, and the best is kept in terms of the number of vehicles or routes, not their cost. It can be a much easier way of implementing that objective than trying to develop special-purpose improvement procedures for reducing the number of routes or vehicles, which is quite difficult. This is similar to bin packing, where randomization is typically better than more sophisticated improvement.
Once the routes are calculated, the question is the minimum number of trucks needed. A driver is assigned to a truck and is not restricted to doing one route a day, especially a route of an hour or less, unless, for example, a union contract allows only one; with any kind of flexibility, which most companies have, the first concern in a VRP is to minimize the number of trucks and drivers needed, and then to use them as much as possible during their ten hours. When loading at the distribution center (DC) takes a fixed time, irrespective of the size of the load, that time can be added to each route’s total time, and several routes can then be added together on one truck: a first route of three hours with its loading ends back at the DC, where the truck is loaded for another, so that two, three or perhaps four routes fit in the ten hours. That is really the major objective. Minimizing the time of the routes tends to give pretty good routes, but it is usually not what a company is most interested in: it would much rather spend an extra hour if that eliminates a truck, since saving one hour is not nearly as beneficial as saving one truck, and routes constructed to minimize time are constructed without that in mind. A commercial solution would add improvement procedures that move a shipment from one route to another: if three routes would fit in ten hours except that the last customer puts them over, that customer could go on another route, increasing the total time a little but eliminating the need for a truck. Determining the minimum number of trucks is essentially a bin packing problem, the problem of determining the minimum number of bins needed for a set of items: each route is an item, its time is its size, and the bins have a fixed size, here ten hours. A problem small enough can be done by hand, and bin packing gives an easy heuristic way to think about it. Bin packing is the model of Model 6 in Lecture 2.7, with the routes as its objects, each route’s time as an object’s volume v_j, and a truck’s day as the volume V of a bin. Lecture 2.7 solved it as a MILP; a heuristic constructs a packing directly:
In bin packing, objects (e.g., boxes) with different volumes v are packed into bins, each of volume V, in a way that tries to minimize the number of bins used. Given each object in arbitrary order, one straightforward algorithm, termed firstfit, is to place the object in the first bin that it fits into; if it does not fit into any bin, put it into a new bin. The following function returns an array where each element is the indices of objects from v in a bin. Each element of v is the volume of the object, and each bin is packed so that its total volume of objects does not exceed V:
# Code block 39: first fitfunctionfirstfit(v, V)# Put first object into first bin B = [[1]] # Array of arrays b = [v[1]] # Array of scalars# Add remaining objects to binsfor i =2:length(v) idx =findfirst(b .+ v[i] .<= V) # Find first bin object fits intoif idx !==nothing# Found existing bin b[idx] += v[i]push!(B[idx], i)else# Create new bin for objectpush!(b, v[i])push!(B, [i])endendreturn Bend
firstfit (generic function with 1 method)
A variation of first fit, instead of taking the objects in a random order, orders them, and what typically works well in practice is to order them by decreasing size: all of the objects are ordered in decreasing size, and then the first fit procedure is applied, which in many cases does better than taking them at random. For some bin packing problems not all of the objects are at hand, so they cannot be sorted. These are called online problems: every hour, say, different objects arrive and a decision has to be made where each goes, so the largest is never seen among all of them, and an online procedure is needed. In an offline problem all of the objects are at hand and can be sorted, and then sorting in decreasing volume and applying first fit is probably the effective procedure. Whether a problem is online or offline can dictate which heuristic is even feasible, and which of those is the most effective.
The routes of a day are all constructed before any is assigned to a truck, so assigning them is an offline problem, and first fit applied to the routes in decreasing order of time is first-fit decreasing. Code block 40 sorts the objects largest first, packs them by firstfit, and returns each bin’s objects by their own indices:
# Code block 40: first-fit decreasingfunctionffd(v, V) # first fit, largest first p =sortperm(v, rev =true) # the objects, decreasingreturn [p[B] for B infirstfit(v[p], V)] # their own indicesend
ffd (generic function with 1 method)
Example 6: Osborn’s routes to trucks
Osborn, Inc., is a company that supplies 45 customers each day from its DC in Detroit, Michigan, by tractor-trailer. Determine its routes, each within a 10-hour day, and the fewest trucks that can run them, by hand and in Julia.
Osborn, Inc., has a DC in Detroit, MI that supplies 45 customers each day with cases of different products using tractor-trailers. Customer location, load density (in lb/ft³), and weight (in lb) of each load for each customer are in the file osborn-detroit.csv. A load can be split between multiple trucks. The file includes the location of the depot (customer 1). Each identical truck must start and complete its route between 7 a.m. and 5 p.m., including travel and unloading time. Each truck requires 20 minutes for loading at the depot. It can be loaded at the depot before 7 a.m., and this loading time should not be included in the 10-hour total, but if the truck is used for more than a single route, the 20 minutes should be included in the 10-hour total. Unloading at each customer takes five minutes for positioning the truck and five minutes per ton of the load.
Each identical truck can carry a maximum of 2,750 ft³ and 25 tons. Each vehicle travels at an average speed of 35 mph and actual road distances can be estimated from great circle distances, times the circuity factor of 1.2 of Lecture 2.2, Sec. 7.
Example 6(a): Routes
Determine the routes, each within the truck’s capacity and the 10 hours, and each route’s time, weight and cube.
Code block 41 reads the customers, builds the truck, with the 10 hours as its maximum route cost, and splits any load larger than a truckload, as the statement allows: whole truckloads are split off as loads of their own, and the rest is kept. A truckload of a load is the most its density lets the trailer carry, maxpayld of Lecture 3.2. Each load’s unloading time is 5 minutes plus 5 minutes a ton:
# Code block 41: Osborn's customers, their loads, the truckdfo = CSV.read("data/osborn-detroit.csv", DataFrame)XYo =hcat(dfo.Longitude, dfo.Latitude) # row 1 is the DCTo =1.2dists(XYo, XYo, :mi) /35# h, at 35 mphtro = (b =1, e=1, Kwt =25, Kcu =2750, maxTC =10)sho =DataFrame(b =1, e=2:nrow(dfo), q = dfo.Weight[2:end] /2000, s = dfo.Density[2:end])for i infindall(sho.q .>maxpayld.(eachrow(sho), Ref(tro))) qmax =maxpayld(sho[i, :], tro) # a truckload of itfor _ in1:floor(Int, sho.q[i] / qmax) # split off whole loadspush!(sho, (b =1, e= sho.e[i], q = qmax, s = sho.s[i]))end sho.q[i] =rem(sho.q[i], qmax) # and keep the restendsho.tU =5/60.+5sho.q /60# 5 min, + 5 min a tonprt(sho[sho.e.== sho.e[end], :]) # the load that was split
b e q s tU
────────────────────────────
1 1 29 0.03 1.17 0.0855
2 1 29 1.61 1.17 0.2174
Customer 29’s load, 3269 lb at a density of 1.17 lb/ft³, is more than the 2,750 ft³ of a trailer, so a full trailer of it, 1.17 \times 2750/2000 = 1.61 tons, is split off, and 0.03 tons are left: 46 loads in all. Fig. 13 draws the DC and the customers.
Show the code that draws this figure
# Code block 42: the DC and the customers on a maplet cube = dfo.Weight[2:end] ./ dfo.Density[2:end] # each load, ft³ fig, ax =basemap(XYo[:, 1], XYo[:, 2]; roads =true) # Code block 7scatter!(ax, XYo[2:end, 1], XYo[2:end, 2]; color = (bluec, 0.6), strokecolor = ink, strokewidth =0.6, markersize =4.+ cube ./160)depot!(ax, XYo) # Code block 7fitmap!(fig, ax)end
Figure 13: The DC (tan square) and Osborn’s 45 customers in and around Detroit, each drawn in proportion to the cube of its load, the interstates faded behind them.
Code block 43 constructs the routes by savings and improves each by 2-opt, with rteTC_vrp as the route cost, which reads the truck’s capacity and maximum and adds each load’s unloading time to the travel time:
# Code block 43: savings and 2-opt, each route's time by rteTC_vrprTTo(rte) =rteTC_vrp(rte, sho, To, tro)[1]Ro = [twoopt_rte(r, rTTo)[1] for r insavings(rTTo, sho)]TTo =rTTo.(Ro)sum(TTo)
32.29879610759186
Code block 44 tabulates each route’s time, weight and cube, and its customers in the order they are visited; with every load loaded at the DC, the route’s unloadings, the elements that are not loadings, give that order:
# Code block 44: each route's time, weight and cubeWto = [sum(sho.q[rte2idx(r)]) for r in Ro] # tcuo =2000sho.q ./ sho.s # each load, ft³Cubeo = [sum(cuo[rte2idx(r)]) for r in Ro]Custo = [sho.e[r[.!isorigin(r)]] for r in Ro] # customers, in orderprt(DataFrame(Time= TTo, Wt = Wto, Cube = Cubeo, Customers =string.(Custo)))
Customer 29 is on two routes, its remainder on one and its full trailer on a route of its own. Fig. 14 draws the routes.
Show the code that draws this figure
# Code block 45: the routes on a maplet lab = ([(:left, :center), (:left, :center), (:center, :top), (:right, :center), (:left, :top), (:left, :center), (:left, :center), (:left, :center), (:left, :bottom), (:right, :bottom)], # each route's number, [(5, 0), (5, 0), (0, -9), (-5, 0), (4, -4), (5, 0), (5, 0), (5, 0), (16, 16), (-4, 4)]), # clear of the lines (fig, ax) =vrpmap(Ro, sho, XYo, tro; lab) # Code block 7 h =string(round(sum(TTo), digits =2)) # to two decimals h =rpad(h, findfirst('.', h) +2, '0')text!(ax, 0.02, 0.03; space =:relative, color = ink, fontsize =13, font =:bold, align = (:left, :bottom), text ="$(length(Ro)) routes: $h h") figend
Figure 14: The routes of Ex. 6 from the DC (tan square), each in its own color and numbered near the center of its stops as in Code block 44’s table, and their total time at the lower left.
The routes are pretty much all limited by cube, and none is close to the weight capacity, which is typical of most trucking: the trailer cubes up. With the big 53-foot trailers assumed here and commercial customers, cube is the main constraint, so as big a trailer as possible is wanted; in a residential area a 53-foot trailer would not be used, and for local deliveries of smaller products shorter trucks are seen, where maximizing cube utilization is not the aim. Time is the other factor, and every route is easily within the ten hours. The heaviest route carries 13.59 of the 25 tons, and 8 of the 10 routes carry more than 2,500 of the 2,750 ft³.
10 routes, 32.3 hours in all, each within 25 tons, 2,750 ft³ and 10 hours; customer 29’s load is split between two routes.
Example 6(b): Routes to trucks by hand
Determine the trucks the routes need, by first-fit decreasing on the route times, and the fewest trucks any assignment could use.
The times of the routes of Ex. 6(a), to two decimals, are t_1, \ldots, t_{10} = 7.11, 5.03, 2.50, 2.32, 3.27, 0.92, 4.12, 3.77, 1.65 and 1.61 hours. A truck’s first route needs no loading in its day, and each later route adds its 20 minutes, t_L = 0.33 hours, so a truck can run the routes B if
=loading time at the depot before each route after a truck’s first (h).
This is bin packing with each route’s volume v_j = t_j + t_L and each truck’s V = 10 + t_L. First-fit decreasing takes the routes longest first and puts each on the first truck whose day Eq. 7 still allows, in Table 6:
Table 6: First-fit decreasing on the route times of Ex. 6(a): each route, longest first, on the first truck whose day stays within 10 hours, the day being the truck’s first route plus 0.33 hours and the time of each later route.
Step 7 is the near miss: route 4 would bring truck 3’s day to 10.02 hours, just over the 10. No assignment can use fewer trucks than the total volume of the routes over the volume of one truck, rounded up, the bound of Ex. 8 in Lecture 2.7:
so the 4 trucks of first-fit decreasing are the fewest possible, a Bounds check of Lecture 1.2. The bound is the minimum count of Lecture 1.3, Sec. 5, with no variability: the hours of work in a day over the hours one truck can work, rounded up.
A lower bound can be calculated for these problems, and sometimes the answer a heuristic gives is the lower bound: when it is equal to the lower bound, the heuristic solution can be said to be the globally optimal solution. When the number of bins exceeds the lower bound, all that can be said is that it is the best found, since not every lower bound is achievable, and even the global optimum can sometimes be above it, so the bound is not a guarantee; a heuristic solution above the lower bound is just the best-known solution.
First-fit decreasing puts the ten routes on 4 trucks, routes 1 and 3 on one, 2 and 7 on another, 8, 5 and 9 on a third, and 4, 10 and 6 on the fourth, which is the bound, so no assignment uses fewer.
Example 6(c): In Julia
Determine the same trucks in Julia, and the fewest trucks by the bin packing model of Lecture 2.7.
Code block 46 gives each route its volume, the route’s time and the loading time, and each truck its day, and assigns the routes to trucks by first-fit decreasing against the bound:
# Code block 46: routes to trucks, by first-fit decreasingtL =20/60# h to load at the DC, a later routev, V = TTo .+ tL, 10+ tL # each route, and a truck's dayLB =ceil(Int, sum(v) / V) # no fewer trucks than thistrucks =ffd(v, V) # the routes on each truck@show trucks(LB = LB, FFD =length(trucks))
trucks = [[1, 3], [2, 7], [8, 5, 9], [4, 10, 6]]
(LB = 4, FFD = 4)
The trucks are those of Table 6, a Triangulate check of the hand working. By Little’s Law of Lecture 1.3, Sec. 3, the 34.3 truck-hours of the day, the routes and the loading before each truck’s later routes, over the 10 hours of a day are the trucks busy on average, 3.43, so at least 4 trucks are needed, as the bound says. Fig. 15 draws each truck’s day.
Show the code that draws this figure
# Code block 47: each truck's daylet fig =Figure(size = (600, 230)) ax =Axis(fig[1, 1]; xlabel ="Hour of the day", ylabel ="Truck", yreversed =true, yticks =1:length(trucks), xticks =7:17)for (k, B) inenumerate(trucks) # each truck, its routes in turn t =7.0for (j, r) inenumerate(B)if j >1# the loading before a later routepoly!(ax, Rect(t, k -0.3, tL, 0.6); color = (bluec, 0.12), strokecolor = ink, strokewidth =0.8) t += tLendpoly!(ax, Rect(t, k -0.3, TTo[r], 0.6); color = (bluec, 0.4), strokecolor = ink, strokewidth =0.8)text!(ax, t + TTo[r] /2, k; text =string(r), color = ink, fontsize =13, font =:bold, align = (:center, :center)) t += TTo[r]endendvlines!(ax, [17]; color = redc, linestyle =:dash)xlims!(ax, 6.8, 17.4) figend
Figure 15: Each truck’s day of Ex. 6 from 7 a.m., its routes (blue), numbered as in Code block 44’s table, and the 20 minutes of loading before each later route (pale blue), against the 10 hours (red, dashed).
Code block 48 repeats the bin packing model of Lecture 2.7, and Code block 49 finds the fewest trucks with it:
Show the bin packing of Lecture 2.7
# Code block 48: the bin packing model of Lecture 2.7functionbinpack(v, V; tlim =60.0, gap =1e-4) M =1:length(v) bp =Model(HiGHS.Optimizer)set_silent(bp)set_time_limit_sec(bp, tlim) # give up after this longset_attribute(bp, "mip_rel_gap", gap) # or once this close@variable(bp, y[M], Bin)@variable(bp, x[M, M], Bin)@objective(bp, Min, sum(y))@constraint(bp, capacity[i ∈ M], # (a) V * y[i] >=sum(v[j] * x[i, j] for j ∈ M))@constraint(bp, assignment[j ∈ M], # (b)sum(x[i, j] for i ∈ M) ==1)optimize!(bp) xᵒ, yᵒ =snapvals(value.(x)), snapvals(value.(y)) used =findall(==(1.0), yᵒ) bins = [findall(==(1.0), xᵒ[i, :]) for i ∈ used] res = (bins = bins, used =Int(objective_value(bp)), status =termination_status(bp), gap =relative_gap(bp), secs =solve_time(bp))return resend
binpack (generic function with 1 method)
# Code block 49: the fewest trucks, by the bin packing modelpacked =binpack(v, V)@show packed.bins@show LB # the bound@showlength(trucks) # first-fit decreasingpacked.used # the optimum
The model’s optimum is 4 trucks, the bound and the count of first-fit decreasing, in a different packing of the routes.
In Julia, as by hand, first-fit decreasing puts the routes on 4 trucks, and the bin packing model of Lecture 2.7 confirms that 4 is the fewest.
Example 7: Acme’s timed routes to vehicles
Acme, Inc., is a company that supplies 45 customers each day with cases of widgets from its DC in Morrisville, North Carolina, each customer with its own delivery window. Determine its routes within those windows, an hour’s wait at most and a 10-hour route, and the vehicles that can run them, by hand and in Julia.
Acme, Inc., has a DC near the RDU airport in Morrisville, NC that supplies 45 customers each day with identical cases of widgets.
Customer location, demand, and time window data is in the file morrisville-vrptw.csv. The file includes the location of the depot and each customer, number of cases required for each customer, and the time window when the delivery can be made. The time window is indicated by the hours (0 to 24) at which the earliest and latest deliveries can occur. Unloading at each customer must occur within its time window, and the vehicle must wait if it arrives prior to the earliest delivery time. Vehicles can load, depart, and return to the depot at any time.
Each identical vehicle can carry a maximum of 75 cases, must complete its route within 10 total hours, including travel, load/unloading, and waiting time (note: this is a driver-related constraint, thus a vehicle used for multiple routes can be assumed to have a different driver for each route if necessary), must complete its delivery within each customer’s specified time window, and should not wait at a customer for more than one hour, not including unloading time. It takes one hour to load a vehicle at the depot, irrespective of the total number of cases loaded, and two minutes per case at each customer for unloading. Each vehicle travels at an average speed of 35 mph, and road distances are estimated as 1.2 times great circle distances.
Code block 50 reads the customers, their cases and their windows, with each customer’s unloading time at 2 minutes a case, and gives the vehicle its capacity of 75 cases:
# Code block 50: Morrisville's customers, cases and windowsdm = CSV.read("data/morrisville-vrptw.csv", DataFrame)XYm =hcat(dm.Longitude, dm.Latitude) # row 1 is the DCTm =1.2dists(XYm, XYm, :mi) /35# h, at 35 mphnm =nrow(dm)shm =DataFrame(b =1, e=2:nm, q = dm.Cases[2:end], tU =2dm.Cases[2:end] /60, # 2 min a case temin = dm.Earliest[2:end], temax = dm.Latest[2:end])trm = (b =1, e=1, Kwt =75) # 75 cases a vehicleprt(first(shm, 5))
Fig. 16 draws the DC and the customers, each colored by the hour its window opens.
Show the code that draws this figure
# Code block 51: the DC and the customers on a maplet (fig, ax) =basemap(XYm[:, 1], XYm[:, 2]; # Code block 7 roads =true) hrs =cgrad(:turbo, 10; categorical =true) # 7 a.m. to 4 p.m. sc =scatter!(ax, XYm[2:end, 1], XYm[2:end, 2]; color = dm.Earliest[2:end], colormap = hrs, colorrange = (6.5, 16.5), strokecolor = ink, strokewidth =0.6, markersize =10)depot!(ax, XYm) # Code block 7fitmap!(fig, ax)Colorbar(fig[1, 2], sc; label ="Window opens (hour)", ticks =7:16, labelsize =13, ticklabelsize =12) figend
Figure 16: The DC (tan square) near the RDU airport and Acme’s 45 customers, each colored by the hour its delivery window opens, one color an hour, the interstates faded behind them.
Example 7(a): Routes
Determine the routes within the windows, the hour of waiting and the 10 hours.
rteTC_vrp reads the capacity and the windows, so Code block 52 first constructs the routes with it alone, and tabulates each route’s time with its hour of loading and its longest wait:
# Code block 52: rteTC_vrp alone, capacity and windowsrTTb(rte) =rteTC_vrp(rte, shm, Tm, trm)[1]Rb = [twoopt_rte(r, rTTb)[1] for r insavings(rTTb, shm)]outb =rteTC_vrp(Rb, shm, Tm, trm)[3]prt(DataFrame(Time=rTTb.(Rb) .+1, # with loading MaxWait = [maximum(o.Wait) for o in outb]))
Of its 9 routes, 5 run past 10 hours with the hour of loading, and 4 wait more than an hour somewhere: rteTC_vrp does not have the two limits. Its maximum total cost maxTC cannot stand in for the 10 hours, since it is checked on the travel and unloading before the scans add any waiting, so a route can pass it and still run past 10 hours once its waits and its hour of loading are counted. Code block 53 adds the two limits by a route cost of one’s own, as Sec. 1 adds a maximum distance: it returns infinity for a route that waits more than an hour anywhere, and adds the hour of loading to the route’s time, returning infinity if that is more than 10 hours:
# Code block 53: the limits rteTC_vrp does not have, a route costfunctionrTTm(rte) TT, _, out =rteTC_vrp(rte, shm, Tm, trm)isinf(TT) &&returnInfmaximum(out.Wait) >1&&returnInf# wait at most an hourreturn TT +1>10 ? Inf: TT +1# an hour of loading at the DCendRm = [twoopt_rte(r, rTTm)[1] for r insavings(rTTm, shm)]TTm =rTTm.(Rm)sum(TTm)
80.36730141289085
Code block 54 reads each route’s span from its schedule: its hour of loading starts an hour before the route leaves the DC, and it ends when the route is back. The schedule rteTC_vrp sets leaves each route as late as its windows allow:
# Code block 54: each route's span, from its loading to its returnoutm =rteTC_vrp(Rm, shm, Tm, trm)[3]bm = [o.Start[1] -1 for o in outm] # loading starts, an hour earlyem = [o.Depart[end] for o in outm] # back at the DCclock(h) = (m =round(Int, 60h); # hours as h:mmstring(m ÷60, ":", lpad(m %60, 2, '0')))ks =sortperm(bm) # by the start of loadingprt(DataFrame(Route = ks, Loads =clock.(bm[ks]), Back =clock.(em[ks]), Hours =round.(em[ks] .- bm[ks], digits =2)))
# Code block 55: the routes on a maplet lab = ([(:left, :center), (:right, :top), (:right, :top), (:right, :top), (:left, :bottom), (:left, :top), (:right, :center), (:left, :center), (:right, :top), (:right, :center), (:center, :bottom)], # route numbers, [(5, 0), (-4, -4), (-4, -4), (-4, -4), (4, 4), (4, -4), (-5, 0), (5, 0), (-4, -4), (-5, 0), (0, 5)]), # off the lines (fig, ax) =vrpmap(Rm, shm, XYm, trm; lab) # Code block 7 h =string(round(sum(TTm), digits =2)) # to two decimals h =rpad(h, findfirst('.', h) +2, '0')text!(ax, 0.98, 0.03; space =:relative, color = ink, fontsize =13, font =:bold, align = (:right, :bottom), text ="$(length(Rm)) routes: $h h") figend
Figure 17: The routes of Ex. 7 from the DC (tan square), each in its own color and numbered near the center of its stops as in Code block 54’s table, and their total time, each with its hour of loading, at the lower right.
11 routes, 80.37 hours with the hour of loading in each, the longest 9.61 hours, every route within 10 hours and no wait over an hour; rteTC_vrp alone gave 9 routes, 5 of them too long.
None of the procedures used so far takes the number of trucks into account. One way to approach it is a Gantt chart, which an industrial engineer has probably seen before, of the beginning and ending times of the routes over the day. From the chart, two routes that do not overlap can be done with one vehicle, two others with a second, one by itself by a third, and perhaps three together by a fourth, going through them systematically by eye. It could be done optimally by finding a directed minimum spanning tree whose forest has as many trees as the minimum number of trucks needed, and with a thousand routes it could not be done by hand; but the directed version is more complicated to implement, and it has not been seen in any package for Julia or Python. Without the optimum, a greedy procedure is easy to code: start with the first route, find one that does not overlap it, combine the two, and go through the routes systematically in that way.
Example 7(b): Routes to vehicles by hand
Determine the vehicles the routes need, by combining routes that do not overlap.
The windows fix when each route runs, so a vehicle can take a second route only if it starts after the first is back. In Code block 54’s table, by the start of loading, the greedy starts with route 9, back at 12:01; the route that starts soonest after that is route 1, loading at 12:40 and back at 19:42, after which no route starts, so vehicle 1 takes routes 9 and 1. Vehicle 2 takes route 6, back at 7:56, and then route 3, loading at 8:36 (route 10 began loading at 7:41, before route 6 was back), and is back at 17:10, after which no route left starts. Vehicle 3 takes route 2, back at 11:40, and every route left starts before then; so does every later route, and routes 4, 10, 11, 5, 8 and 7 each need a vehicle of their own.
Nine vehicles: routes 9 and 1 on one, 6 and 3 on another, and each of the other seven routes on a vehicle of its own.
Example 7(c): In Julia
Determine the fewest vehicles the routes need in Julia, by a model of which route follows which on a vehicle.
The greedy of Ex. 7(b) gives a number of vehicles that is feasible, but not necessarily the fewest. Code block 56 finds the fewest with a model of which route follows which: route j can follow route i on a vehicle only if j starts loading after i is back, and each route has at most one route following it and at most one before it, so each vehicle’s routes form a chain, one tree of the forest in the telling above for each vehicle, and the vehicles are the routes less the links between them:
# Code block 56: the fewest vehicles, a model of which route follows whichR =1:length(Rm)fv =Model(HiGHS.Optimizer)set_silent(fv)@variable(fv, x[i ∈ R, j ∈ R; bm[j] > em[i]], Bin) # j follows i@objective(fv, Min, length(R) -sum(x)) # routes less the links@constraint(fv, next[i ∈ R], # (a) at most one after isum(x[i, j] for j ∈ R if bm[j] > em[i]) <=1)@constraint(fv, before[j ∈ R], # (b) at most one before jsum(x[i, j] for i ∈ R if bm[j] > em[i]) <=1)optimize!(fv)nxt = [findfirst(j -> bm[j] > em[i] &&value(x[i, j]) >0.5, R) for i ∈ R] # the route after each, if anyveh =Vector{Int}[]for i ∈sortperm(bm) # by the start of loadingany(==(i), nxt) &&continue# a route before itpush!(veh, [i]) # a vehicle's first routewhile !isnothing(nxt[veh[end][end]]) # and the chain after itpush!(veh[end], nxt[veh[end][end]])endend@show vehInt(objective_value(fv)) # the fewest vehicles
The fewest is 9 vehicles, the count of the greedy of Ex. 7(b), with the routes paired differently, since more than one pairing needs that few; Fig. 18 draws each vehicle’s routes against the clock.
Show the code that draws this figure
# Code block 57: each vehicle's routes, against the clocklet fig =Figure(size = (600, 330)) ax =Axis(fig[1, 1]; xlabel ="Hour of the day", ylabel ="Vehicle", yreversed =true, yticks =1:length(veh), xticks =4:2:20)for (k, Vk) inenumerate(veh), r in Vkpoly!(ax, Rect(bm[r], k -0.3, 1, 0.6); color = (bluec, 0.12), strokecolor = ink, strokewidth =0.8) # loading at the DCpoly!(ax, Rect(bm[r] +1, k -0.3, em[r] - bm[r] -1, 0.6); color = (bluec, 0.4), strokecolor = ink, strokewidth =0.8)text!(ax, (bm[r] +1+ em[r]) /2, k; text =string(r), color = ink, fontsize =13, font =:bold, align = (:center, :center))endxlims!(ax, 4, 20) figend
Figure 18: Each vehicle of Ex. 7 and its routes against the clock, each route numbered as in Code block 54’s table, its hour of loading at the DC (pale blue) before the route (blue).
The fewest vehicles for the 11 routes is 9, the count the greedy found by hand.
If a route could start a little earlier or later, one vehicle might be able to do two routes. Where the windows are tight, that is probably not possible, but in many other cases, when the start is not specified, it is set arbitrarily, since the procedure is concerned only with minimizing the route total cost. If the objective of minimizing the number of vehicles were included instead, the best time to leave could be adjusted: leaving an hour earlier or later might lengthen a route by an hour, which is bad for the route total cost objective, but it might reduce the number of vehicles by one, which is the more important objective. That is not at all included here; it is an extension.
4. Tactical routing
The periodic VRP of Sec. 1, which minimizes total logistics cost, is the load formation of Lecture 5.2; tactical routing here is a different question, answered without building any route. Most routing procedures are for operational decisions, which, given actual demands, determine actual routes; for tactical decisions, a procedure can only estimate routing performance.
Tactical vehicle routing can only estimate routing performance. There is no actual route sequence, but there are overall estimates of how many vehicles would be needed on average over time. It makes extensive use of averaging, pushing the notion as far as it will go, to see what can be said without developing the routes. In many problems, such as how many vehicles to purchase, or at least lease, over the next year to handle the expected routing needs, the actual demands are not known yet; all that is available are estimates of the long-term average future demand. So it makes sense to wring as much useful information out of those estimates as possible, to help determine, for example, how many vehicles to lease, before solving the vehicle routing problem itself.
Tactical routing does not route a set of actual demands, as an operational problem does. It asks, more generally, how much can likely be done in the future given some idea of the demand: not the actual demand, but a forecast or an average. Panel (a) of Fig. 19 is a single distribution center, such as one serving Raleigh, with all of its delivery vans running individual routes, a classic VRP. With such routes it is hard to offer very tight time windows. That is fine when a request is to be delivered sometime during the day, but not for perishable products, which cannot stay on the truck for eight hours and have to be much closer to the customer. The alternative, in panel (b), is many more micro distribution centers, close enough to their customers that no route needs multiple stops: each delivery is point to point, direct to the customer. The analysis behind the figure did not solve any vehicle routing problems to find the average travel times; it used the TSP estimate of Lecture 5.1, which gives enough information, for a given area and number of stops, to estimate the distance that will be traveled. That distance can be translated into travel time, giving the maximum number of stops that can be made within a given time, or the maximum number of customers that can be served in it. That is an application of tactical routing, and its assumption is the estimate’s: customers uniformly distributed in a circle.
Figure 19: Multi-stop deliveries from a single DC (a) against point-to-point deliveries from several DCs (b), for the same set of customers, each DC a yellow square.3
Fig. 19 shows an example of using several multi-stop routes to make deliveries from a single DC versus making point-to-point deliveries from several DCs. In the figure, the total round-trip distance traveled by vehicles for point-to-point deliveries is about twice the distance required to make the same deliveries as part of a multi-stop route, but with point-to-point, after unloading a delivery at home, the vehicle is available to travel back to the DC.
The estimate of Lecture 5.1 applies only to a single tour, or a single route. Most of the time, though, one delivery van cannot deliver to all of the customers in a city such as Raleigh, and several vans are needed. For a parcel carrier, what really limits a van is that there are only eight hours in the day: a van cannot be on the road for 80 hours delivering one day’s packages, and because of that maximum time it takes several vans. In many other delivery problems it is the capacity of the vehicle that limits, not time: a truck delivering appliances may hold only five or six large ones, so five or six is the most stops it can make in an eight-hour day. And in long-distance trucking a route is limited by the 11 hours a driver can spend behind the wheel. So the two constraints seen most are capacity and maximum time. Both can be in effect, but typically one is binding and the other is not.
Lecture 5.1, Sec. 4, estimated the length of a tour from a central DC through m customers spread uniformly over an area a as Eq. 13 in Lecture 5.1:
=estimated length of a tour from a central DC through m customers (mi)
m
=number of customers
a
=area of the region (mi²)
\varphi
=tour constant, fitted to the two-customer route
=2(\sqrt{2} + 1)/(3\sqrt{\pi}) \approx 0.908.
Whenever a single tour is broken into several separate routes, there is additional travel to and from the depot termed stem travel. Assuming that the expected one-way stem distance is about the average distance from the center of a circle, the 2r/3 of Eq. 6 in Lecture 2.5 with r = \sqrt{a/\pi},
=estimated one-way stem distance, depot to first or last stop (mi)
\hat{d}^{\,\text{stem}}
=estimated stem distance of a route, out and back (mi)
r
=radius of a circle of area a (mi)
\kappa
=stem constant
=4/(3\sqrt{\pi}) \approx 0.752.
For a route to a single customer, the route is all stem, and with a = \pi r^2,\kappa\sqrt{a} = \tfrac{4}{3}r: the average round trip of the pizza delivery of Ex. 4 in Lecture 1.1, 4 mi for a radius of 3 mi, a Landmark check of Lecture 1.2. Fig. 20 draws a route’s stem and its tour.4,5
Figure 20: A route’s stem (red), out from the depot to its first customer and back from its last, and its tour (blue) through its customers.
Translating the TSP estimate to the VRP adds one complication. A TSP tour leaves the depot, which can be considered one of the customers, visits every customer, and returns to its starting point. With the additional constraints of a VRP, capacity or time, a vehicle has to stop delivering and return to the depot before it has reached all of the customers. The travel beyond what the optimal TSP tour would need, the distance out to a route’s first customer and back from its last, is called the stem distance, and the rest is the tour distance, so a route’s total distance is its stem plus its tour. The name comes from a flower: many vehicle routes look like a rose, the tour being the flower itself and the trip there and back to the depot its stem. To add the stem’s distance, or its time, two thirds of the radius, the average distance from the center of a circle, is used as the one-way stem: not exactly right, but right on average. One way, the stem is \frac{2}{3}\sqrt{a/\pi}, and there and back it is twice that, \frac{4}{3\sqrt{\pi}}\sqrt{a}. Just as \varphi wraps up the constant of the tour estimate, the Greek letter \kappa wraps up this one, which never changes and is almost exactly 0.75. The Greek letters are kept as a reminder that neither constant is an empirical result. The factors of the LTL rate estimate of Lecture 3.2, Eq. 12 in Lecture 3.2, such as its 7 divided by 2, are just the results of a big regression and have no exact value; under the assumptions here, with two thirds of the radius as the one-way stem, \kappa is an exact value.
In order to be time feasible, vehicle routes must satisfy:
\begin{gathered}
\begin{aligned}
\begin{array}{r}\text{Stem time} + \text{Tour Time} \\ {} + \text{Service Time}\end{array} &\le \text{Vehicle-time capacity} \\
(N - 1)\frac{\hat{d}^{\,\text{stem}}}{v} + \frac{\hat{d}_m^{TSP}}{v} + m t_s &\le N t_{\max} \\
(N - 1)\frac{\kappa\sqrt{a}}{v} + \frac{\varphi\sqrt{ma}}{v} + m t_s &\le N t_{\max}
\end{aligned} \\
\boxed{\;\left[\kappa(N - 1) + \varphi\sqrt{m}\right]\frac{\sqrt{a}}{v} + m t_s \le N t_{\max}\;}
\end{gathered}
\tag{10}
where
t_{\max}
=maximum operating time of a vehicle (h)
m
=number of customers
N
=number of routes, one vehicle each
a
=service area (mi²)
t_s
=service time at each customer (h)
v
=average vehicle speed (mph).
It assumes no capacity constraints, the estimates \kappa \approx 0.752 and \varphi \approx 0.908 of Eq. 9 and Eq. 8, and that N - 1 means no stem travel if there is one vehicle.
Time feasibility is where these results are used, and capacity feasibility follows it. With N routes, one vehicle each, and a maximum operating time t_{\max}, the right-hand side of Eq. 10 is the total vehicle hours available: an eight-hour day and ten vehicles give 80 hours, and whatever is done to make all of the deliveries, its total time cannot exceed those 80 vehicle hours. On the left is the total time required. With one vehicle, or one route, it is just a TSP: N - 1 = 0 cancels the stem, which is ignored, and what remains is the tour of Lecture 5.1. A distance divided by the travel speed gives a time, since miles over miles per hour leaves hours. Then m is the number of customers and t_s the service time at each, perhaps 2 or 3 minutes for a delivery van: the time it takes a driver to hop out of the van, put the delivery on the porch, take a photo, run back to the van and take off again. All of that added together has to be no more than the vehicle hours available, and with \kappa and \varphi the result is a fairly simple inequality that captures both the stem and the tour, each a multiple of \sqrt{a}/v, plus the service time.
Example 8: Delivery estimates
Determine, from the time feasibility of Eq. 10 and without constructing any route, the minimum operating time of three vehicles, the number of deliveries one vehicle can make in eight hours, and the number of deliveries a firm with six trucks has to outsource, by hand and in Julia.
Example 8(a): Minimum operating time
Determine the minimum per-vehicle operating time.
Three vehicles will make deliveries to 100 customers in a 1,000-square-mile service area. Assuming, on average, a vehicle travels at 30 mph (including stops at red lights) and, after reaching a customer, it takes six minutes to drop off a delivery. Estimate the minimum per-vehicle operating time.
In the symbols of Eq. 10, N = 3,m = 100,a = 1{,}000 mi², v = 30 mph and t_s = 6/60 h, the six minutes in hours, so that every term of the inequality is in hours, a Units check of Lecture 1.2. Dividing Eq. 10 through by N and setting it at equality gives the least t_{\max} the deliveries need:
With the constants rounded to \kappa \approx 0.75 and \varphi \approx 0.9, the same working gives 7.02 h; the constants of Eq. 9 and Eq. 8 give 7.05 h.
Three vehicles serving 100 customers need at least 7.05 h each.
The average speed of 30 mph includes the stops at red lights. For a metropolitan area an average of 20 to 25 mph is reasonable, and no more than 35; over a large area such as all of North Carolina, where trucks travel on interstates with few stoplights, an average closer to 65 mph would be used. Over a long trip, a navigation app’s estimate of the arrival time can come out within a couple of minutes, because of the law of large numbers: added up over many small road segments, the over- and underestimates tend to balance out. The minimum operating time is a simple application of a solver: with the givens entered, the time feasibility is forced to be an equality by driving the absolute value of its left-hand side less its right-hand side to zero, and the solver finds the operating time. Here it is simple enough to do algebraically: dividing Eq. 10 through by N gives the service time as m/N times t_s and the travel time as the stem and tour over N, and the numbers are put in directly. It is best to get the number numerically first and then make sure it can also be done by hand algebraically; it is always nice to have two different ways. When an algebraic solution gets messy, a numerical solve is the practical choice. Getting the same number both ways, in Ex. 8(d), is a Triangulate check of Lecture 1.2.
Example 8(b): Deliveries in eight hours
Determine the number of deliveries one vehicle can make in eight hours.
Assuming that, on average, a vehicle travels at 30 mph (including stops at red lights) and, after reaching a customer, it takes two minutes to drop off a delivery. If the service area is fifty square miles, estimate the number of deliveries that the vehicle can make in eight hours assuming that it has no capacity constraints.
With one vehicle, N = 1, there is no stem, and Eq. 10 at equality is m t_s + \varphi\sqrt{ma}/v = t_{\max}, a quadratic in \sqrt{m} whose root is
Should the estimate be 159 or 160 deliveries? Rounding up to 160 results in total time over 8 h: 159 deliveries take 159 t_s + \varphi\sqrt{159a}/v = 8.00 h, and 160 take 8.04 h, so the estimate is rounded down, a Bounds check of Lecture 1.2.
One vehicle can make 159 deliveries in eight hours.
With the stops at red lights included, a vehicle that drives at 40 mph or more averages about 30 mph, and 2 minutes to drop off a delivery is about what a parcel delivery takes, 2 to 3 minutes. What is nice is that where the customers are does not have to be known: their number is the unknown, and what is known is the total service area. With the known information put into the time feasibility for a maximum of eight hours, m is the only unknown, and solving for it gives 159. When planning, it gives an idea of how many customers one vehicle can serve. With a holiday season coming next week and an idea of the total demand expected over a metropolitan area, it estimates how many drivers are needed to serve all of it, without seeing the actual demand: an example of what is meant by tactical.
The estimate is an average distance. Roughly speaking, half of the time a route will be longer than the estimate and half of the time shorter. From a design point of view, it may be better to go more to the extremes, wanting to know that, say, 95% of the time the distance will not exceed some value, whereas the average is the middle, the 50% point, of the distribution. That has an impact on how the estimate is applied. Keeping in mind what the estimate is, an average, is an Assumptions check of Lecture 1.2.
Example 8(c): Outsourcing
Determine the number of deliveries six trucks can make, the number to outsource, and the number of trucks that would need no outsourcing.
Estimated total delivery requirements are 500 for a 200 mi² service area. How many deliveries will have to be outsourced, given the firm has only six trucks? The trucks travel at 25 mph, service time is six minutes, and seven hours are available for delivery.
With N = 6,Eq. 10 at equality is again a quadratic in \sqrt{m}, now with the stems of five more routes on the right:
A fractional delivery cannot be made, so m_{\max} = \lfloor 308.51 \rfloor = 308, and 500 - 308 = 192 deliveries have to be outsourced; the rounded constants, 0.75 and 0.9, give 309 and 191. With seven trucks the right-hand side is 7(7) - 0.752(6)\sqrt{200}/25 = 46.448, so m = 366.19 and 134 are outsourced; with eight it is 53.022,m = 424.41, and 76 are. Solving Eq. 10 for N instead, with m = 500,
Six trucks can make 308 of the 500 deliveries, so 192 have to be outsourced; seven trucks would outsource 134, eight 76, and ten none.
Ex. 8(c) estimates outsourcing requirements. The firm has only six trucks, and if they cannot make all of the deliveries, the rest have to be served by outsourced trucks. With the number of customers the firm can serve as the unknown, the time feasibility gives 308 whole deliveries, so 192 have to be outsourced. The calculation is useful because outsourcing is probably a lot more expensive per delivery than the firm’s own six trucks and drivers, so it answers what-if questions: buying one or two extra vehicles, seven or eight instead of six, would reduce the outsourcing significantly, at a cost, and whether that is a good deal or a bad one depends on whether 500 a day is the long-run average. A tactical decision of this kind is probably not for multiple years, unless some big contract is being signed, but for the next week or two: an estimate of 500 deliveries a day for a week or two of a Christmas peak, say. The result is then that 192 deliveries a day have to be outsourced for those weeks, and it is probably not worth hiring a permanent employee, since once the season is over the demand drops back, the normal demand being confidently under 300: outsourcing is the choice for the peak period. The same basic tool, time feasibility, answers dozens of mixes and matches of problems like these, but what it leaves off the table is capacity.
Example 8(d): In Julia
Determine the same three estimates in Julia, solving numerically, and how they compare with the hand working.
Code block 58 writes the left-hand side of Eq. 10, the vehicle hours N routes need to serve m customers, as a function:
# Code block 58: time feasibility, as a functionκ =4/(3sqrt(π)) # stem constant, about 0.752φ=0.908# tour constant, Lecture 5.1# vehicle hours that N routes need to serve m customerstfeas(N, m, a, v, ts) = (κ*(N -1) +φ*sqrt(m))*sqrt(a)/v + m*ts
tfeas (generic function with 1 method)
Code block 59 divides the vehicle hours of Ex. 8(a) among its three vehicles:
# Code block 59: Ex. 8(a), the minimum operating timeN, m, a, v, ts =3, 100, 1000, 30, 6/60# vehicles, customers, mi², mph,# and h at each customer@show tmin =tfeas(N, m, a, v, ts)/N; # h a vehicle
tmin = tfeas(N, m, a, v, ts) / N = 7.052349496007735
Code block 60 solves Ex. 8(b) numerically, finding the m at which the hours one vehicle needs equal the eight it has, and times 159 and 160 deliveries:
# Code block 60: Ex. 8(b), one vehicle's deliveries in 8 hoursusingOptima, v, ts, tmax =50, 30, 2/60, 8# mi², mph, h, h# the m at which the vehicle hours needed equal those availablem =optimize(m ->abs(tfeas(1, m, a, v, ts) - tmax), 1, 1000).minimizer@show m # deliveries@showtfeas(1, 159, a, v, ts) # h for 159@showtfeas(1, 160, a, v, ts); # h for 160
m = 159.03204508022122
tfeas(1, 159, a, v, ts) = 7.9986599143525545
tfeas(1, 160, a, v, ts) = 8.04046629809308
Code block 61 does the same for Ex. 8(c), for six, seven and eight trucks, and then solves for the number of trucks that serve all 500:
# Code block 61: Ex. 8(c), six trucks' deliveries, and the resta, v, ts, tmax =200, 25, 6/60, 7# mi², mph, h, h# the most deliveries N trucks can make, a whole numbermmax(N) =floor(Int, optimize(m ->abs(tfeas(N, m, a, v, ts) - N*tmax),1, 1000).minimizer)@showmmax(6)@show500-mmax(6) # outsourced@show500.-mmax.([7, 8]) # with seven or eight trucksNall =optimize(N ->abs(tfeas(N, 500, a, v, ts) - N*tmax),1, 20).minimizer@show Nall; # trucks to serve all 500
The numerical solves agree with the hand working of Ex. 8(a) to (c) in every number, a Triangulate check of Lecture 1.2: the closed form of Eq. 11 and the quadratic of Ex. 8(c) are the roots the solver finds.
In Julia, as by hand: 7.05 h for each of three vehicles; 159 deliveries for one vehicle in eight hours; 308 deliveries for six trucks, 192 outsourced, and ten trucks to serve all 500.
In order to be capacity feasible, a vehicle route must satisfy:
\begin{aligned}
\begin{array}{r}\text{Sum of load size of all} \\ \text{customers along route}\end{array} &\le \text{Vehicle capacity} \\
\frac{m}{N} f &\le q_{\max}
\end{aligned}
\tag{12}
The minimum number of routes and the actual number of routes are
Capacity feasibility is relative to the vehicle’s capacity q_{\max}, the combination of cube and weight capacity of trucking in Lecture 3.2, a known piece of data. With f the demand of each customer and N the number of routes, mf/N is how much each vehicle actually serves, and the requirement is that it be no more than the vehicle’s capacity. From it, two things are calculated. One is the minimum number of routes, using the maximum payload. In actuality, though, the primary objective of a vehicle routing problem is usually to reduce the number of vehicles, not to minimize the distance or the travel time, which is secondary: everything else being equal, most companies would rather eliminate one vehicle, even if it increases the distance or travel time a little. So designing just for the maximum payload, though it minimizes the number of routes, may not be the best approach. It can do better to reduce the deliveries, the number of stops, on each route, so that a vehicle is able to make two or even three routes in the time available. With a payload a little less than the maximum in the denominator and the numerator unchanged, the actual number of routes can be greater than the minimum, which Ex. 9 solves by hand.
Example 9: Minimum number of vehicles
Determine the minimum number of vehicles needed for 100 customers of one unit each, when a vehicle carries 5 units, a full route takes 5 hours, 8 hours are available and a vehicle can run more than one route a day, by hand and in Julia.
Example 9(a): Routes per vehicle
Determine the number of vehicles at one, two and three routes per vehicle, and the minimum.
A single delivery route that uses a vehicle’s full capacity of 5 units takes 5 hours to complete. If 8 hours are available, determine the minimum number of vehicles required. There are m = 100 customers, each with a load of f = 1 unit, and q_{\max} = 5 units.
Ex. 9 starts by assuming one route per vehicle. The five hours of a full route would come from the time feasibility of Eq. 10, with the estimates of the tour, the stem travel time and the service time at each customer. With eight hours available, one route per vehicle is feasible, and it takes 20 vehicles for the 20 routes. The procedure, without making it anything too formal, then asks what if each vehicle runs two routes. With eight hours available, each route has four hours, and assuming that the time a route takes is proportional to its load, which from the time feasibility it basically is, four hours over the five of a full route reduces the payload to four units. With four units, 25 routes are needed, and at two routes per vehicle that is 12.5, rounded up to 13 vehicles.
How much time each reduction saves matters. A full route of five units takes five hours, so a route of four units takes four hours and one of three units three hours. With only eight hours available, three three-hour routes cannot fit into eight hours, so three routes per vehicle needs routes of two units. The procedure, done by hand, starts at the maximum payload of five and keeps increasing the number of routes per vehicle, redoing the calculation each time, and keeps whichever result gives the minimum number of vehicles. By the criteria of the VRP, that is the best solution, whatever the distance or the time required: the minimum number of vehicles that can make all of the deliveries within eight hours.
Table 7 takes the steps, a row for each number of routes per vehicle, each payload within Eq. 12 and its routes by Eq. 13:
Table 7: Ex. 9 by routes per vehicle, each route’s payload cut in proportion to its time and, at three routes, to whole units.
Each unit takes t^{(1)}/q_{\max} = 1 h of route time, so the 100 units need 100 vehicle hours, and \lceil 100/8 \rceil = \lceil 12.5 \rceil = 13 vehicles is a lower bound that two routes per vehicle attains: 13 is the minimum, a Bounds check of Lecture 1.2. The bound is the machine-hours accounting of Lecture 1.3, Sec. 5, with vehicles for machines, the vehicle hours needed over the hours a vehicle has; Eq. 4 in Lecture 1.3 gives \lfloor 12.5 + 1 \rfloor = 13 as well, and differs from the ceiling only when the ratio is a whole number, since a workstation’s capacity must strictly exceed its load, while a day’s planned routes can use all of a vehicle’s hours.
At least 13 vehicles are needed, and two routes per vehicle, each carrying 4 units, attains it.
Example 9(b): With loading at the depot
Determine the minimum number of vehicles when each route first takes 20 minutes of loading at the depot.
Ex. 9(a) ignores the reloading time at the DC. With t_L = 20 min of loading before each route, as in Ex. 6, a vehicle running two routes has t^{(2)} = (t_{\max} - 2t_L)/2 = (8 - 2/3)/2 = 3.67 h for each, a payload of \lfloor \frac{3.67}{5}(5) \rfloor = 3 units, \lceil 100/3 \rceil = 34 routes and \lceil 34/2 \rceil = 17 vehicles; three routes have t^{(3)} = (8 - 1)/3 = 2.33 h, 2 units, 50 routes and again 17 vehicles. The loading time erases the four vehicles that two routes saved, a Nudge check of Lecture 1.2: a small change in a given moves the answer a long way, here because whole units cannot shrink by less than one.
With 20 minutes of loading before each route, 17 vehicles are needed, at two or three routes each.
Example 9(c): In Julia
Determine the same steps in Julia, and how they compare with the hand working.
Code block 62 computes a row of Table 7 for each number of routes per vehicle, and the lower bound:
# Code block 62: Ex. 9, vehicles at one, two and three routes eachm, f, qmax, t1, tmax =100, 1, 5, 5, 8# customers, units, units, h, hrpv =DataFrame(per_vehicle =1:3) # routes per vehiclerpv.t = tmax ./ rpv.per_vehicle # h for each routerpv.q =min.(qmax, floor.(Int, rpv.t ./ t1 .* qmax)) # whole unitsrpv.N =ceil.(Int, m*f ./ rpv.q) # routesrpv.vehicles =ceil.(Int, rpv.N ./ rpv.per_vehicle)prt(rpv)@showceil(Int, m*f*(t1/qmax)/tmax); # the time bound
Code block 63 repeats it with 20 minutes of loading before each route:
# Code block 63: Ex. 9(b), with loading at the depot before each routetL =20/60# h at the depot, each routerpv.t = (tmax .- rpv.per_vehicle .* tL) ./ rpv.per_vehiclerpv.q =min.(qmax, floor.(Int, rpv.t ./ t1 .* qmax))rpv.N =ceil.(Int, m*f ./ rpv.q)rpv.vehicles =ceil.(Int, rpv.N ./ rpv.per_vehicle)prt(rpv)
Every row agrees with Table 7 and Ex. 9(b), a Triangulate check of Lecture 1.2.
In Julia, as by hand: 20, 13 and 17 vehicles at one, two and three routes each, 13 the bound; 17 with 20 minutes of loading.
Tactical routing is much of what an industrial engineer actually does with vehicle routing. Operational routing has become a commodity, in that very good software for it is easy to find. But the operational problem gives no long-term insight into questions such as how many vehicles to lease for a peak period, and those are tactical decisions. Little software does the tactical part; its logic tends to be embedded in an expensive transportation management system, which brings the whole baggage of a commercial software package with it, and it is better to isolate the tactical decision making itself. It boils down to simple calculations like those of Ex. 8 and 9, all predicated on the TSP estimate, so whatever validity its assumptions have carries over. In practice it works pretty well: a mathematician might frown on it, but for engineering purposes it is a pretty effective approach. The questions companies typically have are of this kind: they are not so much interested in what the routes would be as in answers that operational routing cannot give, and tactical routing is a way of looking at such problems and coming up with actual recommendations.
Example 10: North Carolina counties on road time
Determine how many routes a DC at the center of North Carolina needs to deliver to each of the other 99 counties on road time, under the hours of service of Lecture 3.2, first by estimate and then by savings, and how the two compare.
The counties of Lecture 5.1, drawn with their shortest tour on the roads in Fig. 15 in Lecture 5.1, are the customers, one delivery each, 30 minutes at each, and the times between them are the fastest road times of Lecture 4.1, Sec. 5.6 Code block 64 builds the road network around the county points as Ex. 4 in Lecture 5.1 did, times each link as Ex. 3 in Lecture 4.1 did, and keeps the hours between every pair of counties:
# Code block 64: the counties, and the road time between every pairusingSimpleWeightedGraphsdfc =filter(r -> (r.STFIP ==st2fips(:NC)), uscounty())a =sum(dfc.ALAND) +sum(dfc.AWATER) # mi²Nf, Lf =prune_reindex(faf5nodes(), faf5links()) # Lecture 4.1's networkNc, Lc =cropnetwork(Nf, Lf, dfc.LON, dfc.LAT) # a box around the pointsNc, Lc =addconnectors(Nc, Lc, dfc.LON, dfc.LAT; add_nf_nf =false)con =isequal.(Lc.SOURCE, "CONNECTOR")# A link's minutes: FAF5's free-flow time t, or, where a link has none,# 60 d / v at its posted speed v; a connector at 20 mphmins(t, v, d) = t >0 ? t :60d / vtAB = [c ? 60d /20:mins(t, v, d) for (c, t, v, d) inzip(con, Lc.AB_TIME, Lc.SPEED, Lc.DIST)]tBA = [c ? 60d /20:mins(t, v, d) for (c, t, v, d) inzip(con, Lc.BA_TIME, Lc.SPEED, Lc.DIST)]fw, bw = Lc.DIR .!=-1, Lc.DIR .!=1# each link's directionsgT =SimpleWeightedDiGraph([Lc.SRC[fw]; Lc.DST[bw]], [Lc.DST[fw]; Lc.SRC[bw]], [tAB[fw]; tBA[bw]]; combine = min)Tmin, PT =shortestpaths(gT, nrow(dfc)) # minutes, and the pathsTc = Tmin /60# h@showmaximum(Tc); # the longest drive, h
maximum(Tc) = 9.572079284922552
Code block 65 puts the DC at the county nearest the center of the state, each county weighted by its area:
# Code block 65: the DC, at the county nearest the center of the statewc = dfc.ALAND + dfc.AWATER # each county's areactr = [sum(wc .* dfc.LON), sum(wc .* dfc.LAT)] /sum(wc) # weighteddc =argmin([dgc(ctr, [dfc.LON[i], dfc.LAT[i]]) for i in1:nrow(dfc)])dfc.NAME[dc]
"Lee"
The estimate of Eq. 8 measures distance in a straight line across the state, so its speed has to be fitted to the roads: the speed at which the estimated length of a tour of all 100 counties is covered in the time of the fastest tour on the roads, found by the TSP formulation of Lecture 5.1 (Code block 9):
# Code block 66: the fastest tour of the counties, and its speedncT =TSP(Tc) # Lecture 5.1, road hours@show ncT.TC # h@show v =φ*sqrt(nrow(dfc) * a) / ncT.TC; # mph, over the area
Before any route is built, Eq. 10 solved for N, as in Ex. 8(c), gives the number of routes each limit of the hours of service needs: 11 h of driving, without the service time, and 14 h on duty, with it. Committing to that count first is a Prior check of Lecture 1.2:
# Code block 67: the routes the estimate needs, before any is builtm, ts =nrow(dfc) -1, 30/60# customers, h at eachstem = κ *sqrt(a) / v # h out and backtour =φ*sqrt(m * a) / v # h, all m customers@show (tour - stem) / (11- stem) # routes: 11 h driving@show (tour + m * ts - stem) / (14- stem); # routes: 14 h on duty
The time on duty binds, and the estimate is 15 routes. Code block 68 then builds the routes by savings, each county a delivery from the DC, with the hours-of-service route cost of Ex. 5(b) written for this example’s shipments, times and truck:
# Code block 68: routes by savings, under the hours of serviceshc =DataFrame(b = dc, e=setdiff(1:nrow(dfc), dc)) # a delivery eachshc.tU .= ts # h unloading at eachtrc = (b = dc, e= dc) # from the DC and backfunctionrTTc(rte) # hours of service, as Ex. 5(b) TT, _, out =rteTC_vrp(rte, shc, Tc, trc)isinf(TT) &&returnInf drive =sum(out.Cost) # time at the wheelreturn drive >11|| TT >14 ? Inf: TT # 11 h in a 14 h dayendRc =savings(rTTc, shc)@showlength(Rc)@showcount(isinf, rTTc.(Rc)); # routes it cannot run
length(Rc) = 17
count(isinf, rTTc.(Rc)) = 3
3 of the 17 routes cost infinity: each is a single county that cannot be served within the hours of service even alone, and savings returns them without saying so. Code block 69 names them, sets them aside, and improves the other routes by 2-opt:
# Code block 69: the counties set aside, and the routes improvedgone = [rte2idx(r)[1] for r in Rc if isinf(rTTc(r))] # infeasible aloneprintln(dfc.NAME[shc.e[gone]])Rc = [twoopt_rte(r, rTTc)[1] for r in Rc if isfinite(rTTc(r))]drive = [sum(rteTC_vrp(r, shc, Tc, trc)[3].Cost) for r in Rc]prt(DataFrame(stops =length.(rte2idx.(Rc)), drive = drive, duty =rTTc.(Rc)))@showlength(Rc)@showsum(rTTc.(Rc)); # h on duty
Cherokee, Clay and Graham, in the far west, are more than 11 hours of driving out and back from Lee County with their 30 minutes, an Assumptions check of Lecture 1.2: a central DC cannot serve the whole state under the hours of service, and the estimate, which assumes it can, has to be redone for the 96 counties served:
# Code block 70: the estimate for the counties servedms = m -length(gone) # customers served@show (φ*sqrt(ms * a) / v + ms * ts - stem) / (14- stem);
(((φ * sqrt(ms * a)) / v + ms * ts) - stem) / (14 - stem) = 13.984213669796892
For the counties served the estimate is 13.98, so 14 routes, the 14 savings built, a Triangulate check of Lecture 1.2. Fig. 21 draws them.
Show the code that draws this figure
# Code block 71: the routes on the roadsfig, ax =makemap(dfc.LON, dfc.LAT; xexpand =0.05)resize!(fig, 687, 300)for (k, r) inenumerate(Rc) # each route along its roads loc =rte2loc(r, shc, trc) legs =zip(loc[1:end-1], loc[2:end]) path =reduce(vcat, [tracepath(PT[i], i, j)[1:end-1] for (i, j) in legs])push!(path, loc[end])lines!(ax, Nc.LON[path], Nc.LAT[path]; color =rtecol(k), linewidth =1.2) # Code block 7endscatter!(ax, dfc.LON, dfc.LAT; color = ink, markersize =4)outc = shc.e[gone] # the counties set asidescatter!(ax, dfc.LON[outc], dfc.LAT[outc]; marker =:xcross, color = ink, markersize =10)scatter!(ax, [dfc.LON[dc]], [dfc.LAT[dc]]; marker =:rect, color = colorant"#f2d9a0", strokecolor = ink, strokewidth =1.2, markersize =11) # the DCrtelabels!(ax, Rc, shc, hcat(dfc.LON, dfc.LAT), trc, # Code block 7 ([(:left, :bottom), (:left, :center), (:right, :bottom), (:right, :bottom), (:center, :bottom), (:right, :center), (:left, :bottom), (:left, :bottom), (:left, :center), (:right, :top), (:left, :bottom), (:left, :bottom), (:left, :top), (:left, :center)], # each route's number, [(4, 4), (5, 0), (-12, 12), (-4, 4), (0, 5), (-5, 0), (4, 4), (4, 4), (5, 0), (-5, -5), (4, 4), (4, 4), (4, -4), (5, 0)]))text!(ax, 0.98, 0.03; space =:relative, color = ink, fontsize =13, font =:bold, align = (:right, :bottom), # clear of the borders text ="$(length(Rc)) routes, "*"$(round(sum(rTTc.(Rc)), digits =2)) h on duty")fig
Figure 21: The 14 routes from Lee County under the hours of service, each in its own color and numbered near the center of its counties, each leg along its fastest roads in the FAF5 network of 2022, the county points in ink, the three counties set aside marked ×, and the routes’ hours on duty at the lower right.
The estimate of 15 routes, made before any route was built, assumed every county could be served; 3 in the far west cannot, and for the other 96 the estimate, 14 routes, is what savings builds.
Endnotes
G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science 6, no. 1 (1959): 80–91, p. 80, https://doi.org/10.1287/mnsc.6.1.80.↩︎
Bruce Golden, S. Raghavan and Edward Wasil, eds., The Vehicle Routing Problem: Latest Advances and New Challenges (New York: Springer, 2008), preface, p. v, https://doi.org/10.1007/978-0-387-77778-8.↩︎
M. G. Kay, Challenges and Opportunities Associated with Using Autonomous Vehicles and Drones for Home Delivery, 2020, unpublished.↩︎
The stem in the literature. Daganzo and Hall, whose paper is the next endnote, estimate the distance of a set of vehicle routes from a depot in the same two parts, for C deliveries per vehicle and points of density \delta, as d \approx 2\bar{r}/C + k/\sqrt{\delta} per point. Here \bar{r} is the average distance from a stop to the depot, and k is a dimensionless constant that depends on the metric, about 0.57 for Euclidean distance and 0.82 for rectilinear. The first term, the line-haul term, summed over all of the points, is the distance vehicles would travel if their only task were to reach the center of a district and return to the depot.
Summed over m points on N = m/C routes, with \delta = m/a, it is 2\bar{r}N + k\sqrt{ma}. With the depot at the center of a circle, 2\bar{r} = \kappa\sqrt{a} of Eq. 9, so their line-haul term is the stem of every route; Eq. 10 counts N - 1 stems instead, because the tour of Eq. 8 already passes through the DC once, and its tour constant \varphi covers the whole tour where their k covers only the local travel, so the two constants are not interchangeable. Lecture 5.1’s dropdown “The constant in the literature” sets \varphi beside Christofides and Eilon’s constant for the whole tour.↩︎
C. F. Daganzo and R. W. Hall, “A Routing Model for Pickups and Deliveries: No Capacity Restrictions on the Secondary Items,” Transportation Science 27(4), 1993, 315–329; Eq. 2 and its terms on p. 317.↩︎
Shortest against fastest roads. Taking each leg by its fastest route is not the same as taking the shortest. On the same roads, the shortest tour of the counties by distance shares 71 of its 100 legs with the fastest tour of Code block 66, but only 14 in the same direction: the two run mostly in opposite directions around much the same circuit. Driving the shortest tour, each leg by its shortest route, takes 12.3% more time than the fastest tour, the difference between the shortest and the fastest route of Lecture 4.1 at the scale of a whole tour.↩︎