IP-based Techniques for Delay Management with Priority Decisions
IP-based Techniques for Delay Management with Priority Decisions
复制标题
DOI：
10.4230/oasics.atmos.2008.1586
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Michael Schachtebeck;A. Schöbel
中科院分区：
文献类型：
--
作者：
Michael Schachtebeck;A. Schöbel
延误管理是铁路公司日常运营中的一个重要问题。任务是将计划时间表更新为处置时间表，以便尽可能减少对乘客的不便。在这方面必须做出的两个主要决定是等待-离开决定，以决定在延误的情况下应该保持哪些连接，以及确定允许列车通过特定轨道的顺序的优先级决定。由于轨道系统的容量有限，它们在容量有限的情况下是必要的，并且对于确保不同列车之间的间隔得到尊重以及单轨交通的正确路线是至关重要的。虽然等待-离开决策已经在文献中得到了深入的研究（例如[Sch 06，Gat 07]），但到目前为止，在延迟管理优化模型中，容量限制情况下的优先级决策一直被忽略。在目前的文件中，我们添加的优先级决定的整数规划制定的延迟管理问题，因此能够处理的能力有限的情况下。不幸的是，这些约束是析取约束，使得产生的事件活动网络更密集，并破坏了它不包含任何有向循环的属性。尽管如此，我们能够推导出减少技术的网络，使我们能够扩展制定的永不满足的财产从无能力的延迟管理问题的能力限制的情况下。然后，我们使用我们的研究结果，以获得精确的和启发式的解决方案，解决延迟管理问题的程序。从理论和数值的角度来看，算法的结果进行评估。后者是在一个案例研究中使用的铁路网络在该地区的哈茨，德国。
Delay management is an important issue in the daily operations of any railway company. The task is to update the planned timetable to a disposition timetable in such a way that the inconvenience for the passengers is as small as possible. The two main decisions that have to be made in this respect are the wait-depart decisions to decide which connections should be maintained in case of delays and the priority decisions that determine the order in which trains are allowed to pass a specific piece of track. They later are necessary in the capacitated case due to the limited capacity of the track system and are crucial to ensure that the headways between different trains are respected and that single-track traffic is routed correctly. While the wait-depart decisions have been intensively studied in literature (e.g. [Sch06,Gat07]), the priority decisions in the capacitated case have been neglected so far in delay management optimization models. In the current paper, we add the priority decisions to the integer programming formulation of the delay management problem and are hence able to deal with the capacitated case. Unfortunately, these constraints are disjunctive constraints that make the resulting event activity network more dense and destroy the property that it does not contain any directed cycle. Nevertheless, we are able to derive reduction techniques for the network which enable us to extend the formulation of the never-meet property from the uncapacitated delay management problem to the capacitated case. We then use our results to derive exact and heuristic solution procedures for solving the delay management problem. The results of the algorithms are evaluated both from a theoretical and a numerical point of view. The latter has been done within a case study using the railway network in the region of Harz, Germany.