Search Results

Documents authored by Flükiger-Fuchs, Florian

Document
DOI: 10.4230/OASIcs.ATMOS.2026.4
Why Start Over: Incremental MaxSMT for Operational Railway Scheduling

Authors: Thomas Dubach, Florian Flükiger-Fuchs, and Bernardo Martin-Iradi

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract
Railway timetables are planned periodically, but operational planners continuously need to deviate from this base: extra trains are added, or infrastructure changes are made, requiring local updates to the existing schedule. We study this process as a sequential extra train scheduling problem, in which requests arrive one at a time and must be routed and timed against the existing timetable while minimising deviation from it. Commonly, each admitted train is fixed before the next request arrives, and all accumulated solver knowledge is discarded between calls. We propose an incremental MaxSAT framework over Integer Difference Logic (MaxSMT) that retains accumulated solver state across successive extra-train additions, rather than solving from scratch after each request. We evaluate the approach on the Rhätische Bahn network using different solving strategies and compare against a MIP baseline. Retained solver state substantially reduces solve time for successive additions, increasingly so as more extra trains are admitted, and is an order of magnitude faster than MIP given the same setup. Beyond solving time, we show that jointly re-optimising over all admitted extra trains yields better cumulative objective values, and that our approach achieves this while prioritising adjustments in the timetable region affected by the new request.
Cite as

Thomas Dubach, Florian Flükiger-Fuchs, and Bernardo Martin-Iradi. Why Start Over: Incremental MaxSMT for Operational Railway Scheduling. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dubach_et_al:OASIcs.ATMOS.2026.4,
  author =	{Dubach, Thomas and Fl\"{u}kiger-Fuchs, Florian and Martin-Iradi, Bernardo},
  title =	{{Why Start Over: Incremental MaxSMT for Operational Railway Scheduling}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{4:1--4:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.4},
  URN =		{urn:nbn:de:0030-drops-278002},
  doi =		{10.4230/OASIcs.ATMOS.2026.4},
  annote =	{Keywords: MaxSAT, operational railway timetabling, incremental solving}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2026.16
Computing the Cost of Stability in Periodic Microscopic Railway Timetabling via Logic-Based Benders Decomposition (Short Paper)

Authors: Tongcheng Ouyang, Florian Flükiger-Fuchs, Bernardo Martin-Iradi, and Francesco Corman

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract
Periodic railway timetables require stability in operation, but the cost of increasing stability in terms of total travel time remains unclear. We study this cost of stability in microscopic periodic timetabling using the realisable cycle time as a stability measure. To implement stability, we compress the timetable to a shorter realisable cycle time that remains feasible at the microscopic level, and then rescale it back to the nominal period used in regular operation. The difference between this nominal period and the realisable cycle time becomes the time supplement available for absorbing delays. We formulate an optimization problem that jointly considers realisable cycle time and total travel time, and solve it with Logic-Based Benders Decomposition. The master problem optimizes commercial timing variables, while the subproblem verifies microscopic feasibility with routing, periodicity, and resource-conflict constraints. Infeasible subproblems yield activity cuts that constrain the master. Experiments on two Swiss railway case studies show that the proposed decomposition substantially improves computational performance on the larger instance and reveals nonlinear cost-of-stability frontiers with topology-dependent infeasible cycle-time regions and exceptionally high marginal costs at certain stability levels.
Cite as

Tongcheng Ouyang, Florian Flükiger-Fuchs, Bernardo Martin-Iradi, and Francesco Corman. Computing the Cost of Stability in Periodic Microscopic Railway Timetabling via Logic-Based Benders Decomposition (Short Paper). In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 16:1-16:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ouyang_et_al:OASIcs.ATMOS.2026.16,
  author =	{Ouyang, Tongcheng and Fl\"{u}kiger-Fuchs, Florian and Martin-Iradi, Bernardo and Corman, Francesco},
  title =	{{Computing the Cost of Stability in Periodic Microscopic Railway Timetabling via Logic-Based Benders Decomposition}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{16:1--16:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.16},
  URN =		{urn:nbn:de:0030-drops-278128},
  doi =		{10.4230/OASIcs.ATMOS.2026.16},
  annote =	{Keywords: Railway timetabling, periodic stability, microscopic timetabling, logic-based Benders decomposition}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact