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.