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?
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.