Keep on Trucking
Posted January 2010.
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....
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)
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 operations research or management science. Operations research drew heavily on the mathematics and the nascent computer science to assist businesses, governments, and individuals in organizing their work (and play) more efficiently.
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.
The first scholarly paper which addresses what today is called the vehicle routing problem (VRP) appeared in 1959 in the journal Management Science, whose first volume appeared only 4 years before in 1955. The authors of this paper were George Dantzig (1919-2005) and J. H. Ramser. Their work was also presented at the Fifth World Petroleum Congress held in New York in 1959. Dantzig was a well known and important figure in linear programming and operations research and was working for the Rand Corporation at the time. I was unable to find out much information about Ramser, whose full name was John Ramser. At the time he worked with Dantzig on this paper he was an employee of the Atlantic Refining Company in Philadelphia, which later became ARCO and was eventually absorbed into British Petroleum. He wrote at least one other quite mathematical paper ("Theory of Thermal Diffusion under Linear Fluid Shear") and was the author of a variety of patents. Ramser also played a role in the early development of SIAM (the Society for Industrial and Applied Mathematics), having served in its earliest days (1953-1956) on its governing council.
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 vehicle routing question has a special structure. Generally speaking, the goal of the problem is to minimize the cost of carrying out the needed work while not violating the constraints that may be imposed (e.g. truck capacity or the delivery at site 3 must be made between 2 and 3 p.m.). In particular, there is a very special case of the vehicle routing problem which is much better known than the vehicle routing problem itself. Known as the Traveling Salesman Problem, it first began to be studied in about 1930. This problem is so significant that there are whole books devoted only to issues related to the Traveling Salesman Problem (TSP).
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.
Now the cost of the trip from the depot to i, then to j, and then to the depot is:
so if we replace the two trips from the depot to and from each of i and j by the trip from the depot to i and then to j and then back to the depot, we can compute the different in cost between these two different routings:
The number just computed is the "savings" obtained when the tours that go from the depot to i and the depot to j are "coalesced." (From different points of view one can think of this merging process as taking two separate routes carried out by one vehicle as being collapsed to one tour for that truck or as two trips that are carried out by different vehicles now being carried out by a single vehicle.)
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.
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).
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.
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.
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).
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.
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.
The cost of this tour is 31 + 40 + 42 + 48 + 29 = 190.
Keep on trucking!
Applegate, D. and R. Bixby, V. Chvatal, W. Cook, The Traveling Salesman Problem: A Computation Study, Princeton U. Press, Princeton, 2007.
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