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 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: 

  • Solving this TSP 'manually' would have required checking a number of possibilities that is expressed by a one followed by 100,000 zeroes.
  • UK24727 was completed over two years. It is the largest road-distance TSP solved to date, covering 100 times more stops than any other similar example (6).
  • The optimal walking tour that stops at all 24,727 pubs and still gets you home safe (if very exhausted and slightly tipsy) is 45,495.2 km (28,269.4 mi) long.
  •  

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

    3D printing might save your life one day. It's transforming medicine and health care.

    What can 3D printing do for medicine? The "sky is the limit," says Northwell Health researcher Dr. Todd Goldstein.

    Northwell Health
    Sponsored by Northwell Health
    • Medical professionals are currently using 3D printers to create prosthetics and patient-specific organ models that doctors can use to prepare for surgery.
    • Eventually, scientists hope to print patient-specific organs that can be transplanted safely into the human body.
    • Northwell Health, New York State's largest health care provider, is pioneering 3D printing in medicine in three key ways.
    Keep reading Show less
    Big Think Edge
    • Push Past Negative Self-Talk: Give Yourself the Proper Fuel to Attack the World, with David Goggins, Former NAVY SealIf you've ever spent 5 minutes trying to meditate, you know something most people don't realize: that our minds are filled, much of the time, with negative nonsense. Messaging from TV, from the news, from advertising, and from difficult daily interactions pulls us mentally in every direction, insisting that we focus on or worry about this or that. To start from a place of strength and stability, you need to quiet your mind and gain control. For former NAVY Seal David Goggins, this begins with recognizing all the negative self-messaging and committing to quieting the mind. It continues with replacing the negative thoughts with positive ones.

    Maps show how CNN lost America to Fox News

    Is this proof of a dramatic shift?

    Strange Maps
    • Map details dramatic shift from CNN to Fox News over 10-year period
    • Does it show the triumph of "fake news" — or, rather, its defeat?
    • A closer look at the map's legend allows for more complex analyses

    Dramatic and misleading

    Image: Reddit / SICResearch

    The situation today: CNN pushed back to the edges of the country.

    Over the course of no more than a decade, America has radically switched favorites when it comes to cable news networks. As this sequence of maps showing TMAs (Television Market Areas) suggests, CNN is out, Fox News is in.

    The maps are certainly dramatic, but also a bit misleading. They nevertheless provide some insight into the state of journalism and the public's attitudes toward the press in the US.

    Let's zoom in:

    • It's 2008, on the eve of the Obama Era. CNN (blue) dominates the cable news landscape across America. Fox News (red) is an upstart (°1996) with a few regional bastions in the South.
    • By 2010, Fox News has broken out of its southern heartland, colonizing markets in the Midwest and the Northwest — and even northern Maine and southern Alaska.
    • Two years later, Fox News has lost those two outliers, but has filled up in the middle: it now boasts two large, contiguous blocks in the southeast and northwest, almost touching.
    • In 2014, Fox News seems past its prime. The northwestern block has shrunk, the southeastern one has fragmented.
    • Energised by Trump's 2016 presidential campaign, Fox News is back with a vengeance. Not only have Maine and Alaska gone from entirely blue to entirely red, so has most of the rest of the U.S. Fox News has plugged the Nebraska Gap: it's no longer possible to walk from coast to coast across CNN territory.
    • By 2018, the fortunes from a decade earlier have almost reversed. Fox News rules the roost. CNN clings on to the Pacific Coast, New Mexico, Minnesota and parts of the Northeast — plus a smattering of metropolitan areas in the South and Midwest.

    "Frightening map"

    Image source: Reddit / SICResearch

    This sequence of maps, showing America turning from blue to red, elicited strong reactions on the Reddit forum where it was published last week. For some, the takeover by Fox News illustrates the demise of all that's good and fair about news journalism. Among the comments?

    • "The end is near."
    • "The idiocracy grows."
    • "(It's) like a spreading disease."
    • "One of the more frightening maps I've seen."
    For others, the maps are less about the rise of Fox News, and more about CNN's self-inflicted downward spiral:
    • "LOL that's what happens when you're fake news!"
    • "CNN went down the toilet on quality."
    • "A Minecraft YouTuber could beat CNN's numbers."
    • "CNN has become more like a high-school production of a news show."

    Not a few find fault with both channels, even if not always to the same degree:

    • "That anybody considers either of those networks good news sources is troubling."
    • "Both leave you understanding less rather than more."
    • "This is what happens when you spout bullsh-- for two years straight. People find an alternative — even if it's just different bullsh--."
    • "CNN is sh-- but it's nowhere close to the outright bullsh-- and baseless propaganda Fox News spews."

    "Old people learning to Google"

    Image: Google Trends

    CNN vs. Fox News search terms (200!-2018)

    But what do the maps actually show? Created by SICResearch, they do show a huge evolution, but not of both cable news networks' audience size (i.e. Nielsen ratings). The dramatic shift is one in Google search trends. In other words, it shows how often people type in "CNN" or "Fox News" when surfing the web. And that does not necessarily reflect the relative popularity of both networks. As some commenters suggest:

    • "I can't remember the last time that I've searched for a news channel on Google. Is it really that difficult for people to type 'cnn.com'?"
    • "More than anything else, these maps show smart phone proliferation (among older people) more than anything else."
    • "This is a map of how old people and rural areas have learned to use Google in the last decade."
    • "This is basically a map of people who don't understand how the internet works, and it's no surprise that it leans conservative."

    A visual image as strong as this map sequence looks designed to elicit a vehement response — and its lack of context offers viewers little new information to challenge their preconceptions. Like the news itself, cartography pretends to be objective, but always has an agenda of its own, even if just by the selection of its topics.

    The trick is not to despair of maps (or news) but to get a good sense of the parameters that are in play. And, as is often the case (with both maps and news), what's left out is at least as significant as what's actually shown.

    One important point: while Fox News is the sole major purveyor of news and opinion with a conservative/right-wing slant, CNN has more competition in the center/left part of the spectrum, notably from MSNBC.

    Another: the average age of cable news viewers — whether they watch CNN or Fox News — is in the mid-60s. As a result of a shift in generational habits, TV viewing is down across the board. Younger people are more comfortable with a "cafeteria" approach to their news menu, selecting alternative and online sources for their information.

    It should also be noted, however, that Fox News, according to Harvard's Nieman Lab, dominates Facebook when it comes to engagement among news outlets.

    CNN, Fox and MSNBC

    Image: Google Trends

    CNN vs. Fox (without the 'News'; may include searches for actual foxes). See MSNBC (in yellow) for comparison

    For the record, here are the Nielsen ratings for average daily viewer total for the three main cable news networks, for 2018 (compared to 2017):

    • Fox News: 1,425,000 (-5%)
    • MSNBC: 994,000 (+12%)
    • CNN: 706,000 (-9%)

    And according to this recent overview, the top 50 of the most popular websites in the U.S. includes cnn.com in 28th place, and foxnews.com in... 27th place.

    The top 5, in descending order, consists of google.com, youtube.com, facebook.com, amazon.com and yahoo.com — the latter being the highest-placed website in the News and Media category.
    Keep reading Show less
    Big Think Edge
    • Master Execution: How to Get from Point A to Point B in 7 Steps, with Rob Roy, Retired Navy SEALUsing the principles of SEAL training to forge better bosses, former Navy SEAL and founder of the Leadership Under Fire series Rob Roy, a self-described "Hammer", makes people's lives miserable in the hopes of teaching them how to be a tougher—and better—manager. "We offer something that you are not going to get from reading a book," says Roy. "Real leaders inspire, guide and give hope."Anybody can make a decision when everything is in their favor, but what happens in turbulent times? Roy teaches leaders, through intense experiences, that they can walk into any situation and come out ahead. In this lesson, he outlines seven SEAL-tested steps for executing any plan—even under extreme conditions or crisis situations.