An Evolutionary Algorithm for the Train Unit Shunting and Servicing Problem

Abstract

The Train Unit Shunting and Servicing (TUSS) problem is an NP-hard problem encountered by the Dutch railway operator, Nederlandse Spoorwegen (NS). It considers trains at a shunting yard when they are not transporting passengers. It consists of four subproblems, involving assigning the trains at the yard to a transporting timetable (Matching), planning the maintenance tasks that need to be performed for each train while they are at the yard (Servicing), assigning trains to parking tracks during their stay at the yard (Parking), and calculating routes for the movements of the trains over the yard (Routing). The problem
entails finding a conflict-free plan that solves all subproblems.

Currently, plans for the trains at a shunting yard are still devised by human planners, which is a time-consuming and difficult task, which the NS wants to automate. To that end, they are in an advanced stage of the development of an algorithm that can solve instances of TUSS using a local search heuristic, called Hybrid Integrated Planner (HIP). Because it is a heuristic, it has no guarantee of being optimal. Another meta-heuristic that shows good performance on scheduling problems, is the class of Evolutionary Algorithms (EAs). This research creates an EA, called Conflict-Based Crossover (CBC), that can solve TUSS and can outperform the local search heuristic on a subset of locations.

The most complex part of creating an EA for a complicated problem like TUSS is devising a crossover operator, which is a method that can combine two solutions to TUSS to create a new, valid solution. This research devises a functional crossover operator for TUSS, using a graph representation of solutions which is also used in the local search heuristic. Using the same representation as HIP makes it easy to hybridise the algorithm. The operator treats schedules for individual train units as variables and combines solutions by mixing these
variables. To decide which variables are selected from which solution, a heuristic is developed that uses the conflicts of individual train units as the basis of a selection mechanism; the method derives its name from this heuristic.

The performance of CBC is compared to HIP on a set of different shunting yards.
Results show that on Grote Binckhorst, which is a location where most tracks have only one entry and exit, CBC gets outperformed by HIP. However, on Kleine Binckhorst, a location with a lot of open-ended tracks, CBC consistently outperforms HIP. This implies that, on a subset of locations, CBC can be an improvement over HIP to devise feasible plans for TUSS.