85,900-city traveling salesman map

By Olena Shmahalo

January 29, 2013

The largest solved traveling salesman problem, an 85,900-city route calculated in 2006. The layout of the “cities” corresponds to the design of a customized computer chip created at Bell Laboratories, and the solution exhibits the shortest path for a laser to follow as it sculpts the chip.
Comment

Illustration Courtesy of David Applegate, Robert Bixby, Vasek Chvatal and William Cook

Comment on this article

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.