Was ist die optimale Lösung für den TSP-Wettbewerb von Procter and Gamble aus dem Jahr 1962?

Im Jahr 1962 konnten Sie einen Preis von 10 000 USD (ungefähr 80 000 USD in heutigem Geld) gewinnen, wenn Sie die Lösung für ein in 33 Städten definiertes Problem mit euklidischen Handlungsreisenden fanden.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Wenn man das Bild betrachtet, scheint das Problem ziemlich einfach zu sein. Ich konnte jedoch keine detaillierteren Ressourcen zu dem Problem finden.

Kennt jemand weitere Details, wie die genauen Entfernungen und eine optimale Lösung?

optimization traveling-salesman Martin Drozdik
quelle

Ah, die 1960er Jahre ... als niemand Firmen, die Werbung für ihre Produkte machten, mit den Augenlidern schlug, indem sie Polizisten zeigten, die leicht bekleidete Frauen belästigten.

David Richerby

Antworten:

Ausführliche Informationen finden Sie in Robert L. Karg und James L. Thompson, Ein heuristischer Ansatz zur Lösung von Problemen mit Handelsreisenden ( Management Science , 10 (2): 225–248, 1964). Das PDF ist bei JStor und Informs.org erhältlich (beide kostenpflichtig). Dies ist das Papier, das die optimale Tour von 10.861 Meilen produziert hat. Es enthält auch die vollständige Entfernungstabelle, aber ich werde das hier nicht wiedergeben, da es viel zu viel Tipparbeit ist.

Die Lösung wird auch auf Seite 15 des Problems des Handlungsreisenden von David L. Applegate, Robert E. Bixby, Vasek Chvátal und William J. Cook (Princeton University Press, 2007) erläutert . Die Einführung zu diesem Buch, die die entsprechende Seite enthält, ist beim Verlag frei erhältlich .

David Richerby
quelle

"Ein direkterer Ansatz wäre natürlich, einfach alle möglichen Touren in Betracht zu ziehen, aber diese Zahl wächst so schnell, dass die Überprüfung aller Touren auf eine Instanz von bescheidener Größe, sagen wir, in 50 Städten weit über die Möglichkeiten der schnellsten Supercomputer von heute hinausgeht . " (von Linked Applegate et al.)

Jacob Krall