4 ms·
Here's a handy little problem you can solve with road.li - There are 5162 KFC outlets in USA. Say I want to eat a chicken breast at every one of these locations
by dxbydt 13y ago
Here's a handy little problem you can solve with road.li - There are 5162 KFC outlets in USA. Say I want to eat a chicken breast at every one of these locations. What's the shortest route that connects all 5162 locations ? Do a topological sort of all kfc locations and run road.li iteratively ie. route from kfc-1 to kfc-3 via kfc-2, kfc-3 to kfc-5 via kfc-4, etc. until kfc-5162 - that should be a bloody interesting map. KFC will fork out hard cash for that sort of thing.
Then try Domino's, Taco Bell etc.
http://ezlocal.com/blog/post/10-largest-fast-food-chains-in-the-us.aspx http://ezlocal.com/blog/post/10-largest-fast-food-chains-in-...
- jffry 13y ago"What's the shortest route that connects all 5162 locations" AKA Traveling salesman problem? Even with a few hundred cities that would be difficult to find the optimal solution, let alone thousands. You could find a decent to even good solution with other algorithms, though
- Derander 13y agoOne thing to note about this specific problem: this is an example of the traveling salesman problem with a metric. This makes efficient (good) approximation algorithms a possibility. Many NP-hard approximation algorithms classes teach a 1.5 approx known as the Christofides algorithm. This algorithm is guaranteed to provide an approximate solution that is no worse than 1.5 times the optimal total distance, and often much better.
- pyk 13y agoFor the ambitious, some of the leading code for solving the TSP to optimality is Concorde (at best it has optimally solved an 85,900 "city" instance): http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm http://www.math.uwaterloo.ca/tsp/concorde/downloads/download... or solve/run Concorde on Argonne National Laboratory's server here: http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html Disclaimer: free for academic use
- jffry 13y agoAh, cool. So I guess I was wrong that a 5k-city solution was infeasible.
- avalaunch 13y agoIf he can solve that little problem I'm pretty sure Google will pay a tad bit more than KFC...
- dbarlett 13y agoIf you have a helicopter and a burning desire to visit all 478 KFC locations in California, give this to your pilot: https://dl.dropboxusercontent.com/u/22934979/CA_KFC_LK.jpg https://dl.dropboxusercontent.com/u/22934979/CA_KFC_LK.jpg. I used the 2D Euclidean distance between each location and the Lin-Kernighan heuristic [1], so scaling it out to the entire U.S. wouldn't be hard if the data was available. [1] https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristi...
- Arelius 13y agoHow did you do this?
- dxbydt 13y agoVery impressive! Pls post a link to your code if you don't mind.
- dbarlett 13y agohttps://github.com/dbarlett/KFC-Tour https://github.com/dbarlett/KFC-Tour Now uses the the Concorde cutting-plane-based exact TSP solver. Edit: I really should have named the repo colonel-sanders.