Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method
Airline crew pairing optimization problem (CPOP) aims to find a set of flight sequences (crew pairings) that cover all flights in an airline's highly constrained flight schedule at minimum cost. Since crew cost is second only to the fuel cost, CPOP solutioning is critically important for an airline. However, CPOP is NP-hard, and tackling it is quite challenging. The literature suggests, that when the CPOP's scale and complexity is reasonably limited, and an enumeration of all crew pairings is possible, then Metaheuristics are used, predominantly Genetic Algorithms (GAs). Else, Column Generation (CG) based Mixed Integer Programming techniques are used. Notably, as per the literature, a maximum of 45,000 crew pairings have been tackled by GAs. In a significant departure, this paper considers over 800 flights of a US-based large airline (with a monthly network of over 33,000 flights), and tests the efficacy of GAs by enumerating all 400,000+ crew pairings, apriori. Towards it, this paper proposes a domain-knowledge-driven customized-GA. The utility of incorporating domain-knowledge in GA operations, particularly initialization and crossover, is highlighted through suitable experiments. Finally, the proposed GA's performance is compared with a CG-based approach (developed in-house by the authors). Though the latter is found to perform better in terms of solution's cost-quality and run time, it is hoped that this paper will help in better understanding the strengths and limitations of domain-knowledge-driven customizations in GAs, for solving combinatorial optimization problems, including CPOPs.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization
Airline Crew Pairing Optimization (CPO) aims at generating a set of legal flight sequences (crew pairings), to cover an airline's flight schedule, at minimum cost. It is usually performed using Column Generation (CG), a …
A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks
Crew Pairing Optimization (CPO) is critical for an airlines' business viability, given that the crew operating cost is second only to the fuel cost. CPO aims at generating a set of flight sequences (crew pairings) to cov…
Combinatorial OptimizationOn Initializing Airline Crew Pairing Optimization for Large-scale Complex Flight Networks
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…
Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer
We present a case study of using machine learning classification algorithms to initialize a large-scale commercial solver (GENCOL) based on column generation in the context of the airline crew pairing problem, where smal…
General ClassificationImitation LearningSchedulingMachine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation
The crew pairing problem (CPP) is generally modelled as a set partitioning problem where the flights have to be partitioned in pairings. A pairing is a sequence of flight legs separated by connection time and rest period…
BIG-bench Machine Learning