One of the planning problems encountered by the Dutch Railways (NS) at shunting yards is the train unit shunting problem (TUSP). This problem considers idle train units that have to be parked, be cleaned, undergo regular maintenance, and be reconfigured into the scheduled departing train compositions. A local search algorithm is being developed to solve this problem at all shunting yards in the Netherlands. This research considers the optimization of the hyperparameters of this local search algorithm. We take contextual information, based on features of problem instances, into account to construct a mapping from contexts to hyperparameter configurations. General difficulties when considering hyperparameter optimization are the expensive function evaluations of the target algorithm that place a tight budget on the number of possible configurations to query; and noisy observations due to the stochasticity of this algorithm. Therefore, we resort to using Bayesian optimization to construct a surrogate that models our belief of the unobservable objective function. Additional encountered difficulties for this specific problem are heterogeneous problem instances and the underlying problem to be a constraint satisfaction problem (instead of the more commonly studied optimization problem). We show that these difficulties prevent an instance-specific approach and result in a poor generalization from the performance on the training set to test data. We also show that we can improve the performance of the default hyperparameter configuration by proposing strategies to construct portfolios consisting of different configurations.

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.