LAUSR

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 served as a solver for the 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 efficiency of a shift to be selected into a schedule. Moreover, in the GRAVIG, a biased probability destruction strategy is elaborately devised to keep the ‘good’ shifts remained 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.