Solving airline crew pairing problems through constraint partitioning Online publication date: Thu, 15-Dec-2022
by Maryam Radman; Kourosh Eshghi
European J. of Industrial Engineering (EJIE), Vol. 17, No. 1, 2023
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]
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the European J. of Industrial Engineering (EJIE):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook