Tabu search for bus and train driver scheduling with time windows

The bus and train driver scheduling problem involves assigning bus or train work to drivers in such a way that all the bus or train work is covered and the number of drivers and duty costs are minimised. This is complicated by the fact that there are many restrictions on the duty generation.

The generate-and-select approach is at present the most successful for bus and train driver scheduling. It involves generating a set of legal potential driver duties from which a minimal and most efficient subset is selected. Filtering rules are often applied so that the set of potential duties generated would not be prohibitively large. Moreover, windows of relief opportunities (WROs), which provide ranges of opportunities for relieving drivers, are beyond the capability of being handled by the existing systems. The usual practice is to consider one, sometimes two, discrete times within each time window. Optimality of solution is therefore compromised.

The research presented in this thesis focuses on solving the driver scheduling problem with WROs using a constructive approach, which builds and refines a single schedule iteratively. Filtering rules are unnecessary under the approach. The 2-opt heuristic approach is first investigated, during which the potential of constructive heuristics is explored. Based on the experience, the Tabu Search meta-heuristic approach is then investigated. Multi-neighbourhoods and an appropriate memory scheme, which are essential elements of Tabu Search are designed and tailored for the driver scheduling problem with WROs. Alternative designs have been tested and compared with best known solutions drawn from real-life data sets. The tabu search approach is very fast, can handle WROs, and has achieved results comparable to those based on mathematical programming approaches. Taking advantage of WROs, it can improve best known solutions obtained by the existing systems. Consequently, it could be incorporated into existing systems to improve the solution by taking advantage of WROs.