Last week I was impressed by this map of the world's longest pub crawl. A map which shows the shortest route around 25,000 UK pubs. It is also a neat demonstration of a particular Traveling Salesman Problem and its solution.
The map was created by the University of Waterloo's Department of Combinatorics and Optimization. The department actually has a whole website dedicated to exploring the history, applications, and current research into the Traveling Salesman Problem.
The department's Traveling Salesman Problem website includes links to a number of mapped examples of different traveling salesman problems. It also has two demonstration maps created by the university itself; the aforementioned world's largest pub crawl map and US50K, a map of the shortest route around 50,000 sites from the National Register of Historic Places.
It took 310 computers nine months to actually work out the shortest walking route around 50,000 historic locations in the United States. The best route discovered by the university's computers is 217,605 miles long, which is nearly the distance from the Earth to the Moon. You can read more about how the university solved this particular traveling salesman problem on the US50K Index page.
No comments:
Post a Comment