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

Public transport crew scheduling is a worldwide problem, which is nphard. 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 realworld crew scheduling problems show that the gravig can generate highquality solutions close to the lower bounds obtained by the cplex in terms of the number of shifts.