Solving a bus driver scheduling problem with randomized multistart heuristics

The goal of this paper is to propose and experimentally compare several new hybrid metaheuristics to solve a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. To model and satisfy particular collective agreements and labour rules stated by the Italian government but also to generalize the state-of-the-art problem including constraints for a variety of trade-union rules and regulations for transportation companies, we have proposed a new mathematical model with a set of additional constraints originated by our collaboration with PluService Srl, leading Italian group in software for transportation companies. Moreover, depending on the choice of appropriate cost coefficients, the objective function of our model minimizes the total number of shifts and/or the total operational costs. To link our investigation to real world scenarios, in the experimental investigation, we have used several Italian transportation instances provided by PluService Srl.