Loading...

Solving airline crew pairing problems through constraint partitioning

Radman, M ; Sharif University of Technology | 2023

38 Viewed
  1. Type of Document: Article
  2. DOI: 10.1504/EJIE.2023.10044607
  3. Publisher: Inderscience Publishers , 2023
  4. Abstract:
  5. 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. © 2023 Inderscience Enterprises Ltd
  6. Keywords:
  7. Airline industry ; Constraint partitioning ; Crew pairing problem (CPP) ; Crew pairing problems ; Decomposition technique ; Sub-problem
  8. Source: European Journal of Industrial Engineering ; Volume 17, Issue 1 , 2023 , Pages 29-59 ; 17515254 (ISSN)
  9. URL: http://www.inderscience.com/storage/f312652104118971.pdf