Finding the shortest route between every Oxford college

• The travelling scholar problem
• Cooking your own optimal tours at home
• Why is the TSP difficult?
• Appendix: Some specifics
• References and more links

Some runs can be physically hard: the route might be very long, there might be lots of elevation gain, the path might be muddy. But fairly few runs are computationally hard in that you have to solve a difficult optimisation problem in order to run them. The travelling salesman problem (or “TSP”) is a graph-theoretical problem that leads to computationally hard running routes. Formally, it is defined like so:

TSP (formally): Let $G = (V, E, w)$ be a weighted graph where:

• $V$ is a finite set of vertices
• $E \subseteq V \times V$ is a finite set of edges, a symmetric relation on vertices
• $w : E \to \mathbb R _ {\ge 0}$ is a symmetric function assigning each edge $(u, v) \in E$ a positive weight

A tour in $G$ is a sequence of vertices $(v _ 0, \ldots, v _ k)$ such that $v _ 0 = v _ k$ and each vertex occurs in $V$ exactly once. Define the weight of a tour as

Call a tour optimal if it is the lowest weight among all possible tours. Given such a $G$, can you find an optimal tour?

But informally, it asks the question:

TSP (informally): Given a list of landmarks and distances between them, can you find the shortest-distance route that visits every landmark?

So called the “travelling salesman” problem because it lets you save the most amount of fuel as you drive from city to city selling your product, the TSP is very famous in computer science as a prototypical example of a hard optimisation problem: it’s very likely that it’s impossible to write a computer program that does much better than checking every possible route.

The travelling scholar problem

Many online examples for the travelling salesman problem focus use abstract examples on made-up graphs. Here’s a more concrete example. This is a plot of every college and permanent private hall in Oxford:

The travelling salesman problem asks: what is the shortest running route that visits every college? Here is one optimal solution:

1. Christ Church
2. Pembroke College
3. Oriel College
4. Corpus Christi College
5. Merton College
6. The Queen’s College
7. St Edmund Hall
8. University College
9. St Hilda’s College
10. Magdalen College
11. St Catherine’s College
12. Linacre College
13. Mansfield College
14. Harris Manchester College
15. New College
16. Hertford College
17. All Souls College
18. Brasenose
19. Lincoln College
20. Jesus College
21. Exeter College
22. Balliol College
23. Trinity College
24. Wadham College
25. Reuben College
26. Keble College
27. Lady Margaret Hall
28. Wolfson College
29. St Hugh’s College
30. Kellogg College
31. Wycliffe Hall
32. St Antony’s College
33. St. Anne’s College
34. Green Templeton College
35. Somerville College
36. Regen’s Park Colelge
37. St Cross College
38. Blackfriars
39. St John’s College
40. Worcester College
41. Nuffield College
42. St. Peter’s College
43. Campion Hall
44. Christ Church

And here’s what actually running it looks like:

(GPX file of the route).

Of course, it doesn’t matter if you start and end at any other college or run around in reverse since it will still be the same distance. This solution is optimal according to the software I used, assuming that it knows the accurate walking distances between each college. It’s possible that there’s shortcuts that it doesn’t know about (e.g. in the above it’s actually possible to go diagonally across the park next to “New Marston Meadows”) and this could change the solution.

Cooking your own optimal tours at home

It would be very easy to come up with a route between every college by hand, but you wouldn’t know that it was optimal. Here’s how you can use a computer to find a guaranteed optimal solution.

• Ingredients: I used Wolfram Language (formely Mathematica), but if you don’t have access to this, it would also be possible to find a tour using free and open source tools like OR-Tools (Python, C# or Java) as well as manually calculating all the $N^2$ pairwise distances for the distance matrix.
• Make a spreadsheet of the coordinates for every landmark you want to visit. I did this using Google Sheets and Google Maps. Google Maps has a very handy feature where if you right click anywhere, you can immediately copy the coordinates of that point to the clipboard.

• Convert this into a list that can be used in Wolfram Language. I did this by writing an Google Sheets formula which would generate the strings you see on the right in the image above. There’s probably much better ways of doing this but I’m not very familiar with Wolfram. I used the following formula for this: =CONCATENATE("{", char(34), A1, char(34), ", ", "GeoPosition[{", B1, "}]", "},")

• Use the following Wolfram Language program to actually calculate the optimal tour:

namedCoords = {...the list from above...};

distanceFunc[i_, j_] := TravelDistance[{namedCoords[[i, 2]], namedCoords[[j, 2]]}, TravelMethod -> "Walking"];

tour = FindShortestTour[Range[Length[namedCoords]], DistanceFunction -> distanceFunc, PerformanceGoal -> "Quality"];

namedTour = namedCoords[[#]] & /@ tour[[2]]; namedTour

• There are two important things in the above code:
  • Firstly, the TravelMethod needs to be set to "Walking" so that it will use walking distances rather than driving distances.
  • Secondly, setting PerformanceGoal to "Quality" ensures that the solution is optimal rather than an approximation. If you have a lot landmarks, you might need to set the goal to "Speed" instead for it to find a route in any reasonable amount of time. After all, it is a hard problem!
• Look at the list and then plot the route. The above program prints out a list of landmark names. I then used plotaroute.com to create a GPX file which routed between each of the colleges in order.
• Go and run/walk/drive it! If you’re lacking motivation while you’re out actually completing it, remember out of all possible running routes you could’ve made, this one will be the shortest.

Why is the TSP difficult?

One way of measuring the difficulty of problems is the idea of a complexity class. These are ways of categorising problems by measuring the amount of time or space that’s needed to solve them according to how complicated their input is.

Two very important classes are $\mathbf P$, the set of all problems solvable in “polynomial time”, and $\mathbf{NP}$, the set of all problems solvable in “nondeterministic polynomial time”. Skimming over a lot of detail, if a problem is in $\mathbf P$ it means that there’s a computer program that solves it in an amount of time that scales polynomially with the size of the input. Polynomial growth roughly means that the time it takes is given by a formula like $\text{time taken} = \text{size of input}^n$ for some $n$ that stays the same.

If a problem is in $\mathbf{NP}$, it means that it has an algorithm where the amount of time it takes scales exponentially with the size of the input (sort of). For example, the time taken might be given by a formula like $\text{time taken} = n^{\text{size of input}}$ where $n$ is once again a number that stays the same (and is greater than $1$). This is much faster than polynomial!

To be slightly more specific, $\mathbf P$ and $\mathbf{NP}$ also contain all problems where the time it takes to solve them grows slower than polynomially or exponentially. As a consequence of this definition, every problem that is in $\mathbf P$ is also in $\mathbf{NP}$ since exponential growth always beats polynomial growth in the long run. Written mathematically, this is $\mathbf P \subseteq \mathbf{NP}$.

These classes are concerned with “decision problems”: given some input, an algorithm should output true or false depending on whether some condition is met. This includes problems like determining whether a number is prime, checking whether a list is sorted, or seeing if graph admits a Hamiltonian cycle.

The TSP isn’t strictly a decision problem, since a solution to the TSP is instead a path instead of a simple yes or no answer. But it’s possible to convert the TSP into a decision problem by constructing a related question: “given this weighted graph $G = (V, E, w)$ and a positive number $k$, is there a travelling salesman tour with weight less than $k$?”. This question has a yes or no answer and so is a decision problem.

It turns out that you can give an exponential time algorithm for this problem and so it belongs in $\mathbf{NP}$. But this isn’t quite enough to say that the TSP has no algorithm that is quicker than exponential, since to do this, you need to be able to say that the TSP is also not in $\mathbf{P}$.

If the TSP were not in $\mathbf P$, it would imply that $\mathbf P \ne \mathbf{NP}$, which is perhaps the biggest and most famous unsolved problem in computer science. As far as we know, it could be that $\mathbf P = \mathbf{NP}$, and that there is some polynomial time algorithm for TSP, but we just don’t know what that algorithm is. But all evidence so far points towards this not being the case.

Appendix: Some specifics

The tour above uses the walking distance calculated by the TravelDistance function between each college, rather than the straight-line distance. This is to avoid routes that superficially seem to minimise the distance, but actually involve impossible cuts through buildings and grass you’re not supposed to walk on. Interestingly, this actually makes the problem harder – if you’re using straight line distance, then it’s actually an instance of the “metric travelling salesman problem” which is a little easier to solve. For example, the metric travelling salesman problem admits quick approximation algorithms. These are polynomial time algorithms which give you a solution to the TSP, not necessarily optimal, but guaranteed to be within some factor of the optimal. The Christofides algorithm is an approximation algorithm for the TSP which is guaranteed to be at most $1.5$ times the length of the optimal solution.

I used the following coordinates for the colleges. I tried to pick the front of the colleges since the location you get from just typing the name into Google Maps would sometimes be at a random spot inside the college, which might mess up the walking distance calculation made by Wolfram.

References and more links

• [[Notes - ADS HT24, NP-hardness and NP-completeness]]^U
• [[Notes - ADS HT24, Approximation algorithms]]^U
• [[Notes - Models of Computation MT23, Turing machines]]^U
• [[Quantum Computing Since Democritus, Aaronson]]^N, Chapter 6, “$\mathbf P$, $\mathbf{NP}$ and Friends”
• “Travelling salesman problem” on Wikipedia
• “Christofides algorithm” on Wikipedia
• “Complexity class” on Wikipedia