Optimal Shoelacing
This [lacing shoes] is of course an instance of a Traveling Salesman Problem (TSP). Each lace hole represents a city which can be visited exactly once. For example, the slack is maximized by finding the shortest tour, while the slack can be minimized by finding the longest Hamiltonian circuit. Of course, my daughter would prefer finding a good balance between these two extreme solutions, while also ensuring that tightening and loosening the laces are relatively easy to perform. The former objective can be equivalently specified in terms of minimizing deviation from a desired tour length, while the latter requirement can perhaps be approximated by eliminating unfavorable connection patterns and reducing overall friction.
petzoldt:
The “Traveling Sales Man Problem” is a classic in Operations Research. It asked for the shortest round trip through a set of cities given the distances beween them. For 20 cities there are already 2.432.902.008.176.640.000 of such tours. A computer able to calculate a trip length in A computer able to calculate a trip length in one milliseconds would still need 240 billion years checking all of them.
Its fascinating to see how researchers keep pushing the limits when solving ever larger problems using methods from mathematical optimization and Operations Research, such as William Cook who claims to have calculated the best tour visting 1.9 million cities.
Bees solve the Traveling Salesman Problem everyday.
The TSP is heavily used in theoretical compute science and in operations research, and is classified as a NP-hard problem.
In its original formulation, the solver is given a list of cities, and their pairwise distances, and is then tasked with finding the shortest possible distance that will allow them to visit each of the cities exactly once.
…
“Foraging bees solve traveling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum,” explains Dr Nigel Raine.
…
“Despite their tiny brains bees are capable of extraordinary feats of behavior. We need to understand how they can solve the Traveling Salesman Problem without a computer. What short-cuts do they use?” Raine says.
The new investigation could have significant implications for agriculture, because bee pollination patterns are critically important for next year’s crops.
(image source)
![Optimal Shoelacing
This [lacing shoes] is of course an instance of a Traveling Salesman Problem (TSP). Each lace hole represents a city which can be visited exactly once. For example, the slack is maximized by finding the shortest tour, while the slack can be minimized by finding the longest Hamiltonian circuit. Of course, my daughter would prefer finding a good balance between these two extreme solutions, while also ensuring that tightening and loosening the laces are relatively easy to perform. The former objective can be equivalently specified in terms of minimizing deviation from a desired tour length, while the latter requirement can perhaps be approximated by eliminating unfavorable connection patterns and reducing overall friction.](http://24.media.tumblr.com/tumblr_m3eq423g2K1qbby7no1_250.gif)
