IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v28y2017i3d10.1007_s10845-014-1018-0.html
   My bibliography  Save this article

Toward algorithms for multi-modal shortest path problem and their extension in urban transit network

Author

Listed:
  • Linzhong Liu

    (Lanzhou Jiaotong University)

  • Haibo Mu

    (Lanzhou Jiaotong University)

  • Juhua Yang

    (Lanzhou Jiaotong University)

Abstract

This paper investigates the algorithms of the multi-modal shortest path problem (M-SPP) under static and certain environment and their extension in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. Existing algorithms of various M-SPP are usually based on building a new network in terms of the hypergraph or transfer graph and implemented by extending the label correcting algorithm and label setting algorithm (LSA) in such a new network. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on) and, to get their destination, the users can alternate between different modes. As a special demand, the time-window is usually correlated with the M-SPP. In contrast to the algorithms for the classical M-SPP, the algorithms for the M-SPP in UTN are much complicated, particularly, these for the M-SPP with the switching delay and arriving time-window. In this paper, we consider the M-SPP with switching delay and that with both of the switching delay and arriving time-window. Firstly, a new approach is adopted to simplify the mathematical formulas of thes M-SPP with switching delay and then an improved LSA for the M-SPP with switching delay in the UTN is proposed. Afterwards, a reverse LSA is given to solve the M-SPP with both of switching delay and arriving time-window in the UTN. Finally, some examples are given to illustrate the labeling process of the designed algorithms.

Suggested Citation

  • Linzhong Liu & Haibo Mu & Juhua Yang, 2017. "Toward algorithms for multi-modal shortest path problem and their extension in urban transit network," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 767-781, March.
    • Handle: RePEc:spr:joinma:v:28:y:2017:i:3:d:10.1007_s10845-014-1018-0
    DOI: 10.1007/s10845-014-1018-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-014-1018-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10845-014-1018-0?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Spiess, Heinz & Florian, Michael, 1989. "Optimal strategies: A new assignment model for transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 23(2), pages 83-102, April.
    2. Crainic, Teodor G. & Rousseau, Jean-Marc, 1986. "Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 225-242, June.
    3. Lozano, Angelica & Storchi, Giovanni, 2001. "Shortest viable path algorithm in multimodal networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(3), pages 225-241, March.
    4. Horn, Mark E. T., 2003. "An extended model and procedural framework for planning multi-modal passenger journeys," Transportation Research Part B: Methodological, Elsevier, vol. 37(7), pages 641-660, August.
    5. Yang, Lixing & Zhou, Xuesong, 2014. "Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 22-44.
    6. Ziliaskopoulos, Athanasios & Wardell, Whitney, 2000. "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays," European Journal of Operational Research, Elsevier, vol. 125(3), pages 486-502, September.
    7. 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.
    8. Modesti, Paola & Sciomachen, Anna, 1998. "A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 111(3), pages 495-508, December.
    9. Nguyen, S. & Morello, E. & Pallottino, S., 1988. "Discrete time dynamic estimation model for passenger origin/destination matrices on transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 22(4), pages 251-260, August.
    10. Beuthe, Michel & Jourquin, Bart & Geerts, Jean-François & Koul à Ndjang' Ha, Christian, 2001. "Freight transportation demand elasticities: a geographic multimodal transportation network analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 37(4), pages 253-266, August.
    11. Bielli, Maurizio & Boulmakoul, Azedine & Mouncif, Hicham, 2006. "Object modeling and path computation for multimodal travel systems," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1705-1730, December.
    12. Sang Nguyen & Stefano Pallottino & Federico Malucelli, 2001. "A Modeling Framework for Passenger Assignment on a Transport Network with Timetables," Transportation Science, INFORMS, vol. 35(3), pages 238-249, August.
    13. George B. Dantzig, 1960. "On the Shortest Route Through a Network," Management Science, INFORMS, vol. 6(2), pages 187-190, January.
    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. Androutsopoulos, Konstantinos N. & Zografos, Konstantinos G., 2009. "Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network," European Journal of Operational Research, Elsevier, vol. 192(1), pages 18-28, January.
    2. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    3. Andrew Ensor & Felipe Lillo, 2016. "Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(01), pages 1-21, February.
    4. López, David & Lozano, Angélica, 2020. "Shortest hyperpaths in a multimodal hypergraph with real-time information on some transit lines," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 541-559.
    5. Jiang, Y. & Szeto, W.Y., 2016. "Reliability-based stochastic transit assignment: Formulations and capacity paradox," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 181-206.
    6. Häme, Lauri & Hakula, Harri, 2013. "Dynamic journeying under uncertainty," European Journal of Operational Research, Elsevier, vol. 225(3), pages 455-471.
    7. Rahul Nair & Elise Miller-Hooks, 2016. "Equilibrium design of bicycle sharing systems: the case of Washington D.C," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 321-344, August.
    8. Bielli, Maurizio & Boulmakoul, Azedine & Mouncif, Hicham, 2006. "Object modeling and path computation for multimodal travel systems," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1705-1730, December.
    9. Lozano, Angélica & Storchi, Giovanni, 2002. "Shortest viable hyperpath in multimodal networks," Transportation Research Part B: Methodological, Elsevier, vol. 36(10), pages 853-874, December.
    10. Zhang, M. & Pel, A.J., 2016. "Synchromodal hinterland freight transport: Model study for the port of Rotterdam," Journal of Transport Geography, Elsevier, vol. 52(C), pages 1-10.
    11. Younes Hamdouch & Siriphong Lawphongpanich, 2010. "Congestion Pricing for Schedule-Based Transit Networks," Transportation Science, INFORMS, vol. 44(3), pages 350-366, August.
    12. Wang, David Z.W. & Nayan, Ashish & Szeto, W.Y., 2018. "Optimal bus service design with limited stop services in a travel corridor," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 70-86.
    13. Li, Guoyuan & Chen, Anthony, 2022. "Frequency-based path flow estimator for transit origin-destination trip matrices incorporating automatic passenger count and automatic fare collection data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 163(C).
    14. Shang, Pan & Li, Ruimin & Guo, Jifu & Xian, Kai & Zhou, Xuesong, 2019. "Integrating Lagrangian and Eulerian observations for passenger flow state estimation in an urban rail transit network: A space-time-state hyper network-based assignment approach," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 135-167.
    15. Yi Zhao & Ronghui Liu & Xi Zhang & Anthony Whiteing, 2018. "A chance-constrained stochastic approach to intermodal container routing problems," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-22, February.
    16. Zhang, Yu & Tang, Jiafu, 2018. "Itinerary planning with time budget for risk-averse travelers," European Journal of Operational Research, Elsevier, vol. 267(1), pages 288-303.
    17. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    18. Ioannou, Petros & Giuliano, Genevieve & Dessouky, Maged & Chen, Pengfei & Dexter, Sue, 2020. "Freight Load Balancing and Efficiencies in Alternative Fuel Freight Modes," Institute of Transportation Studies, Working Paper Series qt3ns4b894, Institute of Transportation Studies, UC Davis.
    19. Greening, Lacy M. & Dahan, Mathieu & Erera, Alan L., 2023. "Lead-Time-Constrained Middle-Mile Consolidation Network Design with Fixed Origins and Destinations," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    20. Cats, Oded & Koutsopoulos, Haris N. & Burghout, Wilco & Toledo, Tomer, 2013. "Effect of real-time transit information on dynamic path choice of passengers," Working papers in Transport Economics 2013:28, CTS - Centre for Transport Studies Stockholm (KTH and VTI).

    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:spr:joinma:v:28:y:2017:i:3:d:10.1007_s10845-014-1018-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.