A tutorial on non-periodic train timetabling and platforming problems

被引:45
作者
Cacchiani, Valentina [1 ]
Galli, Laura [2 ]
Toth, Paolo [1 ]
机构
[1] Univ Bologna, DEI, Viale Risorgimento 2, I-40136 Bologna, Italy
[2] Univ Pisa, Dipartimento Informat, I-56127 Pisa, Italy
关键词
Train timetabling; Train platforming; Integer programming; Heuristic; Branch-and-cut-and-price;
D O I
10.1007/s13676-014-0046-4
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this tutorial, we give an overview of two fundamental problems arising in the optimization of a railway system: the train timetabling problem (TTP), in its non-periodic version, and the train platforming problem (TPP). We consider for both problems the planning stage, i.e. we face them from a tactical point of view. These problems correspond to two main phases that are usually optimized in close sequence by the railway infrastructure manager. First, in the TTP phase, a schedule of the trains in a railway network is determined. A schedule consists of the arrival and departure times of each train at each (visited) station. Second, in the TPP phase, one needs to determine a stopping platform and a routing for each train inside each (visited) station, according to the schedule found in the TTP phase. Due to the complexity of the two problems, an integrated approach is generally hopeless for real-world instances. Hence, the two phases are considered separately and optimized in sequence. Although there exist several versions for both problems, depending on the infrastructure manager and train operators requirements, we do not aim at presenting all of them, but rather at introducing the reader to the topic using small examples. We present models and solution approaches for the two problems in a didactic way and always refer the reader to the corresponding papers for technical details.
引用
收藏
页码:285 / 320
页数:36
相关论文
共 71 条
  • [1] On-line timetable re-scheduling in regional train services
    Adenso-Díaz, B
    González, MO
    González-Torre, P
    [J]. TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 1999, 33 (06) : 387 - 398
  • [2] Barber F, 2008, TECHNICAL REPORT
  • [3] Using integer programming to solve the train-platforming problem
    Billionnet, A
    [J]. TRANSPORTATION SCIENCE, 2003, 37 (02) : 213 - 222
  • [4] Borndorger R, 2008, OPERAT RES PROCEED, P117
  • [5] Borndorfer R., 2006, COMP REGULAT NETWORK, V1, P163
  • [6] Railway timetabling using Lagrangian relaxation
    Brannlund, U
    Lindberg, PO
    Nou, A
    Nilsson, JE
    [J]. TRANSPORTATION SCIENCE, 1998, 32 (04) : 358 - 369
  • [7] A sequencing approach for creating new train timetables
    Burdett, R. L.
    Kozan, E.
    [J]. OR SPECTRUM, 2010, 32 (01) : 163 - 193
  • [8] Burer S., 2012, SURVEYS OPERATIONS R, V17, P97, DOI [10.1016/j.sorms.2012.08.001, DOI 10.1016/J.S0RMS.2012.08.001]
  • [9] Burkard R. E., 2009, ASSIGNMENT PROBLEMS
  • [10] A column generation approach to train timetabling on a corridor
    Cacchiani, Valentina
    Caprara, Alberto
    Toth, Paolo
    [J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2008, 6 (02): : 125 - 142