Rescheduling of Train Shunting in Railway Stations
Masao Sugi*, Hidetoshi Nagai**, Masashi Yamamoto**,
Yusuke Shiomi**, and Jun Ota***
*Department of Mechanical Systems Engineering, Graduate School of Engineering, Tokyo University of Agriculture and Technology, 2-24-16 Naka-cho, Koganei-shi, Tokyo 184-8588, Japan
**Systems Research & Development Center, Solutions Corporation, 3-1 Minatomirai 3-chome, Nishi-ku, Yokohama-shi, Kanagawa 220-8401, Japan
***Research into Artifacts, Center for Engineering (RACE), The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8568, Japan
This paper is intended to propose rescheduling rules for train shunting in railway stations in the event of delayed arrival of trains or some problems with resources, such as tracks. In particular, we propose an algorithm using the Affected Operation Rescheduling (AOR) approach in combination with appropriatelytimed operational commutation rules to allow for rapid rescheduling operations. In the problem of the magnitude of six resources (i.e. tracks and lines) and four trains, the proposed algorithm has accomplished in about 1 millisecond train-rescheduling operations in the event of a train problemon a certain track, proving the feasibility of the obtained solutions as well as the effectiveness of the proposed algorithm.
-  N. Tomii, “An Introduction to Railway Systems,” Kyoritsu Shuppan, 2001 (in Japanese).
-  N. Tomii, J. Z. Li, and N. Fukumura, “An Algorithm for Shunting Scheduling Problems combining Probabilistic Local Search and PERT,” IEEJ Trans. on Electronics, Information, and Systems (IEEJEISS), Vol.119, No.3, pp. 29-34, 1999 (in Japanese).
-  T. Sato, Y. Kakumoto, and T. Murata, “Shunting Scheduling Method in a Railway Depot for Dealing with Changes in Operational Conditions,” IEEJ Trans. on Electronics, Information, and Systems (IEEJEISS), Vol.127, No.2, pp. 274-283, 2007 (in Japanese).
-  D. Bjorner, C. George, and S. Prehn, “Scheduling and Rescheduling of Trains,” M. G. Hinchey and J. P. Bowen, editors, Industrial-Strength Formal Methods in Practice, Springer-Verlag, London, pp. 157-184, 1999.
-  C. George, “A Theory of Distributing Train Rescheduling,” Lecture Notes in Computer Science, Vol.1051, pp. 499-517, 1996.
-  Y. Bartal, H. Karloff, and Y. Rabani, “A Better Lower Bound for On-Line Scheduling,” Information Processing Letters, Vol.50, pp. 113-116, 1994.
-  R. J. Abumaizar and J. A. Svestka, “Rescheduling Job Shops under Random Disruptions,” Int. J. of Production Research, Vol.35, pp. 2065-2082, 1997.
-  M. Gendreau, F. Guertin, J. Y. Potvin, and E. Taillard, “Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching,” Transportation Science, Vol.33, No.4, pp. 381-390, 1999.
-  T. Li,M. Sugi, H. Nagai, M. Yamamoto, Y. Shiomi, and J. Ota, “Online rescheduling in Shunting Scheduling Problems,” Proc. of JSPE Semestrial Meeting, Vol.2009-S, pp. 535-536, 2009 (in Japanese).
-  M. Sugi, M. Cheng, M. Yamamoto, H. Ito, K. Inoue, and J. Ota, “Online Rescheduling in Semiconductor Manufacturing,” Int. J. of Automation Technology (IJAT), Vol.4, No.2, pp. 184-197, 2010.