Skip to main content
SpringerLink
Log in

Timetabling optimization of a single railway track line with sensitivity analysis

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

The paper deals with the timetabling problem of a single-track railway line. To solve the timetabling problem, we propose a three-stage approach combining several optimization criteria. Initially and mainly, the maximum relative travel time (ratio of travel time to minimum possible travel time) is minimized subject to a set of constraints, including departure time, train speed, minimum and maximum dwell time, and headway at track segments and stations. Since this problem has many solutions, the process is repeated for other trains, keeping the relative travel times of the critical train fixed, until all trains have been assigned their optimal relative travel times. In the second stage, the prompt allocation of trains is a secondary objective, and finally, in the third stage, the one minimizing the sum of the station dwell times of all trains, keeping the relative travel times constant, is selected to reduce fuel consumption, as a tertiary objective. To consider the user preferences in the optimization problems, the user preference departure time is used instead of the actual planned departure times. In order to guarantee that the exact or a very good approximate global optimum is attained, an algorithm based on the bisection rule is used. This method allows the computation time to be reduced in at least one order of magnitude for 42 trains. The problem of sensitivity analysis is also discussed, and closed form formulas for the sensitivities in terms of the dual variables are given. Several examples of applications are presented to illustrate the goodness of the proposed method. The results show that an adequate selection of intermediate stations and of the departure times are crucial in the good performance of the line and that inadequate spacings between consecutive trains can block the line. In addition, it is shown that, in order to improve performance, regional trains must be scheduled just ahead of or following the long distance trains, rather than having independent schedules. The sensitivities are shown to be very useful in identifying critical trains, segments, stations, departure times, and headways and in suggesting line infrastructure changes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Abbreviations

e ij ::

Leaving time for train i from segment j.

pi,j::

Actual running time for train i at segment j.

r i ::

Actual departure time of train i from its first station.

s ij ::

Entering time for train i at segment j.

\(x_{i,i_{1},j}\) ::

A binary variable, which takes value 1 if train i 1 is scheduled before train i 2 in segment j.

Z::

Objective function value.

d ij ::

Minimum required station dwell time before train i entering segment j.

\(\bar{d}_{ij}\) ::

Maximum required station dwell time before train i entering segment j.

gaprel::

Tolerance for the relative gap.

h j ::

Minimum headway between entrance and exit times of two consecutive trains at segment j.

i::

Train index.

itermax ::

Maximum number of iterations.

I::

Set of all trains.

I0::

Subset of trains.

j::

Segment index.

k::

Route segment index.

ℓ::

Segment end index (1 origin, 2 destination).

M::

A large number.

m i ::

Total number of segments on route of train i.

n::

Node index.

p ij ::

Running time for train i at segment j.

p ℓ ij ,p u ij ::

Lower and upper bounds, respectively, of running time for train i at segment j.

r 0 i ::

User desired departure time.

r ℓ i ,r u i ::

Lower and upper bounds, respectively, of departure time from the origin station for train i.

S*::

A given bound and the optimal value of S.

t0::

Maximum computation time for one trial.

t 0 i ::

Reference time for train i, that is, free running time of train i, including station dwells.

\(t_{i_{1}}^{*}\) ::

Maximum relative travel time.

(t min ,t max )::

Is the time interval when trains circulate (it excludes maintenance periods).

u::

Station index.

v ij ::

Takes value 1, −1, or 0 if train i travels segment j in the inbound, outbound, or no travel, respectively, in segment j.

βi,k::

Downstream station number of segment k in route of train i.

ε0::

(ε max +ε min )/2.

ε1::

Tolerance value for the relative travel time.

ε*::

Local optimal value of ε.

ε * i ::

A fixed relative travel time for train i.

εmin ,εmax ::

Lower and upper bounds of ε *.

\(\lambda_{r_{i}}\) ::

Dual variables.

\(\mu_{i_{1},i_{2},j}^{k}\) ::

Dual variables giving the changes in the optimum maximum relative travel time due to a change of the headway h j for segment j and trains i 1 and i 2.

\(\mu_{r_{i}}^{\ell},\mu_{r_{i}}^{u}\) ::

Dual variables associated with the corresponding lower and upper bounds.

μ t ::

Dual variable.

\(\mu_{d_{ik}},\mu_{\bar{d}_{ik}}\) ::

Dual variables associated with the corresponding lower and upper bounds of dwell station.

\(\mu_{t_{i}}^{\min},\mu_{t_{i}}^{\min}\) ::

Dual variables associated with the corresponding t min  and t max .

\(\mu_{\varepsilon_{i}^{*}}\) ::

Dual variable associated with the corresponding ε * i .

σ ik ::

Segment number of the kth segment in route of train i (is equal to |route(i,k)|).

References

  • Adenso-Diaz B, González MO, González-Torre P (1999) On-line timetable re-scheduling in regional train services. Transp Res Part B 33(6):387–398

    Article  Google Scholar 

  • Amit I, Goldfarb D (1971) The timetable problem for railways. Dev Oper Res 2:379–387

    Google Scholar 

  • Assad A (1980) Models for rail transportation. Transp Res Part A 14(3):205–220

    Article  Google Scholar 

  • Brannlund U, Lindberg PO, Nou A, Nilsson JE (1998) Railway timetabling using Lagrangian relaxation. Transp Sci 32(4):358–369

    Article  Google Scholar 

  • Cai X, Goh CJ, Mees AI (1998) Greedy heuristics for rapid scheduling of trains on a single track. IIE Trans 30(5):481–493

    Article  Google Scholar 

  • Caprara A, Fischetti M, Toth P (2002) Modeling and solving the train timetabling problem. Oper Res 50(5):851–861

    Article  Google Scholar 

  • Caprara A, Kroon L, Monaci M, Peeters M, Toth P (2006) Passenger railway optimization. In: Barnhart, C, Laporte, G (eds) Handbooks in operations research and management science, vol 14, pp 129–187

  • Carey M (1994a) A model and strategy for train pathing with choice of lines, platforms and routes. Transp Res Part B 28(5):333–353

    Article  Google Scholar 

  • Carey M (1994b) Extending a train pathing model from one-way to two-way track. Transp Res Part B 28(5):395–400

    Article  Google Scholar 

  • Carey M, Lockwood D (1995) A model, algorithms and strategy for train pathing. J Oper Res Soc 46(8):988–1005

    Article  Google Scholar 

  • Castillo E, Cobo A, Jubete F, Pruneda RE, Castillo C (2000) An orthogonally based pivoting transformation of matrices and some applications. SIAM J Matrix Anal Appl 22:666–681

    Article  Google Scholar 

  • Castillo E, Conejo A, Pedregal P, García R, Alguacil N (2001) Building and solving mathematical programming models in engineering and science. Pure and applied mathematics. Wiley, New York

    Google Scholar 

  • Castillo E, Jubete F, Pruneda RE, Solares C (2002) Obtaining simultaneous solutions of linear subsystems of equations and inequalities. Linear Algebra Appl 346:131–154

    Article  Google Scholar 

  • Castillo E, Hadi AS, Conejo A, Fernández-Canteli A (2004) A General Method for local sensitivity analysis with application to regression models and other optimization problems. Technometrics 46(4):430–444

    Article  Google Scholar 

  • Castillo E, Conejo A, Mínguez R, Castillo C (2006a) A closed formula for local sensitivity analysis in mathematical programming. Eng Optim 38:93–112

    Article  Google Scholar 

  • Castillo E, Conejo A, Castillo C, Mínguez R, Ortigosa D (2006b) A perturbation approach to sensitivity analysis in nonlinear programming. J Optim Theory Appl 128(1):49–74

    Article  Google Scholar 

  • Castillo E, Conejo AJ, Castillo C, Mínguez R (2007) Closed formulas in local sensitivity analysis for some classes of linear and non-linear problems. TOP 15(2):355–371

    Article  Google Scholar 

  • Conejo A, Castillo E, Mínguez R, García-Bertrand R (2006) Decomposition techniques in mathematical programming. Engineering and science applications. Springer, Berlin

    Google Scholar 

  • Chen B, Harker PT (1990) Two moments estimation of the delay on single-track rail lines with scheduled traffic. Transp Sci 24(4):261–275

    Article  Google Scholar 

  • Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–404

    Article  Google Scholar 

  • D’Ariano A, Pranzo M 2004. A real time train dispatching system based on blocking time theory. In: Proceedings of the 8th TRAIL 8th annual congress 2004, a world of transport, infrastructure and logistics, Delft, DUP Science, pp 129–152

  • Dorfman MJ, Medanic J (2004) Scheduling trains on a railway network using a discrete event model of railway traffic. Transp Res Part B 38(1):81–98

    Article  Google Scholar 

  • Enevoldsen I (1994) Sensitivity analysis of reliability-based optimal solution. J Eng Mech, ASCE 120(1):198–205

    Article  Google Scholar 

  • Frank O (1965) Two-way traffic on a single line of railway. Oper Res 14:801–811

    Article  Google Scholar 

  • Ghoseiri K, Szidarovszky F, Asgharpour MJ (2004) A multi-objective train scheduling model and solution. Transp Res Part B 38:927–952

    Article  Google Scholar 

  • Greenberg HH (1968) A branch-and-bound solution to the general scheduling problem. Oper Res 16(2):352–361

    Article  Google Scholar 

  • Haghani AE (1987) Rail freight transportation: a review of recent optimization models for train routing and empty car distribution. J Adv Transp 21:147–172

    Google Scholar 

  • Hellström P 1998. Analysis and evaluation of systems and algorithms for computer-aided train dispatching. Licentiate thesis, Uppsala University, Sweden

  • Higgins A, Kozan E (1998) Modeling train delays in urban networks. Transp Sci 32(4):346–357

    Article  Google Scholar 

  • Higgins A, Kozan E, Ferreira L (1996) Optimal scheduling of trains on a single line track. Transp Res Part B 30(2):147–161

    Article  Google Scholar 

  • Iida Y 1988. Timetable preparation by A.I. approach. In: Proceeding of European simulation multiconference, Nice, France, pp 163–168

  • Jia L-M, Zhang X-D (1993) Distributed intelligent railway traffic control based on fuzzy decision making. Fuzzy Sets Syst 62(3):255–265

    Article  Google Scholar 

  • Jovanovic D, Harker PT (1991) Tactical scheduling of rail operations: the SCAN I system. Transp Sci 25(1):46–64

    Article  Google Scholar 

  • Komaya K (1992) An integrated framework of simulation and scheduling in railway systems. In: Murthy TKS, Allan J, Hill RJ, Sciutto G, Sone S (eds) Management. Computers in railways III, vol 1. Computational Mechanics Publications, Southampton, pp 611–622

    Google Scholar 

  • Komaya K, Fukuda T 1991. A knowledge-based approach for railway scheduling. In: Proceedings of the seventh IEEE conference on artificial intelligence for applications. IEEE Comput Soc Press, pp 404–411

  • Komaya K, Fukuda T (1989) ESTRAC-III: an expert system for train track control in disturbed situations. In: Perrin JP (ed) IFAC control, computers, communications in transportation, IFAC/IFIP/IFORS Symposium, Paris, France, 19–21 September 1989. International Federation of Automatic Control by Pergamon Press, Paris, pp 147–153

    Google Scholar 

  • Kraay D, Harker PT, Chen B (1991) Optimal pacing of trains in freight railroads: model formulation and solution. Oper Res 39:82–99

    Article  Google Scholar 

  • Kraay DR, Harker PT (1995) Real-time scheduling of freight railroads. Transp Res Part B 29(3):213–229

    Article  Google Scholar 

  • Petersen ER, Taylor AJ (1982) A structured model for rail line simulation and optimization. Transp Sci 16:192–206

    Article  Google Scholar 

  • Petersen ER, Taylor AJ, Martland CD (1986) An introduction to computer aided train dispatching. J Adv Transp 20:63–72

    Article  Google Scholar 

  • Rudd DA, Storry AJ 1976. Single track railway simulation, new models and old. Rail Int June, 335–342

  • Sahin I (1999) Railway traffic control and train scheduling based on inter-train conflict management. Transp Res Part B 33(7):511–534

    Article  Google Scholar 

  • Schaefer H, Pferdmenges S 1994. An expert system for real-time train dispatching. Comput Railw (COMPRAIL) 94

  • Sobiesky JS, Barthelemy JF, Riley KM (1982) Sensitivity of optimal solutions of problem parameters. AIAA J 20(9):1291–1299

    Article  Google Scholar 

  • Sorensen JD, Enevoldsen I (1992) Sensitivity Analysis in reliability-based shape optimization. In: Optimization and artificial intelligence in civil and structural engineering, vol I. Kluwer Academic, Netherlands, pp 617–637

    Google Scholar 

  • Szpigel B (1973) Optimal train scheduling on a single track railway. Operations research, vol 72, pp 343–352. North-Holland, Amsterdam

    Google Scholar 

  • Vansteenwegen P, Van Oudheusden D (2007) Decreasing the passenger waiting time for an intercity rail network. Transp Res Part B 41:478–492

    Article  Google Scholar 

  • Vanderplaats G (1984) Numerical optimization techniques for engineering design with applications. McGraw-Hill, New York

    Google Scholar 

  • Vieira P, Neto LE, Bessa E, Gomide F 1999. Railway dispatch and control. In: Proceedings for NAFIPS—the 18th international conference of the North American fuzzy information processing society, pp 134–138

  • Zhou X, Zhong M (2005) Bi-criteria train scheduling for high-speed passenger railroad planning applications. Eur J Oper Res 167(3):752–771

    Article  Google Scholar 

  • 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

  • Zhou X, Zhong M (2007) Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds. Transp Res B 41:320–341

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Computational Sciences, University of Cantabria, 39005, Santander, Spain

    Enrique Castillo

  2. Department of Civil Engineering, University of Castilla-La Mancha, 13071, Ciudad Real, Spain

    Enrique Castillo, Inmaculada Gallego, José María Ureña & José María Coronado

Authors
  1. Enrique Castillo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Inmaculada Gallego
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José María Ureña
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. José María Coronado
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Enrique Castillo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Castillo, E., Gallego, I., Ureña, J.M. et al. Timetabling optimization of a single railway track line with sensitivity analysis. TOP 17, 256–287 (2009). https://doi.org/10.1007/s11750-008-0057-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-008-0057-0

Keywords

Mathematics Subject Classification (2000)

Search

Navigation