An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network

Yun-Hong Min, Myoung-Ju Park, Sung-Pil Hong and Soon-Heum Hong

Transportation Research Part B: Methodological, 2011, vol. 45, issue 2, 409-429

Abstract: In practice, a train-conflict resolution is decentralized around dispatchers each of whom controls a few segments in a global railway network with her rule-of-thumb to operational data. Conceptually, the global sub-optimality or infeasibility of the decentralized system is resolved by a network controller who coordinates the dispatchers and train operators at the lower layers on a real-time basis. However, such notion of a multi-layer system cannot be effectual unless the top layer is able to provide a global solution soon enough for the dynamic lower layers to adapt in a seamless manner. Unfortunately, a train-conflict resolution problem is NP-hard as formally established in this paper and an effective solution method traded off between computation time and solution quality has been lacking in literature. Thus, we propose a column-generation-based algorithm that exploits the separability of the problem. A key ingredient of the algorithm is an efficient heuristic for the pricing subproblem for column generation. Tested on the real data from the Seoul metropolitan railway network, the algorithm provides near-optimal conflict-free timetables in a few seconds for most cases. The performance of the proposed algorithm is compared to the ones of the previous MIP-based heuristic by Törnquist and Persson (2007) and the priority-based heuristic by Sahin (1999).

Keywords: Train-conflict; resolution; NP-hardness; Column; generation; Fix-and-regenerate (search for similar items in EconPapers)
Date: 2011
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/S0191-2615(10)00102-5
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:45:y:2011:i:2:p:409-429

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

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