 Transit timetable synchronization for transfer time minimizationMojtaba Abdolmaleki, Neda Masoud and Yafeng Yin Transportation Research Part B: Methodological, 2020, vol. 131, issue C, 143-159 Abstract: This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting. Keywords: Transit network; Timetable synchronization; Transfer waiting time; Maximum cut (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:131:y:2020:i:c:p:143-159 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2019.12.002 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.