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

作者：Peng, K.; Shen, Y.^*

来源：Scientia Iranica, 2018, 25(2): 831-840.

DOI：10.24200/sci.2017.4434

• Public transit
• Crew scheduling
• Variable iterated greedy
• Grey relational analysis
• Local search

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 efficiency 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.

• 出版日期2018-4
• 单位华中科技大学