Multiple TSP with a twist

Question

A couple weeks ago I encountered a problem that I virtually broke down to a variation of the traveling salesman problem. The twists are:

There are multiple salemen. The list of cities is dynamically increasing (as in, live input) Each city is only fully profitable for a limited amount of time, as in after a certain time the city will return less of a reward And there is an overall time limit

Obviously, this problem is NP. I was wondering if there were any good TSP approximations that could have been modified to fit this problem?

Answer 1

You may be able to use some operations research software to solve your problem, e.g. Coin-OR, the reason being that it's generally easier to add new constraints / objectives to an OR constraint/linear/integer/etc programming solver than to e.g. a specialized TSP solver written in C or Fortran or whatever (and it's not likely that you'll find some C/Fortran code to solve your precise problem). Here is a tutorial on how to code a Tabu search to solve the basic TSP using Coin-OR. In addition, here is an article on modeling the time-dependent TSP (the article uses branch-and-bound to solve the problem which probably isn't appropriate for your problem as it doesn't scale beyond a hundred cities or so, but the model should carry over to an approximate solver like Coin-OR).

To account for having multiple salesmen, you may want to look into graph partitioning to divide up the cities among the different salesmen, for example here is a fast online graph partitioning algorithm. The advantage is that once you've partitioned the graphs you can reduce or even eliminate synchronization between the different salesmen.