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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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/

Answer 5

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