An Adaptive Large Neighborhood Search Heuristic to Solve the Crew Scheduling Problem

This paper presents an adaptation of the adaptive large neighborhood search (ALNS) heuristic in order to solve the crew scheduling problem (CSP) of urban buses. The CSP consists in minimizing the total of crews that will drive a fleet in daily operation as well as the total overtime. The solution for the CSP is a set of duties performed by the crews throughout the day, and those duties must comply with labor laws, labor union agreements, and the company’s operational rules. The CSP is a NP-hard problem and it is usually solved by metaheuristics. Therefore, an ALNS-like heuristic was developed to solve the CSP. Its implementation was tested with real data from a bus company which operates in Belo Horizonte, MG-Brazil, and it provided solutions quite superior to those both adopted by the company and the ones generated by other methods in the literature.