Utilizing General Planners to Solve the Train Unit Shunting Problem Extended with Servicing

Bachelor thesis (2023)

Authors

B.P. Andonov Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - EEMCS (supervisor 1)
I.K. Hanou Algorithmics - EEMCS (supervisor 1)
R. Hai Web Information Systems - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Bozhidar Andonov
More Info
expand_more

Published Date

28-06-2023

Language

English

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

When not in use, trains are stored at shunting yards, where they may need servicing. Planning for where the rolling stock should be parked during its stay at the yard is known as the Train Unit Shunting Problem (TUSP) and it is NP-hard. Algorithmic planners can assist with this computationally difficult task by providing a sequence of actions to be executed for the trains in the shunting yard. To output such a sequence, planners should be given a domain and an instance of it as input, both of which can be defined in the Planning Domain Definition Language (PDDL). In this paper, we first formalize the TUSP extended with servicing and implement a domain for it in PDDL. Then, we compare four planners submitted to the International Planning Competition 2018 against 9 instances of the domain. The best of these planners reduces the problem to the Boolean Satisfiability Problem. We improve its performance with 31.5% by removing redundant clauses and an irrelevant computational element of the reduction.