Last year, The New York Times reported that UPS managed to save 3 million gallons of gas in 2006 by altering the routes of delivery trucks to avoid left turns. According to them, the company uses software called "package flow" to map out daily routes for drivers.
Clearly, the method or "algorithm" this software employs to design efficient routes has sizeable economic (and greenhouse gas) consequences. And, not only is it far from perfect, but the general routing problem is so difficult that, well, if in the course of reading this article you happen upon an efficient solution, you will become immediately famous, at least among computer scientists.
The problem the UPS driver faces, generally speaking, is that of the "traveling salesman," in which our hero seeks the shortest possible round trip route given a list of required stops. Arising in road trip planning, school bus pickups, parking meter coin collection, power cable layout, and microchip design, it is not a new problem.
The famous 19th century Irish mathematician Sir William Rowan Hamilton, who at age 12 once defeated the notorious American "calculating boy" Zerah Colburn in an arithmetic-off, invented the "Icosian game," in which players attempt to find round-trip routes through a twelve-sided figure such that each vertex is visited exactly once and no edge is visited twice (Regarding the spin-off "Traveler's Dodecahedron," the puzzle museum website states, "the rules have been simplified and made much more attractive than the original." The puzzle museum also notes that the Icosian game is more of a puzzle than a game.)
Inspired by Hamilton's early work and puzzle-making prowess, mathematicians in Vienna and Cambridge began studying the general form of the traveling salesman problem (TSP for short) in the 1930s.
In 1972, UC Berkeley Professor Richard Karp published perhaps the most famous paper written to date in computer science, called "Reducibility Among Combinatorial Problems." The point, broadly speaking, is that most problems that appear difficult to solve exactly most likely are. Rather than proving that all kinds of problems have no easy solution, Karp gave a clever method for showing that many different sorts of problems are equivalent in a certain sense: if you provide a magic fast solver for hard problem A, Karp uses it to build a fast solver for hard problem B.
As a result, researchers are amassing an impressive set of hard problems, all reducible to each other, so that if anyone ever found a magic solver for just one of them, well, things would get pretty crazy. A variant of the TSP, that of undirected Hamiltonian Circuits (same Hamilton), was in Karp's original list of 21 problems.
To understand what this means for the salesman, consider: A TSP with 5 cities has 12 possible routes; with 10 cities there are 181,440 possibilities; with 61 cities there are more possible paths than there are atoms in the universe. Seriously. In computer science terms, the solution space is exponential — adding one city roughly doubles the number of possible paths. Karp's result suggests that in general, determining the optimal path for the salesman is a matter of checking all those possibilities — though shortcuts may exist, none are likely to lift the exponential burden. And though computers are growing more powerful, even IBM's supercomputer, Blue Gene, which can perform a ridiculous 500 thousand billion computations per second, would have little hope of solving a 30-city TSP by the brute-force approach.
Instead, computer scientists spend much time devising heuristics — approximate methods for dealing with intractable situations. Here's a simple heuristic for the traveling salesman: when trying to decide which stop to visit next on the tour, pick the closest remaining one. While in many cases, this rule yields a route much less efficient than the optimal one, it works reasonably well on average. Many papers have been written about more complex heuristics for the TSP. For example, in 1997 Marco Dirigo used a simulated ant colony to explore the space of solutions, iteratively refining paths left by virtual ants (virtual pheromones were also involved).
The TSP variant that UPS would like to solve is no Icosian puzzle game. There are 95,000 trucks delivering packages every day, and each one needs a route assignment. These routes are not independent: removing a stop from one means adding it to another. The resulting problem is staggeringly difficult to solve exactly, and good heuristics are necessary.
The "no-left-turn" innovation is a heuristic that helps realize the difference between driving time and driving distance. Or, as Jim Winestock, a UPS vice president in Atlanta, explains, "I know it drives my wife crazy, but I've been known to pass up drug stores, three or four on the left-hand side of the road, just to get to the one on the right."
Dan Gillick blogs for Scientific Blogging.
