Title: Solving airline crew pairing problems through constraint partitioning

Authors: Maryam Radman; Kourosh Eshghi

Addresses: Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran ' Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Abstract: In this paper, a decomposition technique based on constraint partitioning is developed to solve the crew pairing problem (CPP) which has an overriding importance in the airline industry as it determines the crew cost. The method is based on the observation that in large-scale problems, the constraints can be partitioned to some sub-problems which involve special subsets of variables. The resultant structure is called the 'partitioned structure'. Therefore, in the proposed method, first, a feasible solution is generated for a reduced CPP with a 'partitioned structure' through the optimal solutions of its sub-problems. Then, at each step, the feasible solution is improved through adding/removing some pairings to/from it. The proposed algorithm is applied to a case study from the literature as well as some randomly generated test problems. One advantage of the proposed method is finding multiple feasible solutions with lower time than the method used to solve the case. [Submitted: 8 May 2020; Accepted: 29 December 2021]

Keywords: crew pairing problems; CPPs; constraint partitioning; decomposition technique; sub-problem; airline industry.

DOI: 10.1504/EJIE.2023.127738

European Journal of Industrial Engineering, 2023 Vol.17 No.1, pp.29 - 59

Accepted: 29 Dec 2021
Published online: 15 Dec 2022 *