Modeling and solving the train timetabling problem
Modeling and solving the train timetabling problem
复制标题
DOI：
10.1287/opre.50.5.851.362
复制
发表时间：
2002-09-01
影响因子：
2.7
通讯作者：
Toth, P
中科院分区：
文献类型：
--
作者：
Caprara, A;Fischetti, M;Toth, P
列车调度问题的目的是确定一组列车的周期性时刻表，该时刻表不违反轨道能力并满足某些操作约束。我们集中讨论连接两个主要车站和中间若干中间车站的单一单向轨道的问题。每列火车沿轨道连接沿着两个给定的车站（可能与两个大站不同）并且可能必须在一些中间站停一段最短时间火车只能在中间站的对应位置超车，本文提出了一个用有向多重图来描述该问题的图论公式，图中的节点对应于出发点和到达点。在给定的时刻到达某个车站这个公式被用来推导一个整数线性规划模型，该模型以拉格朗日方式放松。我们模型的一个新特点是放松约束中的变量只与节点相关联。（与弧相反）的上述图形，这允许相当大的速度-在松弛的解中松弛被嵌入到启发式算法中，该算法广泛使用与拉格朗日乘子相关联的对偶信息。我们报告了由Ferrovie dello Stato SpA提供的关于真实的世界实例的广泛计算结果，意大利铁路公司和Ansaldo Segnalamento Ferroviano SpA。
The train timetabling problem alms at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints In particular, we concentrate on the problem of a single one-way track linking two major stations with a number of intermediate stations in between Each train connects two given stations along the track (possibly different from the two major stations) and may have to stop for a minimum time in some of the intermediate stations Trains can overtake each other only in correspondence of an intermediate station, and a minimum time interval between two consecutive departures and arrivals of trains in each station is specifiedIn this paper we propose a graph theoretic formulation for the problem using a directed multigraph in which nodes correspond to departures/arrivals at a certain station at a given time instant This formulation is used to derive an integer linear programming model that is relaxed in a Lagrangian way A novel feature of our model is that the variables in the relaxed constraints are associated only with nodes (as opposed to arcs) of the aforementioned graph This allows a considerable speed-up in the solution of the relaxation The relaxation .is embedded within a heuristic algorithm which makes extensive use of the dual information associated with the Lagrangian multipliers We report extensive computational results on real world instances provided from Ferrovie dello Stato SpA, the Italian railway company, and from Ansaldo Segnalamento Ferroviano SpA.