Multiobjective metaheuristics for the bus-driver scheduling problem

We present new multiobjective metaheuristics for solving real-world crew sc heduling problems in public bus transport companies. Since the crews of the se companies are drivers, we will designate the problem as bus-driver sched uling. Crew scheduling problems are well known, and several mathematical pr ogramming-based techniques have been proposed to solve them, in particular, using the single-objective set-covering formulation. However, in practice, there exists the need to consider multiple objectives, some of them in con flict with each other; for example, the cost and service quality, implying also that alternative solution methods have to be developed. We propose mul tiobjective metaheuristics based on the tabu search and genetic algorithms. These metaheuristics also present some innovation features related with th e structure of the crew scheduling problem that guide the search efficientl y and enable them to find good solutions. Some of these new features can al so be applied to the development of heuristics to other combinatorial optim ization problems. A summary of computational results with real-data problem s is presented. The methods have been successfully incorporated in the GIST Planning Transportation Systems and are actually used by several companies .