zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

90B35Scheduling theory, deterministic
90C29Multi-objective programming; goal programming
90B06Transportation, logistics
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, No. 33, 387-398 (1999)
[2] Assad, A.: Models for rail transportation. Transportation research A, No. 14, 205-220 (1980)
[3] Bhat, C.: A heteroscedastic extreme value model of intercity travel mode choice. Transportation research B, No. 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)
[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, No. 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, No. 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, No. 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, No. 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, No. 30, 147-161 (1996)
[14] ILOG, 2001. ILOG Cplex 7.1, Reference Manual
[15] Kraay, D. R.; Harker, P. T.: Real-time scheduling of freight railroads. Transportation research B, No. 29, 213-229 (1995)
[16] Kraft, E. R.: A branch and bound procedure for optimal train dispatching. Journal of the transportation research forum 28, No. 1, 263-276 (1987)
[17] Kraft, E.R., 1998. A reservations-based railway network operations management system. Ph.D. Dissertation, Department of Systems Engineering, University of Pennsylvania, Philadelphia, PA
[18] KPMG Peat Marwick, Koppelman, F.S., 1990. Analysis of the market demand for high speed rail in the Quebec-Ontario corridor. Report produced for Ontario/Quebec Rapid Train Task Force, KPMG Peat Marwick, Vienna, VA
[19] Larson, R.; Odoni, A.: Urban operations research. (1981)
[20] Ma, J., Hu, S., Xu, H., Fan, J., 2002. A multi-objective model for train working diagram for Jinghu high-speed train line. In: Proceedings of the Third International Conference on Traffic and Transportation, ICTTS, Beijing, pp. 350-355
[21] Nagar, A.; Haddock, J.; Heragu, S.: Multiple and bicriteria scheduling: A literature survey. European journal of operational research 81, No. 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, No. 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, No. 2, 356-373 (1996) · Zbl 0943.90584
[24] Nie, L., Hu, A., Zhang, X., 2000. Simulation analysis of traffic organization on high speed railway. In: Proceedings of the Second International Conference on Traffic and Transportation, ICTTS, Beijing, pp. 929-934
[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)
[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, No. 1, 68-79 (1990)
[27] Sabuncuoglu, I.; Bayiz, M.: Job shop scheduling with beam search. European journal of operational research 118, No. 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, No. 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, No. 2, 435-449 (1999)
[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, No. 2, 431-450 (1998) · Zbl 0943.90042
[31] Szpigel, B.: Optimal train scheduling on a single track railway, operations research’72. (1973)
[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, No. 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, No. 4, 505-526 (2003) · Zbl 1026.90044
[35] Von Neumann, J.; Morgenstern, O.: Theory of games and economics behaviour. (1947) · Zbl 1241.91002
[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, No. 36, 277-289 (2002)
[37] Zhou, L., Hu, S., Ma, J., Yue, Y., 1998. Network hierarchy parallel algorithm of automatic train scheduling. In: Proceedings of the Conference on Traffic and Transportation Studies, ICTTS, pp. 358-368