A genetic algorithm approach to periodic railway synchronization. (English) Zbl 0847.90098

Summary: We consider the compilation of timetables for periodic served railway networks. The calculation of timetables with minimal waiting time for passengers changing trains is modeled by a period network optimization problem. We present a genetic algorithm which is combined with a greedy heuristic and a local improvement procedure.


90B90 Case-oriented studies in operations research
90C90 Applications of mathematical programming
90C35 Programming involving graphs or networks


Full Text: DOI


[1] Brucker, P.; Burkard, R.; Hurink, J., Cyclic schedules for \(r\) irregularly occurring events, J. Comput. Appl. Math., 30, 173-189 (1990) · Zbl 0718.90043
[2] Brucker, P.; Hurink, J., A railway scheduling problem, Z. Opns Res., A223-A227 (1986) · Zbl 0617.90046
[3] Burkard, R. E., Optimal schedules for periodically recurring events, Discrete Appl. Math., 15, 167-180 (1986) · Zbl 0614.90050
[4] Davis, L., (Handbook of Genetic Algorithms (1990), Van Nostrand Rheinold: Van Nostrand Rheinold New York)
[5] Domschke, W., Schedule synchronization for public transit networks, OR Spektrum, 17-24 (1989) · Zbl 0658.90034
[6] Goldberg, D., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Boston · Zbl 0721.68056
[7] Grefenstette, J., Incorporating problem specific knowledge into genetic algorithms, (Davis, L., Genetic Algorithms and Simulated Annealing (1987)), 42-60
[8] Holland, J., Adaptation in Natural and Artificial Systems (1975), Michigan Press
[9] Jog, P.; Suh, J.; van Gucht, D., The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem, (Proceedings of the Third International Conference on Genetic Algorithms (1989)), 110-115
[10] Mühlenbein, H.; Gorges-Schleuter, M.; Krämer, O., Evolution algorithms in combinatorial optimization, Parallel Comput., 7, 65-85 (1988) · Zbl 0646.65054
[11] Nachtigall, K., Exact solution methods for periodic programs, Hildesheimer Informatik-Berichte 14/93 (1993)
[13] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM J. Discrete Math., 2, 550-581 (1989) · Zbl 0676.90030
[14] Ulder, N.; Pesch, E.; van Laarhoven, P.; Bandelt, H.; Aarts, E., Genetic local search algorithms for the traveling salesman problems, (Schwefel, H.; Männer, R., Parallel problem solving from nature (1991), Springer: Springer Berlin), 109-116
[15] Vaessens, R.; Aarts, E.; van Lint, J., Genetic algorithms in coding theory—a table for \(A_3(n, d)\), Discrete Appl. Math., 71-87 (1993) · Zbl 0780.94014
[16] Weigand, W., The man-machine dialogue and timetable planning, Rail Int., 8-25 (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.