RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Four Heuristic Solutions to the Traveling Salesperson Problem

The Traveling Salesperson Problem doesn't have a realistic single best solution, but you can use heuristics to find good solutions and possibly enjoy big savings on fuel costs.

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 8x1015 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.
N 5 10 15 20 25 30
N! 120 3.63x106 1.30x1012 2.43x1018 1.55x1025 2.65x1032

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.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date