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 traveling salesman problem. For a large number of cities, however, such a brute-force approach requires a huge amount of computation.

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

Optimal route for 10 cities.

Nonetheless, researchers have found ways to compute optimal tours for a remarkably large number of cities. One such route, worked out in May 2004, visits all 24,978 cities, towns, and villages in Sweden. The tour is about 72,500 kilometers long. No shorter route is possible.

The Sweden tour was found by David Applegate, Robert Bixby, Vašek Chvátal, William Cook, and Keld Helsgaun.

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

Mathematician Robert Bosch and student Adrianne Herman developed a computer program that brought the traveling salesman problem into the world of art. They used the routes that result from solving the problem to create continuous-line drawings. See "One Continuous Line."

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.

In their procedure for creating continuous-line drawings, Bosch and Herman started with a black-and-white digital image. Each pixel of the image had a grayscale value between 0 (completely black) and 255 (completely white). The picture was then divided into squares, each one consisting of a block of pixels. Next, the average darkness of each square was computed.

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

To find an approximate solution to the corresponding traveling salesman problem, Bosch and Herman used a method developed by William Cook and his collaborators. The resulting tour was a continuous-line drawing of the target image.

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

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

Bosch used the technique to create a number of continuous-line portraits, including ones of Marilyn Monroe and other people. His artful routes sometimes involved 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.

Originally posted January 3, 2005

See also "Constructing Domino Portraits."