Contextual Hyperparameter Optimization for the Train Unit Shunting Problem

Abstract

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.