Traveling Drunkenman Problem

The Traveling Salesman Problem is a classic in computing. Given a list of cities and distances between each city, what is the shortest path that lets a salesperson visit each city exactly once and return to the starting point?

It's a bit of a tough problem at high numbers of cities, due to the exponentially increasing number of paths one can take each time a new city has been added. Because of that, the problem is useful in testing optimization processes that don't rely on simply checking all possible combinations by brute force.

What's more fun is to adapt it in such a way as to optimize, say, your drinking habits. For instance, what's the shortest path to visit the 10 best pubs in Edmonton and return to where you started?

In order to be somewhat objective, I used the Yelp list of the 10 highest rated pubs. Of course, when you're on a mathematically optimized pubcrawl, it's important to not drink and drive - so distances are converted into dollar figures following the City of Edmonton bylaws for taxis.

2 pubs: $19.40 round trip

If we start with the #1 and #2 pubs on the list, it would cost just under $20 to visit them both by taxi. No computer necessary - there's really only one way to get there and back (unless the taxi driver takes you on an expensive sight-seeing tour).

3 pubs: $30.40-33.40 round trip

There are 6 different ways to do this trip once you'd added #3 on the list, but it's not at all difficult to check out all the combinations for yourself and plan it without using a computer. Normally there wouldn't be any variation in the price (as you'd just be traveling along the same three sides of a triangle), but in the case of downtown Edmonton with all its one-way streets, some ways to drive between places end up being slightly more expensive than others.

4: $35.40-39.40

Things get a wee bit more fun here - 24 combinations to deal with, with 12 different paths between pubs to take into account.

5: $39.60-43.60

120 combinations, 20 paths between pubs. Still not too much variation between the paths yet.

6: $42.60-58.80

720 combinations, 30 paths between them. At this point there are relatively significant savings to be had by trying to optimize, but 720 combinations would be an awful lot to check by hand. The major reason why there is suddenly so much variation between different paths is that the 6th pub on the Yelp list is very close to the first. Paths that take advantage of this do well, and paths that ignore it  end up costing a lot more than necessary.

7: $46.00-63.80

5,040 combinations. Things are getting really exciting now.

8: $49.40-72.60

40,320 combinations formed from 56 different possible paths between the 8 pubs.

9: $53.00-82.40

362,880 combinations. Let's just say that's an awful lot of things to check by hand (also messes with Excel a wee bit...).

10: $57.00-98.40

3,628,800 combinations. Again, quite a bit of a burden on poor Excel. But what's cool is that by optimizing your path between 10 of Edmonton's most popular pubs, you can save more than $40 in taxi fees.

This optimized pubcrawl through these pubs would look something like this:

What became readily obvious was the sheer amount of computing power necessary to check all of these. I have Excel files that are over half a gigabyte large in order to calculate the 4 million different combinations. Solutions to larger sized problems typically require other cool algorithms that I didn't feel like actually studying to learn.

Enjoy! Hope to see you out on the nerdiest tour of Edmonton's finest pubs next weekend!

Special thanks to Finbarr Timbers and Elizabeth Croteau for the idea, and Daniel Johns for helping me out of a tricky spot with VBA.