The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a MILP with typically general integer variables. However, even for rather small instances, good dual bounds are notoriously hard to obtain. We therefore investigate the split closure of the periodic timetabling polytope and show that split inequalities are identical with so-called flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms. We prove that pseudo-polynomial-time separation of split/flip cuts is best possible unless P = NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and that a combination of a heuristic and an exact cut generation approach is able to provide better dual bounds for five instances.

We present an approach that extends the well-known Periodic Event Scheduling Problem (PESP) by integrating safety constraints and platform assignment options, offering a comprehensive and efficient solution for real-world transportation networks. While the traditional PESP framework focuses solely on scheduling events with periodicity constraints, it often overlooks the crucial aspect of infrastructure utilization. To address this limitation, we showcase two mixed-integer programming ideas. The first makes use of constraints based on cyclic orders of conflicting activities, and we show how this formulation is able to deal with simple instances and requirements. Secondly, we present a formulation based on a matching problem, capable of modelling much more complex situations, even allowing more efficient infrastructure capacity utilization. To demonstrate the practical efficacy of our approach, we evaluate it on real-world instances, including the S-Bahn Berlin network.

The line plan, timetable, and vehicle schedule are key components of public transportation planning, and high-quality service can only be provided if they are well coordinated. We present the Integrated Line Planning and Periodic Timetabling with Track Choice Model, which addresses each of these aspects simultaneously and can cover different modeling requirements, depending on the detail of planning intended.
We introduce the extended infrastructure-aware event-activity network (EAN) as the core object: Based on an implicitly given line plan, it encodes all potential vehicle paths that a line could be realised as, taking into account the underlying infrastructure.

We obtain a mixed-integer linear optimization formulation by generalising the periodic event scheduling problem (PESP) to accommodate the extended infrastructure-aware EAN. Vehicle routing decisions are made by an imposed binary flow on the EAN, which in turn activates traditional PESP constraints. The line planning aspect is included by frequency coverage constraints.

We demonstrate applicability of our model by using it for re-planning purposes in the context of construction sites: Infrastructure becomes unavailable and the regular service cannot be upheld as capacity issues on tracks arise. The goal is then to recover as much of the regular service as possible while satisfying safety requirements. We show that our model is well suited to this purpose on multiple real-life construction site scenarios in the network of S-Bahn Berlin.

It becomes evident that the solving process benefits from good starting solutions. As has been observed for other PESP-related problems in the past, we demonstrate a SAT (Boolean Satisfiability) approach to be effective as a primal heuristic.

Public transport operators are increasingly adopting electric battery-powered bus fleets with a significant impact on associated vehicle scheduling problems. Available driving ranges are still limited compared to combustion-powered counterparts, such that buses may have to recharge in-service. This needs to be taken into account within vehicle schedules via additional downtime and possibly detours. The relationship between charge states and charge duration is non-linear due to the complex chemical processes within batteries, however, electric vehicle scheduling models usually rely on a linearized description in order to access the powerful tools offered by mixed-integer linear programming.

In this talk, we examine the approximation error this introduces and its impact on solution feasibility. We highlight worst-case behavior, study piecewise linear charge curves considered state-of-the-art in the literature, and propose an alternative.