Multiple depot vehicle and crew scheduling with time windows for scheduled trips

This paper examines time windows for scheduled trips in multiple depot vehicle and crew scheduling problems that arise in public bus transportation. In practice, the two planning tasks vehicle scheduling and crew scheduling are traditionally solved sequentially with the implicit understanding that the scheduled time for timetabled trips remains fixed. In order to improve cost efficiency two concepts have been developed over the last years: In order to obtain better flexibility when scheduling crews, vehicle and crew scheduling problems are tackled simultaneously. In order to extend flexibility while scheduling vehicles, variable trip departure and arrival times are considered. Obviously the combination of both concepts promises the largest savings, but probably leads to bursting computational times due to growing problem complexity. In this paper we combine both concepts by extending the integrated vehicle and crew scheduling problem with the possibility to shift scheduled trips within defined time windows. We examine the tradeoffs between solution quality and computational time for different solution approaches.