DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2026.6

From Routes to Resources: A Model for Real-Time Train Dispatching with No-Wait Constraints

Authors: Luka Stärk, Ralf Borndörfer, and Niels Lindner

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

Abstract

Optimization for train dispatching promises to reduce delays. Yet scalable applications are challenging. We present an efficient MIP model, based on generalized disjunctive graphs, for the train dispatching problem with no-wait constraints. For each train, we model its possible movements with microscopic detail as a DAG of operations. We select one train path per DAG and associate it with reservation and release times for the exclusive infrastructure it uses, such that the resulting schedule is conflict-free. When the connecting velocity between consecutive operations is positive, no-wait constraints apply. Additionally, we give a procedure to transform realistic infrastructure constraints based on route exclusions into an equivalent representation on resources by means of edge clique covers and incorporation of overlap exclusions. This makes resource-based dispatching models applicable to real-life infrastructure. We embed the MIP into an iterative algorithm, which we evaluate on the DISPLIB benchmark set and on a real-life dataset from German dispatching regions that we publish together with this paper. We prove optimality for 70 of the 112 DISPLIB instances within short running times, and we find 27 new best known solutions within a 10-minute time limit.

Cite as

Luka Stärk, Ralf Borndörfer, and Niels Lindner. From Routes to Resources: A Model for Real-Time Train Dispatching with No-Wait Constraints. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{stark_et_al:OASIcs.ATMOS.2026.6,
  author =	{St\"{a}rk, Luka and Bornd\"{o}rfer, Ralf and Lindner, Niels},
  title =	{{From Routes to Resources: A Model for Real-Time Train Dispatching with No-Wait Constraints}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{6:1--6:20},
  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.6},
  URN =		{urn:nbn:de:0030-drops-278024},
  doi =		{10.4230/OASIcs.ATMOS.2026.6},
  annote =	{Keywords: Train Dispatching, No-Wait Constraints, Disjunctive Graph, Edge Clique Cover, Microscopic Railway Timetabling}
}

Search Results

Documents authored by Stärk, Luka

From Routes to Resources: A Model for Real-Time Train Dispatching with No-Wait Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message