zbMATH — the first resource for mathematics

Examples
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.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
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)
Timetabling optimization of a mixed double- and single-tracked railway network. (English) Zbl 1205.90118
Summary: The paper deals with the timetabling problem of a mixed multiple- and single-tracked railway network. Out of all the solutions minimizing the maximum relative travel time, the one minimizing the sum of the relative travel times is selected. User preferences are taken into account in the optimization problems, that is, the desired departure times of travellers are used instead of artificially planned departure times. To find the global optimum of the optimization problem, an algorithm based on the bisection rule is used to provide sharp upper bounds of the objective function together with one trick that allows us to drastically reduce the number of binary variables to be evaluated by considering only those which really matter. These two strategies together permit the memory requirements and the computation time to be reduced, the latter exponentially with the number of trains (several orders of magnitude for existing networks), when compared with other methods. Several examples of applications are presented to illustrate the possibilities and excellences of the proposed method. The model is applied to the case of the existing Madrid-Sevilla high-speed line (double track), together with several extensions to Toledo, Valencia, Albacete, and Málaga, which are contemplated in the future plans of the high-speed train Spanish network. The results show that the computation time is reduced drastically, and that in some corridors single-tracked lines would suffice instead of double-tracked lines.
MSC:
90B35Scheduling theory, deterministic
90B10Network models, deterministic (optimization)
90B06Transportation, logistics
90C26Nonconvex programming, global optimization
References:
[1]A. Caprara, L. Kroon, M. Monaci, M. Peeters, P. Toth, Passenger railway optimization, in: C. Barnhart, G. Laporte (Eds.), Handbooks in Operations Research and Management Science, vol. 14, 2006, pp. 129 – 187.
[2]Carey, M.: A model and strategy for train pathing with choice of lines, platforms and routes, Transp. res. Part B 28, No. 5, 333-353 (1994)
[3]Carey, M.; Lockwood, D.: A model, algorithms and strategy for train pathing, J. oper. Res. soc. 46, No. 8, 988-1005 (1995) · Zbl 0832.90068
[4]Higgins, A.; Kozan, E.; Ferreira, L.: Optimal scheduling of trains on a single line track, Transp. res. Part B 30, No. 2, 147-161 (1996)
[5]Cordeau, J. F.; Toth, P.; Vigo, D.: A survey of optimization models for train routing and scheduling, Transp. sci. 32, No. 4, 380-404 (1998) · Zbl 0987.90507 · doi:10.1287/trsc.32.4.380
[6]Zhou, X.; Zhong, M.: Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds, Transp. res. B 41, No. 3, 320-341 (2007)
[7]Sahin, I.: Railway traffic control and train scheduling based on inter-train conflict management, Transp. res. Part B 33, No. 7, 511-534 (1999)
[8]Jia, L-M.; Zhang, X-D.: Distributed intelligent railway traffic control based on fuzzy decision making, Fuzzy sets syst. 62, No. 3, 255-265 (1993)
[9]Kraay, D. R.; Harker, P. T.: Real-time scheduling of freight railroads, Transp. res. Part B 29, No. 3, 213-229 (1995)
[10]A. D’Ariano, M. Pranzo, A real time train dispatching system based on blocking time theory, in: Proceedings of the Eighth TRAIL Eighth Annual Congress 2004, A World of Transport, Infrastructure and Logistics, Delft, DUP Science, 2004, pp.129 – 152.
[11]D’ariano, A.; Pranzo, M.; Hansen, I. A.: Conflict resolution and train speed coordination for solving real-time timetable perturbations, IEEE trans. Intell.transp. syst. 8, No. 2 (2007)
[12]A. D’Ariano, D. Pacciarelli, P. Pranzo, R. Hemelrijk, Evaluating the performance of railway dynamic traffic management, in: Proceedings of the 11th World Conference on Transport Research, Berkeley, University of California, USA, 2007, pp. 1 – 12.
[13]Törnquist, J.; Persson, J. A.: N-tracked railway traffic re-scheduling during disturbances, Transp. res. B 41, No. 3, 342-362 (2007)
[14]Petersen, E. R.; Taylor, A. J.; Martland, C. D.: An introduction to computer aided train dispatching, J. adv. Transp. 20, 63-72 (1986)
[15]Ghoseiri, K.; Szidarovszky, F.; Asgharpour, M. J.: A multi-objective train scheduling model and solution, Transp. res. Part B 38, No. 10, 927-952 (2004)
[16]P. Hellström, Analysis and Evaluation of Systems and Algorithms for Computer-aided Train Dispatching, Licentiate Thesis, Uppsala University, Sweden, 1998.
[17]Amit, I.; Goldfarb, D.: The timetable problem for railways, Dev. oper. Res. 2, 379-387 (1971)
[18]Assad, A.: Models for rail transportation, Transp. res. Part A 14, No. 3, 205-220 (1980)
[19]Haghani, A. E.: Rail freight transportation: a review of recent optimization models for train routing and empty car distribution, J. adv. Transp. 21, 147-172 (1987)
[20]Frank, O.: Two-way traffic on a single line of railway, Oper. res. 14, 801-811 (1965) · Zbl 0149.38201 · doi:10.1287/opre.14.5.801
[21]D.A. Rudd, A.J. Storry, Single track railway simulation, new models and old, Rail Int. (1976) 335 – 342.
[22]Petersen, E. R.; Taylor, A. J.: A structured model for rail line simulation and optimization, Transp. sci. 16, No. 2, 192-206 (1982)
[23]Y. Iida, Timetable preparation by A.I. approach, in: Proceeding of European Simulation Multiconference, Nice, France, 1988, pp. 163 – 168.
[24]Komaya, K.; Fukuda, T.: ESTRAC-III: an expert system for train track control in disturbed situations, IFAC control, computers, communications in transportation, IFAC/IFIP/IFORS symposium, Paris, France, 19 – 21 September, 1989, 147-153 (1989)
[25]Komaya, K.; Fukuda, T.: A knowledge-based approach for railway scheduling, , 404-411 (1991)
[26]Komaya, K.: An integrated framework of simulation and scheduling in railway systems, Management 1, 611-622 (1992)
[27]H. Schaefer, S. Pferdmenges, An expert system for real-time train dispatching, in: Computers in Railways (COMPRAIL) IV, Vol 2 Railway Operations, 1994, pp. 27 – 34.
[28]P. Vieira, L.E. Neto, E. Bessa, F. Gomide, Railway dispatch and control, in: Proceedings for NAFIPS – The 18th International Conference of the North American Fuzzy Information Processing Society, 1999, pp. 134 – 138.
[29]Szpigel, B.: Optimal train scheduling on a single track railway, , 343-352 (1973)
[30]Jovanovic, D.; Harker, P. T.: Tactical scheduling of rail operations: the SCAN I system, Transp. sci. 25, No. 1, 46-64 (1991)
[31]Kraay, D.; Harker, P. T.; Chen, B.: Optimal pacing of trains in freight railroads: model formulation and solution, Oper. res. 39, 82-99 (1991)
[32]Carey, M.: Extending a train pathing model from one-way to two-way track, Transp. res. Part B 28, No. 5, 395-400 (1994)
[33]Brannlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J. E.: Railway timetabling using Lagrangian relaxation, Transp. sci. 32, No. 4, 358-369 (1998) · Zbl 1004.90035 · doi:10.1287/trsc.32.4.358
[34]Castillo, E.; Gallego, I.; Ureña, J. M.; Coronado, J. M.: Timetabling optimization of a single railways track line with sensitivity analysis, Top 17, No. 2, 256-287 (2009) · Zbl 1181.90063 · doi:10.1007/s11750-008-0057-0
[35]S. Mackenzie, Train timetabling on complex networks, in: Proceedings from the Conference on Railway Engineering (CORE2000), Adelaide, Australia, 2000.
[36]Zhou, X.; Zhong, M.: Bi-criteria train scheduling for high-speed passenger railroad planning applications, Eur. J. Oper. res. 167, No. 3, 752-771 (2005) · Zbl 1077.90033 · doi:10.1016/j.ejor.2004.07.019
[37]Törnquist, J.: Railway traffic disturbance management, Transp. res. Part A: policy pract. 41, No. 3, 249-266 (2007)
[38]D’ariano, A.; Pacciarelli, D.; Pranzo, M.: A branch and bound algorithm for scheduling trains in a railway network, Eur. J. Oper. res. 183, No. 2, 643-657 (2007) · Zbl 1179.90135 · doi:10.1016/j.ejor.2006.10.034
[39]Cai, X.; Goh, C. J.; Mees, A. I.: Greedy heuristics for rapid scheduling of trains on a single track, IIE trans. 30, No. 5, 481-493 (1998)
[40]Caprara, A.; Fischetti, M.; Toth, P.: Modeling and solving the train timetabling problem, Oper. res. 50, No. 5, 851-861 (2002) · Zbl 1163.90482 · doi:10.1287/opre.50.5.851.362
[41]Greenberg, H. H.: A branch-and-bound solution to the general scheduling problem, Oper. res. 16, No. 2, 352-361 (1968) · Zbl 0155.28704 · doi:10.1287/opre.16.2.353
[42]Adenso-Diaz, B.; González, M. O.; González-Torre, P.: On-line timetable re-scheduling in regional train services, Transp. res. Part B 33, No. 6, 387-398 (1999)
[43]Higgins, A.; Kozan, E.: Modeling train delays in urban networks, Transp. sci. 32, No. 4, 346-357 (1998) · Zbl 0987.90518 · doi:10.1287/trsc.32.4.346
[44]L. Zhou, S. Hu, J. Ma, Y. Yue, Network hierarchy parallel algorithm of automatic train scheduling, in: Proceedings of the Conference on Traffic and Transportation Studies, ICTTS, 1998, pp. 358 – 368.
[45]Dorfman, M. J.; Medanic, J.: Scheduling trains on a railway network using a discrete event model of railway traffic, Transp. res. Part B 38, No. 1, 81-98 (2004)
[46]Vansteenwegen, P.; Van Oudheusden, D.: Decreasing the passenger waiting time for an intercity rail network, Transp. res. Part B 41, No. 4, 478-492 (2007)
[47]Carey, M.; Crawford, I.: Scheduling trains on a network of busy complex stations, Transp. res. Part B 41, No. 1, 159-178 (2007)
[48]Castillo, E.; Hadi, A. S.; Conejo, A.; Fernández-Canteli, A.: A general method for local sensitivity analysis with application to regression models and other optimization problems, Technometrics 46, 430-444 (2004)
[49]Castillo, E.; Conejo, A. J.; Mı&acute, R.; Nguez; Castillo, C.: A closed formula for local sensitivity analysis in mathematical programming, Eng. optim. 38, No. 1, 93-112 (2006)
[50]Castillo, E.; Conejo, A. J.; Castillo, C.; Mínguez, R.: Closed formulas in local sensitivity analysis for some classes of linear and non-linear problems, Top 15, No. 2, 355-371 (2007) · Zbl 1145.90087 · doi:10.1007/s11750-007-0023-2
[51]Castillo, E.; Conejo, A. J.; Pedregal, P.; García, R.; Alguacil, N.: Building and solving mathematical programming models in engineering and science, Pure and applied mathematics (2001)
[52]Conejo, A.; Castillo, E.; Mínguez, R.; García-Bertrand, R.: Decomposition techniques in mathematical programming, Engineering and science applications (2006)
[53]Castillo, E.; Conejo, A.; Castillo, C.; Mínguez, R.; Ortigosa, D. A.: Perturbation approach to sensitivity analysis in nonlinear programming, Journal of optimization theory and applications 128, No. 1, 49-74 (2006) · Zbl 1130.90045 · doi:10.1007/s10957-005-7557-y