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.

enter image description here

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
        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);
            //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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.