up vote 8 down vote favorite
1
share [g+] share [fb]

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?

link|improve this 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 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 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 at 1:51
feedback

1 Answer

up vote 1 down vote

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.

link|improve this answer
1  
Haha, +1 for "write this algorithm" answer – Fopedush Mar 1 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 at 17:58
feedback

Your Answer

 
or
required, but never shown
discard

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