Approaches to a real-world Train Timetabling Problem in a railway node

被引:78
作者
Cacchiani, Valentina [1 ]
Furini, Fabio [2 ]
Kidd, Martin Philip [1 ]
机构
[1] Univ Bologna, DEI, I-40136 Bologna, Italy
[2] Univ Paris 09, LAMSADE, F-75775 Paris, France
来源
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE | 2016年 / 58卷
关键词
Train Timetabling; Integer Linear Programming; Relaxation; Heuristic algorithm; ALGORITHMS; PERFORMANCE; OPERATIONS; RECOVERY; MODELS;
D O I
10.1016/j.omega.2015.04.006
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a highly congested railway node in which different Train Operators wish to run trains according to timetables that they propose, called ideal timetables. The ideal timetables altogether may be (and usually are) conflicting, i.e. they do not respect one or more of the track operational constraints. The goal is to determine conflict-free timetables that differ as little as possible from the ideal ones. The problem was studied for a research project funded by Rete Ferroviaria Italiana (RFI), the main Italian railway Infrastructure Manager, who also provided us with real-world instances. We present an Integer Linear Programming (ILP) model for the problem, which adapts previous ILP models from the literature to deal with the case of a railway node. The Linear Programming (LP) relaxation of the model is used to derive a dual bound. In addition, we propose an iterative heuristic algorithm that is able to obtain good solutions to real-world instances with up to 1500 trains in short computing times. The proposed algorithm is also used to evaluate the capacity saturation of the railway nodes. (C) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码:97 / 110
页数:14
相关论文
共 46 条
[1]   An assessment of railway capacity [J].
Abril, M. ;
Barber, F. ;
Ingolotti, L. ;
Salido, M. A. ;
Tormos, P. ;
Lova, A. .
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2008, 44 (05) :774-806
[2]  
Ahuja RK, 1993, Network flows
[3]  
[Anonymous], 2011, WILEY ENCY OPERATION
[4]  
[Anonymous], 2001, ELECTRON NOTES THEOR
[5]   Expanding the Spanish high-speed railway network [J].
Blanco, Victor ;
Puerto, Justo ;
Ramos, Ana B. .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2011, 39 (02) :138-150
[6]  
Borndorfer R, 2012, ANN OPER RES, P1
[7]   Railway timetabling using Lagrangian relaxation [J].
Brannlund, U ;
Lindberg, PO ;
Nou, A ;
Nilsson, JE .
TRANSPORTATION SCIENCE, 1998, 32 (04) :358-369
[8]   Techniques for absolute capacity determination in railways [J].
Burdett, RL ;
Kozan, E .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2006, 40 (08) :616-632
[9]   A column generation approach to train timetabling on a corridor [J].
Cacchiani, Valentina ;
Caprara, Alberto ;
Toth, Paolo .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2008, 6 (02) :125-142
[10]   An overview of recovery models and algorithms for real-time railway rescheduling [J].
Cacchiani, Valentina ;
Huisman, Dennis ;
Kidd, Martin ;
Kroon, Leo ;
Toth, Paolo ;
Veelenturf, Lucas ;
Wagenaar, Joris .
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2014, 63 :15-37