Instance Space Analysis for the Bus Driver Scheduling Problem

Abstract

The Bus Driver Scheduling Problem is a combinatorial optimisation problem with important real-world applications. The goal is to assign bus drivers to predetermined bus tours in order to minimise an objective function that considers the total time of each employee’s one-day work shift and their dissatisfaction. Due to the amount of complex rules specified by a collective agreement and European laws, this problem is highly constrained. Thus, exact methods are com- putationally intractable. In recent work, two metaheuristics have been proposed to solve this problem: Large Neighbourhood Search (LNS) and Construct, Merge, Solve and Adapt (CMSA). In the literature, 65 real-world-like instances have been used to test the algorithms. Among those instances, LNS seems to outperform CMSA; nevertheless, the reason was still obscure. In order to investigate the reason, we use Instance Space Analysis to show the weaknesses and strengths of the two solution methods. First, we greatly extend an instance generator to be able to generate varied real-world-like and synthetic instances. This allows us to expand the previous set of instances from the literature. We then present a set of features that describe the hardness of the instances. The features consider the structure of the instance, such as the average break length for each vehicle or the distribution of bus tours in the city. We observe that even if LNS outperforms CMSA in real-world-like instances, it does not for some synthetic ones. Using Instance Space Analysis, each instance is projected into a 2D plane based on selected features. We see clusters of instances in the instance space, and the real-world-like are in the centre. The bus tour structure appears to have an impact on the performance of the algorithms. Using this information, we can gain insights into the weaknesses and strengths of the two algorithms