Ivars Peterson's MathTrek

January 3, 2005

Artful Routes

A traveling salesman must visit customers in a given number of cities scattered across the country. The problem is to find the shortest route that takes the traveler just once to each city before returning home.

Listing all possible routes, calculating the length of each one, and picking the shortest is one possible strategy for solving the problem. For a large number of cities, however, such a brute-force approach requires a huge amount of computation.

Optimal route for 10 cities.

For example, to find the shortest possible route to visit 10 cities, a computer would have to evaluate 362,880 (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) possibilities. As the number of cities increases, the number of possible routes skyrockets.

This image represents an optimal tour through 13,509 cities in the United States.
Credit: Courtesy of William Cook, Georgia Tech

Nonetheless, researchers have found ways to compute optimal tours for a remarkably large number of cities. The current record-holder, computed in May 2004, is a tour that visits all 24,978 cities, towns, and villages in Sweden (see http://www.tsp.gatech.edu/sweden/index.html). The route is about 72,500 kilometers long. No shorter route is possible.

This record tour was found by David Applegate of AT&T Labs–Research, Robert Bixby of Rice University, Vašek Chvátal of Rutgers University, William Cook of Georgia Tech, and Keld Helsgaun of Roskilde University.

Mathematician Robert Bosch and student Adrianne Herman of Oberlin College in Ohio have now developed a computer program that brings the traveling salesman problem into the world of art. They use the routes that result from solving the problem to create continuous-line drawings.

Art teachers are fond of asking beginning students to make such drawings. The idea is to look at an object, place the tip of your pencil on a sheet of paper, then make a drawing of the object without letting the pencil's tip leave the paper until the picture is finished. That's a lot like finding an optimal route that links a large number of cities.

Bosch and Herman start with a black-and-white digital image. Each pixel of the image has a grayscale value between 0 (completely black) and 255 (completely white). The picture is then divided into squares, each one consisting of a block of pixels. Next, the average darkness of each square is computed.

A blank digital "canvas" is then divided into squares to match those of the original image. The computer randomly places points (representing cities) within each square in such a way that the points are uniformly distributed within the square. The number of points placed in each square is related to the square's darkness. Distances between the points are then computed.

To find an approximate solution to the corresponding traveling salesman problem, Bosch and Herman use a method developed by the same group that recently found the record tour. The resulting tour is a continuous-line drawing of the target image.

Approximately solving the traveling salesman problem for a set of 27,486 carefully placed cities produces an impressive likeness of the Mona Lisa.
Credit: Courtesy of Robert Bosch

Magnified view of the route required to create part of a continuous-line portrait of the Mona Lisa.
Credit: Courtesy of Robert Bosch

Bosch has used the technique to create a number of continuous-line portraits, including ones of Marilyn Monroe and other people. His artful routes sometimes involve more than 100,000 cities.

So, the same sorts of techniques used for solving optimization problems—which range from routing telephone calls and constructing schedules to allocating resources and designing networks—can also play a role in creating ingenious artworks.

References:

Becker, T.J. 2004. No accidental tourist. Research Horizons (Fall). Available at http://gtresearchnews.gatech.edu/reshor/rh-f04/tsp.html.

Bosch, R., and A. Herman. 2004. Continuous line drawings via the traveling salesman problem. Operations Research Letters 32(July):302-303. Preprint available at http://www.oberlin.edu/math/faculty/bosch/tspart.pdf.

Fowler, Y.G. 2004. One continuous line. Oberlin Alumni Magazine (Spring). Available at http://www.oberlin.edu/alummag/spring2004/ats.html.

Peterson, I. 2003. Constructing domino portraits. MAA Online (April 14).

______. 2000. Calculating swarms. Science News 158(Nov. 11):314-316. Available at http://www.sciencenews.org/articles/20001111/bob10.asp.

______. 1997. The traveling monkey. MAA Online (July 7).

Robert Bosch has a Web page at http://www.oberlin.edu/math/faculty/bosch.html. His domino artwork is featured at http://www.dominoartwork.com/.

Information about the traveling salesman problem is available at http://www.tsp.gatech.edu/.