Scheduling of Railway Maintainance Projects

Y.R. de Weert, K. Gkiotsalitis, E.C. van Berkum,
Improving the scheduling of railway maintenance projects by minimizing
passenger delays subject to event requests of railway operators,
Computers & Operations Research, Volume 165, 2024

Exam Project
Mathematical Optimization Course
SDIC Master Degree, University of Trieste (UniTS)

Marco Tallone
June 2025

Table of Contents

1. Model Description
  • Problem Description
  • Decision Variables
  • Objective
  • Constraints
2. Model Improvements
  • Parameter Analysis
  • Meta-Heuristics
  • Valid Inequalities
3. Scalability Analysis
  • Solution Strategies
  • Dataset Generation
  • Results

Model Description

Problem description


Nodes representing the railway stations: \[ N = \{1, 2, \ldots, n\} \] Bidirecitonal arcs connecting stations: \[ \mathcal{A} = \{a_{ij}=(i, j) \mid \forall i, j \in N, i < j\} \] Train travel times: $\quad \omega^e_a \in \mathbb{R}^+$
Alternative travel times: $\quad \omega^j_a \in \mathbb{R}^+$

Problem description


When travelling from origin $o$ to destination $d$, passengers can consider up to $K \in \mathbb{N}$ possible routes.
The set $R$ contains, for each origin-destination pair $(o,d) \in N \times N \mid o \neq d$, the $K$ shortest paths connecting them.
Then the set of average train times from origin to destination is: \[ \Omega_{od}, \quad \forall (o, d) \in N \times N \mid o \neq d \]

Problem description

Finite discrete time horizon: \[ T = \{1, 2, \ldots, T_{end}\} \]

Set of maintenance jobs: \[ J = \{1, 2, \ldots, n_{\text{jobs}}\} \]

Processing time of job $j$: $\quad \pi_j \in \mathbb{N}$
Set of arcs associated to job $j$: $\quad \mathcal{A}_j \subseteq \mathcal{A}$
Set of jobs associated to arc $a$: $\quad J_a \subseteq J$
Time interval for consecutive jobs: $\quad \tau_a \in \mathbb{N}$

Problem description


Passenger flow from $o$ to $d$: $ \quad \phi_{odt} \in \mathbb{N}$
Trains have "unlimited" capacity $M \gg 1$: \[ M > \sum_{(o,d) \in N \times N} \sum_{t \in T} \phi_{odt} \] Alternative services capacity on $a$: $ \quad \Lambda_{at} \in \mathbb{N}$
The set $C$ contains all the combinations of arcs that cannot be unavailable simultaneously:

Problem description


It might happen that, at any time $t \in T$ an event might occur that increases the passenger demand by a factor $\beta_{odt}$ in a subset of arcs of the network $\rightarrow$ modelled by the set $E$ of tracks segments $s$: \[ E = \{ [a_{12}, a_{23}], [a_{45}, a_{35}, \dots], \dots \} \] During events, the capacity of alternative services is limited: \[ \Lambda_{st} = \sum_{a \in s} \Lambda_{at},\quad \forall s \in E, \forall t \in T \]

Decision Variables

The decision variables of the model are the following:

  1.    $y_{jt}$:    binary variable that is equal to 1 if job $j$ starts at time $t$, 0 otherwise
  2.    $x_{at}$:    binary variable that is equal to 1 if arc $a$ is available (by train) at time $t$, 0 otherwise
  3.    $h_{odtk}$:    binary variable that is equal to 1 if route option $k$ is used when travelling from origin $o$ to destination $d$ at time $t$, 0 otherwise
  4.    $w_{at}$:    continuous variable representing the travel time traversing arc $a$ at time $t$
  5.    $v_{odt}$:    continuous variable representing the travel time from origin $o$ to destination $d$ at time $t$

Objective

The goal of the model is to minimize the total passenger delay in the network.

Delay = increase in the travel time compared to the average travel time $\Omega_{od}$ between an origin $o$ and a destination $d$.

According to this, the following objective function is defined: \[ \underset{v}{\min} \sum_{(o,d) \in N \times N} \sum_{t \in T} \phi_{odt} (v_{odt} - \Omega_{odt}) \tag{1} \]

Constraints

A feasible solution of this model schedules all the jobs within the time horizon $T_{end}$ \[ \sum_{t=1}^{T_{end} - \pi_j + 1} y_{jt} = 1, \quad \forall j \in J \tag{2} \]

Constraints

Each job must start only once and, while it's being processed, the subset $\mathcal{A}_j$ of its arcs must be unavailable for other jobs (since they are occupied) \[ x_{at} + \sum_{t'=\max(1, t-\pi_j+1)}^{\min(T_{end}, t)} y_{jt'} \leq 1, \quad \forall a \in \mathcal{A}, \forall t \in T, \forall j \in J_a \tag{3} \]

Constraints

Accordingly the travel time $w_{at}$ on an arc $a$ at time $t$ depends on the availability of the train services on that arc by the following constraint: \[ w_{at} = \omega^e_a x_{at} + \omega^j_a (1 - x_{at}), \quad \forall a \in \mathcal{A}, \forall t \in T \tag{4} \]
Since variables $x_{at}$ are only bounded by $(3)$, an optional constraint is added to ensure the correct arc traversal time for free variables: \[ \underbrace{\sum_{t \in T} x_{at}}_{\text{total time}\atop\text{availability of arc }a} = T_{end} - \underbrace{\sum_{j \in J_a} \pi_j,}_{\text{total processing time}\atop\text{of jobs on }a} \quad \forall a \in \mathcal{A} \tag{5} \]

Constraints

Due to the fact that there might be multiple combinations $c$ of arcs that cannot be unavailable simultaneously according to set $C$, the following constraint is added: \[ \sum_{a \in c} (1 - x_{at}) \leq 1, \quad \forall c \in C, \forall t \in T \tag{6} \]
Example: suppose $C = \{[a_{12}, a_{23}]\}$, then at any $t \in T$:
  • $x_{a_{12}t} = 1 \land x_{a_{23}t} = 1$ ✅
  • $x_{a_{12}t} = 1 \land x_{a_{23}t} = 0$ ✅
  • $x_{a_{12}t} = 0 \land x_{a_{23}t} = 1$ ✅
  • $x_{a_{12}t} = 0 \land x_{a_{23}t} = 0$ ❌

Constraints

Since jobs on the same arc cannot overlap in time the following constriant is needed: \[ \sum_{j \in J_a} \sum_{t'=\max(1, t-\pi_j-\tau_a)}^{t} y_{jt'} \leq 1, \quad \forall t \in T, \forall a \in \mathcal{A} \tag{7} \]

Constraints

For a track segment $s$ included in an event request the passenger flow in the peak moment of the considered time period must be less than the capacity of the alternative services: \[ \sum_{a \in s} \sum_{(o,d) \in N \times N} \sum_{\substack{i = 1 \\ a \in R_{odi}}}^K h_{odti} \beta_{odt} \phi_{odt} \leq \Lambda_{st} + M \sum_{a \in s} x_{at}, \quad \forall s \in E_t, \forall t \in T \tag{8} \]
Concerning alternative routes, we must ensure that passenger flow is served by at least one (and no more than one) of the $K$ possible routes: \[ \sum_{i = 1}^K h_{odti} = 1, \quad \forall (o,d) \in N \times N, \forall t \in T \tag{9} \]

Constraints

Accordingly, the following two constraints provide a lower and an upper bound for the travel time from origin $o$ to destination $d$ at time $t$: \[ \forall i \in \{1,\dots,K\}, \forall (o,d) \in N \times N, \forall t \in T \] \[ v_{odt} \geq \sum_{a \in R_{odi}} w_{at} - M (1 - h_{odti}) \tag{10} \] \[ v_{odt} \leq \sum_{a \in R_{odi}} w_{at} \tag{11} \]

Example


$n = 5$ stations
$T_{\text{end}} = 10$ time slots
$n_{\text{jobs}} = 10$ jobs
$K = 3$ routes
$0 \leq \phi_{odt} \leq 2000$ passengers

Example

Example

In this example we set: \[ C = \{ [a_{45}, a_{35}], [a_{14}, a_{25}] \} \]

We can see how the solution changes by adding arc $a_{12}$ to the second list of required simultaneously available arcs $\dots$

Example

In this example we set: \[ C = \{ [a_{45}, a_{35}], [a_{14}, a_{25}] \} \]

We can see how the solution changes by adding arc $a_{12}$ to the second list of required simultaneously available arcs $\dots$

\[ C = \{ [a_{45}, a_{35}], [a_{14}, a_{25}, a_{12}] \} \]

Model Improvements

Parameter Analysis

Values of variables associated to arcs never included in any job can be considered as fixed \[ x_{at} = 1, \quad \forall a \in \{a \in \mathcal{A} \mid J_a = \emptyset\}, \forall t \in T \tag{12} \] \[ w_{at} = \omega^e_a, \quad \forall a \in \{a \in \mathcal{A} \mid J_a = \emptyset\}, \forall t \in T \tag{13} \]

Parameter Analysis

Consider $K$ routes from $o$ to $d$ at time $t$ that all pass through arc $a$, which is also included in an event request $E_t$.
If $\beta_{odt} \phi_{odt} > \Lambda_{at}$ (capacity of alternative services) for such arc, we must ensure the availability of the arc to avoid an infeasible solution \[ x_{at} = 1, \quad \forall (a,t) \in \{ \substack{(a,t) \in \mathcal{A} \times T \mid \exists s \in E_t \text{ s.t. } a \in s \\ \land\ \exists (o,d) \in N \times N \text{ s.t. } a \in R_{odi} \forall i \in \{1,\dots,K\} \\ \land\ \beta_{odt} \phi_{odt} > \Lambda_{st}} \} \] \[ \tag{14} \]

Parameter Analysis

Given the $K$ routes from $o$ to $d$ at time $t$, if route option $\tilde{k} \in \{1, \dots, K\}$ is never used, we can set the associated variable $h_{odt\tilde{k}} = 0$

When is a route option never used?

Parameter Analysis

Given the $K$ routes from $o$ to $d$ at time $t$, if route option $\tilde{k} \in \{1, \dots, K\}$ is never used, we can set the associated variable $h_{odt\tilde{k}} = 0$

When is a route option never used?

Consider path from $o$ to $d$:       $p_{od} = (a_1, \dots, a_n)$

  • max travel time: when all arcs of the path are unavailable simultaneously
  • min travel time: when all arcs of the path are available simultaneously

\[ \text{max time of } p^{(1)}_{od} < \text{min time of } p^{(2)}_{od} \quad \Rightarrow \quad p^{(2)}_{od} \text{ is never used} \]

Parameter Analysis

Given the $K$ routes from $o$ to $d$ at time $t$, if route option $\tilde{k} \in \{1, \dots, K\}$ is never used, we can set the associated variable $h_{odt\tilde{k}} = 0$

When is a route option never used?

\[ \text{max time of } p^{(1)}_{od} < \text{min time of } p^{(2)}_{od} \quad \Rightarrow \quad p^{(2)}_{od} \text{ is never used} \]

\[ h_{odti} = 0, \quad \forall (o, d, i) \in \{(o, d, i) \in N \times N \times [K] \mid \min_{i \in [K]} \Omega_{odi} > \max_{j \neq i \in [K]} \Omega_{odj }\} \tag{15} \]

Valid Inequalities

Sousa and Wolsey inequality from the "Single Machine Scheduling" problem [Appendix 1]: \[ \sum_{t' \in Q_j} y_{jt'} + \sum_{\substack{j' \in J_a \\ j' \neq j}} \sum_{t' \in Q'_{j'}} y_{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j \in J_a, \forall t \in T, \forall \Delta \in \{2,\dots,\Delta_{max}\} \tag{B1} \]
$Q_j = [t - p_j +1, t+ \Delta -1] \cap T$
$Q'_{j'} = [t - p_{j'} + \Delta, t] \cap T$
$\Delta_{max} = \underset{\substack{j' \in J_a \\ j' \neq j}}{\max} (\pi_{j'} + \tau_a)$
Non-overlapping jobs inequality [Appendix 2]: \[ y_{jt} + y_{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j, j' \in J_a, \forall t, t' \in T \mid j \neq j' \land t' \in (t - \pi_{j'} - \tau_a, t + \pi_j + \tau_a) \cap T \] \[ \tag{B2} \]

Meta-Heuristics: Simulated Annealing

Simulated Annealing has been used to find a good initial solution for the MILP model.

Meta-Heuristics: Simulated Annealing

Initial solution: schedule jobs from the one with most arcs to ones with less arcs
Example: Job $5$ $\rightarrow$ Job $2$ $\rightarrow$ Job $7$ $\rightarrow$ Job $10$ $\rightarrow$ Job $3$ $\rightarrow$ $\dots$
Objective: $18499.47$

Meta-Heuristics: Simulated Annealing

Neighbor solution: reschedule a single job by moving it to a different time slot
Example: Reschedule job $7$ to a feasible time slot
Objective: $18560.96$

Scalability Analysis

Solution Strategies

  • Models implemented in Python (3.11.5) using Gurobi (12.0.1)
  • Run on $\text{Intel}^{\text{(R)}} \text{ Core}^{\text{(TM)}} \text{ i}7\text{-}8565\text{U}$ CPU with $40$GB of RAM
  • Time limit: $5$ minutes for Gurobi solver and $5$ minutes for simulated annealing
Model $0$
"As-is" Gurobi model
No meta-heuristics
No valid inequalities
Model $1$
Improved initial solution
Simulated annealing heuristic
No valid inequalities
Model $2$
Full model
Simulated annealing heuristic
Valid inequalities
Addition of cutting planes [A3]

Dataset Generation

To test the scalability of the model, problem istances have been generated with combinations of the following parameters:

  • Number of stations: $|N| \in \{10, 20, 40\}$
  • Number of jobs: $|J| \in \{10, 40, 80\}$
  • Time horizon: $T_{end} \in \{10, 50, 100\}$
  • Number of route options: $K = 3$

Set $E = \emptyset$ (no event requests) and $C = \emptyset$ (no simultaneous arc unavailability)

Remaining model parameters have been randomly generated within fixed input bounds.

Problem Istances

ID $|N|$ $|J|$ $|T|$ $K$
1 10 10 10 3
2 10 10 50 3
3 10 10 100 3
4 10 40 10 3
5 10 40 50 3
6 10 40 100 3
7 10 80 10 3
8 10 80 50 3
9 10 80 100 3
ID $|N|$ $|J|$ $|T|$ $K$
10 20 10 10 3
11 20 10 50 3
12 20 10 100 3
13 20 40 10 3
14 20 40 50 3
15 20 40 100 3
16 20 80 10 3
17 20 80 50 3
18 20 80 100 3
ID $|N|$ $|J|$ $|T|$ $K$
19 40 10 10 3
20 40 10 50 3
21 40 10 100 3
22 40 40 10 3
23 40 40 50 3
24 40 40 100 3
25 40 80 10 3
26 40 80 50 3
27 40 80 100 3

Results: MIP Gap (%)

Results: Gap Development of instance n°5

Results: Nodes Explored

Results: Runtime and Heuristics Time

Appendix 1: Valid Inequality (B1)

Sousa and Wolsey inequality from the "Single Machine Scheduling" problem: \[ \sum_{t' \in Q_j} y_{jt'} + \sum_{\substack{j' \in J_a \\ j' \neq j}} \sum_{t' \in Q'_{j'}} y_{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j \in J_a, \forall t \in T, \forall \Delta \in \{2,\dots,\Delta_{max}\} \tag{B1} \]
$Q_j = [t - p_j +1, t+ \Delta -1] \cap T$
$Q'_{j'} = [t - p_{j'} + \Delta, t] \cap T$
$\Delta_{max} = \underset{\substack{j' \in J_a \\ j' \neq j}}{\max} (\pi_{j'} + \tau_a)$
with $p_j = \pi_j + \tau_a$ the total processing time of job $j$ considering also the pause time $\tau_a$.
Back to Valid Inequalities

Appendix 1: Valid Inequality (B1)


Example: Consider $t=5$, $\tau_a = 1$ and two jobs with $\pi_1 = 3$ and $\pi_2 = 2$.
Hence:
$p_1 = \pi_1 + \tau_a = 4$, $\; p_2 = \pi_2 + \tau_a = 3$
Then, setting $j = 1 \Rightarrow \Delta = \{2, 3\}$.
Considering $\Delta = 2$ first we get: \[ Q_1 = \{2, 3, 4, 5, 6\} \quad \text{and} \quad Q'_2 = \{4, 5\} \] So $(B1)$ becomes: \[ \sum_{t' \in \{2, 3, 4, 5, 6\}} y_{1t'} + \sum_{t' \in \{4, 5\}} y_{2t'} \leq 1 \]

Appendix 1: Valid Inequality (B1)


Then considering $\Delta = 3$ we get: \[ Q_1 = \{2, 3, 4, 5, 6, 7\} \quad \text{and} \quad Q'_2 = \{5\} \] So $(B1)$ becomes: \[ \sum_{t' \in \{2, 3, 4, 5, 6, 7\}} y_{1t'} + y_{2,5} \leq 1 \]

Appendix 2: Valid Inequality (B2)

Non-overlapping jobs inequality: \[ y_{jt} + y_{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j, j' \in J_a, \forall t, t' \in T \mid j \neq j' \land t' \in (t - \pi_{j'} - \tau_a, t + \pi_j + \tau_a) \cap T \] \[ \tag{B2} \]
Back to Valid Inequalities

Appendix 3: Cutting Planes

  • Boolean quadric polytope cuts
  • Clique cuts
  • Cover cuts
  • Flow cover cuts
  • Flow path cuts
  • Gomori cuts
  • GUB cuts
  • Implied bounds cuts
  • Lift-and-project cuts
  • MIR cuts
  • Mod-k cuts
  • Network cuts
  • Relax-and-lift cuts
  • Strong-CG cuts
  • $\{0, \frac{1}{2}\}$ cuts
Back to Solution Strategies