Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods

Yongxiang Zhang, Qiyuan Peng, Yu Yao, Xin Zhang and Xuesong Zhou

Transportation Research Part B: Methodological, 2019, vol. 128, issue C, 344-379

Abstract: The cyclic train timetabling problem aims to synchronize limited operational resources toward a master periodic schedule of transport services. By introducing an extended time-space network construct, this paper proposes a new type of integer programming model reformulation for the cyclic train timetabling problem on a double-track railway corridor at the macroscopic level. This reformulation method also holds the promises to be applied in a broader set of routing and scheduling problems with periodic activity requirements. We also hope that this space-time network extension technique, as a special version of variable splitting methods in the dual decomposition literature, could potentially bridge the modeling gaps between cyclic and non-cyclic timetables. Specifically, the existing mathematical programming model for the periodic event scheduling problem (PESP) is transformed into a multi-commodity network flow model with two coupled schedule networks and side track capacity constraints. In addition, two dual decomposition methods including Lagrangian relaxation and Alternating Direction Method of Multipliers (ADMM), are adopted to dualize the side track capacity constraints. For each train-specific sub-problem in an iterative primal and dual optimization framework, we develop an enhanced version of forward dynamic programming to find the time-dependent least cost master schedule across the time-space network over multiple periods. ADMM-motivated heuristic methods with adjusted penalty parameters are also developed to obtain good upper bound solutions. Based on real-world instances from the Beijing-Shanghai high-speed railway corridor, we compare the numerical performance between the proposed reformulation and the PESP model that involves the standard optimization solver.

Keywords: Cyclic train timetabling; Extended time-space network; Lagrangian relaxation; ADMM (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261518312359
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:128:y:2019:i:c:p:344-379

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.2019.08.001

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 ().