Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method

• URL: http://arxiv.org/abs/2003.03792v2
• Date: Sat, 27 May 2023 20:59:13 GMT
• Title: Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method
• Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Back, and Michael Emmerich
• Abstract summary: Airline crew pairing optimization problem (CPOP) aims to find a set of flight sequences that cover all flights in an airline's highly constrained flight schedule at minimum cost. CPOP is NP-hard, and tackling it is quite challenging. This paper proposes a domain-knowledge-driven customized-GA.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Communication-Efficient Federated Group Distributionally Robust Optimization [49.14751984342068]
  Federated learning faces challenges due to the heterogeneity in data volumes and distributions at different clients. Existing approaches to address this issue based on group distributionally robust optimization (GDRO) often lead to high communication and sample complexity. This work introduces algorithms tailored for communication-efficient Federated Group Distributionally Robust Optimization.
  arXiv  Detail & Related papers  (2024-10-08T21:07:53Z)
• Controllable Prompt Tuning For Balancing Group Distributional Robustness [53.336515056479705]
  We introduce an optimization scheme to achieve good performance across groups and find a good solution for all without severely sacrificing performance on any of them. We propose Controllable Prompt Tuning (CPT), which couples our approach with prompt-tuning techniques. On spurious correlation benchmarks, our procedures achieve state-of-the-art results across both transformer and non-transformer architectures, as well as unimodal and multimodal data.
  arXiv  Detail & Related papers  (2024-03-05T06:23:55Z)
• AffineGlue: Joint Matching and Robust Estimation [74.04609046690913]
  We propose AffineGlue, a method for joint two-view feature matching and robust estimation. AffineGlue selects potential matches from one-to-many correspondences to estimate minimal models. Guided matching is then used to find matches consistent with the model, suffering less from the ambiguities of one-to-one matches.
  arXiv  Detail & Related papers  (2023-07-28T08:05:36Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• GAIA: A Transfer Learning System of Object Detection that Fits Your Needs [136.60609274344893]
  Transfer learning with pre-training on large-scale datasets has played an increasingly significant role in computer vision and natural language processing. In this paper, we focus on the area of object detection and present a transfer learning system named GAIA. GAIA is capable of providing powerful pre-trained weights, selecting models that conform to downstream demands such as latency constraints and specified data domains.
  arXiv  Detail & Related papers  (2021-06-21T18:24:20Z)
• Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation [23.980050729253612]
  Crew pairing problem ( CPP) is generally modelled as a set problem where the flights have to be partitioned in pairings. We use machine learning (ML) to produce clusters of flights having a high probability of being performed consecutively by the same crew. We show, on monthly CPPs with up to 50 000 flights, that Commercial-GENCOL-DCA with clusters produced by ML-baseds outperforms Baseline fed by initial clusters.
  arXiv  Detail & Related papers  (2020-09-30T22:38:47Z)
• Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer [23.980050729253612]
  We present a case study of using machine learning classification algorithms to initialize a large-scale commercial solver (GENCOL) Small savings of as little as 1% translate to increasing annual revenue by dozens of millions of dollars in a large airline.
  arXiv  Detail & Related papers  (2020-09-26T01:32:07Z)
• A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks [0.0]
  This paper proposes a novel CG, which has enabled the in-house development of an Airline Crew Pairing (AirCROP) The efficacy of the CPO/AirCROP has been tested on real-world, large-scale, complex network instances with over 4,200 flights, 15 crew bases, and multiple hub-and-spoke sub-networks.
  arXiv  Detail & Related papers  (2020-05-18T12:19:02Z)
• On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization [0.0]
  This paper proposes a novel adaptation of the Variational Graph Auto-Encoder for learning plausible patterns among the flight-connection data. The resulting flight-connection predictions are combined on-the-fly using a novel to generate new pairings. The utility of the proposed approach is demonstrated on large-scale (over 4200 flights), real-world, complex flight-networks of US-based airlines, characterized by multiple hub-and-spokeworks and several crew bases.
  arXiv  Detail & Related papers  (2020-04-28T20:16:22Z)
• On Initializing Airline Crew Pairing Optimization for Large-scale Complex Flight Networks [0.0]
  This paper aims at generating a set of flight sequences (crew pairings) covering a flight-schedule, at minimum-cost, while satisfying several legality constraints. For real-world large and complex flight network (including over 3200 flights and 15 crew bases) provided by GE Aviation, the proposed datasets shows upto a ten-fold speed improvement over another state-of-the-art approach.
  arXiv  Detail & Related papers  (2020-03-15T08:21:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.