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 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. In this paper, we propose a GRASP that computes suboptimal feasible solutions. Preliminary results are reported for a set of real-word problems, where GRASP is compared is with an exact method.