Publications

2024

1. ICAPS

   Replanning in Advance for Instant Delay Recovery in Multi-Agent Applications: Rerouting Trains in a Railway Hub

   Issa Hanou*, Devin Wild Thomas*, Wheeler Ruml, and Mathijs De Weerdt

   In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling, 2024

   Abs HTML PDF Code Poster

   Train routing is sensitive to delays that occur in the network. When a train is delayed, it is imperative that a new plan be found quickly, or else other trains may need to be stopped to ensure safety, potentially causing cascading delays. In this paper, we consider this class of multi-agent planning problems, which we call Multi-Agent Execution Delay Replanning. We show that these can be solved by reducing the problem to an any-start-time safe interval path planning problem. When an agent has an any-start-time plan, it can react to a delay by simply looking up the precomputed plan for the delayed start time. We identify crucial real-world problem characteristics like the agent’s speed, size, and safety envelope, and extend the any-start-time planning to account for them. Experimental results on real-world train networks show that any-start-time plans are compact and can be computed in reasonable time while enabling agents to instantly recover a safe plan.

2. TRA

   Increasing the Capacity of Shunting Yards within the Current Infrastructure: A Computational Perspective

   Issa Hanou, Sebastijan Dumančić, Mathijs De Weerdt, Roel Van Den Broek, Paul Van Der Voort, and Marjan Van Den Akker

   In Lecture Notes in Mobility, 2024

   Abs PDF PosterTo be published

   With a dense infrastructure and limited space, the opportunities for increasing the capacity of the railway network in the Netherlands are limited. There are many components included in the problem, and previous research often focuses on a subset of these. We introduce a framework for positioning previous research along an axis of abstractions and highlight a promising future direction: the development of a new approach that combines previous approaches and methods.

2023

1. ICAPS

   Moving Trains Like Pebbles: a Feasibility Study on Tree Yards

   Issa Hanou, Jesse Mulderij, and Mathijs De Weerdt

   In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, 2023

   Abs HTML PDF Supp Poster

   The Train Unit Shunting Problem concerns the parking of trains outside their scheduled use on so-called shunting yards. This is an NP-hard problem, and the current algorithm used by the Netherlands Railways cannot detect whether an instance is infeasible. So, infeasible instances can cause needlessly long computation times. Therefore, this paper fills the gap by providing novel approaches to determine the feasibility. For this, the Pebble Motion problem is considered which moves pebbles from their starting node to their goal node in the graph, such that no two pebbles occupy a node at the same time. A variant of the Pebble Motion problem is proposed to model the Train Unit Shunting Problem, where train units are represented by pebbles and the arrival and departure of train unit combinations are also included. This paper specifically looks at dead-end track shunting yards, as they can be abstractly represented by trees, such that trains arrive and depart at the root node. Furthermore, trains cannot be reallocated between arrival and departure in the tree, since reallocation in practice is a very costly process as moves need to be performed by a small set of drivers. The conditions for realizing the departure order of trains are studied, and an efficient method to (partially) determine the feasibility of problem instances is given, which can find the minimal number of tracks required to park the trains. Furthermore, a special case with tracks of length two is shown to be polynomially solvable, while another subset of problem instances with tracks of length six or more is demonstrated to be NP-complete.

2022

1. TU Delft

   Applying the Pebble Motion problem: studying the feasibility of the Train Unit Shunting Problem

   Issa Hanou

   Delft University of Technology, 2022

   MSc thesis

   Abs HTML PDF

   Shunting yards are the locations where trains, which are not included in the train schedule at a certain time, are parked until they are required again. Managing the parking of the trains such that all trains can leave at the desired time is a complicated task, and results in the problem formally known as the Train Unit Shunting Problem (TUSP). This problem is an NP-hard problem, and current algorithms cannot always determine whether an instance is feasible. We analyze a simplified variant of the TUSP, leaving out details from the real-world scenario to study the theoretical conditions for basic scenarios to be feasible. To this extent, we identify essential elements of the TUSP and include these in a modification of the Pebble Motion problem. Based on this Pebble Motion variant, we establish new problems that can be studied to analyze the feasibility of the TUSP. For each of these problems, we examine the complexity and look into different solution approaches.