The shortest covering path (SCP) problem involves finding the shortest path between an origin node and a destination node, where the path traverses the network and passes within a maximal covering distance of all nodes of the network. This problem was originally proposed by Current, ReVelle, and Cohon. Since that time researchers have proposed both heuristic and optimal approaches for this problem as well as have developed more general forms, including the maximal covering shortest path problem. From the outset, it has been assumed that any optimal covering path would never loop or double back on itself. This assumption is examined in detail. We demonstrate that this assumption can lead to longer than necessary covering paths. We also present a new, more general construct, which can be used to generate optimal SCPs and demonstrate its use on an example problem.
AertsJ. C. J. H.EisingerE.HeuvelinkG. B. M.StewartT. J.. 2003. “Using Linear Integer Programming for Multi-site Land-use Allocation.”Geographical Analysis35:148–69.
2.
BoffeyB.NarulaS. C.. 1998. “Models for Multi-path Covering Routing Problems.”Annals of Operations Research82:331–42.
3.
BrookesC. J.1997. “A Parameterized Region Growing Programme for Site Allocation on Raster Suitability Maps.”International Journal of Geographical Information Science11:375–96.
4.
CurrentJ.1981. “Multiobjective Design of Transportation Networks.”PhD Dissertation, Department of Geography and Environmental Engineering, Johns Hopkins University, Baltimore, MD.
5.
CurrentJ.PirkulH.RollandE.. 1994. “Efficient Algorithms for Solving the Shortest Covering Path Problem.”Transportation Science28:317–27.
6.
CurrentJ.ReVelleC.CohonJ.. 1984. “The Shortest Covering Path Problem: An Application of Locational Constraints to Network Design.”Journal of Regional Science24:161–83.
7.
CurrentJ. R.ReVelleC. S.CohonJ. L.. 1985. “The Maximum Covering/Shortest Path Problem: A Multiobjective Network Design and Routing Formulation.”European Journal of Operational Research21:189–99.
8.
CurrentJ. R.SchillingD. A.. 1989. “The Covering Salesman Problem.”Transportation Science23:208–12.
9.
CurrentJ. R.SchillingD. A.. 1994. “The Median Tour and Maximal Covering Tour Problems: Formulations and Heuristics.”European Journal of Operational Research73:114–26.
10.
CurtinK. M.BibaS.. 2011. “The Transit Route Arc-node Service Maximization Problem.”European Journal of Operational Research208:46–56.
11.
DantzigG.FulkersonR.JohnsonS.. 1954. “Solution of a Large-scale Traveling Salesman Problem.”Journal of the Operations Research Society2:393–410.
12.
FoxK. R.GavishB.GravesS. C.. 1980. “An n-constraint Formulation of the Time Dependent Travelling Salesman Problem.”Operations Research28:1018–21.
13.
GavishB.GravesS. C.. 1978. “The Travelling Salesman Problem and Related Problems.”Working paper OR-078-78, Operations Research Center, MIT, Cambridge, MA.
14.
HutsonV.ReVelleC.. 1989. “Maximal Direct Covering Tree Problems.”Transportation Science23:288–99.
15.
HutsonV.ReVelleC.. 1993. “Indirect Covering Tree Problems on Spanning Tree Networks.”European Journal of Operations Research65:20–32.
16.
LangevinA. F.SoumisF.DesrosiersJ.. 1990. “Classification of Travelling Salesman Formulations.”OR Letters9:127–32.
17.
LaporteG.MesaJ.OrtegaF.. 2000. “Optimization Methods for the Planning of Rapid Transit Systems.”European Journal of Operations Research122:1–10.
18.
MatisziwT. C.DemirE.. 2012. “Inferring Network Paths from Point Observations.”International Journal of Geographical Information Science26:1979–96.
19.
MatisziwT. C.MurrayA. T.KimC.. 2006. “Strategic Route Extension in Transit Networks.”European Journal of Operations Research171:661–73.
20.
MillerC. E.TuckerA. W.ZemlinR. A.. 1960. “Integer Programming Formulation of Travelling Salesman Problems.”Journal of the ACM7:326–29.
21.
OrmanA. J.WilliamsH. P.. 2004. “A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem.”Working Paper LSEOR 04.67, The Department of Operational Research, The London School of Economics and Political Science, London, UK.
22.
PadbergM.SungT.-Y.. 1991. “An Analytical Comparison of Different Formulations of the Travelling Salesman Problem.”Mathematical Programming52:315–58.
23.
SlaterP. J.1980. Centrality of Paths and Vertices in a Graph: Cores and Pits. SAND-80-1140C. Albuquerque, NM: Sandia National Labs.
24.
SlaterP. J.1981. “On Locating a Facility to Service Areas within a Network.”Operations Research29:523–531.
25.
SlaterP. J.1982. “Locating Central Paths in a Graph.”Transportation Science16:1–18.
WongR. T.1980. “Integer Programming Formulations of the Travelling Salesman Problem.”Proceedings IEEE Conference on Circuits and Computers: 149–52.
28.
WrightJ.ReVelleC.CohonJ.. 1983. “A Multiobjective Integer Programming Model for the Land Acquisition Problem.”Regional Science and Urban Economics13:31–53.
29.
WuC.MurrayA. T.. 2005. “Optimizing Public Transit Quality and System Access: The Multiple-route, Maximal Covering/Shortest-path Problem.”Environment and Planning32:163–78.
