Beam me up, beam me up, beam me uptown. Beam me down, beam me down, beam me back downtown.
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.
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.
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. (…)
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.
image { Peter Crnokrak }
