ompanies with big fleets of vehicles track fuel prices with manic single-mindedness?and for good reason! Drivers for Federal Express, UPS, DHL, and other delivery companies drive hundreds of millions of miles per year. The United States Postal Service (USPS) alone drives around 1.1 billion miles and uses about 125 million gallons of fuel per year. If you multiply those numbers by the current cost of fuel, you can see that the stakes are enormous.

A fuel price increase of only a few cents per gallon can mean millions of dollars in added expense. Conversely, reducing fuel use by even 1 or 2 percent can save millions. Changing technologies and educating drivers to save fuel can help. For example, the USPS is replacing older vehicles to attain better mileage, moving to bigger vehicles to reduce the number of trips they must drive, and improving infrastructure to reduce the number of trips back to refueling centers.

But another way to reduce fleet costs is to optimize routes so vehicles travel as few miles as possible. That not only reduces fuel consumption, but it also reduces wear and tear on vehicles and lets drivers visit more stops in the same amount of time.

The Traveling Salesperson Problem
The goal of the Traveling Salesperson Problem (TSP) is to find the shortest possible route through a network that visits a given set of stops and then returns to its starting point. That’s exactly the problem that shipping companies such as Federal Express, UPS, and DHL face every day. A carrier must drive from a central collection point to a bunch of delivery stops and then back by the shortest route possible.

Unfortunately TSP is a very hard problem and there is no known algorithm for solving it exactly for larger problems.

Any solution to TSP provides the order in which the stops should be visited. One sure-fire approach to solving TSP is to examine every possible solution exhaustively. If there are N stops to visit, there are N! possible arrangements of the stops; therefore there are N! possible solutions. The function N! (pronounced “N Factorial”) equals N * (N-1) * (N-2) * … * 1. As you can imagine, the number of calculations grows extremely quickly as N increases, which unfortunately means that using an exhaustive approach to examine every possible solution is impractical for all but the smallest problems.

Table 1 shows the values of N! for several values of N. A TSP problem that visits only 10 stops has more than 3 million possible solutions and larger problems are completely out of reach. Even if you have a blazingly fast computer that can examine 1 billion possible solutions per second, to solve a 30-stop TSP you would need more than 8×10¹⁵ years (that’s 8 quadrillion years) to solve the problem exhaustively! While cutting back on fuel would be nice, you’re going to have to find a faster method if you want to claim the savings in the current fiscal year.

Table 1. The factorial function grows extremely quickly as N increases.

But a 30-stop route is not uncommon in real-world situations. To make matters even worse, companies such as UPS and Federal Express must build different routes every day (in fact, several times every day) so they don’t have much time to wait for good solutions.

For TSP problems with more than a dozen or so stops, you must turn to heuristics. A heuristic is an algorithm that doesn’t guarantee the best possible solution but that should produce a usable result. While you may not be able to achieve the full 6.7 percent possible savings for a route, you may be able to find a solution that saves 6.1 percent?and do it before your retirement party.

Divide and Conquer
One approach that many fleet companies take is to divide the stops into smaller groups and then build routes for the groups separately. Street networks often subdivide into regions naturally and that makes dividing up the stops easier. For example, a river, canyon, or highway may divide a city so roads cross over it at only a few places. It would usually be inefficient to make a route that jumps back and forth across the divide, so it probably makes sense to divide the stops into two groups, one for each side of the obstacle, and then plan routes for the groups separately.

Many companies carefully plan out delivery areas and then assign all the stops in a particular area to a single driver. That not only lets them plan routes one area at a time, but it also gives drivers time to become familiar with an area so they learn the shortcuts and don’t get lost as often.

While dividing stops into delivery areas helps, it still leaves you short of a full solution. Suppose delivery people drive four-hour shifts and can deliver about four packages per hour. Because that’s 16 packages per shift, it would be nice if you could solve at least 16-stop TSP problems. Even with the super computer described earlier flashing through 1 billion solutions per second, it would take you almost 6 hours to solve this problem exhaustively.

This still isn’t good enough, particularly if deliveries are faster than four per hour. Dividing the stops helps but you need more heuristics to avoid an exhaustive search.

The Random Approach
A very straightforward approach to solving TSP is to simply pick a bunch of random orderings for the stops and then see which one is best. This may seem like a stupid approach. After all, the chances of guessing the best solution for a 30-stop TSP are almost indistinguishable from zero?almost as bad as those of winning the lottery. However, picking random solutions is very quick and easy. If you examine a few thousand random solutions, you almost certainly won’t find the best solution but you may find one that’s pretty good.

	?
Figure 1. Random Route Strategy: Testing random routes is quick but doesn’t always lead to great solutions.

Testing random solutions is quick and easy but it’s, well, random. There’s no notion of working towards a better solution. You just make a bunch of haphazard guesses and see which one is best.

Figure 1 shows the downloadable TSP example program that accompanies this article (in both Visual Basic and C# versions) displaying a randomly generated solution to a 35-stop TSP. The program generated 10,000 random routes and picked the one shown in Figure 1 as the best. It’s not a great solution?after a few minutes with pencil and paper, you could probably improve on this route considerably.

Instead of just making a bunch of random solutions, you improve this algorithm significantly if you try to improve the random solution. Rather than testing a random guess and moving on to the next one, you try making small changes to the random guess to see if such changes improve it.

There are several ways you can try to improve a solution. One of the easiest is to randomly pick two stops, swap them, and see if that made the route better. If the route is better, you keep the change and try to make other improvements. If the swap didn’t improve the solution, you move the stops back to their original positions and try again with two other stops.

	?
Figure 2. Improved Random Strategy: Improved random solutions often give better results than purely random solutions.

You can continue trying random improvements for either a certain number of trials or until you’ve tried some reasonable number of random swaps without generating any improvement. For example, you might try random swaps until you make 100 swaps in a row without any improvement. At that point it’s getting hard to find improvements, so you can record the best solution so far and move on.

Figure 2 shows a solution to a 35-stop TSP that uses the technique of improving random solutions. It generated a single random solution and then tried to improve it until it failed to make any improvements 10,000 times in a row.

The result shown in Figure 2 is much better than the one shown in Figure 1, although you can probably spot a few places for improvement.

The problem with this approach is that it sometimes gets stuck with a route that is not perfect but that cannot be improved by simply swapping two stops. The program might need to rearrange three, four, or even more stops to find any improvement.

One way to make this approach more robust is to repeat it many times. Pick a random solution and improve it for a while. Then start over with another random solution and improve it. Repeat the process, picking and improving a few thousand random solutions, until you decide you’ve found a good enough solution.

Another approach is to specifically try other kinds of improvement. Instead of just swapping two stops, you can try other operations for improving the initial random solution.

Making Smarter Improvements

	?
Figure 3. Two-opt Strategy: The Two-opt heuristic looks for improvements by swapping pairs of links.

The random improvement heuristic picks two stops in the route and swaps them to see if it can make an improvement. The Two-opt heuristic randomly picks two links between stops. It removes those links and replaces them with others that keep the route connected and checks whether the change is an improvement.

Figure 3 shows an initial route and an improved version found by Two-opt. The 2-6 and 7-3 links in red on the left have been removed and replaced by the 2-3 and 6-7 links in blue on the right. Notice also that the path 6-5-4-3 on the left was reversed to 3-4-5-6 on the right to keep the route valid.

Comparing Strategies

	?
Figure 4. Comparing Strategies: Different heuristics may produce dramatically different results.

You can make other heuristics that consider rearranging three, four, or more stops or links but the more complicated the heuristic is, the harder it is to implement and debug. Often it’s just about as effective to run more trials starting from different random solutions as it is to build a much more complex heuristic.

Figure 4 shows the TSP example program displaying results for several different heuristics on a 35-stop TSP. The Random heuristic tested 10,000 random solutions in about 0.09 seconds and found one where the total length of the links in the solution was 3,345.

The Random Improvement heuristic generated a single solution and tried to improve it by making random swaps until it found no improvements in 10,000 trials in a row. This example took 0.02 seconds and examined 13,917 possible improvements. This test examined almost 40 percent more possible solutions than the Random heuristic did but in only about a quarter as much time. It was faster because it did not need to pick a completely new solution each time it looked for improvements. Instead it just swapped two stops on the route and checked the result.

The Four-opt heuristic does almost the same thing that Random Improvement does. It picks two stops and considers swapping them. But rather than actually performing the swap and then calculating the new solution’s cost, this program determines how much it would change the route’s cost to rearrange the four links leading into and out of the two stops, then actually makes the swap only if it will be profitable. In this test, Random Improvement found a slightly better solution than Four-opt did in about the same amount of time. In general these algorithms are pretty similar, although Four-opt may save some time in large problems because it doesn’t need to recalculate the whole solution’s cost at each step.

The Two-opt heuristic tries swapping links as described earlier. In this example it found a solution that is significantly better than the ones found by the previous methods.

Finally, the Mix heuristic uses the Four-opt and Two-opt heuristics many times until neither technique can find an improvement in 100 trials. You can see that this technique performed a lot more trials (more than 2 million versus around 10,000) and took longer, although it did find a slightly better solution.

	?
Figure 5. Brute Force: Exhaustive search finds the best possible result but can be very slow.

How good is this solution? I don’t know and I never will. It seems like a pretty good solution but the only way to be certain is to perform an exhaustive search. Until quantum computers appear, or some other science-fiction-like technology comes along, the sun would be a cold dark cinder before my computer could check all of the possible solutions.

Figure 5 shows one final example displaying the results of an exhaustive search for a 10-stop TSP. The exhaustive search took about .3 seconds to examine 3.6 million possible solutions. If you look closely, you’ll see that the more advanced heuristics produced increasingly better results. In this example, the Mix heuristic found the best possible solution, although in general any one of the heuristics might get lucky and find a perfect solution?or might be unlucky and always find bad solutions.

How long you let a heuristic run is for you to decide. You could let the heuristic run indefinitely, constantly displaying the best result it has found so far, until you decide you need to actually drive the route and get some work done. It might be nice to wait for the perfect solution, but if your boss is anything like mine, you won’t be able to wait billions of years for a solution.

Even if you don’t own a huge fleet, these savings can add up. I drive about 15,000 miles per year. If I can reduce this by 10 percent by using shorter routes, then I can save about 1,500 miles. If I get 30 miles per gallon (and most people don’t do that well), that would save about 50 gallons per year. At today’s prices that’s nothing to sneeze at.