The Assignment of Bus-Drivers to trips problem without prior driver's shift.

Abstract

The present study addresses a specific Bus Crew Scheduling problem (CSP) that arises in a public transport company in Spain. The classical CSP problem tries to create bus-driver schedules covering all the bus routes and timetables published by the company. In contrast, the problem considered here does not require all the published schedules to be covered, but rather focuses on optimizing driver assignments and on maximizing passenger collections. This relaxed constraint arises from the difficulty of acquiring new drivers and resources, and from the resulting need to design a tool capable of making intelligent use of those available. We propose an integer programming model for the problem. The real instances to be solved are clustered beforehand to allow general solvers to provide us with an optimal solution. Subsequently, we present a novel bi-objective constructive heuristic that determines a good solution for the instances that we have not solved exactly. As a result, the transportation company can have valuable solutions within a reasonable execution time. This is demonstrated in a final computational experiment.