Efficient Algorithms for Solving the Shortest Covering Path Problem

John Current, Hasan Pirkul and Erik Rolland
Additional contact information
John Current: Fisher College of Business Administration, The Ohio State University, Columbus, Ohio 43210
Hasan Pirkul: Fisher College of Business Administration, The Ohio State University, Columbus, Ohio 43210
Erik Rolland: Graduate School of Management, University of California, Riverside, Riverside, California 92521

Transportation Science, 1994, vol. 28, issue 4, 317-327

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

Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.28.4.317 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:28:y:1994:i:4:p:317-327

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().