IDEAS home Printed from https://ideas.repec.org/a/sae/inrsre/v39y2016i1p131-151.html
   My bibliography  Save this article

The Shortest Covering Path Problem

Author

Listed:
  • Timothy J. Niblett
  • Richard L. Church

Abstract

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.

Suggested Citation

  • Timothy J. Niblett & Richard L. Church, 2016. "The Shortest Covering Path Problem," International Regional Science Review, , vol. 39(1), pages 131-151, January.
    • Handle: RePEc:sae:inrsre:v:39:y:2016:i:1:p:131-151
    DOI: 10.1177/0160017614550082
    as

    Download full text from publisher

    File URL: https://journals.sagepub.com/doi/10.1177/0160017614550082
    Download Restriction: no
    File URL: https://libkey.io/10.1177/0160017614550082?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Wright, Jeffrey & Revelle, Charles & Cohon, Jared, 1983. "A multiobjective integer programming model for the land acquisition problem," Regional Science and Urban Economics, Elsevier, vol. 13(1), pages 31-53, February.
    2. Current, J. R. & Re Velle, C. S. & Cohon, J. L., 1985. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation," European Journal of Operational Research, Elsevier, vol. 21(2), pages 189-199, August.
    3. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    4. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    5. Hutson, Vicki Aaronson & ReVelle, Charles, 1993. "Indirect covering tree problems on spanning tree networks," European Journal of Operational Research, Elsevier, vol. 65(1), pages 20-32, February.
    6. John R. Current & David A. Schilling, 1989. "The Covering Salesman Problem," Transportation Science, INFORMS, vol. 23(3), pages 208-213, August.
    7. John Current & Hasan Pirkul & Erik Rolland, 1994. "Efficient Algorithms for Solving the Shortest Covering Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 317-327, November.
    8. Peter J. Slater, 1982. "Locating Central Paths in a Graph," Transportation Science, INFORMS, vol. 16(1), pages 1-18, February.
    9. Brian Boffey & Subhash Narula, 1998. "Models for multi-path covering-routing problems," Annals of Operations Research, Springer, vol. 82(0), pages 331-342, August.
    10. Peter J. Slater, 1981. "On Locating a Facility to Service Areas within a Network," Operations Research, INFORMS, vol. 29(3), pages 523-531, June.
    11. Laporte, Gilbert & Mesa, Juan A. & Ortega, Francisco A., 2000. "Optimization methods for the planning of rapid transit systems," European Journal of Operational Research, Elsevier, vol. 122(1), pages 1-10, April.
    12. Kenneth R. Fox & Bezalel Gavish & Stephen C. Graves, 1980. "Technical Note—An n -Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem," Operations Research, INFORMS, vol. 28(4), pages 1018-1021, August.
    13. Matisziw, Timothy C. & Murray, Alan T. & Kim, Changjoo, 2006. "Strategic route extension in transit networks," European Journal of Operational Research, Elsevier, vol. 171(2), pages 661-673, June.
    14. Current, John R. & Schilling, David A., 1994. "The median tour and maximal covering tour problems: Formulations and heuristics," European Journal of Operational Research, Elsevier, vol. 73(1), pages 114-126, February.
    15. Vicki Aaronson Hutson & Charles S. ReVelle, 1989. "Maximal Direct Covering Tree Problems," Transportation Science, INFORMS, vol. 23(4), pages 288-299, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.
    2. Matisziw, Timothy C. & Murray, Alan T. & Kim, Changjoo, 2006. "Strategic route extension in transit networks," European Journal of Operational Research, Elsevier, vol. 171(2), pages 661-673, June.
    3. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    4. Russell Halper & S. Raghavan, 2011. "The Mobile Facility Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 413-434, August.
    5. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    6. Eusebio Angulo & Ricardo García-Ródenas & José Luis Espinosa-Aranda, 2016. "A Lagrangian relaxation approach for expansion of a highway network," Annals of Operations Research, Springer, vol. 246(1), pages 101-126, November.
    7. Murawski, Lisa & Church, Richard L., 2009. "Improving accessibility to rural health services: The maximal covering network improvement problem," Socio-Economic Planning Sciences, Elsevier, vol. 43(2), pages 102-110, June.
    8. Prashant Singh & Ankush R. Kamthane & Ajinkya N. Tanksale, 2021. "Metaheuristics for the distance constrained generalized covering traveling salesman problem," OPSEARCH, Springer;Operational Research Society of India, vol. 58(3), pages 575-609, September.
    9. Kamruzzaman, Md. & Hine, Julian & Gunay, Banihan & Blair, Neale, 2011. "Using GIS to visualise and evaluate student travel behaviour," Journal of Transport Geography, Elsevier, vol. 19(1), pages 13-32.
    10. J. Beasley & E. Nascimento, 1996. "The Vehicle Routing-Allocation Problem: A unifying framework," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(1), pages 65-86, June.
    11. Eduardo Álvarez-Miranda & Markus Sinnl, 2020. "A branch-and-cut algorithm for the maximum covering cycle problem," Annals of Operations Research, Springer, vol. 284(2), pages 487-499, January.
    12. Roy, Sandeepan & Maji, Avijit, 2019. "A Station Location Identification Model for an Integrated Interoperable High-Speed Rail System," ADBI Working Papers 956, Asian Development Bank Institute.
    13. Renaud, Jacques & Boctor, Fayez F., 1998. "An efficient composite heuristic for the symmetric generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 108(3), pages 571-584, August.
    14. Glize, Estèle & Roberti, Roberto & Jozefowiez, Nicolas & Ngueveu, Sandra Ulrich, 2020. "Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 812-824.
    15. Lari, Isabella & Ricca, Federica & Scozzari, Andrea, 2008. "Comparing different metaheuristic approaches for the median path problem with bounded length," European Journal of Operational Research, Elsevier, vol. 190(3), pages 587-597, November.
    16. Fischer, Vera & Pacheco Paneque, Meritxell & Legrain, Antoine & Bürgy, Reinhard, 2024. "A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection," European Journal of Operational Research, Elsevier, vol. 315(1), pages 338-353.
    17. Avella, P. & Benati, S. & Canovas Martinez, L. & Dalby, K. & Di Girolamo, D. & Dimitrijevic, B. & Ghiani, G. & Giannikos, I. & Guttmann, N. & Hultberg, T. H. & Fliege, J. & Marin, A. & Munoz Marquez, , 1998. "Some personal views on the current state and the future of locational analysis," European Journal of Operational Research, Elsevier, vol. 104(2), pages 269-287, January.
    18. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    19. Glock, Katharina & Meyer, Anne, 2023. "Spatial coverage in routing and path planning problems," European Journal of Operational Research, Elsevier, vol. 305(1), pages 1-20.
    20. Danwen Bao & Shijia Tian & Rui Li & Tianxuan Zhang & Ting Zhu, 2022. "Multi-Objective Decision Method for Airport Landside Rapid Transit Network Design," Networks and Spatial Economics, Springer, vol. 22(4), pages 767-801, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:sae:inrsre:v:39:y:2016:i:1:p:131-151. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: SAGE Publications (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.