An Evolutionary Algorithm Based on Grey Relational Analysis for Crew Scheduling

A pioneering application of grey relational analysis (GRA) to crew scheduling problems in public transport is presented. In many existing crew scheduling approaches, shift evaluation plays a crucial role, which determines the efficiency of the scheduling approaches. Based on GRA, this paper proposes a new grey shift evaluation approach, which contains eight parameters: distinguishing coefficient and the other seven parameters derived from the domain knowledge. To determine the optimal parameters, an evolutionary algorithm based on grey relational analysis (EGRA) is proposed, in which a hybrid genetic algorithm (GA) embedded a quick local search is devised. The best schedule generated is a by-product corresponding to the resulting set of parameters. Experiments show that the EGRA can produce schedules better than the best-known solutions. Moreover, the produced schedules are close to the lower bounds obtained by a standard linear programming solver in terms of the number of shifts.