Article ID: | iaor2003768 |
Country: | United States |
Volume: | 35 |
Issue: | 3 |
Start Page Number: | 286 |
End Page Number: | 303 |
Publication Date: | Aug 2001 |
Journal: | Transportation Science |
Authors: | Desrosiers Jacques, Haase Knut, Desaulniers Guy |
Keywords: | transportation: general, vehicle routing & scheduling |
This paper presents an exact approach for solving the simultaneous vehicle and crew scheduling problem in urban mass transit systems. We consider the single depot case with a homogeneous fleet of vehicles. This approach relies on a set partitioning formulation for the driver scheduling problem that incorporates side constraints for the bus itineraries. The proposed solution approach consists of a column generation process (only for the crew schedules) integrated into a branch-and-bound scheme. The side constraints on buses guarantee that an optimal vehicle assignment can be derived afterwards in polynomial time. A computational study shows that this approach out-performs the previous methods found in the literature for a set of randomly generated instances. A heuristic version of the solution approach is also proposed and tested on larger instances.