Abstract
In this paper we present a three-phase structure algorithm devised within a constraint programming paradigm to solve real-life single-track railway scheduling instances of problems. The combination of a hill-climbing, easing the process of finding iteratively improved solutions, and a branch-and-bound strategies allows us to solve 21 real-life problems in a reasonable time, 19 of them to optimality.
In addition, this paper discusses a group of practical constraints, incorporated into the software, that arise in real-life problems to which little attention has hitherto been paid. Results comparing the gain on using this approach on large instances problems are also presented.
The author is a PhD student funded by CAPES under Grant BEX-1162/96-9.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baptiste, P., Le Pape, C, and Nuijten, W. Constraint-Based Optimization and Approximation for Job-Shop Scheduling. AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, IJCAI-95, Montreal Canada, 1995.
Cai, X. and Goh, C.J. A Fast Heuristic for The Train Scheduling Problem. Computers and Operations Research, 21(5):499–510, 1994.
Higgins, A., Kozan, E., and Ferreira, L. Optimal Scheduling of Trains on a Single Line Track. Transportation Research, 30(2):147–161, 1996.
Jovanovic, D. Improving Railroad On-Time Performance: Models, Algorithms and Applications. PhD thesis, The Wharton School, University of Pennsylvania, 1989.
Kreuger, P., Carlson, M., Olsson, J., Sjoland, T., and Astro, E. Trips Scheduling on Single Track Networks-The TUFF Train Scheduler. CP’97 Workshop on Industrial Constraint-Directed Scheduling, pages 1–12, 1997.
Oliveira, E. Solving Single-Track Railway Scheduling Problem Using Constraint Programming. PhD thesis, School of Computing, University of Leeds, September 2001.
Pinedo, M. Scheduling: Theory, Algorithms and Systems. Prentice Hall, 1995.
Vaessens, R.J.M., Aarts, E.H.L., and Lenstra, J.K. Job Shop Scheduling by Local Search. INFORMS Journal on Computing, 8(3):302–317, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oliveira, E., Smith, B.M. (2001). A Combined Constraint-Based Search Method for Single-Track Railway Scheduling Problem. In: Brazdil, P., Jorge, A. (eds) Progress in Artificial Intelligence. EPIA 2001. Lecture Notes in Computer Science(), vol 2258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45329-6_36
Download citation
DOI: https://doi.org/10.1007/3-540-45329-6_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43030-8
Online ISBN: 978-3-540-45329-1
eBook Packages: Springer Book Archive