# Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial solutions as well. For example, if I simply don't have enough time to visit all n nodes, what's the shortest path that connects any n-1 nodes?

For example, in this image, the shortest path visiting 4 nodes is CBAD, 3 nodes would be CBA, and 2 nodes would be CB. The n-1 case seems approachable at least, by solving TSP for each subset of nodes excluding 1 node and taking the shortest of these solutions, but the problem appears to become less elegant if you are attempting to to find the shortest path with a length of say n-5 or something.

I cannot simply truncate partial paths when solving using branch and bound, because my bound calculation still needs to know how to calculate a bound for shorter than total length path (though perhaps that is still the best solution).

Is there a name for this type of problem, and/or discussion of solution approaches?

Update: I've been experimenting with ways to modify the bound calculation for this type of problem. One approach that seems to produce correct results, albeit at a steep performance cost, is to change the bounding function so that instead of summing all best paths out of each unvisited node, it only takes the k lowest paths out, where k=(partialPathLength - currentPathLength).

//bound = cost of current steps + minimum edge from each unvisited node
int getBoundForPath(final byte[] path){
int bound = 0;
//sum the cost of each step so far
...
//if this is the complete path, we're done
...

//then add the minimum distance out from each remaining nodes
nBestPaths.clear();
for(int i = 1; i <= numNodes ; i++){
//if we've been to i, skip it
...

int lowest = Integer.MAX_VALUE;
for(int j = 1; j <= numNodes ; j++){
//if you can't get from i to j, or we've been to j, skip it
...
lowest = Math.min(shortestPaths.get(nodeList[j]).get(nodeList[i]), lowest);
}
nBestPaths.enqueue(lowest);
//bound += lowest; //normal approach, sum all
}
//new approach: only sum the best k elements
for(int i = 0; i < maxPathLength-second && i < nBestPaths.size(); i++){
bound += nBestPaths.dequeueInt();
}
return bound;
}


This is not really a viable strategy, however, as the performance cost of looping and dequeuing that many times every single time I check a bound totally trashes the performance of my implementation. I could clean up this code a little, but I'm not sure it's going the best direction.