Bicriteria train scheduling for high-speed passenger railroad planning applications. (English) Zbl 1077.90033

Summary: This paper is concerned with a double-track train scheduling problem for planning applications with multiple objectives. Focusing on a high-speed passenger rail line in an existing network, the problem is to minimize both (1) the expected waiting times for high-speed trains and (2) the total travel times of high-speed and medium-speed trains. By applying two practical priority rules, the problem with the second criterion is decomposed and formulated as a series of multi-mode resource constrained project scheduling problems in order to explicitly model acceleration and deceleration times. A branch-and-bound algorithm with effective dominance rules is developed to generate Pareto solutions for the bicriteria scheduling problem, and a beam search algorithm with utility evaluation rules is used to construct a representative set of non-dominated solutions. A case study based on Beijing-Shanghai high-speed railroad in China illustrates the methodology and compares the performance of the proposed algorithms.


90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
90B06 Transportation, logistics and supply chain management


Full Text: DOI


[1] Adenso-Diaz, B.; Gonzalez, M. O.; Gonzalez-Torre, P., On-line timetable re-scheduling in regional train services, Transportation Research B, 33, 387-398 (1999)
[2] Assad, A., Models for rail transportation, Transportation Research A, 14, 205-220 (1980)
[3] Bhat, C., A heteroscedastic extreme value model of intercity travel mode choice, Transportation Research B, 29, 471-483 (1995)
[4] Brannlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J. E., Railway timetabling using Lagrangian relaxation, Transportation Science, 32, 358-369 (1998) · Zbl 1004.90035
[5] Brooke, A.; Kendrick, D.; Meeraus, A., GAMS—A User’s Guide (Release 2.50) (2000), The Scientific Press: The Scientific Press Redwood City, CA
[6] Brucker, P.; Drexl, A.; Mohring, R.; Newmann, K.; Pesch, E., Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research, 112, 1, 3-41 (1999) · Zbl 0937.90030
[7] Bussieck, M. R.; Kreuzer, P.; Zimmermann, U. T., Optimal lines for railway systems, European Journal of Operational Research, 96, 1, 54-63 (1997) · Zbl 0926.90005
[8] Chang, Y. H.; Yeh, C. H.; Shen, C. C., A multiobjective model for passenger train services planning: application to Taiwan’s high-speed rail line, Transportation Research B, 34, 91-106 (2000)
[9] Cordeau, J.-F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transportation Science, 32, 380-404 (1998) · Zbl 0987.90507
[10] Framinan, J. M.; Leisten, R.; Ruiz-Usano, R., Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimization, European Journal of Operational Research, 141, 3, 559-569 (2002) · Zbl 1081.90555
[11] Greenberg, H. H., A branch and bound solution to the general scheduling problem, Operations Research, 16, 352-361 (1968) · Zbl 0155.28704
[12] Higgins, A.; Kozan, E., Modeling train delays in urban networks, Transportation Science, 32, 346-357 (1998) · Zbl 0987.90518
[13] Higgins, A.; Kozan, E.; Ferreira, L., Optimal scheduling of trains on a single line track, Transportation Research B, 30, 147-161 (1996)
[15] Kraay, D. R.; Harker, P. T., Real-time scheduling of freight railroads, Transportation Research B, 29, 213-229 (1995)
[16] Kraft, E. R., A branch and bound procedure for optimal train dispatching, Journal of the Transportation Research Forum, 28, 1, 263-276 (1987)
[19] Larson, R.; Odoni, A., Urban Operations Research (1981), Prentice-Hall: Prentice-Hall NJ
[21] Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: A literature survey, European Journal of Operational Research, 81, 1, 88-104 (1995) · Zbl 0913.90178
[22] Nazareth, T.; Verma, S.; Bhattacharya, S.; Bagchi, A., The multiple resource constrained project scheduling problem: A breadth-first approach, European Journal of Operational Research, 112, 2, 347-366 (1999) · Zbl 0938.90031
[23] Neppalli, V. R.; Chen, C.-L.; Gupta, J. N.D., Genetic algorithms for the two-stage bicriteria flow shop problem, European Journal of Operational Research, 95, 2, 356-373 (1996) · Zbl 0943.90584
[25] Patterson, J. H.; Slowiski, R.; Talbot, F. B.; Weglarz, J., An algorithm for a general class of precedence and resource constrained scheduling problems. Advances in Project Scheduling (1989), Elsevier, pp. 3-28
[26] Patterson, J. H.; Slowiski, R.; Talbot, F. B.; Weglarz, J., Computational experience with a backtracking algorithm for solving a general class of resource constrained scheduling problems, European Journal of Operational Research, 90, 1, 68-79 (1990) · Zbl 1403.90678
[27] Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 2, 390-412 (1999) · Zbl 0940.90037
[28] Sahin, I., Railway traffic control and train scheduling based on inter-train conflict management, Transportation Research B, 33, 511-534 (1999)
[29] Sayin, E.; Karabati, S., A bicriteria approach to the two-machine flow shop scheduling problem, European Journal of Operational Research, 113, 2, 435-449 (1999) · Zbl 0957.90064
[30] Sprecher, A.; Drexl, A., Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm, European Journal of Operational Research, 107, 2, 431-450 (1998) · Zbl 0943.90042
[31] Szpigel, B., Optimal train scheduling on a single track railway, Operations Research’72 (1973), North-Holland: North-Holland Amsterdam, Netherlands, pp. 343-352
[32] T’kindt, V.; Billaut, J.-C., Multicriteria scheduling problems: A survey, RAIRO—Recherche Opérationnelle/Operations Research, 35, 143-163 (2001) · Zbl 1014.90046
[33] T’kindt, V.; Monmarché, N.; Tercinet, F.; Laügt, D., An Ant Colony optimization algorithm to solve a 2-machine bicriteria flow shop scheduling problem, European Journal of Operational Research, 142, 2, 250-257 (2002) · Zbl 1082.90592
[34] T’kindt, V.; Gupta, J. N.D.; Billaut, J.-C., Two-machine flow shop scheduling with a secondary criterion, Computers and Operations Research, 30, 4, 505-526 (2003) · Zbl 1026.90044
[35] Von Neumann, J.; Morgenstern, O., Theory of Games and Economics Behaviour (1947), Princeton University Press: Princeton University Press Princeton, NJ
[36] Wong, W. G.; Han, B. M.; Ferreira, L.; Zhu, X. N.; Sun, Q. X., Evaluation of management strategies for the operation of high-speed railways in China, Transportation Research A, 36, 277-289 (2002)
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.