Viewing Railway Timetable Creation as Mathematical Optimization and a Scheduling Problem

I normally see a train timetable as nothing more than a table telling me what time the train will show up. It's that white sheet of paper enthroned on the station wall. Look at it with a slightly mathematical eye, though, and it turns out to be a rather fascinating creature.

Creating a timetable is not a matter of lining up departure times one after another. Tracks, stations, signals, platforms, train types, passenger flows, transfers, rolling stock, crews, delay risk. It is the craft of tailoring a schedule that holds together as a whole while keeping an eye on all of these at once. In research it goes by the train timetabling problem or the railway timetabling problem. Roughly speaking, it is a constrained scheduling problem as well as a combinatorial optimization problem.

Think of it as a giant jigsaw whose pieces keep interfering with one another. What follows, partly as a note to myself, is how that puzzle can be organized when framed as a mathematical optimization problem (honestly, it's mostly a note to myself).

Deciding Arrival and Departure Times

To begin with, what is it we actually want to decide? What a passenger wants to know is something like: depart station A at 8:00, arrive at station B at 8:03, arrive at station C at 8:10. Rephrased mathematically, it is the problem of deciding, for each train, the arrival and departure times at each station. Let train be $i$ and station be $s$. Arrival and departure times can be written as follows.

$$a_{i,s} = \text{the time train } i \text{ arrives at station } s$$ $$d_{i,s} = \text{the time train } i \text{ departs from station } s$$

So timetable creation is the problem of deciding $a_{i,s}$ and $d_{i,s}$ for every train $i$ and station $s$. Of course, you can't just pick times as you please. Running times between stations, dwell times at stations, safe spacing from the trains ahead and behind, passing on single-track sections. Platform capacity, overtaking, turnbacks, transfer connections — the constraints pile up like a mountain. And it is precisely this abundance of constraints that makes railway timetables interesting.

Running Time and Dwell Time

The most basic of them is the running time constraint. The running time from station $s$ to the next station $s+1$ has a lower bound. A train physically cannot run faster than that. Letting the lower and upper bounds of running time be $[\underline r_{i,s}, \overline r_{i,s}]$, we can write:

$$\underline r_{i,s} \le a_{i,s+1}-d_{i,s} \le \overline r_{i,s}$$

Think of the lower bound as the minimum required running time and the upper bound as the allowable time including slack. Next comes dwell time at stations. When a train reaches a station, passengers board and alight, doors are handled, and safety is confirmed. At crowded stations, dwell time stretches further. Letting the lower and upper bounds of dwell time be $[\underline w_{i,s}, \overline w_{i,s}]$, we get:

$$\underline w_{i,s} \le d_{i,s}-a_{i,s} \le \overline w_{i,s}$$

Dwell time is not merely a service condition. It is also time during which the platform is occupied. The longer a train dwells, the harder it becomes to fit following trains into that station. In high-frequency operation especially, dwell time at stations can end up determining overall capacity.

Headway and Track Capacity

On a railway, multiple trains run on the same track. So a safe spacing is needed between consecutive trains, and this is commonly called the headway. Say train $i$ runs first and train $j$ follows on the same section $(s,s+1)$. Then a minimum interval is imposed on departure and arrival times.

$$d_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s}$$ $$a_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}$$

In actual models, however, we also have to decide which train runs first. That is why 0-1 variables are often brought in. Set $x_{ij,s}=1$ if train $i$ goes first and $x_{ij,s}=0$ if train $j$ goes first.

$$d_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s}-M(1-x_{ij,s})$$ $$a_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}-M(1-x_{ij,s})$$

Here $M$ is a sufficiently large number. Around this point, timetable creation suddenly starts wearing the face of combinatorial optimization. It's no longer just about what minute a train leaves; you also have to decide, at the same time, which train to let through first.

Track as a Shared Resource

The constraints below illustrate part of a model for choosing which train goes first. Constraints covering only one ordering do not establish safe separation for the reverse ordering. A complete model needs constraints for both orders, time bounds, and a big-M value suited to those conditions.

Let's generalize a bit further. Track sections, block sections, switches, and routes inside stations can all be viewed as resources that a train occupies for a certain period. Say train $i$ occupies resource $b$ during $[u_{i,b}^{\text{in}},u_{i,b}^{\text{out}}]$, and another train $j$ wants the same resource. Then one of them has to clear it first.

$$u_{j,b}^{\text{in}} \ge u_{i,b}^{\text{out}}+\tau_b \quad \text{or} \quad u_{i,b}^{\text{in}} \ge u_{j,b}^{\text{out}}+\tau_b$$

The formula looks imposing, but what it says is entirely intuitive. Multiple trains cannot use the same track section, the same route, or the same platform at the same time. A railway timetable is, among other things, the problem of allocating such shared resources along the time axis.

Single-track sections make things harder still. On single track, up and down trains use the same line in opposite directions. One cannot enter until the other has left. Suppose up and down trains $i$ and $k$ use the same single-track section $\ell$. A binary variable $y_{ik,\ell}$ lets us write:

$$\text{enter}_{k,\ell} - \text{leave}_{i,\ell} \ge \tau_\ell - M(1-y_{ik,\ell})$$ $$\text{enter}_{i,\ell} - \text{leave}_{k,\ell} \ge \tau_\ell - M y_{ik,\ell}$$

On single track, the positions of passing stations and signal stations matter enormously. Where trains pass each other can reshape the entire timetable. Staring at the printed schedule, you'd never notice. Single-track sections are the most delicate corner of the whole puzzle.

Stations as Choke Points

It isn't only the track; stations become bottlenecks too. If a station has only two platforms, there is a ceiling on how many trains it can handle at once. So the number of trains using platform $p$ at time $t$ must not exceed capacity $C_{s,p}$.

$$\sum_{i} \mathbf{1}\{i \text{ occupies } p \text{ at } t\} \le C_{s,p}$$

In high-frequency operation, station throughput can clog up before the track itself does. A train that lingers at a station keeps the platform occupied. An occupied platform means the next train can't be let in, and delays ripple out to the trains behind.

In short, railway capacity isn't settled by how many tracks there are. Only once you include signals, blocks, platforms, switches, dwell time, and the mix of train types do you finally arrive at it. Counting the tracks and calling it a day is a little premature.

Mixing Express and Local Trains

One especially interesting aspect of railway timetables is the mix of express and local trains. Locals stop at many stations, so their travel time inevitably runs long. Expresses skip intermediate stations and are faster. Run both on the same track and, sure enough, the fast one catches up with the slow one.

That's where refuge and overtaking come in. If a local is running ahead and an express is coming up behind it, the local is held at a station with overtaking facilities and the express is let through. Mathematically, this means the order of trains gets swapped at an intermediate station. In section $(s-1,s)$ the local was ahead, but after waiting at station $s$, the express is ahead in section $(s,s+1)$.

Stations that permit this kind of order inversion are overtaking stations; where no overtaking facilities exist, the order cannot be swapped. So the difference between express and local goes beyond travel time. It is also a difference that multiplies the ordering constraints between trains. Add more expresses and speed goes up, but locals wait for overtaking more often and more track capacity gets eaten. A trade-off lurks here as well.

Transfer Connections

Transfer connections are yet another constraint. Suppose that at station $s$ we want passengers to transfer from train $i$ to train $j$. If the minimum time needed to transfer is $\tau^{\text{tr}}_{ij,s}$, the constraint is:

$$d_{j,s}-a_{i,s}\ge \tau^{\text{tr}}_{ij,s}$$

That is, train $j$ cannot depart until the transfer time has elapsed after train $i$ arrives. On regional lines and for last trains, these connections matter a great deal. Then again, holding a train to keep a connection can let its delay spill over to following trains. Protect the connection, or protect punctuality? This too is one of the vexing parts of timetable creation.

What Makes a Good Timetable

There isn't necessarily just one timetable that satisfies the constraints. So we need to define, as an objective function, what counts as a good timetable. We'd like to cut total passenger waiting time, transfer waiting time, and total travel time. We'd like to keep the required rolling stock and operating cost down.

We'd like congestion leveled out and robustness against delays. We'd like as little deviation from the existing timetable as possible. The candidates keep coming. It's a greedy wish list, if I say so myself.

But these can't necessarily all be satisfied at once. More trains may cut waiting time, but rolling stock and crew costs swell. More expresses may raise speed, yet locals end up waiting for overtaking more often, which can make things less convenient overall. More slack makes the timetable sturdier against delays, but travel time stretches and track capacity gets squeezed.

Please one side and you upset the other. Simplifying drastically, the objective function can be written as follows.

$$\min\; \alpha \cdot \text{passenger time} +\beta \cdot \text{operating cost} +\gamma \cdot \text{delay / fragility} +\delta \cdot \text{deviation from existing timetable}$$

Here $\alpha,\beta,\gamma,\delta$ are weights expressing how much each objective matters. Depending on how you set them, the resulting timetable takes on an utterly different character. One prizes speed, another holds down costs, another shrugs off delays.

Event-Activity Networks and Periodic Timetables

A representation that comes up often in timetable research is the Event-Activity Network. It expresses a timetable as a network of events and activities. Events are happenings like "train A arrives at station X," "train A departs from station X," and "train B arrives at station Y."

Activities, on the other hand, represent the relationships between events. Running between stations, dwelling at a station, transferring, and keeping safe spacing from the trains ahead and behind all count. With this representation, running time, dwell time, transfers, and headways can all be handled uniformly as time-difference constraints between events.

For periodic timetables, this leads to the Periodic Event Scheduling Problem (PESP). In PESP, each event $i$ is assigned a time $\pi_i$ within a period $T$, and for each activity $(i,j)$ the following constraint must hold.

$$l_{ij}\le \pi_j-\pi_i + T p_{ij}\le u_{ij}$$

Here $l_{ij},u_{ij}$ are the minimum and maximum time differences, and $p_{ij}$ is an integer variable that allows crossing the period boundary.

The beauty of periodic timetables is that once you design a single period, an hour or 30 minutes say, you can unroll it across the whole day. A timetable where trains come at the same minute every hour is easy for passengers to grasp, and connections are easier to line up. That said, if demand swings widely by time of day, a fully periodic timetable can turn out inefficient. So in practice, many timetables use a periodic pattern as the base and add extra services only at peak hours.

Beyond the Timetable

Finishing the timetable does not mean everyone gets to go home. In practice, the timetable becomes the input for rolling stock and crew scheduling. After a train reaches its terminal, the same vehicle may turn back as the next train. If the time needed for the turnback is $\tau^{\text{turn}}_{ij,u}$, another constraint joins the party.

$$d_{j,u} - a_{i,u} \ge \tau^{\text{turn}}_{ij,u}$$

A timetable that works on paper won't run if there aren't enough actual vehicles. The same goes for crews: drivers and conductors come with constraints on working hours, breaks, relief locations, and start and end locations. More trains means more vehicles and more crews. Tightening turnback times raises vehicle efficiency, at the cost of slack against delays.

The timetable, rolling stock scheduling, and crew scheduling are tightly bound together. Try to optimize all of it as one integrated problem, however, and the problem size balloons. So in practice, the timetable, vehicles, and crews are often planned one after another, or only the parts that need it are optimized jointly, or humans check and fix things.

Bracing for Delays

A timetable needs a certain amount of slack. Pack it tight with nothing but minimum running times and minimum dwell times, and the smallest delay will spread straight to the trains behind. So slack known as buffer time or recovery time is added.

This is indispensable for stopping delays from spreading, but add too much and travel time stretches and track capacity shrinks. With little slack, travel time is short, but delays hit hard. With lots of slack, delays are absorbed, but travel time stretches and capacity gets squeezed. Efficiency and robustness sit in a neat trade-off, and where to strike that balance is one of the key design decisions in timetable creation.

Can't We Just Hand It to a Solver?

A wide range of optimization methods is used for railway timetable problems. The headliners are Integer Programming and Mixed Integer Linear Programming. Discrete decisions like train order, platform choice, keeping connections, and route choice map neatly onto 0-1 variables.

Constraint Programming, meanwhile, is a good fit for hunting down feasible solutions under complex constraints. Graph representations such as Event-Activity Networks, space-time networks, and alternative graphs are also common. For large real-world problems, though, computing an exact optimum directly is hard. So column generation, Lagrangian relaxation, decomposition methods, heuristics, and metaheuristics get brought in.

That may come as a bit of a surprise. Hear "mathematical optimization" and you tend to picture writing a model, tossing it at a solver, and getting the optimum back. But at the scale of a real railway timetable, the constraints and objectives are large and exceptions abound. Naively dump it all on a solver and the next timetable revision may arrive before the answer does. In the end, humans draft a plan, the system evaluates it, and it gets revised as needed. I suspect that loop is the realistic approach.

That's my look at railway timetables as a mathematical optimization problem. In a nutshell, a railway timetable is a problem in which multiple trains compete for shared resources on a graph with a time axis. The resources are tracks, stations, platforms, vehicles, and crews; the requirements are safe spacing, connections, capacity, turnbacks, and delay tolerance. On top of that, passenger convenience, operating cost, and robustness have to be optimized.

Behind that white sheet on the station wall, constraints of running time, dwell time, headway, single-track passing, overtaking, transfers, vehicles, crews, and delay recovery are stacked layer upon layer. And the puzzle gets solved, every single day, within real-world limits of safety, convenience, and cost. That is exactly what makes railway scheduling so interesting.

References and Sources

Here are the materials I found especially helpful in my reading.

• Serafini, P.; Ukovich, W. A Mathematical Model for Periodic Scheduling Problems (1989). https://doi.org/10.1137/0402049
• Peeters, L. Cyclic Railway Timetable Optimization (PhD thesis, 2003). https://repub.eur.nl/pub/429/EPS2003022LIS_9058920429_PEETERS.pdf
• Caprara, A.; Fischetti, M.; Toth, P. Modeling and Solving the Train Timetabling Problem (2002). https://doi.org/10.1287/opre.50.5.851.362
• Cordeau, J.-F.; Toth, P.; Vigo, D. A Survey of Optimization Models for Train Routing and Scheduling (1998). https://doi.org/10.1287/trsc.32.4.380
• Caimi, G. et al. Periodic Railway Timetabling with Event Flexibility (2007). https://drops.dagstuhl.de/storage/01oasics/oasics-vol007-atmos2007/OASIcs.ATMOS.2007.1173/OASIcs.ATMOS.2007.1173.pdf
• Liebchen, C.; Möhring, R. The Modeling Power of the Periodic Event Scheduling Problem (2007). https://depositonce.tu-berlin.de/bitstreams/c616b6de-1dc6-4bf3-8c3b-ba9a8f2de60d/download
• Bešinović, N. et al. Review of railway timetabling developments, planning phases, goals and future directions (2021). https://doi.org/10.1080/01441647.2021.1904543
• Caimi, G.; Kroon, L.; Liebchen, C. Models for railway timetable optimization: Applicability and applications in practice (2016). https://doi.org/10.1016/j.jrtpm.2016.11.002
• Harrod, S. A tutorial on fundamental model structures for railway timetable optimization (2012). https://doi.org/10.1016/j.sorms.2012.08.002
• Petering, M.; Heydar, M.; Bergmann, D. Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming (2015). https://doi.org/10.1287/trsc.2015.0652
• Castillo, E. et al. Timetabling optimization of a single railway track line with sensitivity analysis (2009). https://doi.org/10.1007/s11750-008-0057-0
• Brännlund, U. et al. Railway Timetabling Using Lagrangian Relaxation (1998). https://doi.org/10.1287/trsc.32.4.358
• Cacchiani, V.; Caprara, A.; Toth, P. A column generation approach to train timetabling on a corridor (2008). https://doi.org/10.1007/s10288-007-0037-5
• Cacchiani, V. et al. An overview of recovery models and algorithms for real-time railway rescheduling (2014). https://doi.org/10.1016/j.trb.2014.01.009
• König, E. A review on railway delay management (2020). https://doi.org/10.1007/s12469-020-00233-1
• Yan, F.; Bešinović, N.; Goverde, R. Multi-objective periodic railway timetabling on dense heterogeneous railway corridors (2019). https://doi.org/10.1016/j.trb.2019.04.004