## Keep on TruckingAnyone sitting in traffic in a large city knows that trucks come in a staggering array of types, ranging from relatively small delivery trucks to the giant trucks that carry ore from mines to other locations. We will see that there are different types of problems that arise for these different types of trucks....
Joseph Malkevitch
## Introduction
Love may make the world go round but what makes our daily lives so much easier is trucks. Trucks deliver the food that we eat to the supermarkets and restaurants we use, they deliver the gasoline to the stations where we refill the gas tanks in our cars, and they are responsible for a huge part of the movement of supplies throughout local regions and nationally.
(Photo courtesy of Wikipedia)
## Background
During World War II the Allies discovered that wars were not only waged by soldiers but by the people who designed the efficiency of the scheduling of troop movements and materiel that were necessary for soldiers to fight the war. With no lines of supply, soldiers can not be very effective. The ideas laid down during the war became codified in the area of knowledge that has come to be called
(George Dantzig)
Although the simplex method can in the worst case require exponential time to carry out, it runs very well in practice, a phenomenon which mathematicians are trying to understand better. There are polynomial-time algorithms for linear programming due to Leonid Kachiyan and Narendra Karmarkar. However, in many situations where linear programming is employed, the simplex method outperforms those polynomial-time algorithms, which fall into groups classified as interior point methods or ellipsoidal methods. ## Some history
The first scholarly paper which addresses what today is called the vehicle routing problem (VRP) appeared in 1959 in the journal ## A special vehicle routing problem
Anyone sitting in traffic in a large city knows that trucks come in a staggering array of types, ranging from relatively small delivery trucks to the giant trucks that carry ore from mines to other locations. We will see that there are different types of problems that arise for these different types of trucks. Although there are many applied questions which involve trucks and, more generally, vehicles, what has come to be called the
Figure 1 (4-site instance of a TSP, with edge subsidies)
One of the amazing things about important mathematical problems is how they pop up in places one might not initially think of. For a long time my favorite unexpected application of the TSP was to the fabrication of chips. To manufacture a chip requires the insertion of various components, typically using a robot. The optimal insertion order for these insertions involves solving an asymmetric TSP. However, I recently learned from David Johnson of work by Adam Buchsbaum (and colleagues). The basic idea is that large companies such as a phone company generate tables of information consisting of many fixed length records. A large company might have to store over a billion records per month, where the records could contain such information as the exchanges between which calls are made, call lengths, and costs, etc. In light of the huge amounts of data involved, it is desirable to store this data in compressed form. While for photos that appear in articles such as this one, compression that loses information is acceptable, for the application in this case lossless compression is mandatory. Oversimplifying greatly, it turns out that one can compress parts of the data set (sets of columns) and follow this by a compression of additional columns that make up the data set. The space used up at the end will generally depend on the order in which the sequence of compressions is carried out as well as the ordering of the columns in the group being compressed. Hence, one can profitably use the TSP (the asymmetric case) as one piece in the methodology to store the large data set as compactly as possible. ## The Clarke-Wright heuristic
One seminal paper in the area of vehicle routing was published in 1964 by G. Clarke and J.W. Wright and has come to be known as the Clarke-Wright Algorithm. The Clarke-Wright Algorithm is a "greedy" algorithm which has a very intuitive structure. c_{2,3} will denote the cost of going from site 2 to site 3 while c_{4,0} will denote the cost of going from site 4 to the depot. We will, only for convenience, assume that the cost of going from i to j is the same as going from j to i. Now if we currently have a vehicle that goes from the depot to i and back and another vehicle going from the depot to j and back, the cost for the first vehicle will be c_{0,i} + c_{i,0} which, since these two costs are the same, is 2c_{0,i}, and, similarly, we get a cost of 2c_{0,j} for the second vehicle to go from the depot to j and back. If it is possible to use one truck for both of these "deliveries" we can consider the route which "merges" these two "subroutes" and go from the depot to i and then continue on from i to j (rather than going back to the depot) and then return to the depot from j.
Now the cost of the trip from the depot to
so if we replace the two trips from the depot to and from each of
The number just computed is the "savings" obtained when the tours that go from the depot to
The Clarke-Wright heuristic algorithm is a "greedy" algorithm. This means that at each stage when something is carried out, a "locally" (at that moment) best decision is made. Of course, there is no guarantee that such locally good choices end up with a solution that is globally good or even nearly good. (For many greedy algorithms an optimal answer will be obtained.) There are by now many, many variants of the Clarke-Wright heuristic. I will try to give you the gist of the ideas in as non-technical language and notation as possible. i and j. We can then try to adopt a "greedy" approach by trying to coalesce subtours at each stage using a "short cut" edge with the greatest savings (as suggested by the approach in Figure 2, where one can also think of the single edges as subtours, and not necessarily as a single edge).Figure 2 So the idea behind Clarke-Wright is to merge "subtours" when possible to get a longer, cheaper tour of all the sites. Figures 3 and Figure 4 show what subtours might look like when solving a moderately sized problem by hand. Note that if we have two trucks these diagrams might (depending on the constraints of the problem) represent the final result of the algorithm. However, when we are using the Clarke-Wright heuristic to solve a TSP we would not be finished at this stage. Using Figure 4 we can see the ways that these tours (which currently are: 0, 1, 2, 6, 0 and 0, 4, 5, 3, 0 listed in order, although they could be written in reverse cyclic order) might be merged. To merge these two circuits we could use edge 63 to get the circuit 0,1,2,6,3,5,4,0; edge 64 to get 01264530; edge 31 to get 04531260; or edge 41 to get 03541260 (or these four circuits in reverse cyclic order). Figure 3
Figure 4
We will think of each of the two variants of the Clarke-Wright heuristic under consideration as having two steps. Step 1 is the same for both variants. i, j (i, j different and neither 0). Now order these savings in nonincreasing order.Variant A:Step 2 Begin with the edge at the top of the saving list. Move through the list of savings. When considering the saving S _{i,j } check if there are currently tours using edges 0,j and 0,i and if these tours can be feasibly merged, do so by adding i,j to the tour and deleting edges 0,j and 0,i.(Note: If the trucks being used for these two tours have limited capacity, one reason why it might not be feasible to join the two tours using edge i,j, even if the edge conditions above are met, is that the sizes of the pickups at i and or j, when added to the vehicle's load in this merged tour would exceed the room available on either truck being used for the smaller tours. One tries to merge tours as one goes through the list of savings. When one achieves a single tour for all the sites or runs out of edges, one terminates.) Variant B:Step 2 Begin with the edge at the top of the savings list. Use the next edge in the savings list to expand the current route by using this edge to extend the tour currently being worked on. If this tour cannot be extended, try to extend another tour using this edge. If no tour can be extended using the current edge, move to the next edge in the savings list. (Note: Initially, one can always add the maximum saving edge unless the capacity of the vehicles serving the sites at its ends are too large for one of the vehicles to be used. The idea here is to try to expand the current tour as long as possible with the edge providing the largest possible saving. One only moves on to another tour when the current tour cannot be added to.) When there are other constraints such as capacity of vehicles or restrictions on the number of sites on a tour, etc., the algorithm above is modified to check that adding the edge i, j which has the greatest saving at a particular stage is feasible with respect to the constraints, in addition to being possible from the point of view of enabling the merging of the tours.Experiments have been done to compare the two variants described above. There are some indications that Variant A tends to work better. To give you the flavor of the Clarke-Wright algorithm we will discuss how to use Variant 1 to solve a very small example. In the graph below we have a depot, labeled 0, and four sites labeled 1 to 4. This example involves a complete graph on 5 vertices (every pair of the vertices is joined by an edge). Furthermore, there is a cost associated with every edge in the graph which you can interpret as the amount of time it typically takes to travel between the pair of sites that are at the ends of the edges. Figure 5 (A four site instance of a VRP) In this example, the driving times in each direction between two sites are the same. We also have the property that for of any three vertices the sum the lengths of any two sides of the triangle they form has weight greater than the weight (cost) of the third side. We will initially think of this as a TSP problem, that is, we want to find a reasonably short route from the depot which visits each site exactly once and returns to the depot. We initialize our solution by thinking of the vehicle going from the depot to each site and back again. At this stage we have the diagram in Figure 6. We will then see how to improve this very inefficient "tour" to one which hopefully would be a lot better. Figure 6
We will assume that the trucks we are using have infinite capacity. Thus, we will be treating this problem as if what we are trying to do is find a TSP solution. We start by computing the savings that are associated with edges that connect two sites other than the depot (0). Figure 7 The edge with the next largest saving is edge 1,2. This edge can be added to merge the tours 0, 1, 0 and 0, 2, 3, 0, to obtain the tour 0, 1, 2, 3, 0. We can see the resulting collection of tours at this stage in Figure 8. Figure 8 The edge with the next largest sorted order would be 3,4. This edge can be used to merge the tours 0, 4, 0 and 0, 1, 2, 4, 0 to form a final tour, visiting all sites of 0, 1, 2, 3, 4, 0. Note that had 2, 4 been the cheapest edge at this stage it could not be used to merge the two tours. Had edge 1,4 been cheapest, then the merged tour would have been 0, 3, 2, 1, 4, 0 which visually is self-intersecting but permitted. Given the actual numbers here, the final tour is shown in Figure 9. Figure 9
The cost of this tour is 31 + 40 + 42 + 48 + 29 = 190. Keep on trucking! ## References:
Applegate, D. and R. Bixby, V. Chvatal, W. Cook, The Traveling Salesman Problem: A Computation Study, Princeton U. Press, Princeton, 2007.
Joseph Malkevitch Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |