Using PDDL models to solve TUSS

How to model TUSS as an Automated Planning problem and solve it

Master Thesis (2024)
Author(s)

N.B. Lonyuk (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

M. Weerdt – Mentor (TU Delft - Algorithmics)

I.K. Hanou – Mentor (TU Delft - Algorithmics)

K.G. Langendoen – Graduation committee member (TU Delft - Embedded Systems)

Faculty
Electrical Engineering, Mathematics and Computer Science
More Info
expand_more
Publication Year
2024
Language
English
Graduation Date
09-12-2024
Awarding Institution
Delft University of Technology
Programme
['Electrical Engineering | Embedded Systems']
Faculty
Electrical Engineering, Mathematics and Computer Science
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Due to the increased demand for train travel, train operators are considering increasing their rolling stock. Before achieving this, they must enhance the capacity of their shunting yards. This is attempted by improving methodologies for solving the Train Unit Shunting and Servicing (TUSS) problem. To address the TUSS problem, a planner determines routes on shunting yards for trains, ensuring they visit designated service tracks before parking in a configuration that facilitates a smooth departure.
TUSS is a well-studied problem, and various approaches have been proposed. The first approach capable of solving real-world, complete TUSS instances is a local search method introduced by van den Broek et al. In this thesis, we explore an alternative approach using PDDL models. PDDL is the standard language for describing Automated Planning problems. Automated Planning is a well-established field within artificial intelligence, and new, improved algorithms are continually developed to solve PDDL models for problems similar to TUSS.
In this thesis, we design a detailed model in PDDL and propose several methods to simplify the model so that planning algorithms perform more efficiently compared to the detailed model. When solving simplified models, a post-processing routine is employed to generate detailed shunting plans. The performance of several model-independent PDDL planners was analysed, and the best-performing planner was identified as Temporal FastDownward.
By analysing plans obtained from experiments, we identified areas for improvement. Based on this knowledge, we developed a new TUSS-specific planner called Train Order Preserving Search (TOPS). TOPS employs a search algorithm with effective pruning of symmetrical states and a custom heuristic that guides the search towards states where the order of trains aligns with the departure order. TOPS significantly outperformed Temporal FastDownward in these experiments.

Files

License info not available