Traveling Salesman Problem

At 6:30 AM, a customer in Los Angeles calls to confirm a pickup time. At 6:42 AM, a shipper in Palm Springs leaves a message regarding a delivery window. By 7:00 AM, customers in Santa Barbara, Bakersfield, Las Vegas, Phoenix, Portland and Seattle have all confirmed their loads for the next two weeks. Based on the hours of service schedule, the dispatcher has determined which driver can complete these jobs. The only question now is which order the cities should be visited in order to save the most amount of fuel, waste the least amount of time, and satisfy all customers’ requirements.

This type of problem is at the heart of what fleet management professionals do every day. It’s called the Traveling Salesman Problem and in its core form it looks deceptively simple. “What is the shortest possible route that connects a list of cities and returns to the original point?” It may come as a surprise that this is one of the hardest math problems in modern times. Experts at universities including Harvard, Oxford, Cambridge and Stanford have spent over 100 years trying to solve it. It is so challenging, in fact, that the Clay Mathematics Institute will award $1,000,000 to the person who discovers the solution.

It appears intuitive. Given a list of cities, one would only have to tally up the different trips that connect them and then figure out which trip is the shortest. The problem with this approach is that the number of possible trips dramatically increases with the number of cities. In the example above, there are 40,320 possible trips between the 8 cities given. Even if a computer could calculate one trip’s length every second, it would take over 11 hours to find the shortest possible trip. Mathematicians have had success finding the shortest route between 50, 100, 1,000 and even 50,000 cities. They have been able to find routes that are only 40% longer than the shortest possible route between any set of cities. But they have not been able to create an algorithm that finds the shortest possible route between any number of cities in the world. Such an algorithm would have implications that touch codebreaking, manufacturing, economics, biology – and, not least of all, fleet management.

A solution to the Traveling Salesman Problem would mean fleet managers would be able to quickly identify the shortest possible route for every one of their drivers, every time, no matter how many locations were on the list. Fuel costs would be slashed. Maintenance schedules would be relieved. It would be a much different world. In the real world, there are plenty of tools that help fleet managers reduce costs and time spent on the job as much as possible. Some of these tools may already be familiar and some are about to be mandated by the federal government. They help find the shortest possible route that is known to modern mathematics, reducing waste and expense along the way. They make the complex world of fleet management much simpler. They are readily available, trusted by many, and, fortunately, won’t cost anyone $1,000,000.