Rescheduling of Train Shunting in Railway Stations

Masao Sugi; Hidetoshi Nagai; Masashi Yamamoto; Yusuke Shiomi; Jun Ota

doi:10.20965/ijat.2010.p0495

single-au.php

IJAT Vol.4 No.6 pp. 495-501

doi: 10.20965/ijat.2010.p0495

(2010)

Paper:

Views over last 60 days: 397

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

Received:

May 10, 2010

Accepted:

August 25, 2010

Published:

November 5, 2010

Keywords:

train shunting in railway stations, rescheduling, affected operation rescheduling approach

Abstract

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.

Cite this article as:

M. Sugi, H. Nagai, M. Yamamoto, Y. Shiomi, and J. Ota, “Rescheduling of Train Shunting in Railway Stations,” Int. J. Automation Technol., Vol.4 No.6, pp. 495-501, 2010.

Data files:

References

[1] N. Tomii, “An Introduction to Railway Systems,” Kyoritsu Shuppan, 2001 (in Japanese).
[2] 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).
[3] 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).
[4] 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.
[5] C. George, “A Theory of Distributing Train Rescheduling,” Lecture Notes in Computer Science, Vol.1051, pp. 499-517, 1996.
[6] Y. Bartal, H. Karloff, and Y. Rabani, “A Better Lower Bound for On-Line Scheduling,” Information Processing Letters, Vol.50, pp. 113-116, 1994.
[7] R. J. Abumaizar and J. A. Svestka, “Rescheduling Job Shops under Random Disruptions,” Int. J. of Production Research, Vol.35, pp. 2065-2082, 1997.
[8] 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.
[9] 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).
[10] 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.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] N. Tomii, “An Introduction to Railway Systems,” Kyoritsu Shuppan, 2001 (in Japanese).

[2] [2] 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).

[3] [3] 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).

[4] [4] 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.

[5] [5] C. George, “A Theory of Distributing Train Rescheduling,” Lecture Notes in Computer Science, Vol.1051, pp. 499-517, 1996.

[6] [6] Y. Bartal, H. Karloff, and Y. Rabani, “A Better Lower Bound for On-Line Scheduling,” Information Processing Letters, Vol.50, pp. 113-116, 1994.

[7] [7] R. J. Abumaizar and J. A. Svestka, “Rescheduling Job Shops under Random Disruptions,” Int. J. of Production Research, Vol.35, pp. 2065-2082, 1997.

[8] [8] 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.

[9] [9] 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).

[10] [10] 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.

Rescheduling of Train Shunting in Railway Stations

Masao Sugi*, Hidetoshi Nagai**, Masashi Yamamoto**, Yusuke Shiomi**, and Jun Ota***

Masao Sugi^, Hidetoshi Nagai^, Masashi Yamamoto^,
Yusuke Shiomi^, and Jun Ota^