The Shortest Route Between All the Pubs in the UK
From John o’ Groats to Land’s End (1) – that proverbial phrase covers the entire island of Great Britain. Here is a novel one: from the Bells But & Ben in Yell to the Witchball in The Lizard. That’s the northernmost and southernmost pub in Britain, respectively. This map shows the shortest route between both – and every other pub in the UK, all 24,725 of them. That is one massive pub crawl.
But why? Computational mathematics, is why. This monster of a map is a solution to a cartographic conundrum called the Travelling Salesman Problem (2).
Suppose you are a salesman presenting your wares at several locations today. The problem: work out the shortest route between all, taking into account that you need to start from home and arrive back there at the end of the day. For a small number of locations, the solution to that problem usually is self-evident. Add enough locations, and the solution becomes more difficult. Difficult enough for a manual to be published in 1832 called Der Handlungsreisende, proposing a number of routes for salesmen travelling through Germany and Switzerland.
The solutions it proposed were based on experience, but the Travelling Salesman Problem (TSP) tantalised scientists, who sought to formulate a universal answer. The first to come to grips with the problem was the 19th-century Irish mathematician W.R. Hamilton, who developed the icosian game, the purpose of which is to find a Hamiltonian cycle in a dodecahedron (cf. inf.): a circuit that starts and ends at the same point, and visits all other points only once (3).
Another important TSP theorist was Viennese mathematician Karl Menger, who in the 1930s conceded that
“of course, this problem is solvable by finitely many trials, but rules which would push the number of trials below the number of permutations of the given points are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route”.
As Menger states, the easiest solution to the TSP is to simply to try all options. But even for a relatively low number of locations, the number of variables is enormous – for just 10 cities there are over 180,000 combinations, for example.
But a systematic solution remains elusive even today, as computers are currently able to calculate solutions for millions of points only to within 2% to 3% of the optimal result (4).
The TSP has many useful applications, from finding the shortest mailman routes to devising the optimal sequence to drill holes in circuit boards, and even calculating the easiest way for Santa to complete his annual one-night tour of all the chimneys in the world. Perhaps the most important consequence of the TSP is that there are no known algorithms to crack the codes on which we rely to keep our data secure.
Finding the shortest route between all pubs in Great Britain may not have figured high on the list of TSP issues to be solved, but solved it now has been, thanks to the Faculty of Mathematics at the University of Waterloo in Canada.
They attacked the TSP by mapping out the shortest-possible walking tour through the pubs of the United Kingdom, or as they so scientifically called the project: UK24727, after the number of pubs (5) involved. Some stats:
This line drawing conveys the route of the tour, which also includes ferry excursions off the British mainland for pub tours in the Hebrides, Orkney and Shetland islands, the isle of Man and Northern Ireland.
The entire map, with a Google Maps markers for each of the pubs, gives the impression that most of Britain is covered by an unbroken canopy of red balloons – darker areas indicating a concentration of balloon ridges, where the greater density of pubs suggests the presence of large cities.
Apart from solving a mathematical problem, the map also has an obvious practical use, for planning your next pub crawl. Attempting the entire route is not recommended, but zoom in to certain areas or the cities listed in the menu on the right, and plot your next excursion.
Like this drinking trip of the Hebrides: arrive by ferry from Oban, slake your thirst at the Am Politician in South Uist, wet your whistle at the Langass Lodge in Loch Eport, polish your pint at Harmersay House in Lochmaddy and get one for the road in the Carlton at Stornoway, before jumping on the ferry back to the mainland at Ullapool (where you can continue indulging at the Ceilidh Place).
Or why not find the watering holes closest to the UK’s other two extremities: have a session the Black Cat in Belleek, the westernmost pub in the realm, and take in spirits at the Royal Falcon in Lowestoft, probably the easternmost pub – there are quite a few bunched together in that area, so you might have to visit a few more.
Visit the legendary watering holes of London in the time-saving succession devised by these thirsty mathematicians: make your way from De Hems to the French House via the Golden Lion and then on to… wait, weren’t we going in the other direction? Doesn’t matter: thanks to this Hamiltonian cycle, we’ll end up here again eventually.
Having devised the world’s longest pub crawl, the TSP team at Waterloo University is gearing up for the next challenge: sending their putative salesman on the shortest possible tour past all 49,603 places listed in the U.S. National Register of Historic Places. “This problem is quite a beast”, they admit.
“We currently have a tour of length 350,201,525 meters. That is a little less than the distance to the moon. But we don’t know if this is actually the shortest tour. There might possibly be a tour that is 196 meters shorter than our tour. Ouch! Close is just not good enough”.
Find the entire map here. Warning: loads slowly! For more information on the UK pub crawl, and other road-TSP projects covering 120 German cities, 50 U.S. landmarks and others, see the TSP page at the University of Waterloo’s Mathematics Faculty. Many thanks to Joel Winten and Folkard Wohlgemuth for sending in this map.
Strange Maps #818
Got a strange map? Let me know at [email protected].
(1) John o’ Groats, in Scottish Gaelic Taigh Iain Ghròt, is a village of 300 at the northern tip of the Scottish mainland. It is the northernmost inhabited place in Great Britain. Dunnet Head, about fifteen miles (24 km) to the east, is the northernmost place per se. John o’ Groats was named after Jan de Groot, a Dutchman who operated a ferry from here to Orkney around the year 1500.
Land’s End, in Cornish Penn an Wlas, is a headland and holiday resort at the western tip of Britain (7), on the Penwith peninsula in Cornwall. It is about 33 miles (53 km) east of Lizard Point, Britain’s southernmost extremity. The 838 miles (1,349 km) trip between John o’ Groats and Land’s End is the longest one possible between two inhabited places in Britain.
(2) Or in this case, the Travelling Alesman Problem.
(3) Related to the Seven Bridges of Königsberg problem, proven by Euler to be unsolvable. More on that at #536.
(4) For actual travelling salesmen, not the theoretical ones dreamt up by Hamilton, Menger e.a., the TSP is even more complex, for distance is only one of the variables; the more important ones are time and money: How long does it take to get anywhere, and how much does it cost? For example, is it worth it to take the plane instead of the car to get from A to B and C and back to A again? That depends on whether the value of the time saved outweighs the value of the extra money spent.
(5) Since the exact number of pubs fluctuates due to closures and openings of various establishments, the study was based on the 24,727 pubs as listed in on the Pubs Galore website.
(6) I.c. the route connecting the 200 Tesla superchargers in the United States, a road-TSP problem solved by Mortada Meyhar. Below his map of the Travelling Tesla Salesman.
(7) Actually, the westernmost point of England, but not of Britain. As reader Kevin Jones points out, “the most westerly point of mainland island of Great Britain is Corrachadh Mòr, only 0.5 degree further west than Land’s End. If you are ever in Scotland, it is wonderful place to visit, with its views over the islands of the Inner Hebrides. The geology is very interesting, it being a remnant of an igneous complex from the splitting of the North Atlantic about 60 million years ago”.
