Die kürzeste Strecke in jede Kneipe Englands

pubs-uk

Die Karte oben mit allen Kneipen in UK geht grade rum und auf Reddit findet man sie total ironisch „super helpful“. Die Karte ist tatsächlich in echt total hilfreich, denn sie stammt aus einer Spielerei mit dem Problem des Handlungsreisenden der Uni Waterloo, die auf dieser Karte den kürzesten Weg durch alle Kneipen Englands errechnet hatte.

pubs

Die Tour hat eine Länge von rund 45k Kilometern, was circa 5000 Kilometer länger ist als der Umfang der Erde. Hier die Strecke und alle Pubs auf Google Maps. Happy travelboozing.

The optimal tour has length 45,495,239 meters. To be clear, our main result is that there simply does not exist any pub tour that is even one meter shorter (measuring the length using the distances we obtained from Google) than the one produced by our computation. It is the solution to a 24,727-city traveling salesman problem (TSP).

The UK Pubs tour is easily the largest such road-distance TSP that has been solved to date, having over 100 times more stops than any road-distance example solved previously by other research groups.

travl