Show HN: Find the fastest route via a place

Re:Show HN: Find the fastest route via a place by dxbydt on Tuesday September 03, 2013 @07:02PM (#6324462)

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-...

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by jffry on Tuesday September 03, 2013 @07:07PM (#6324478)

"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

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by Derander on Tuesday September 03, 2013 @09:57PM (#6325112)

One 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.

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by pyk on Wednesday September 04, 2013 @01:44AM (#6325798)

For 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/download...

or solve/run Concorde on Argonne National Laboratory's server here:

http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html

Disclaimer: free for academic use

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by jffry on Wednesday September 04, 2013 @01:39PM (#6329096)

Ah, cool. So I guess I was wrong that a 5k-city solution was infeasible.

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by dbarlett on Tuesday September 03, 2013 @11:37PM (#6325383)

If 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. 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_heuristi...

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by dxbydt on Wednesday September 04, 2013 @02:33PM (#6329477)

Very impressive! Pls post a link to your code if you don't mind.

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by dbarlett on Wednesday September 04, 2013 @11:01PM (#6331936)

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.

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by Arelius on Wednesday September 04, 2013 @12:05AM (#6325475)

How did you do this?

[ Parent | on HN ]

Re:Show HN: Find the fastest route via a place by avalaunch on Tuesday September 03, 2013 @09:35PM (#6325022)

If he can solve that little problem I'm pretty sure Google will pay a tad bit more than KFC...

[ Parent | on HN ]