An integrated algorithm for shift scheduling problems for local public transport companies

This paper presents an integrated approach to solve two shift scheduling problems for local public bus companies: the first one aims at finding a schedule for vehicles, given a set of rides to do; the second one aims at assigning drivers to vehicle schedules. The first subproblem to be faced is the Multiple Depot Vehicle Scheduling Problem that is known to be NP-hard. Therefore, heuristic algorithms are needed to find feasible solutions for real-life instances. In this work a starting solution for this problem is found by using a greedy algorithm. This solution is then improved by a simulated annealing strategy that exploits several local search techniques. The second problem to deal with is the Crew Scheduling Problem where each trip is assigned to a driver. This problem is still NP-Hard. In this paper an initial solution for the Crew Scheduling Problem is firstly found with a classical sequential approach. This solution is then modified by changing the allocation of trips on vehicles in order to minimize the combined objective function. Both the problems have been modeled taking into account as more real-world constraints as possible. Several constraints take into account the European Union restrictions related to how the driver shifts must be composed. The proposed problem is different from the ones presented in the literature, as the mathematical model, and the related algorithm, are designed based on real world-requirements. Computational results have been carried out on large real-word instances. The results show that the proposed algorithm is able to find quickly good solutions within a limited computational time