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

Linzhong Liu (), Haibo Mu and Juhua Yang
Additional contact information
Linzhong Liu: Lanzhou Jiaotong University
Haibo Mu: Lanzhou Jiaotong University
Juhua Yang: Lanzhou Jiaotong University

Journal of Intelligent Manufacturing, 2017, vol. 28, issue 3, No 29, 767-781

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

Keywords: Shortest path problem (SPP); Multi-modal shortest path problem (M-SPP); Time-window; Label correcting algorithm (LCA); Label setting algorithm (LSA) (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10845-014-1018-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joinma:v:28:y:2017:i:3:d:10.1007_s10845-014-1018-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10845

DOI: 10.1007/s10845-014-1018-0

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

More articles in Journal of Intelligent Manufacturing from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().