Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition

Wenliang Zhou, Junli Tian, Lijuan Xue, Min Jiang, Lianbo Deng and Jin Qin

Transportation Research Part B: Methodological, 2017, vol. 105, issue C, 144-173

Abstract: To provide passengers with strict regularity of train operation, this research is devoted to modeling and solving the multi-periodic train timetabling problem to simultaneously optimize operation periods, arrival times, and departure times of all period types of trains on a double-track rail network. Based on the construction of a weighted directed graph, a multi-path searching model, namely, a 0-1 linear programming model, is built to minimize the total travel time of all period-types of trains subject to many operational constraints, including station parking capacity and train minimum load factors. After decomposing this model by introducing some Lagrangian multipliers to relax its complicated constraints, a solution algorithm, including a multi-path simultaneous searching sub-algorithm for each period-type of train, is designed to optimize both the feasible and dual solutions, which correspond to the upper and lower bounds, respectively. Finally, the performance, convergence, sensitivity, and practicability of our method are analyzed using many instances on both a small rail network and the high-speed railway between Beijing and Shanghai in China.

Keywords: Train timetabling; Multiple periods; Directed graph; Lagrangian relaxation; Decomposition (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261517301340
Full text for ScienceDirect subscribers only

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:eee:transb:v:105:y:2017:i:c:p:144-173

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2017.08.005

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
Bibliographic data for series maintained by Catherine Liu ().