Abstract
In this paper, an effective estimation of distribution algorithm (EDA) is presented for solving the multi-track train scheduling problem (MTTSP). The individual of the EDA is represented as the permutation of train priority. With a proper track assignment rule, the individual is decoded into feasible schedule. In addition, the EDA builds a probability model for describing the distribution of the solution space. In every generation, it samples the promising region for generating new individuals and updates the probability model with the superior population. Moreover, the influence of parameter setting is investigated based on design-of-experiment method and a set of suitable parameter values is suggested. Simulation results based on some instances and comparisons with the existing algorithm demonstrate the effectiveness and efficiency of the EDA.
This is a preview of subscription content, log in via an institution to check access.
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
Gholami, O., Sotskov, Y.N., Werner, F.: Job-Shop Problems with Objectives Appropriate to Train Scheduling in a Single-Track Railway. In: Proceedings of 2nd International Conference on Simulation and Modeling Methodologies, Technologies and Applications, Rome, pp. 425–430 (2012)
Ghoseiri, K., Szidarovszky, F., Asgharpour, M.J.: A Multi-Objective Train Scheduling Model and Solution. Transportation Research Part B: Methodological 38(10), 927–952 (2004)
Dorfman, M.J., Medanic, J.: Scheduling Trains on a Railway Network Using a Discrete Event Model of Railway Traffic. Transportation Research Part B: Methodological 38(1), 81–98 (2004)
Zhou, X., Zhong, M.: Bicriteria Train Scheduling for High-Speed Passenger Railroad Planning Applications. European Journal of Operational Research 167(3), 752–771 (2005)
D’ariano, A., Pacciarelli, D., Pranzo, M.: A Branch and Bound Algorithm for Scheduling Trains in a Railway Network. European Journal of Operational Research 183(2), 643–657 (2007)
Burdett, R.L., Kozan, E.: A Disjunctive Graph Model and Framework for Constructing New Train Schedules. European Journal of Operational Research 200(1), 85–98 (2010)
Liu, S.Q., Kozan, E.: Scheduling Trains as a Blocking Parallel-Machine Job Shop Scheduling Problem. Computers & Operations Research 36(10), 2840–2852 (2009)
Zhang, Q.L., Chen, Y.S.: Train Scheduling Problem and Its Solution Based on Hybrid Particle Swarm Optimization Algorithm. China Mechanical Engineering 24(14), 1916–1922 (2013)
Zhang, Q.L., Chen, Y.S.: Hybrid Particle Swarm Optimization Algorithm for Hybrid Flow Shop Scheduling Problem with Blocking. Information and Control 42(2), 252–257 (2013)
Wang, S.Y., Wang, L., Fang, C., Xu, Y.: Advances in Estimation of Distribution Algorithms. Control and Decision 27(7), 961–966 (2012)
Wang, L., Fang, C.: An Effective Estimation of Distribution Algorithm for the Multi-Mode Resource-Constrained Project Scheduling Problem. Computer & Operations Research 39(2), 449–460 (2012)
Wang, L., Wang, S.Y., Liu, M.: A Pareto-Based Estimation of Distribution Algorithm for the Multi-Objective Flexible Job-Shop Scheduling Problem. International Journal of Production Research 51(12), 3574–3592 (2013)
Wang, L., Wang, S.Y., Xu, Y., Zhou, G., Liu, M.: A Bi-Population Based Estimation of Distribution Algorithm for the Flexible Job-Shop Scheduling Problem. Computers & Industrial Engineering 62(4), 917–926 (2012)
Wang, S.Y., Wang, L., Liu, M., Xu, Y.: An Effective Estimation of Distribution Algorithm for the Flexible Job-Shop Scheduling Problem with Fuzzy Processing Time. International Journal of Production Research 51(12), 3778–3793 (2013)
Wang, S.Y., Wang, L., Liu, M., Xu, Y.: An Effective Estimation of Distribution Algorithm for Solving the Distributed Permutation Flow-Shop Scheduling Problem. International Journal of Production Economics 145(1), 387–396 (2013)
Larranaga, P., Lozano, J.A.: Estimation of distribution algorithms: A new tool for evolutionary computation. Springer, Netherlands (2002)
Wang, L.: Shop scheduling with genetic algorithms. Tsinghua University & Springer Press, Beijing (2003)
Montgomery, D.C.: Design and analysis of experiments. John Wiley & Sons, Arizona (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang, S., Wang, L. (2014). An Effective Estimation of Distribution Algorithm for Multi-track Train Scheduling Problem. In: Huang, DS., Jo, KH., Wang, L. (eds) Intelligent Computing Methodologies. ICIC 2014. Lecture Notes in Computer Science(), vol 8589. Springer, Cham. https://doi.org/10.1007/978-3-319-09339-0_70
Download citation
DOI: https://doi.org/10.1007/978-3-319-09339-0_70
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09338-3
Online ISBN: 978-3-319-09339-0
eBook Packages: Computer ScienceComputer Science (R0)