Solving an integrated mathematical model for crew pairing and rostering problems by an ant colony optimisation algorithm. (25th February 2022)

• Record Type: Journal Article
• Authors: Saemi, Saeed; Komijan, Alireza Rashidi; Tavakkoli-Moghaddam, Reza; Fallah, Mohammad
• Is Part Of: European journal of industrial engineering. Volume 16:Number 2(2022)
• Page Start: 215
• Page End: 240
• Publication Date: 2022-02-25
• Subjects: crew pairing and crew rostering -- crew scheduling -- inseparable flights -- ant colony optimisation -- ACO; Industrial engineering -- Europe -- Periodicals; 658.50094
• Languages: English
• ISSNs: 1751-5254

Abstract

The crew pairing problem (CPP) and the crew rostering problem (CRP) are two sub-problems of a crew scheduling problem (CSP). Solving these problems based on a sequential approach may not yield the optimum solution. Therefore, the present study aims to consider the integrated CPP and CRP and present a new mathematical formulation. Due to its NP-hardness complexity, a meta-heuristic algorithm based on ant colony optimisation (ACO) is designed and used to solve the integrated problem and sequential approach (CRP followed by CPP) in some test problems extracted from a data set. The solutions provided by ACO for the integrated problem show 21.64% cost reduction in a reasonable time increase in comparison with those obtained by the sequential approach. Also, the ACO algorithm can provide solutions with a 2.96% average gap to the optimal solutions (by the exact method) for small-sized problems. Also, the proposed integrated approach leads to solutions with the best/optimal number of crew members to be assigned. The findings indicate that the proposed ACO has an efficient performance in solving the integrated problem. [Received: 20 May 2020; Accepted: 8 April 2021]