Software to plan shortest route to many addresses

8

1

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?

user348998

Posted 2012-01-09T10:38:05.277

Reputation: 81

Question was closed 2012-10-21T17:50:13.850

2Perhaps 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 – 2012-01-09T13:53:59.833

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 – 2012-02-12T04:39:25.423

Search with these keywords: logistic software delivery optimization. There's many software dedicated for these kind of problem.http://duckduckgo.com/?q=logistic+software+delivery+optimization&t=1

– climenole – 2012-02-23T01:51:01.360

Answers

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.

emptyset

Posted 2012-01-09T10:38:05.277

Reputation: 421

1Haha, +1 for "write this algorithm" answer – Fopedush – 2012-03-01T22:12:28.787

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 – 2012-03-04T17:58:21.803

Asked: 2012-01-09T10:38:05.277

Viewed: 601 times

Active: 2017-07-31T19:27:44.403