Heuristics for real-time train dispatching

Thesis title: Heuristics for real-time train dispatching
Author: Švrčina, Jan
Thesis type: Diploma thesis
Supervisor: Rada, Miroslav
Opponents: Černý, Michal
Thesis language: English
Abstract:
This thesis addresses the train dispatching problem (TDP) by creating a heuristic capable of real-time decision-making for complex railway networks. Our method uses a top-down approach for routing decisions, motivated by a structural analysis of the instances, including safety concerns, and a path-and-cycle formulation for conflict resolution, which removes the need for big-M constraints. Both routing and conflict resolution are based on an efficient aggregation procedure and an innovative link graph structure. The aggregation procedure reduces the problem size and can be utilized for any scheduling problem with resource allocation. The link graph maintains information about resource dependencies for the current route selection and allows us to create structural implication rules that can be used to identify critical parts when making routing decisions, and to reduce the number of required variables and constraints in conflict resolution. The heuristic successfully solved the majority of the instances in the DISPLIB benchmark library and provided a significant improvement in speed compared to the winning solutions, albeit at the cost of sometimes suboptimal solutions. The results clearly demonstrate the advantages and drawbacks of the path-and-cycle formulation, and illustrate how the link graph structure is used in practice.
Keywords: train dispatching problem (TDP); heuristic; aggregation; link graph; path-and-cycle formulation
Thesis title: Heuristiky pro dispatching vlaků v reálném čase
Author: Švrčina, Jan
Thesis type: Diplomová práce
Supervisor: Rada, Miroslav
Opponents: Černý, Michal
Thesis language: English
Abstract:
Tato práce se zabývá problémem dispečerského řízení vlaků (TDP) a návrhem heuristiky schopné rozhodování pro komplexní železniční sítě v reálném čase. Naše metoda využívá přístup shora dolů pro rozhodování o trasování, motivovaný strukturní analýzou instancí, včetně bezpečnostních hledisek, a formulaci pomocí cest a cyklů pro řešení konfliktů, což odstraňuje nutnost používat omezení s velkým M. Procedury pro trasování i řešení konfliktů vycházejí z efektivního agregačního postupu a inovativní struktury grafu propojení (link graph). Agregační postup zmenšuje velikost problému a lze jej využít pro jakoukoli rozvrhovací úlohu s alokací zdrojů. Graf propojení uchovává informace o závislostech zdrojů pro aktuální výběr tras a umožňuje nám vytvářet strukturní implikační pravidla, která lze použít k identifikaci kritických částí při rozhodování o trasování a ke snížení počtu požadovaných proměnných a omezení při řešení konfliktů. Heuristika byla použita k vyřešení většiny instancí v knihovně benchmarků DISPLIB a přinesla výrazné zlepšení rychlosti ve srovnání s vítěznými řešeními, i když za cenu občasných sub-optimálních řešení. Výsledky jasně ukazují výhody a nevýhody formulace cest a cyklů a ilustrují, jak se struktura grafu propojení využívá v praxi.
Keywords: Problém dispečerského řízení vlaků (TDP); heuristika; agregace; graf propojení; formulace pomocí cest a cyklů

Information about study

Study programme: Ekonometrie a operační výzkum
Type of study programme: Magisterský studijní program
Assigned degree: Ing.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Econometrics

Information on submission and defense

Date of assignment: 30. 1. 2026
Date of submission: 3. 5. 2026
Date of defense: 9. 6. 2026
Identifier in the InSIS system: https://insis.vse.cz/zp/95396/podrobnosti

Files for download

    Last update: