The Traveling Salesman Problem: The Short Pub Crawl

In order to bring the lower bound for an estimate closer to the true outcome (optimal path), you enlarge the minimum spanning tree graph: you remove point A (whatever it is) and then connect the two nearest neighbors. A to that. The result is called a 1-tree. Then you take the minimum spanning tree again and repeat the whole thing with another point, creating another 1-tree. Do this until you find the 1-tree with the largest total length: the maximum 1-tree. It is suitable for low range as it is only up to the optimum path.

Estimates of approximation methods for the traveling salesman problem are based on these maximum 1-trees. You compare the approximate result (ie, the length of the nearest neighbor access tour) to the length of the maximum 1-tree of the corresponding problem.

Christophides Algorithm

Computer scientist Christofides saw another advantage in minimum spanning trees: if they already represent an optimal solution (they are the shortest tree), then they can be the starting point for searching for the shortest circular route. In the first step of the Christofides algorithm, you create a minimum spanning tree for the points (eg the locations you want to visit). Now some points may be connected to only one edge or to three edges. The traveling salesman problem cannot have this odd number of links: you are looking for a circular route that visits each destination exactly once. This means that every point is connected to exactly two edges.

That’s why in the second step of the Christofides algorithm you isolate all points with an odd number of edges. Pairs are formed from these isolated points by connecting the two pieces together – the resulting connections are as short as possible. This resulted in a new graph with additional edges. From this you can create a circular route that passes each point only once – thus corresponding to the path you are looking for.

The most complex computational step in the Christofides algorithm for computers is to find the optimal connection of isolated points: that is, points with an odd number of connections. Overall, the amount of computation required for this is approx n²log(n) There are 50 stops from the DHL warehouse and one way back, ie: 51²·log(51) ≈ 4441 calculations are required – a regular laptop can easily do it.

Approximate solutions can be improved

Once a tour is found using the Christophides algorithm or another approach, there are some tricks to improve the result. One possibility is to change the order of the two stops and check if this shortens the overall route: (A → B → C → D → E), for example (B → A → C → D → E) gives the shortest result. By changing all the points into pairs, you can improve a route a bit.

Another option is to view a map of the calculated route. If two links intersect, their endpoints are interchanged, creating a shorter path. Using these and similar methods, the computed routes can be further refined. However, you end up with a kind of dead end: in this case, you have a map that cannot be further improved using the improvement methods described, but still does not correspond to the best solution.

To escape such a “dead end”, you must allow the situation to worsen. For example, you can make changes to a path that initially extends the entire path. If you gradually shorten this step, you can reach the optimum.

Given the high relevance of the topic, many sophisticated methods have now been developed to determine optimal routes for some special cases. For example, logistics companies and delivery services work with such approximation methods to plan their routes. So Cook and his colleagues were able to calculate a short tour of all British pubs.

Researchers didn’t just look at pub crawls; A hike on the 100 highest Austrian peaks (starting and ending at the University of Vienna), which, according to the researchers, takes 27 days. And they have determined the optimal paths, Around the stations of the popular mobile game Pokémon GO In different cities like New York City or Toronto.

Cook offers a reward of ¥49,687 for the shortest pub crawl in British pubs (the number of pubs his research team solved the problem). But before you get down to business: the prize money is over €300 – currently the equivalent of around €6 a pint, a neighborhood in London you won’t be able to cross on your pub crawl.