Robert Bosch has created a fascinating series of instances of the traveling salesman problem (TSP) that provide continuous-line drawings of well-known pieces of art. Techniques for developing such point sets have evolved over the past several years through work of Bosch and Craig Kaplan.
One of Bosch's instances is the 100,000-point set for the Mona Lisa TSP Challenge. Additional instances range in size up to 200,000 cities, providing a difficult test for TSP solution methods. The data sets are specified in TSPLIB format. We thank Bob for making these beautiful problems available to the research community.
|Original Art||Data Set||Cities|
|da Vinci's Mona Lisa||mona-lisa100K.tsp||100,000|
|van Gogh's Self Portrait 1889||vangogh120K.tsp||120,000|
|Botticelli's The Birth of Venus||venus140K.tsp||140,000|
|Velazquez's Juan de Pareja||pareja160K.tsp||160,000|
|Courbet's The Desperate Man||courbet180K.tsp||180,000|
|Vermeer's Girl with a Pearl Earring||earring200K.tsp||200,000|
The following papers discuss the mathematics behind the selection of city locations for these TSP Art instances.
Pretty examples of other TSP drawings can be found on Robert Bosch's TSP Art page and on the page of Craig Kaplan.
The best known results for the TSP Art instances are given in the table below. The tour length, given in the Best Tour column, is a link to the tour in TSPLIB format. I would be happy to post any improvements you find.
|Problem||Best Tour||Source of Tour|
|mona-lisa100K||5,757,191||Yuichi Nagata (2009)|
|vangogh120K||6,543,609||Kazuma Honda, Yuichi Nagata, Isao Ono (2013)|
|venus140K||6,810,665||Yuichi Nagata (2011)|
|pareja160K||7,619,953||Yuichi Nagata (2011)|
|courbet180K||7,888,731||Kazuma Honda, Yuichi Nagata, Isao Ono (2013)|
|earring200K||8,171,677||Yuichi Nagata (2011)|