pith. sign in

arxiv: 2605.02355 · v1 · submitted 2026-05-04 · 🧮 math.OC · cs.DM

Optimizing Travel Time and Regenerative Energy for Periodic Timetables

Sarah Roth , Sven J\"ager , Niels Lindner , Anita Sch\"obel This is my paper

Pith reviewed 2026-05-08 17:43 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords periodic timetablesregenerative brakingbicriteria optimizationPESPrailway schedulingenergy efficiencytravel time
0
0 comments X

The pith

A bicriteria optimization model extends periodic event scheduling to jointly minimize passenger travel time and maximize brake-traction overlap for energy regeneration in railway timetables.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper formulates the PESP-Passenger-Energy problem, an extension of the Periodic Event Scheduling Problem, as a bicriteria task that minimizes total passenger travel time while maximizing the cumulative time when one train's braking can supply another's traction. This matters because regenerative braking offers a direct route to lower energy consumption in rail networks, yet timetables that increase such overlaps often lengthen passenger journeys through added waiting or detours. The authors establish that the problem remains NP-hard even when optimizing only the energy objective on one-station networks, yet they isolate polynomial-time solvable special cases based on matchings and Hamiltonian paths. Two case studies illustrate how the resulting Pareto fronts can be computed in practice.

Core claim

The central claim is that the PESP-Passenger-Energy problem can be modeled by augmenting standard periodic event variables with additional constraints and an objective term that counts brake-traction overlap intervals, yielding a combinatorial structure whose complexity is fully characterized on simple networks and whose solutions produce explicit trade-off curves between travel time and regenerated energy.

What carries the argument

The PESP-Passenger-Energy model, which augments the standard periodic event scheduling framework with an energy objective defined directly on the total duration of brake-traction overlap intervals.

If this is right

  • Timetables exist that increase regenerative overlap without proportionally increasing passenger travel time.
  • Finding an energy-maximizing timetable is already NP-hard, so exact solutions on general networks require exponential effort or heuristics.
  • On one-station networks certain objective combinations admit polynomial algorithms via reduction to matchings or paths.
  • The Pareto front of feasible timetables can be generated to reveal concrete operating points balancing time and energy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If overlap time proves a reliable proxy for actual energy savings, operators could adopt these timetables to lower traction power purchases while keeping passenger delays bounded.
  • Embedding the model into larger networks would require propagating overlap constraints across multiple stations and lines.
  • Testing the model against recorded energy meter data from real services would quantify how much of the theoretical overlap translates into usable regeneration.

Load-bearing premise

The assumption that brake-traction overlap time accurately captures usable regenerative energy and that passenger travel time can be modeled solely through event timings in a periodic framework without additional real-world constraints like dwell times or capacity limits.

What would settle it

Direct measurement on an operating line showing that the actual kilowatt-hours recovered from regenerative braking do not increase when brake-traction overlap time is increased according to the model, or that adding explicit dwell and capacity constraints produces a qualitatively different optimal timetable.

Figures

Figures reproduced from arXiv: 2605.02355 by Anita Sch\"obel, Niels Lindner, Sarah Roth, Sven J\"ager.

Figure 1
Figure 1. Figure 1: Timetable patterns of braking, waiting and acceleration phases of four trains, see view at source ↗
Figure 2
Figure 2. Figure 2: Event-activity network with energy activities view at source ↗
Figure 3
Figure 3. Figure 3: Energy arc with periodic timetable, tension, acceleration time, and braking time, see view at source ↗
Figure 4
Figure 4. Figure 4: The four cases from the proof of Theorem 3.2. The overlap of the braking and view at source ↗
Figure 5
Figure 5. Figure 5: Brake-traction overlap oa as a function of the periodic tension xa on energy activity a, see [JRS24] Provided that the intersection is non-empty, we receive the length of the overlap by the minimum of the lengths of the four periodic intervals [πj , πj + t ac j ]T , [πi − t br i , πi ]T , [πj , πi ]T , [πi − t br i , πj + t ac j ]T . These four cases are illustrated in view at source ↗
Figure 6
Figure 6. Figure 6: Example of non-optimal greedy and Hamiltonian path matchings for view at source ↗
Figure 7
Figure 7. Figure 7: Artificial four-train instance with activity weights for the waiting (black) and transfer view at source ↗
Figure 8
Figure 8. Figure 8: Pareto fronts for various modifications of the artificial instance with four trains. The view at source ↗
Figure 9
Figure 9. Figure 9: Infrastructure layout of the S-Bahn Berlin part of the Ostkreuz station with two view at source ↗
Figure 10
Figure 10. Figure 10: Arrivals and departures at Ostkreuz in weekend nights according to the annual view at source ↗
Figure 11
Figure 11. Figure 11: Pareto front (blue circles) and computation times (wall times, red squares) for the view at source ↗
Figure 12
Figure 12. Figure 12: Two Pareto-optimal timetables for the Ostkreuz instance, showing braking (orange), view at source ↗
read the original abstract

Regenerating braking energy is one major pathway to make rail traffic energy-efficient. It is therefore desirable to design timetables that exploit this feature. However, timetables that allow to regenerate energy are often bad for the passengers. We hence formulate and analyze a bicriteria optimization problem (PESP-Passenger-Energy) to find periodic railway timetables that maximize the regenerated energy in terms of the brake-traction overlap time and minimize the travel time of the passengers. Our model extends the Periodic Event Scheduling Problem (PESP) and offers a rich combinatorial theory. We investigate its computational complexity on one-station networks, building on matchings and Hamiltonian paths. Besides showing its NP-hardness even for a single objective, we identify several polynomial-time solvable special cases. Finally, we provide two case studies, underlining the practicability of our model, and analyzing the Pareto front.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formulates a bicriteria optimization problem (PESP-Passenger-Energy) extending the Periodic Event Scheduling Problem to minimize passenger travel time while maximizing regenerative energy, where energy is quantified via brake-traction overlap time in periodic railway timetables. It analyzes the computational complexity of this model on one-station networks using matchings and Hamiltonian paths, establishing NP-hardness even for single objectives alongside several polynomial-time special cases, and presents two case studies examining the Pareto front.

Significance. If the results hold, the work supplies a combinatorial framework for trading off passenger service quality against energy recovery in periodic timetabling, with explicit complexity classifications that could inform algorithmic design. The case studies indicate practical relevance, but the overall significance is tempered by the modeling choice to proxy energy solely through overlap duration.

major comments (2)
  1. [Model section (PESP-Passenger-Energy formulation)] Model section (PESP-Passenger-Energy formulation): regenerative energy is defined exclusively as brake-traction overlap time without electrical network details such as instantaneous power, catenary voltage, storage acceptance, or efficiency losses; this assumption is load-bearing for both the bicriteria objective and the claimed practical meaning of the Pareto fronts, yet no justification or correlation analysis with actual kWh recovery is provided.
  2. [Complexity analysis on one-station networks] Complexity analysis on one-station networks: the NP-hardness and polynomial-time results are derived from reductions to matchings and Hamiltonian paths, but the manuscript must clarify whether the bicriteria nature (simultaneous travel-time minimization) preserves these classifications exactly or introduces additional hardness in the special cases identified.
minor comments (2)
  1. [Case studies section] Case studies section: quantitative details on network sizes, specific overlap-time values, travel-time reductions, and Pareto-front trade-offs are referenced but not reported; adding tables or figures with these metrics would improve verifiability.
  2. [Notation throughout] Notation throughout: ensure uniform definition of event variables and overlap indicators when extending standard PESP constraints to the energy objective to prevent ambiguity in the combinatorial arguments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which help us improve the clarity and completeness of the manuscript. We address each major comment below and indicate the planned revisions.

read point-by-point responses

  1. Referee: Model section (PESP-Passenger-Energy formulation): regenerative energy is defined exclusively as brake-traction overlap time without electrical network details such as instantaneous power, catenary voltage, storage acceptance, or efficiency losses; this assumption is load-bearing for both the bicriteria objective and the claimed practical meaning of the Pareto fronts, yet no justification or correlation analysis with actual kWh recovery is provided.

    Authors: We agree that the overlap-time proxy is a modeling choice that requires explicit justification. This proxy is standard in the combinatorial timetabling literature because it isolates the scheduling decisions from detailed electrical dynamics while still capturing the essential opportunity for energy recovery. We will expand the model section with references to prior studies that establish a positive correlation between overlap duration and recovered energy under typical catenary and efficiency assumptions. At the same time, we acknowledge that a quantitative kWh correlation analysis would require network-specific power-flow simulations and real-world validation data, which lies outside the scope of the present combinatorial study. In the revision we will therefore add both the requested justification and an explicit limitations paragraph discussing the proxy's assumptions and the conditions under which it remains a reliable indicator. revision: partial

  2. Referee: Complexity analysis on one-station networks: the NP-hardness and polynomial-time results are derived from reductions to matchings and Hamiltonian paths, but the manuscript must clarify whether the bicriteria nature (simultaneous travel-time minimization) preserves these classifications exactly or introduces additional hardness in the special cases identified.

    Authors: The NP-hardness proofs are already stated for each single objective separately (passenger travel time alone and energy recovery alone). Consequently, the bicriteria problem inherits the same hardness classifications, as any algorithm solving the bicriteria version would also solve the single-objective versions. For the polynomial-time special cases, the manuscript identifies network topologies and constraint structures that permit efficient enumeration of the Pareto front via adapted matching or path algorithms; these algorithms directly optimize the combined objective without introducing extra hardness. We will insert a short clarifying subsection that explicitly separates the single-objective hardness results from the bicriteria setting and confirms that the identified polynomial cases remain polynomial for the bicriteria problem. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new PESP extension with independent combinatorial analysis

full rationale

The paper formulates a bicriteria extension of the standard Periodic Event Scheduling Problem (PESP) to optimize passenger travel time against brake-traction overlap time as a proxy for regenerative energy. Complexity results (NP-hardness for single objectives and polynomial cases on one-station networks) are derived directly from combinatorial structures such as matchings and Hamiltonian paths, without any reduction of predictions to fitted inputs, self-definitional loops, or load-bearing self-citations. The modeling assumptions (e.g., overlap time as energy proxy) are explicit choices, not circular derivations. No ansatzes or uniqueness theorems are imported from prior author work in a way that collapses the central claims. The derivation chain remains self-contained against external PESP benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available so ledger is partial; model relies on standard PESP periodicity assumptions and introduces overlap time as energy proxy without new entities.

axioms (1)
  • domain assumption Periodic Event Scheduling Problem (PESP) framework applies to railway events with fixed periods
    The model explicitly extends PESP as stated in the abstract.

pith-pipeline@v0.9.0 · 5452 in / 1150 out tokens · 71206 ms · 2026-05-08T17:43:30.548862+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Tropical neighbourhood search: A new heuristic for periodic timetabling

    [BLM22] Enrico Bortoletto, Niels Lindner, and Berenike Masing. Tropical neighbourhood search: A new heuristic for periodic timetabling. In Mattia D’Emidio and Niels Lindner (eds.):22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), vol. 106 ofOASIcs, art. 3, Dagstuhl, Germany, September

    work page 2022

  2. [2]

    Periodic event scheduling with flexible infrastructure assignment

    [BvLML24] Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner. Periodic event scheduling with flexible infrastructure assignment. In24th Sympo- sium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024), vol. 123 ofOASIcs. Schloss Dagstuhl — Leibniz-Zentrum f¨ ur Informatik,

    work page 2024

  3. [3]

    [Deu25a] Deutsche Bahn AG

    Ac- cessed on 16-03-2026. [Deu25a] Deutsche Bahn AG. Integrierter Bericht

    work page 2026

  4. [4]

    deutschebahn.com/2024/fileadmin/downloads/DB_IB24_d_web_01.pdf,

    URL:https://ibir. deutschebahn.com/2024/fileadmin/downloads/DB_IB24_d_web_01.pdf,

    work page 2024

  5. [5]

    [Deu25b] Deutscher Bundestag

    Accessed on 25-08-2025. [Deu25b] Deutscher Bundestag. Drucksache 21/2573. URL:https://dserver.bundestag. de/btd/21/025/2102573.pdf,

    work page 2025

  6. [6]

    [DGTP16] Shuvomoy Das Gupta, J

    Accessed on 16-03-2026. [DGTP16] Shuvomoy Das Gupta, J. Kevin Tobin, and Lacra Pavel. A two-step linear pro- gramming model for energy-efficient timetables in metro railway networks.Trans- portation Research Part B: Methodological, 93:57–74, November

    work page 2026

  7. [7]

    Bahntechnik und Bahnbetrieb – Beschleunigungsrech- ner/Verz¨ ogerungsrechner

    [Gol] Johannes Golling. Bahntechnik und Bahnbetrieb – Beschleunigungsrech- ner/Verz¨ ogerungsrechner. URL:https://www.bahntechnik-bahnbetrieb.de. Accessed on 2025-12-10. [GS21] Vera Grafe and Anita Sch¨ obel. Solving the Periodic Scheduling Problem: An As- signment Approach in Non-Periodic Networks. In Matthias M¨ uller-Hannemann and Federico Perea (eds.)...

    work page 2025

  8. [8]

    Periodic timetabling: Travel time vs

    [JRS24] Sven J¨ ager, Sarah Roth, and Anita Sch¨ obel. Periodic timetabling: Travel time vs. regenerative energy. In Paul C. Bouman and Spyros C. Kontogiannis (eds.): 24th Symposium on Algorithmic Approaches for Transportation Modelling, Opti- mization, and Systems (ATMOS 2024), vol. 123 ofOASIcs, art. 10, Dagstuhl, Germany,

    work page 2024

  9. [9]

    [KB04] Christian Kr¨ auchi and Paul Blumenthal.Mehr Zug f¨ ur die Schweiz: die Bahn- 2000-Story

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. [KB04] Christian Kr¨ auchi and Paul Blumenthal.Mehr Zug f¨ ur die Schweiz: die Bahn- 2000-Story. AS Verl. & Buchkonzept, Z¨ urich, 1 edition,

    work page 2000

  10. [10]

    Nahverkehrsplan Berlin 2019-2023, Anlage 2 – Rahmenbedingungen

    [Sen19] Senatsverwaltung f¨ ur Umwelt, Verkehr und Klimaschutz, Abteilung Verkehr. Nahverkehrsplan Berlin 2019-2023, Anlage 2 – Rahmenbedingungen. URL:https: //www.berlin.de/sen/uvk/mobilitaet-und-verkehr/verkehrsplanung/ oeffentlicher-personennahverkehr/nahverkehrsplan/#nvp, October

    work page 2019

  11. [11]

    [SGK17] Gerben M

    retrieved on 2025-12-10. [SGK17] Gerben M. Scheepmaker, Rob M. P. Goverde, and Leo G. Kroon. Review of energy- efficient train control and timetabling.European Journal of Operational Research, 257(2):355–376, March

    work page 2025

  12. [12]

    A two-objective timetable optimiza- tion model in subway systems.IEEE Transactions on Intelligent Transportation Systems, 15(5):1913–1921, October

    38 [YNLT14] Xin Yang, Bin Ning, Xiang Li, and Tao Tang. A two-objective timetable optimiza- tion model in subway systems.IEEE Transactions on Intelligent Transportation Systems, 15(5):1913–1921, October

    work page 1913