A GRASP for the bus driver scheduling problem

This paper addresses the problem of determining the best scheduling for Bus Drivers, i.e. the problem of finding the minimum number of drivers required to cover a set of Piece-Of-Works (POWs) subject to a variety of rules and regulations that must be enforced such as the overspread and the working time. This problem is known in literature as Crew Scheduling Problem and in particular in public transportation it is designated as Bus Driver Scheduling Problem. The Bus Driver Scheduling Problem is an extremely complex part of the Transportation Planning System. Its combinatorial nature and the large dimension of real-world problems has led to the development of several heuristics. Wren and Rousseau~\cite{Wren-conference} give an outline of the Bus Driver Scheduling Problem (BDSP) and propose various approaches for solving it