×

An advanced real-time train dispatching system for minimizing the propagation of delays in a dispatching area under severe disturbances. (English) Zbl 1162.90375

Summary: In highly utilized rail networks, as in the Netherlands, conflicts and subsequent train delays propagate considerably in time and space during operations. In order to realistically forecast and minimize delay propagation, there is a need to extend short-term traffic planning up to several hours. On the other hand, as the magnitude of the time horizon increases the problem becomes computationally intractable and hard to tackle. In this paper, we decompose a long time horizon into tractable intervals to be solved in cascade with the objective of improving punctuality. We use the ROMA dispatching system to pro-actively detect and globally solve conflicts on each time interval. The future evolution of railway traffic is predicted on the basis of the actual track occupation, the Dutch signaling system and dynamic train characteristics. Extensive computational tests are carried out on the railway dispatching area between Utrecht and Den Bosch.

MSC:

90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manage Sci 34:391–401 · Zbl 0637.90051 · doi:10.1287/mnsc.34.3.391
[2] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
[3] Assad AA (1980) Models for rail transportation. Transp Res Part A 14(A):205–220 · doi:10.1016/0191-2607(80)90017-5
[4] Chambers R, Carraway R, Towe T, Morin T (1991) Dominance and decomposition heuristics for single machine scheduling. Oper Res 39(4):639–647 · Zbl 0736.90042 · doi:10.1287/opre.39.4.639
[5] Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–420 · Zbl 0987.90507 · doi:10.1287/trsc.32.4.380
[6] D’Ariano A, Albrecht T (2006) Running time re-optimization during real-time timetable perturbations. In: Allan J, Brebbia CA, Rumsey AF, Sciutto G, Sone S, Goodman CJ (eds) Computers in railways X. WIT, Southampton, pp 531–540
[7] D’Ariano A, Corman F, Pacciarelli D, Pranzo M (2006) Real-time train conflict detection and resolution: global sequencing and local rerouting. In: van Zuylen HJ (ed) Proceedings 9th TRAIL congress, selected papers. Delft University Press, Delft, pp 77–92
[8] D’Ariano A, Pacciarelli D, Pranzo M (2007a) A branch and bound algorithm for scheduling trains in a railway network. Eur J Oper Res 183(2):643–657 · Zbl 1179.90135 · doi:10.1016/j.ejor.2006.10.034
[9] D’Ariano A, Pranzo M, Hansen IA (2007b) Conflict resolution and train speed co-ordination for solving real-time timetable perturbations. IEEE Trans Intell Transp Syst 8(2):208–222 · doi:10.1109/TITS.2006.888605
[10] Hansen IA, Dekking FM, Goverde RMP, Heidergott B, Meester LE (eds) (2005) Proceedings of the 1st international seminar on railway operations modelling and analysis, Delft, 8–10 June 2005
[11] Jacobs J (2004) Reducing delays by means of computer-aided ’on-the-spot’ rescheduling. In: Allan J, Brebbia CA, Hill RJ, Sciutto G, Sone S (eds) Computers in railways IX. WIT, Southampton, pp 603–612
[12] Kauppi A, Wikström J, Sandblad B, Andersson AW (2006) Future train traffic control: control by re-planning. Cogn Technol Work 8(1):50–56 · doi:10.1007/s10111-005-0019-3
[13] Mascis A, Pacciarelli D (2002) Job shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143(3):498–517 · Zbl 1082.90528 · doi:10.1016/S0377-2217(01)00338-1
[14] Mascis A, Pacciarelli P, Pranzo M (2004) Scheduling models for short-term railway traffic optimization. In: Proceedings of the 9th international conference on computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems, San Diego, 9–11 August 2004 · Zbl 1168.90460
[15] Mazzarello M, Ottaviani E (2007) A traffic management system for real-time traffic optimization in railways. Transp Res Part B 41(2):246–274 · doi:10.1016/j.trb.2006.02.005
[16] Oh SM, Hong SH, Choi IC (2004) Railway conflict detection and resolution in the Korean railway system. In: Allan J, Brebbia CA, Hill RJ, Sciutto G, Sone S (eds) Computers in railways IX. WIT, Southampton, pp 675–684
[17] Ovacik IM, Uzsoy R (1997) Decomposition methods for complex factory scheduling problems. Kluwer, Boston
[18] Pacciarelli D, Pranzo M (2006) Speed regulation in rail networks. In: van Zuylen HJ, Middelham F (eds) Proceedings of the 11th IFAC symposium on control in transportation systems, Delft, 29–31 August 2006
[19] Pachl J (2002) Railway operation and control. VTD Rail, Mountlake Terrace
[20] Pardalos P, Resende G (2002) Handbook of applied optimization. Oxford University Press, New York · Zbl 0996.90001
[21] Rodriguez J (2000) Empirical study of a railway traffic management constraint programming model. In: Allan J, Hill RJ, Brebbia CA, Sciutto G, Sone S (eds) Computers in railways VII. WIT, Southampton, pp 1017–1025
[22] Rodriguez J (2007) A constraint programming model for real-time trains scheduling at junctions. Transp Res Part B 41(2):231–245 · doi:10.1016/j.trb.2006.02.006
[23] Törnquist J (2005) Computer-based decision support for railway traffic scheduling and dispatching: a review of models and algorithms. In: 5th workshop on algorithmic methods and models for optimization of railways. http://drops.dagstuhl.de/opus/volltexte/2006/659
[24] Törnquist J, Persson JA (2007) N-tracked railway traffic re-scheduling during disturbances. Transp Res Part B 41(3):342–362 · doi:10.1016/j.trb.2006.06.001
[25] van den Top J (2006) Effectiveness of performance indicators and process control in Dutch rail transport. In: van Zuylen HJ (ed) Proceedings 9th TRAIL congress, CD-ROM. Delft University Press, Delft
[26] Zeng X, Happiette M, Rabenasolo B (1998) Analysis of the temporal decomposition procedure for scheduling with release and due dates. Eur J Oper Res 109:599–619 · Zbl 0943.90039 · doi:10.1016/S0377-2217(97)00176-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.