Hybrid methods for the Bus Driver Scheduling Problem

Abstract

The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimisation problem that involves assigning bus drivers to predetermined bus tours. The objective function takes into account the operational cost as well as driver satisfaction. This problem is heavily constrained due to stringent rules derived from laws and collective agreements. In the literature, many methods exist to solve variants of the problem, but often they do not optimally solve larger instances. This causes the need for new, efficient methods to solve large-scale problem instances. In this thesis, we focus on a challenging variant of this problem based on the Austrian collective agreement. This variant has been introduced recently in the literature, and exact and heuristic methods have been developed. While these approaches give very good results, optimal solutions have not yet been found for large instances.In this thesis, we proposed new metaheuristic approaches based on Tabu Search (TS) and Iterated Local Search (ILS). After thoroughly evaluating and comparing various algorithmic components, our experiments showed that TS scales very well to larger instances that are out of reach for exact methods. Then, we presented a comprehensive study of a Large Neighbourhood Search (LNS) framework that uses Branch and Price (B&P) or Column Generation (CG) for the repair phase to solve the BDSP. We studied several variants of the LNS, as well as a deeper integration of B&P and LNS, in which we store the generated columns from the subproblems, and reuse them for other subproblems or to find better global solutions. Our analysis shows that this strategy improves several best-known solutions even more than B&P or LNS on their own, constituting a new state-of-the-art solution for this problem. This idea has still not been intensively explored and can be applied to other scenarios or to other optimisation problems. Finally, we introduced an instance generator capable of producing new instances that are either synthetic or real-world-like. By doing so, we can expand the benchmark set of instances. Using those new instances in combination with the recently developed Instance Space Analysis (ISA) methodology, we gained insights into the strengths and weaknesses of our methods compared with the state-of-the-art algorithms.