Hybrid genetic algorithms for scheduling bus and train drivers

Abstract

Introduces the subject of bus- and train-driver scheduling, and outlines a standard successful approach (TRACS II) using a blend of heuristics and integer linear programming. We discuss a few limitations of this system; in order to overcome these, we have investigated a range of metaheuristics and constraint programming approaches, and some of these are outlined. Finally, we present a hybrid genetic algorithm which is successfully used to overcome the above limitations. In this approach, all probable potential shifts are generated according to well-developed heuristics that are already used in TRACS II. The selection of such shifts to form a schedule is modeled as a set-covering problem, and the relaxation of this problem, ignoring integer conditions, is solved to optimality. A genetic algorithm then develops a solution schedule based on some of the characteristics of the relaxed solution. It is suggested that this approach might be suitable for other set-covering problems.