A hybrid evolutionary algorithm for the vehicle and crew scheduling problem in public transit

The vehicle and crew scheduling problem in public transit aims at finding minimum cost bus and crew schedules such that all trips of a given timetable are operated respecting all operational constraints. In this paper we present a novel hybrid evolutionary algorithm for the multiple-depot integrated vehicle and crew scheduling problem that combines mathematical programming techniques with an evolutionary algorithm. Computational results on randomly generated benchmark instances demonstrate that our approach outperforms the traditional sequential treatment of vehicle and crew scheduling. Furthermore, it is competitive with solution approaches from literature that fully integrate both planning problems.