Skip to content
Sayash RaajRésumé

Work

Optimization · Case study

Schedule-aware railway routing

Find routes through a railway network that respect actual train timetables, a temporal variant of the Traveling Salesman Problem where the cost of an edge depends on when you arrive.
Organization
IIT Madras
Context
Undergraduate thesis · awarded maximum grade
Period
2023
Methods
Time-expanded graphs · Dynamic programming · Pruning heuristics
Tools
Python · C++

Max. grade

thesis evaluation

Thesis document (opens in a new tab)

01Problem

In a road network you can leave whenever you like. In a railway network you can only move when a scheduled train does. Travel time between two stations therefore depends on arrival time, because a missed connection means waiting for the next departure. A route that visits a set of stations must be planned against the timetable, not a static distance matrix.

This makes it a temporal variant of the Traveling Salesman Problem. The usual TSP machinery assumes fixed edge costs, so it does not apply directly.

02Formulation

Build a time-expanded graph G=(V,E)G = (V, E) where each node is a station at a specific time, v=(s,t)v = (s, t). Two kinds of edges encode the timetable:

(s,t)→(s′,t′)(s, t) \to (s', t')
Ride edge: a scheduled train departing ss at tt and arriving at s′s' at t′t'
(s,t)→(s,t+)(s, t) \to (s, t^{+})
Wait edge: stay at station ss until its next event time t+t^{+}

Every path in GG is feasible by construction, so timetable constraints disappear from the search. With a set RR of required stations, the objective is the makespan, the time at which the route completes:

min⁡path P in G  tend(P)s.t. P visits every station s∈R\begin{aligned} &\min_{\text{path } P \text{ in } G} \; t_{\text{end}}(P) \\ &\text{s.t. } P \text{ visits every station } s \in R \end{aligned}

Dynamic programming runs over states (v,S)(v, S), the current time-station node and the set of required stations already visited, keeping the earliest arrival for each state.

Time-expanded graph for three stationsStations A, B and C are horizontal lanes over time from 08:00 to 12:00. Six trains connect departure and arrival events. The highlighted route rides from A at 08:10 to B at 08:50, waits at B until 09:30, and rides to C, arriving at 10:10, having visited all three stations.08:0009:0010:0011:0012:00Station AStation BStation Cmakespan 10:10Scheduled train (ride edge)Waiting at a stationFeasible route visiting A, B, C
Time-expanded graph for three stations. Diagonal edges are scheduled trains and horizontal edges are waiting. The highlighted path is a feasible route that visits all three stations.

03Method

  • Dynamic programming over (node, visited-set) states on the time-expanded graph.
  • Pruning heuristics discard partial routes that cannot lead to a better solution, keeping the state space tractable.
  • Implemented in Python and C++.

04Validation and results

Tested on sampled timetable data against greedy baselines. The method improved feasible scheduling and reduced makespan relative to the greedy baselines. The thesis was awarded the maximum grade.

05Limitations

  • State space grows exponentially in the number of required stations; pruning helps in practice but does not change the worst case.
  • Evaluated on sampled timetables, not a full national schedule.