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

Zhou, Xuesong; Zhong, Ming

Eur. J. Oper. Res. 167, No. 3, 752-771 (2005).

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.

MSC:

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

Keywords:

Scheduling; Multiple objective programming; Transportation; Railway

Software:

CPLEX; GAMS

References:

[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)