Viewing Railway Timetable Creation as Mathematical Optimization and a Scheduling Problem

We usually see a train timetable as a table of what time a train arrives.

But looked at mathematically, it gets quite interesting.

Creating a timetable is not simply a matter of lining up departure times. It is the work of building a schedule that holds together as a whole, while simultaneously considering tracks, stations, signals, platforms, train types, passenger flows, transfers, rolling stock, crews, and delay risk.

In research, such problems are called the train timetabling problem or the railway timetabling problem. Roughly speaking, it is a constrained scheduling problem, and also a combinatorial optimization problem.

In this article, partly as a note to myself, I try to organize how railway timetable creation can be framed as a mathematical optimization problem.

What Does a Railway Timetable Decide?

First, what do we want to decide when creating a timetable?

From a passenger's point of view, the information they want looks like this.

Depart station A at 8:00
Arrive at station B at 8:03
Arrive at station C at 8:10

Mathematically, this is the problem of deciding the arrival and departure times at each station for each train.

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$$

In other words, timetable creation can be seen as the problem of deciding $a_{i,s}$ and $d_{i,s}$ for every train $i$ and station $s$.

Of course, times cannot be chosen arbitrarily.

There are many constraints: running times between stations, dwell times at stations, safe spacing between preceding and following trains, passing on single-track sections, platform capacity, overtaking, turnbacks, and transfer connections.

This abundance of constraints is what makes railway timetables interesting.

Running Time and Dwell Time

The most basic are the running time constraints.

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}$$

The lower bound is the minimum required running time, and the upper bound can be thought of as the allowable time including slack.

Next, there is dwell time at stations.

When a train reaches a station, passengers need to board and alight, doors need to be handled, and safety needs to be confirmed. At crowded stations, dwell time grows 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 just a service condition. It is also the time the platform is occupied.

In other words, the longer the dwell time, the harder it is to fit following trains into that station. In high-frequency operation especially, dwell time at stations can determine overall capacity.

Headway and Track Capacity

On railways, multiple trains run on the same track.

So a safe spacing is needed between the train ahead and the train behind. This spacing is often called the headway.

For example, suppose train $i$ runs first and train $j$ runs afterward on the same section $(s,s+1)$.

Then a minimum interval is required for 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, we also have to decide "which train runs first," so this is often expressed using 0-1 variables.

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.

From this point, railway timetable creation becomes quite combinatorial.

It is not just about deciding "what minute to dispatch." We also have to decide "which train to let through first" at the same time.

The Same Track Section Cannot Be Used Simultaneously

Generalizing a bit more, track sections, block sections, switches, and routes inside stations can be viewed as resources occupied by a train for a certain period of time.

Suppose train $i$ occupies a resource $b$ during $[u_{i,b}^{\text{in}},u_{i,b}^{\text{out}}]$.

If another train $j$ uses the same resource, one of them must pass 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$$

This is quite intuitive.

Multiple trains cannot use the same track section, the same route, or the same platform at the same time.

A railway timetable is also a problem of how to allocate such shared resources along the time axis.

Single-Track Sections Are Even Harder

On single-track sections, up and down trains use the same track in opposite directions.

So one cannot enter the section until the other has left it.

When up and down trains $i$ and $k$ use the same single-track section $\ell$, using a binary variable $y_{ik,\ell}$ we can 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 are quite important.

That is because where trains pass each other greatly changes the shape of the whole timetable.

It is hard to notice when just looking at a timetable, but the schedule for a single-track section is a rather delicate puzzle.

Platform Capacity and Station Congestion

Not only the track but also the station can be a bottleneck.

For example, if a station has only two platforms, there is a limit on the number of trains it can handle at once.

The constraint that the number of trains using platform $p$ at time $t$ does not exceed the capacity $C_{s,p}$ can be written as:

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

In high-frequency operation, station throughput can become clogged before the track itself does.

If a train stays at a station for a long time, that platform does not free up. If the platform doesn't free up, the next train can't be let in. Then delays propagate to following trains.

In other words, railway capacity is not determined only by "how many tracks there are."

It is determined by everything including signals, blocks, platforms, switches, dwell time, and the mix of train types.

What Happens When Express and Local Trains Are Mixed

One interesting aspect of railway timetables is the mix of express and local trains.

Local trains stop at many stations, so their travel time inevitably gets longer. Express trains pass through intermediate stations and are faster.

If you run these two types on the same track, the fast train catches up to the slow train.

What is needed then is refuge and overtaking.

For example, when a local train runs first and an express comes behind it, the local is stopped at a station with overtaking facilities and the express is let through first.

Mathematically, this means the order of trains is swapped at an intermediate station.

In section $(s-1,s)$ the local was ahead, but it waits at station $s$, and in section $(s,s+1)$ the express is ahead.

Stations that allow such order inversion become overtaking stations.

Conversely, where there are no overtaking facilities, order inversion is impossible.

In other words, the difference between express and local is not just a difference in travel time. It is also a difference that increases the ordering constraints between trains.

Adding more express trains raises speed, but in exchange local trains must wait more often for overtaking, and more track capacity is consumed.

There is a trade-off here too.

Transfer Connections Are Also Constraints

Transfer connections are also important in a timetable.

For example, suppose there is a station $s$ where we want passengers to transfer from train $i$ to train $j$.

If the minimum time required for the transfer is $\tau^{\text{tr}}_{ij,s}$, the constraint is:

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

In other words, train $j$ cannot depart until the time required for the transfer has passed after train $i$ arrives.

On regional lines and for last trains, these connections are quite important.

On the other hand, if a train is made to wait to keep a connection, that train's delay may propagate to following trains.

Protect the connection, or protect punctuality?

This too is one of the hard parts of timetable creation.

Objective Function: What Makes a Good Timetable

There is not necessarily only one timetable that satisfies the constraints.

So we need to define "what makes a good timetable" as an objective function.

There are many possible objectives.

• Minimize total passenger waiting time
• Minimize transfer waiting time
• Minimize total travel time
• Minimize the required rolling stock and operating cost
• Level out congestion
• Make it robust to delays
• Minimize changes from the existing timetable

These cannot necessarily be satisfied at the same time.

Increasing the number of trains may reduce waiting time, but the cost of rolling stock and crews rises.

Adding more express trains may raise speed, but local trains have to wait for overtaking more, which can make things less convenient overall.

Adding slack makes the timetable more robust to delays, but travel time gets longer and track capacity is squeezed.

Simplifying considerably, 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 indicating how much importance to place on each objective.

Depending on how these weights are set, you get timetables of different character, such as "a timetable that prioritizes speed," "a timetable that keeps costs down," or "a timetable that is robust to delays."

Event-Activity Networks and Periodic Timetables

A representation that often appears in railway timetable research is the Event-Activity Network.

It is a way of representing a timetable as a network of events and activities.

Events are things like the following.

Train A arrives at station X
Train A departs from station X
Train B arrives at station Y

Activities represent relationships between events.

Running between stations
Dwelling at a station
Transferring
Keeping safe spacing between preceding and following trains

Using this representation, running time, dwell time, transfers, headways, and so on can all be treated as "time difference constraints between events."

For periodic timetables, this connects 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 be satisfied.

$$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 nice thing about periodic timetables is that if you design one period, such as an hour or 30 minutes, you can expand it across the whole day.

A timetable where trains arrive at the same minute every hour is easy for passengers to understand. Connections are also easier to align.

However, if demand varies greatly by time of day, a fully periodic timetable can be inefficient.

So in reality, many timetables are based on a periodic pattern and add extra services only during peak hours.

Problems Outside the Timetable

Creating the timetable is not the end.

In practice, the timetable becomes the input for rolling stock and crew operations.

After a train reaches its terminal, the same vehicle may turn back and run as the next train.

If the time required for the turnback is $\tau^{\text{turn}}_{ij,u}$, the constraint is:

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

Even if the timetable holds up on paper, it cannot be operated if there are not enough actual vehicles.

The same goes for crews.

Drivers and conductors have constraints such as working hours, breaks, relief locations, and start and end locations.

If you increase the number of trains, you need more vehicles and crews.

Shortening the turnback time raises vehicle efficiency, but reduces slack against delays.

The timetable, rolling stock operations, and crew operations are strongly interconnected.

However, trying to optimize everything as one integrated problem makes the problem size grow enormously.

So in practice, the timetable, vehicles, and crews are often planned sequentially, or only the necessary parts are optimized jointly, or humans check and fix things.

Timetables Robust to Delays

A timetable needs some amount of slack.

If you pack it using only minimum running times and minimum dwell times, even a small delay propagates immediately to following trains.

So slack called buffer time or recovery time is added.

This is important for preventing delay propagation, but adding too much makes travel time longer and reduces track capacity.

In other words, efficiency and robustness are a trade-off.

Little slack:
  Short travel time, but weak against delays

Lots of slack:
  Strong against delays, but longer travel time and squeezed capacity

How to balance this is also an important design decision in timetable creation.

What Optimization Methods Are Used

Various optimization methods are used for railway timetable problems.

Representative ones are Integer Programming and Mixed Integer Linear Programming.

This is because discrete decisions such as train order, platform choice, connection maintenance, and route choice are easy to express with 0-1 variables.

On the other hand, Constraint Programming is also a good fit when searching for feasible solutions that satisfy complex constraints.

Graph representations such as Event-Activity Networks, space-time networks, and alternative graphs are also often used.

For large practical problems, it is hard to obtain exact optimal solutions directly.

So column generation, Lagrangian relaxation, decomposition methods, heuristics, metaheuristics, and so on are used.

This may be a little surprising.

When you hear "mathematical optimization," the impression is that you write a model, throw it at a solver, and get the optimal solution.

But for practical-size problems like railway timetables, the constraints and objectives are large and there are many exceptions.

Ultimately, I think a loop where humans draft a plan, the system evaluates it, and it is revised as needed is what is realistic.

Summary

On the surface, a railway timetable looks like just a schedule table.

But viewed mathematically, it is a fairly complex optimization problem.

In a nutshell, I think a railway timetable is the following kind of problem.

On a graph with a time axis,
multiple trains compete for shared resources: tracks, stations, platforms, vehicles, and crews,
and the problem is to optimize passenger convenience, operating cost, and robustness
while satisfying safe spacing, connections, capacity, turnbacks, and delay tolerance.

Behind a timetable we normally see only as "what time the train comes," constraints such as running time, dwell time, headway, single-track passing, overtaking, transfers, vehicles, crews, and delay recovery are layered on top of each other.

Seen this way, a railway timetable is a giant puzzle.

And making that puzzle hold up within real-world safety, convenience, and cost is what makes railway scheduling 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