# The Shortest Route Between All the Pubs in the UK

Plotting out the world's longest pub crawl had a serious, mathematical point

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 19^{th}-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 F*rench 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 #81 8**

Got a strange map? Let me know at strangemaps@gmail.com.

(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".

## Should you defend the free speech rights of neo-Nazis?

Former president of the ACLU Nadine Strossen discusses whether our society should always defend free speech rights, even for groups who would oppose such rights.

- Former ACLU president Nadine Strossen understands that protecting free speech rights isn't always a straightforward proposition.
- In this video, Strossen describes the reasoning behind why the ACLU defended the free speech rights of neo-Nazis in Skokie, Illinois, 1977.
**The opinions expressed in this video do not necessarily reflect the views of the Charles Koch Foundation, which encourages the expression of diverse viewpoints within a culture of civil discourse and mutual respect.**

## Moon mission 2.0: What humanity will learn by going back to the Moon

Going back to the moon will give us fresh insights about the creation of our solar system.

- July 2019 marks the 50th anniversary of the moon landing — Apollo 11.
- Today, we have a strong scientific case for returning to the moon: the original rock samples that we took from the moon revolutionized our view of how Earth and the solar system formed. We could now glean even more insights with fresh, nonchemically-altered samples.
- NASA plans to send humans to a crater in the South Pole of the moon because it's safer there, and would allow for better communications with people back on Earth.

## Top vets urge dog lovers to stop buying pugs and bulldogs

Pugs and bulldogs are incredibly trendy, but experts have massive animal welfare concerns about these genetically manipulated breeds.

- Pugs, Frenchies, boxers, shih-tzus and other flat-faced dog breeds have been trending for at least the last decade.
- Higher visibility (usually in a celebrity's handbag), an increase in city living (smaller dogs for smaller homes), and possibly even the fine acting of Frank the Pug in 1997's
*Men in Black*may be the cause*.* - These small, specialty pure breeds are seen as the pinnacle of cuteness – they have friendly personalities, endearing odd looks, and are perfect for Stranger Things video montages.

## U.S. Air Force warns UFO enthusiasts against storming Area 51

Jokesters and serious Area 51 raiders would be met with military force.

- Facebook joke event to "raid Area 51" has already gained 1,000,000 "going" attendees.
- The U.S. Air Force has issued an official warning to potential "raiders."
- If anyone actually tries to storm an American military base, the use of deadly force is authorized.