3
$\begingroup$

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

$\endgroup$

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.