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. (1998) Computer aided railway engineering. u: Mellit B., Hill R.J., Allan J., Sciutto G., Brebbia C.A. [ur.] Computers in railways VI, York, England: WIT press - Computational Mechanics Publications, Comreco Rail Ltd, str. 199-211
Cai, X., Goh, C.J. (1994) A fast heuristic for the train scheduling problem. Computers and Operations Research, 21 (5): 499
Chiu, C.K., Chou, C.M., Lee, J.H.M., Leung, H.F., Leung, Y.W. (1996) A constraint-based interactive train rescheduling tool. u: Proceedings of Second International Conference on Principles and Practice of Constraint Programming
Cowling, P., Johansson, M. (2002) Using real time information for effective dynamic scheduling. European Journal of Operational Research / EJOR, 139(2), str. 230-244
Čicak, M., Vesković, S., Mladenović, S. (2002) Models for establishing the railway capacity. Belgrade: Faculty of Transport and Traffic Engineering
Jones, A., Rabelo, L.C. (1998) Survey of job shop scheduling techniques. u: Technical Paper, NISTIR, Gaithersburg, MD: National Institute of Standards and Technology
Kreuger, P., Carlsson, M., Olsson, J., Sjoland, T., Astrom, E. (1997) Trip scheduling on single track networks: The TUFF train scheduler. u: Workshop on Industrial Constraint Directed Scheduling, 1-12
Marriott, K., Stuckey, P.J. (1998) Programming with Constraints: An Introduction. Cambridge: The Massachusetts Institute of technology Press
Mladenović, S., Vesković, S., Čicak, M. (2001) SIZES: Software for establishing the capacity of the single track. u: Proceedings of XLV ETRAN Conference, Bukovička Banja, Volume III, 63-66
Oliveira, E., Smith, B.M. (2001) A hybrid constraint-based method for single-track railway scheduling problem. u: Report 2001. 04, Leeds: School of Computing
Pinedo, M. (1995) Scheduling: Theory, algorithms and systems. Englewood Cliffs, NJ, itd: Prentice Hall
Vieira, E.G., Herrmann, J.W., Lin, E. (2003) Rescheduling manufacturing systems: A framework of strategies, policies and methods. Journal of Scheduling, 6(1): 39
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
