Title: Solving an integrated mathematical model for crew pairing and rostering problems by an ant colony optimisation algorithm

Authors: Saeed Saemi; Alireza Rashidi Komijan; Reza Tavakkoli-Moghaddam; Mohammad Fallah

Addresses: Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran ' Department of Industrial Engineering, Firoozkooh Branch, Islamic Azad University, Firoozkooh, Iran ' School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran; Universal Scientific Education and Research Network (USERN), Tehran, Iran ' Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran

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]

Keywords: crew pairing and crew rostering; crew scheduling; inseparable flights; ant colony optimisation; ACO.

DOI: 10.1504/EJIE.2022.121188

European Journal of Industrial Engineering, 2022 Vol.16 No.2, pp.215 - 240

Received: 20 May 2020
Accepted: 08 Apr 2021
Published online: 28 Feb 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article