Variation on Travelling salesman problem - pick a good subroute from many nodes based on constraints

Question

TLDR version: Most important issue is, that in a TSP problem, instead of finding the shortest Hamiltonian cycle, what are good ways to find the best path (I suppose the one that visits the most nodes) which is at most X length, with a fixed starting point.

Full version:

I'm interested in some ideas for a problem that involves TSP. First, an example real-world TSP problem is when you have N geographical locations to visit and you need driving directions for an optimal route (or near-optimal) to visit all, either a roundtrip or A to Z. There is a nice JS implementation for this at http://www.gebweb.net/optimap/ and a JS TSP solver available at http://code.google.com/p/google-maps-tsp-solver/.

Now consider that you have N = 100 - 1000+ locations. At that point you cannot calculate the route with any reasonable amount of time/resources, but even if it were possible that is not that useful for most real world scenarios. Let's say you pick a fixed starting point and based on that, from those 1000+ locations you want to generate an optimal subroute which fits into a (relatively small) max constraint (for example, a route that can be covered in 1 day or 1 week). How can this be solved in near real time? My thoughts sofar:

1. Build the duration matrix from starting point (this step is feasible even at a few thousand points) and pick a small subset of points which are closest to the starting point. Ideally this subset should be large enough, that visiting it fully is definitely > max constraint, but small enough to process quickly, at least with heuristic algorithms.

2. Find an optimal route considering the locations chosen in step 1. But instead of a route that visits all points from this set, I need the best route which satisfies max constraint thus it should not visit all points (it can visit all but that would be the edge case). I'm especially not sure on how it would be best to tackle this one in an efficient way?

Any links, or ideas appreciated, especially for point 2.

Disclaimer: Of course the core of the problem is language-agnostic, I'm using JS/Google Maps as an example of real world application.

Answer 1

OK, here's my sketch of a solution, in pseudo code. You need to know about Priority Queues

Define a data structure Route {
  the route taken so far, 
  and can give the score (nodes visited)
  the distance traveled
  and the remaining nodes allowed
  the current location.
}

Define a Priority Queue of Routes which sorts on distance traveled.
Define a SortedSet of Routes which sorts on score called solutions.

Add a Route of Length 0, at the depot to the priority queue.
Loop until the head of the priority queue is greater than MAX
   Route r = take the head of the priority queue.
   for each potential remaining node n in r, 
     (in increasing order of distance from the current location)
      child = a new route of r with n appended
      if child distance < max, append to priority queue, otherwise break
   if no children were appended add r to solutions

This effectively does a breadth first search of the solution space, in a reasonably memory efficient manner. Moreover, if it is too slow, then when looping over all children you can speed up the algorithm by only taking N nearest neighbors, where N is configurable. You may miss the optimum solution, but it should be reasonable in most cases.