A variable iterated greedy algorithm based on grey relational analysis for crew scheduling

Public transport crew scheduling is a worldwide problem, which is NP-hard. This paper presents a new crew scheduling approach, called GRAVIG, which integrates Grey Relational Analysis (GRA) into a Variable Iterated Greedy (VIG) algorithm. The GRA is utilized as a solver for shift selection during the schedule construction process, which can be considered as a Multiple Attribute Decision Making (MADM) problem, since there are multiple static and dynamic criteria governing the eciency of a shift to be selected into a schedule. Moreover, in the GRAVIG, a biased probability destruction strategy is elaborately devised to maintain the ʹgoodʹ shifts in the schedule without compromising the randomness. Experiments on eleven real-world crew scheduling problems show that the GRAVIG can generate high-quality solutions close to the lower bounds obtained by the CPLEX in terms of the number of shifts