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

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.