No Accidental Tourist

Solving the traveling salesman problem

has been a 16-year passion for Georgia Tech researcher.by T.J. BECKER

Although William Cook couldn’t have helped John Kerry or George Bush with swing voters, he certainly could have designed the optimal campaign tour for them.

The so-called “traveling salesman problem” is a mathematical puzzle, which seeks the most efficient route among a particular number of cities. It is renowned for both its complexity and number of real-world applications.

Illustration: Mac Evans A professor at Georgia Tech’s School of Industrial and Systems Engineering, Cook is a reigning champ of the traveling salesman problem (TSP). This math puzzle, which seeks the most efficient route among a particular number of cities, is renowned for both its complexity and number of real-world applications. For example, practical uses for the TSP include routing trucks for parcel pickups, material handling in warehouses and overhauling gas-turbine engines.

Although easy to state, the problem is tough to solve. And its complexity increases exponentially as more destinations are added to a journey. For example, if you want to visit four cities, there are three potential routes. But if you wish to travel to 12 cities, you’ll confront 20 million possibilities. Jump to 16 cities and you’ll face more than 653 billion paths to ponder.

“Mathematicians didn’t really start studying the TSP until the 1930s, but people have struggled with this problem on their own for ages,” Cook says. For example, Abraham Lincoln was no stranger to the TSP as he traveled from town to town on circuit-court duty.

TSP progress began in the 1950s when linear programming emerged as a computational tool. A 1954 milestone: Three Rand Corp. mathematicians (George Dantzig, Ray Fulkerson and Selmer Johnson) published a TSP solution for 49 cities, an impressive number at the time.

Cook launched his first TSP project in 1988 while a professor at Columbia University in New York, joined by Vašek Chvátal, a math professor at Rutgers University. Later the two researchers recruited David Applegate, a Carnegie Mellon University graduate student, and Robert Bixby, a professor at Rice University in Houston.

In 1992, the four found the optimal route for 3,038 cities, breaking the previous record for 2,392 cities set in 1987 by Manfred Padberg of New York University and Giovanni Rinaldi of the Institute of Systems Analysis and Computer Science in Rome. No small feat,

Discovermagazine deemed their 3,038-city solution one of the top 50 science stories of 1992.Since then, Cook’s team has one-upped itself five times. The researchers solved the TSP for a national tour of 4,461 cities in 1993, 7,397 cities in 1994, 13,509 cities in 1998 and a German tour of 15,113 cities in 2001. In April 2004, they set their current record -- an optimal tour of 24,978 Swedish cities.

The hunt for cutting planesIn attacking the TSP, researchers look at the problem as a 3-D graph. Each city is mapped as a point in space, and lines connecting those points are potential roads, each associated with a particular distance or cost.

William Cook, a professor at Georgia Tech’s School of Industrial and Systems Engineering, is a reigning champ of the traveling salesman problem.

Photo: Gary Meek Download 300 dpi version Finding a feasible route is just part of the problem. The greater challenge lies in proving that route is, indeed, optimal.

“Bounds are used in optimization problems like the TSP to give quality assurance,” Cook says. “The upper bound is the best tour you’ve found so far whereas the lower bound is a figure that you can’t possibly improve upon. You’re trying to squeeze the two together so they meet.”

The primary tools for determining upper bounds are heuristic algorithms, mathematical shortcuts that find economic routes without requiring the computer to check every possibility. Linear programming, a relatively young field of math used for optimization problems, helps determine the lower bounds. Yet linear programming has a drawback: It also produces illegal solutions, such as using one-third of a road and two-thirds of another.

To eliminate these fractional solutions, Dantzig, Fulkerson and Johnson introduced an algorithmic technique known as “cutting planes.” Cook and his colleagues employed the same method, but found more sophisticated cutting planes, which enabled them to solve larger problems.

“Not all cutting planes are created equal,” Cook explains. “The goal is not simply to cut off the fractional solution, but rather to solve the TSP. And each fractional point gives you some clue about where a good tour might be.”

Another innovation introduced by Cook’s team was “strong branching,” which helped improve the lower bound when cutting planes stopped making progress. Other researchers had experimented with branching techniques, but hadn’t fully exploited them, Cook says.

This image represents an optimal tour through 13,509 cities in the United States.

Image Courtesy William Cook Branching splits the tour into two collections each time mathematicians consider a road between two cities: 1) all tours that use the road in question and 2) all tours that don’t use the road. Although this helps mathematicians improve bounds, it also doubles the size of the problem.

“Branching is such a major decision, we decided to spend lots of computer time on it and test each road in question before we branch,” Cook explains. “It’s a very simple plan in retrospect and strong branching is now widely used in integer programming and other problems.”

Yet perhaps the team’s biggest TSP innovation has been “local cuts,” a technique that automates the cutting-plane process. Instead of drawing the fractional solutions on paper and spotting the cutting planes by sight, as Dantzig did, Cook’s team developed a computer program to identify cutting planes. This breakthrough enabled them to scale from 7,397 cities in 1994 to 13,509 cities in 1998.

In 1994, the researchers created Concorde, a computer code that incorporates the local-cuts technique for solving TSP and related optimization problems. Written in ANSI C programming language, the code is available for academic research and can be licensed for commercial use.

Reality TSPObviously, a 25,000-city tour is a far-fetched endeavor for even the most zealous traveler. “Yet the whole point of solving the TSP is to find solutions to real-world applications,” Cook says. “The TSP serves as a platform for discovering new algorithmic ideas.”

Here the traveling salesman problem is applied to obtain optimal drilling of a printed circuit board with 3,038 holes.

Image Courtesy William Cook TSP solutions have been used in transportation planning, operations, facility location, production scheduling and supply-chain management. For example, the TSP can help reduce manufacturing costs by determining the most efficient pattern for punching holes in a printed circuit board or other objects. Although the drilling technology may vary, the holes to be drilled represent the number of cities, and the time it takes to move the drill head from one hole to the next is the cost of travel.

In particular, the Concorde code has been used by:

• Rand McNally for travel-planning software.

• A semiconductor manufacturer for optimizing scan chains (routes on a chip used for testing purposes) in integrated circuits.

• Researchers at the National Institutes of Health in genome sequencing, using data on different radiation hybrid (RH) panels to construct a single RH map for a genome. The TSP software has enabled researchers to produce higher quality maps in a shorter timeframe than software specifically designed for RH mapping.

With each new tour, Cook and his colleagues have continued to improve the Concorde code. Yet the Swedish tour will probably be the last TSP record established with Concorde, Cook says. Even with recent refinements, the code is limited as to how big a problem it can handle.

With that in mind, Cook and his collaborators have turned to a new problem: Finding an optimal route for a “World Tour” -- 1.9 million populated places around the globe.

Why such an ambitious undertaking? “Tackling that big of a problem forces you to think in a different way,” he says. “One tactic we’re trying is to break the problem into smaller pieces that we can solve and then glue these smaller solutions together. It’s a divide-and-conquer approach.’’

This figure shows an optimal world tour of 1.9 million cities.

Image Courtesy William Cook Assisting Cook on the World Tour project are Daniel Espinoza and Marcos Goycoolea, two graduate students from Georgia Tech’s School of Industrial and Systems Engineering. Keld Helsgaun, a Danish researcher at Roskilde University, is also collaborating on the project.

In related research for the Office of Naval Research, Cook is developing QSopt, which provides a set of functions for creating, manipulating and solving mixed-integer programming (MIP) problems for large applications related to logistics and planning. For a project funded by the National Science Foundation, Cook is generalizing the concept of local cuts for MIP use.

“Many industries, such as telecommunications, are dependent on discrete optimization to guide them through complex design procedures,” Cook says. His goal is to develop new methods for solving MIP and optimization problems that are beyond the reach of existing techniques.

When it comes to solving optimization problems like the TSP, patience pays off. There was a 40-year gap between Dantzig’s cutting-plane technique and the Concorde code. It might take a couple of decades to crack the World Tour, Cook admits.

So it’s fortunate that the TSP is an addictive endeavor. Sixteen years after beginning his first TSP project, Cook remains fascinated by the challenge.

“It’s a beautifully simple problem,” he explains. “You can describe it easily, yet it seems impossible to solve. That combination makes you focus on what makes the problem hard. Optimization is all about solving hard problems.”

A portion of this article is based upon work supported by the Office of Naval Research under Award No. N00014-03-1-0040. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the Office of Naval Research.For more information,William Cook at 404-385-4179 or 609-688-1324 or william.cook@isye.gatech.edu.

Contents Research Horizons GT Research News GTRI Georgia Tech

Send questions and comments regarding these pages to webadmin@edi.gatech.edu

Last updated: November 20, 2004