On Spacefilling Curves & the Traveling Salesman Problem

“Paul Goldsman used the spacefilling curve heuristic to solve the same instance [15,112 cities in Germany]. Our solution was about 34% longer. At a leisurely 600 km of travel per day this means the time to drive our solution would be about 147 days versus 110 days for the solution of Bixby, Chvatal, and Cook. But our computation took less than a second on a cheap laptop, so here is the tradeoff: Use our heuristic and you get a reasonable route immediately. Alternatively, configure a network of 110 processors, then spend two months computing the shortest route to save a month of driving.”

Fascinating & accessible write-up on the use of spacefilling curves to solve the traditional traveling salesman problem. The researchers have already applied their technique to practical good use: routing blood for the Red Cross, delivery routes for Meals-on-Wheels and to target a space-based laser. (Ironic; life & death.)