ls satyarth.me

about contact archive

Shortest Tour of Cambridge Colleges

What's the most efficient way to visit every college in Cambridge in a single tour? AKA the travelling salesman problem.

I wondered what the most efficient way to visit every college in Cambridge in a single tour was. I investigated. I found the answer.

TL;DR

The shortest tour is:

Selwyn → Clare Hall → Robinson → Churchill → Girton → Fitzwilliam → Murray Edwards → St Edmund’s → Lucy Cavendish → Magdalene → St John’s → Sidney Sussex → Jesus → Christ’s → Emmanuel → Downing → Hughes Hall → Homerton → Peterhouse → Pembroke → St Catharine’s → Corpus Christi → King’s → Gonville and Caius → Trinity Hall → Trinity → Clare → Queens’ → Darwin → Newnham → Wolfson → Selwyn

Notes

  • As fun as it would have been to write my own TSP solver, I used Concorde. Concorde’s last release was all the way back in 2003 but apparently it was “state of the art” as recently as 2007. To set the problem up for Concorde I had to get the coordinates of the colleges, then calculate the distance between each pair of colleges.
  • I fetched the coordinates for colleges via the Google Maps API, but Google resolves Clare College to Memorial Court, and Trinity College to somewhere in the North Paddock, which isn’t entirely accurate.
  • I calculated distances as the geodesic distance between pairs of coordinates, leading to a relatively short tour length of about 15.83 km. This also assumes you can fly, which is probably not the case. It’s possible to fix this by calculating distances with the Google Distance Matrix API, which would give me the distance when walking along the shortest route, but… meh.

← Archive