2026-10-04T00:29:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27802 2026-10-02T13:58:19Z ddc:004 open_access

From Routes to Resources: A Model for Real-Time Train Dispatching with No-Wait Constraints Stärk, Luka Borndörfer, Ralf Lindner, Niels Train Dispatching No-Wait Constraints Disjunctive Graph Edge Clique Cover Microscopic Railway Timetabling 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luka Stärk and Ralf Borndörfer and Niels Lindner 2026 Is Part Of OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2026.6 urn:nbn:de:0030-drops-278024 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode