An integrated crew scheduling problem considering reserve crew in air transportation: Ant colony optimization algorithm

A Crew Scheduling Problem (CSP) is a highly complex airline optimization problem, which includes two sub-problems, namely Crew Rostering Problem (CRP) and Crew Pairing Problem (CPP). Solving these problems sequentially may not lead to an optimal solution. To overcome this shortcoming, the present study introduces a new bi-objective formulation for the integrating CPP and CRP by considering the reserve crew with the objectives of crew cost minimization and crew reserve maximization. The integrated model generates and assigns pairings to a group of crew members by taking into account the rules and regulations about employing the manpower (i.e., crew member) and crew reservation in order to reduce flight delays or even cancellations due to the unexpected disruptions. An Ant Colony Optimization (ACO) algorithm is used to solve the considered problem. To justify the efficiency of this proposed algorithm in solving the presented model, different test problems are generated and solved by ACO and GAMS. The computational results indicate that solutions obtained by the proposed ACO algorithm have a 2.57% gap with the optimal solutions reported by GAMS as optimization software on average and significantly less CPU time for small-sized problems. Also, ACO obtains better solutions in significantly shorter CPU time for large-sized problems. The results indicate the efficient performance of the proposed algorithm in solving the given problems.