Efficient Algorithms for Solving the Shortest Covering Path Problem

The Shortest Covering Path Problem (SCPP) is one of identifying the least cost path from a pre-specified starting node to a pre-specified terminus node. The path is constrained by the condition that it must cover every node in the network. A node is considered to be covered if it is within some pre-specified covering distance of a node on the path. This SCPP has many potential applications, especially in hierarchical network design, and bi-modal routing problems. In this paper we introduce two efficient algorithms for solving the SCPP. The first is a heuristic based upon a Lagrangian relaxation of the problem. The second is an exact algorithm based upon a branch and bound procedure which utilizes the bounds generated by the Lagrangian relaxation scheme. Computational tests indicate that both procedures are very efficient. The heuristic identified and verified the optimal solution for 135 of the 160 test problems solved. The optimal solution to the remaining 25 problems was readily identified by the exact algorithm.