In the final weeks of the general election campaign, the party leaders are criss-crossing the country.
But not the whole country. Their destinations are mostly the marginal constituencies, the ones that will decide the outcome on May 7.
It’s a logistical nightmare. Working out the shortest round trip between a fixed number of points is a well-studied and notoriously difficult mathematical problem, usually called the Travelling Salesman Problem, or TSP.
The difficulty arises from the number of possible tours. With, say, 50 places to visit, there are 49 x 48 x 47 x … x 3 x 2 x 1 ways to travel between them. This number is 63 digits long:
608281864034267560872252163321295376887552831379210240000000000
It’s absurdly big. Humungous! So, just say we wanted to find the shortest route between the 50 most marginal constituencies, how would we do it?
I asked Bill Cook, of the University of Waterloo in Canada. He is the world expert on the TSP and the author of the excellent popular maths book In Pursuit of the Traveling Salesman.
First of all, I had to supply him with 50 post codes, one in each constituency. I chose significant destinations, usually the town hall but in some cases a football stadium, a pub and in Scotland, a castle. The Guardian election team had supplied me with the constituencies, and you can see that with the exception of Northern Ireland they cover pretty much the whole country.
We all know that when you stick two addresses in Google Maps, it gives you the shortest distance between them. Bill entered the 50 post codes, which produced a list of 492 = 2401 distances between any two post codes.
Armed with this data, he entered them in Concorde, his massive TSP-solving computer programme. By hand, the computation might have taken a few people a few weeks. It took Concorde 0.23 seconds.
And the map is here. The drive is 2,669 miles long and will take 61hs 44mins.
I find looking at the route fascinating. Even though the problem is difficult, once you see optimal route it seems so obvious!
The marginal constituencies are often seen as a country within a country. So it’s interesting to see just how they fit together geographically.
For Concorde, which Bill has been tweaking for more than a decade, solving the TSP for 50 points is a cinch. But finding a tour gets significantly more difficult the more points you add. “If you want to solve the problem in under a day, then 2500 cities is about the limit.”
In 2004, Bill worked out the shortest tour of all 24,978 towns in Sweden – which remains the largest example of a TSP tour ever worked out. It took 84.8 years of computer time.
There are about 43,000 cities, towns and villages in the UK. Bill estimates that to find the shortest route between all these places would now take about a hundred years of computer time “Running [computers] in parallel this could be done in several months on the network I have at Waterloo,” he said.
No chance of a complete UK TSP tour before May 7, then.
When the number of points gets even higher, computer science hits a wall. “Even if you throw the kitchen sink at the problem, no one can currently solve examples with 100,000 points,” Bill laments.
So: off we go! Starting at the Tate Modern, in Bermondsey and Southwark, our first destination is Brighton Kemptown before returning up the M 23 heading right into Kent for the Thanets, then Essex and East Anglia:
Continuing north and passing through Nick Clegg’s Sheffield Hallam we take a detour west into Lancashire...but not too far!
The route gets particularly scenic as we head into Scotland.
Returning to England down the west side now.
Touching the toes of the Island at St Ives.
And back to London in time for dinner...
My latest book Alex Through the Looking-Glass: How Life Reflects Numbers and Numbers Reflect Life is just out in paperback.
If you want to be kept in touch with this blog I’m on Twitter, Facebook and Google+.
