Heuristic approach to train rescheduling
DOI:
https://doi.org/10.2298/YJOR0701009MKeywords:
train rescheduling, job shop scheduling, constraint programming, heuristicsAbstract
Starting from the defined network topology and the timetable assigned beforehand, the paper considers a train rescheduling in respond to disturbances that have occurred. Assuming that the train trips are jobs, which require the elements of infrastructure - resources, it was done by the mapping of the initial problem into a special case of job shop scheduling problem. In order to solve the given problem, a constraint programming approach has been used. A support to fast finding "enough good" schedules is offered by original separation, bound and search heuristic algorithms. In addition, to improve the time performance, instead of the actual objective function with a large domain, a surrogate objective function is used with a smaller domain, if there is such. .References
Bater, W.M., “Computer aided railway engineering”, in: Mellit, B., Hill R.J., Allan J., Sciutto, G., Brebbia, C.A. (Eds.), Computers in Railways VI, WIT Press, 1998, 199-211.
Cai, X., and Goh, C.J., “A fast heuristic for the train scheduling problem”, Computers and Operations Research, 21(5) (1994) 499-510.
Chiu, C.K., et al., “A constraint-based interactive train rescheduling tool”, Proceedings of Second International Conference on Principles and Practice of Constraint Programming, 1996, 104-118.
Cowling, P., Johansson, M., “Using real-time information for effective dynamic scheduling”, European Journal of Operational Research, 139(2) (2002) 230-244.
Čicak, M., et al., Models for Establishing the Railway Capacity, Faculty of Transport and Traffic Engineering and Želnid, Belgrade, 2002. (in Serbian)
Jones, A., and Rabelo, L.C., “Survey of job shop scheduling techniques”, Technical Paper, NISTIR, 1998.
Kreuger, P., et al., “Trip scheduling on single track networks – the TUFF train scheduler”, Workshop on Industrial Constraint Directed Scheduling, 1997, 1-12.
Marriott, K., and Stuckey, P.J., Programming with Constraints: An Introduction, MIT Press, 1998.
Mladenović, S., et al., “SIZES – software for establishing the capacity of the single track”, Proceedings of XLV ETRAN Conference, 2001, 63-66. (in Serbian)
Oliveira, E., and Smith, B.M., “A hybrid constraint-based method for single-track railway scheduling problem”, Report 2001.04, University of Leeds, 2001.
Pinedo, M., Scheduling: Theory, Algorithms and Systems, Prentice Hall, 1995.
Vieira, E.G, et al., “Rescheduling manufacturing systems: a framework of strategies, policies and methods”, Journal of Scheduling, 6 (2003) 39-62.
Downloads
Published
Issue
Section
License
Copyright (c) 2007 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
