2020/03/15 by Divyam Aggarwal, Dhish Kumar Saxena, Aggarwal, Divyam +5
Business, Management and Accounting · Economics, Econometrics and Finance · Engineering · #Artificial Intelligence (cs.AI) #Aviation Industry Analysis and Trends #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2003.06423
openalex publication_date 2020/03/15 · openalex created_date 2020/03/23 · openalex updated_date 2026/07/28
Crew pairing optimization (CPO) is critically important for any airline, since its crew operating costs are second-largest, next to the fuel-cost. CPO aims at generating a set of flight sequences (crew pairings) covering a flight-schedule, at minimum-cost, while satisfying several legality constraints. For large-scale complex flight networks, billion-plus legal pairings (variables) are possible, rendering their offline enumeration intractable and an exhaustive search for their minimum-cost full flight-coverage subset impractical. Even generating an initial feasible solution (IFS: a manageable set of legal pairings covering all flights), which could be subsequently optimized is a difficult (NP-complete) problem. Though, as part of a larger project the authors have developed a crew pairing optimizer (AirCROP), this paper dedicatedly focuses on IFS-generation through a novel heuristic based on divide-and-cover strategy and Integer Programming. For real-world large and complex flight network datasets (including over 3200 flights and 15 crew bases) provided by GE Aviation, the proposed heuristic shows upto a ten-fold speed improvement over another state-of-the-art approach. Unprecedentedly, this paper presents an empirical investigation of the impact of IFS-cost on the final (optimized) solution-cost, revealing that too low an IFS-cost does not necessarily imply faster convergence for AirCROP or even lower cost for the optimized solution.