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
- 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, andTrinity 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.
Hey, you there! check out my mixtape
Other posts:
2024-02-21Sonification of Chaotic Trafficmusic2024-01-25Bikesatanist Manifestobikessatanism2023-10-09Bike Synthesizerbikesmusic2019-03-12Important YouTube Videosweb2015-05-30Supa Bot 🔥Fire🔥: I Spit Thatpythondank-memes2015-03-26Shortest Tour of Cambridge Collegesmaps2015-02-10Pixel Sortingartpython2015-02-09Under the Hoodweb2014-01-22Lorem Ipsumtest