Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility

Xiaopeng Tian and Huimin Niu

Transportation Research Part B: Methodological, 2020, vol. 142, issue C, 143-173

Abstract: This paper aims to optimize demand-oriented train timetables under overtaking operations for a high-speed rail corridor. With the application of the constructed space-time network representation, the timetabling and skip-stopping decisions in response to passenger demand for heterogeneous train traffic are formulated into an integer linear programming model. Specifically, we carefully assign the hour-dependent origin-to-destination demand to the skip-stop-flexible timetable by using a group of tailored constraints that bind the origin station and destination station together. While solving the proposed model under the column-generation-based framework, the biggest barrier is that the pricing subproblem cannot be successfully solved through the standard dynamic programming algorithm, because the dual price from the demand constraint is dependent upon two coupled stations. To dynamically eliminate the indivisibility attached to the demand-oriented timetabling problem, we propose a novel approach to replace the two-station-dependent dual variable with its single-station-dependent surrogate counterpart. A branch-and-price-and-cut procedure is also conducted to achieve the corresponding integer solutions, where specific families of valid inequalities are selected to narrow the feasible solutions in the restricted master problem. Finally, numerical experiments are implemented to demonstrate the efficiency and effectiveness of the proposed method.

Keywords: Train timetable; Demand-oriented; Overtaking operation; Indivisibility; Surrogate dual variable; Column generation; Branch-and-price-and-cut (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261520303945
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:142:y:2020:i:c:p:143-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.2020.09.010

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