Hacker News new | past | comments | ask | show | jobs | submit login

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.


"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

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.

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:


Disclaimer: free for academic use

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

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

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


Now uses the the Concorde cutting-plane-based exact TSP solver.

Edit: I really should have named the repo colonel-sanders.

How did you do this?

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

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact