Heuristiky pro dispatching vlaků v reálném čase

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.