A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem
针对公平导向的乘务排班问题，提出一种结合列生成与变深度邻域搜索的三阶段启发式算法，在荷兰铁路的实际案例中优于商业求解器。
The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver.