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

详细信息    查看全文

• 作者：Yun-Hong Min^a ; ^{myh@snu.ac.kr} ; Myoung-Ju Park^a ; Sung-Pil Hong^a ; ; Soon-Heum Hong^b
• 关键词：Train-conflict resolution ; NP-hardness ; Column generation ; Fix-and-regenerate
• 刊名：Transportation Research Part B: Methodological
• 出版年：2011
• 出版时间：February 2011
• 年：2011
• 卷：45
• 期：2
• 页码：409-429
• 全文大小：645 K

文摘

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