Genetic algorithms for the SearchCol++ framework : application to drivers’ rostering

Abstract

This paper presents a new genetic algorithm included in the SearchCol++ framework. The new genetic algorithm includes an elitism strategy and a local search procedure to improve the quality of solutions and performance. The new algorithm is tested in a Bus Driver Rostering Problem decomposition model included in the framework in order to build valid rosters combining subproblems’ solutions, obtained previously by using column generation. Each subproblem solution is a valid work-schedule for the driver corresponding to the subproblem. Computational tests show relevant improvement in the effectiveness and efficiency of the new algorithm to build valid rosters to the BDRP.