Operations Research 2025
Abstract Submission

251. A two-stage model for periodic timetabling with fixed line activities

Invited abstract in session TA-1: Routing, transportation, and scheduling, stream Mobility, Transportation, and Traffic.

Thursday, 8:45-10:15
Room: Audimax

Authors (first author is the speaker)

1. Niels Lindner
Optimization, Zuse Institute Berlin
2. Christian Liebchen
Engineering and Natural Sciences, TH Wildau

Abstract

The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency does not only lead to NP-hard optimization problems, but is also computationally challenging in practical applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds.

These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer or headway duration can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time.

By precomputing these piecewise linear functions, and inserting them into a mixed-integer program with the initial departure times as variables, we introduce a new, yet equivalent, formulation for reduced periodic timetable optimization problems. The model bears analogies with quadratic semi-assignment approaches, but is more compact, and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances.

Keywords

Status: accepted

Back to the list of papers