Travelling salesman with a few constraints

Question

I'm trying to find the most optimal way to driving through points say A, B, C and D

with some additional constraints - certain points have to be reached before others. Say D has to be reached before B. In other words ordering for some of the points.

Google Maps apis can help solve this problem if there are no additional constraints. Is there another service that can help solve this problem? Is there a way to do this with Google Maps apis that I missed?

0x90 · Answer 1 · 2013-02-20T22:13:54.827

1

You say google has an API function let's name it bestWay(point a, point b):

you have {A,B,C,D} as points and you have to visit them in the following order:

A,C,D,B

Find the bestWay for (A,C) then from (C,D) and (D,B) and you build your way.

If you have only such as constraint C before D you might have to check all the permutations:

A->C->B->D
A->B->C->D
...
B->A->C->D

edited Feb 20 '13 at 22:13

answered Feb 20 '13 at 22:08

0x90

39,472
36
165
245

1

Checking all those permutations will be a scalability problem. – Geoffrey De Smet Feb 21 '13 at 14:31
You right it is an NP complete problem. but if you have 5 points it is OK. – 0x90 Feb 21 '13 at 14:33
1

The problem is that each bestWay calculation is another http request which will be too expensieve – Noam Feb 21 '13 at 20:41

vitaut · Accepted Answer · 2013-02-20T23:33:20.813

A traveling salesman problem can be formulated as a integer programming problem (this link gives a formulation) or a constraint programming problem, so you can use any MIP or CP solver such as CBC or Gecode to solve the TSP problem with any extra constraints you want to add. However, if you need to plot the results on Google Maps, you'll have to do it manually using the Google Maps API.

If you prefer a web-based solution then you can use NEOS server for optimization which provides access to a variety of solvers via XML-RPC API. As an additional advantage this method allows submitting problems in a high-level modeling language such as AMPL rather than dealing with low-level solver APIs directly.

Yet another solver you might want consider if you go down this path: Drools Planner ([video which alters constraints of a Vehicle Routing problem](http://www.youtube.com/watch?annotation_id=annotation_624044&feature=iv&src_vid=GybpV0uLrxc&v=4hp_Qg1hFgE)) — Geoffrey De Smet, Feb 21 '13 at 14:24

Micromega · Answer 3 · 2013-02-22T15:13:47.153

0

Here is an exact solver in Javascript: http://www.iaindunning.com/?page_id=39. It uses a linear programming and cutting plane method like here http://www.tsp.gatech.edu/methods/dfj/index.html.

edited Feb 22 '13 at 15:13

answered Feb 20 '13 at 23:03

Micromega

12,486
7
35
72

score 0 · Answer 4 · answered Mar 07 '13 at 13:34

There is an open-source implementation of the Travelling Salesman Problem available at http://www.openopt.org/TSP - it's written in Python though.

I have incorporated the above OpenOpt TSP and Google Directions together to provide a web site that does what you require (except the ordering constraints), available at http://www.speedyroute.co.uk/

score 0 · Answer 5 · answered Aug 04 '13 at 08:03

0

check this out http://xsolve.info/TSP.html It is a program in JAVA.You can modify this to add your own constraints

answered Aug 04 '13 at 08:03

Kunal Das

1

Travelling salesman with a few constraints

5 Answers5