Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

I have about 300 addresses in a city and I'm trying to find software that can solve the travelling salesman problem for it. I've tried OptiMap a browser based solution that uses the Google API but it's capped at 100 destinations (Even when you change hard coded limits) and the browsers I try eventually run out of memory. I know the problem is NP hard but this isn't a new problem, surely someone has written software already. The only commercial solutions I've seen are US based only (it's an Australian city) or have low limits.

Is there free or commercial software to accomplish this task and it's size?

share|improve this question

closed as off topic by Nifle, Indrek, Kyle, 8088, DragonLord Oct 21 '12 at 17:50

Questions on Super User are expected to relate to computer software or computer hardware within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
Perhaps you can solve the problem in chunks of 100. Can you break the locations into clusters and feed them to OptiMap in chunks. Then handle the transitions manually? –  uSlackr Jan 9 '12 at 13:53
    
I've always seen the traveling salesman problem used as an example, something like a foobarbaz hello world thing. It's amusing to see that it has such a practical potential. By the way, NP hard or not, genetic algorithms will give an excellent (not perfect) solution in minutes or less. Also, 300 addresses? That looks like the kind of WTF situation that OptiMap devs did not account for. File a bug? –  Camilo Martin Feb 12 '12 at 4:39
    
Search with these keywords: logistic software delivery optimization. There's many software dedicated for these kind of problem.duckduckgo.com/… –  climenole Feb 23 '12 at 1:51

1 Answer 1

Not exactly "free" - but perhaps implement the approximation algorithm for TSP outlined in this textbook.

IIRC, it gives a solution TSP for planar graphs a factor of 2 within the optimal solution.

share|improve this answer
1  
Haha, +1 for "write this algorithm" answer –  Fopedush Mar 1 '12 at 22:12
    
I think it's funny when people think they're going to find a website with custom written software to solve their specific scenario. –  emptyset Mar 4 '12 at 17:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.