A Rescheduling Algorithm of Train-Group for Railway Emergencies and its Parallelization

Abstract:

In order to reduce the delays of train groups when suffering from railroad emergencies, we propose a rescheduling algorithm of train groups to reschedule trains, instead of previous just waiting. A heuristic algorithm is designed to search the proper path for the trains involved in the railroad emergencies. An evaluation criterion based on the extent of the disturbance towards the original timetable and limited time is designed to select the optimal path for each train. And a conflicts resolution strategy is designed to deal with the path and time conflicts among trains when rescheduling. In the end, due to the real-time needs of the railroad scheduling, we implement the parallel processing for the train-group rescheduling referring to the allocation of loads. Experimental results show that the rescheduling algorithm is efficient to reduce the delays of train groups and the parallel processing meets the real-time response of the train-group rescheduling well.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3680-3686
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3680
• Online since: September 2013
• Authors: Zi Feng Wang, Li Ruan, Li Min Xiao
• Keywords: Parallel Processing, Railroad Emergencies, Rescheduling, Train Groups

References

[1] Sundaravalli Narayanaswami (2012) Scheduling and Rescheduling of Railway Operations: A Review and Expository Analysis. Technol. Oper. Manag (July–December 2011) 2(2): 102–122.

DOI: 10.1007/s13727-012-0006-x

[2] C.K. Chiu (2002) A Constraint-Based Interactive Train Rescheduling Tool. Kluwer Academic Publishers. Manufactured in The Netherlands.

[3] P. E. Hart, N. J. Nilsson, and B. Raphael (1968) A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2): 100-107.

DOI: 10.1109/tssc.1968.300136

[4] http: /zh. wikipedia. org/wiki/DFS.

[5] http: /zh. wikipedia. org/wiki/BFS.

[6] Z. F. Wang (2011) Distributed train-group modeling and simulaiton based on cellular automaton and multi-agent. H. Deng et al. (Eds. ): AICI 2011, Part I, LNAI 7002, p.146–154.

[7] R. Acuna-Agost (2011) A MIP-based Local Search Method for the Railway Rescheduling Problem. NETWORKS—2011—DOI 10. 1002/net 2010 Wiley Periodicals, Inc.

DOI: 10.1002/net.20384

[8] Chikaka Hirai (2006) A new algorithm for train rescheduling using rescheduling patterns. Railway Technology Avalanche No. 14, August 10, (2006).

[9] K. Kumazawa (2008) A novel train rescheduling algorithm for correcting disrupted train operations in a dense urban environment. Wit press 199.

DOI: 10.2495/cr080551

[10] Keisuke Sato (2012) Real-time freight locomotive rescheduling and uncovered train detection during disruption. European Journal of Operational Research 221 (2012) 636–648.

DOI: 10.1016/j.ejor.2012.04.025

[11] Tomii Norio (2005) Train Rescheduling Algorithm Which Minimizes Passengers' Dissatisfaction. M. Ali and F. Esposito (Eds. ): IEA/AIE 2005, LNAI 3533, pp.829-838, (2005).

DOI: 10.1007/11504894_113

[12] Setsuo Tsuruta (1999) A Coordination Technique in A Highly Automated Train Rescheduling System. 0-7803-5731-0/99/ 1999 IEEE.

[13] http: /zh. wikipedia. org/wiki/ChinaRailwayNetwork.