On Initializing Airline Crew Pairing Optimization for Large-scale Complex Flight Networks

• URL: http://arxiv.org/abs/2003.06423v1
• Date: Sun, 15 Mar 2020 08:21:38 GMT
• Title: On Initializing Airline Crew Pairing Optimization for Large-scale Complex Flight Networks
• Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas B\"ack, Michael Emmerich
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

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)
• Cost-Sensitive Multi-Fidelity Bayesian Optimization with Transfer of Learning Curve Extrapolation [55.75188191403343]
  We introduce utility, which is a function predefined by each user and describes the trade-off between cost and performance of BO. We validate our algorithm on various LC datasets and found it outperform all the previous multi-fidelity BO and transfer-BO baselines we consider.
  arXiv  Detail & Related papers  (2024-05-28T07:38:39Z)
• CANOS: A Fast and Scalable Neural AC-OPF Solver Robust To N-1 Perturbations [0.7545833157486899]
  In the simplest setting, Optimal Power Flow (OPF) determines how much power to generate in order to minimize costs. Power grid operators use approximations of the AC-OPF problem because solving the exact problem is prohibitively slow with state-of-the-art solvers. In the present work, we train a deep learning system (CANOS) to predict near-optimal solutions (within 1% of the true AC-OPF cost) without compromising speed.
  arXiv  Detail & Related papers  (2024-03-26T12:47:04Z)
• Joint User Association, Interference Cancellation and Power Control for Multi-IRS Assisted UAV Communications [80.35959154762381]
  Intelligent reflecting surface (IRS)-assisted unmanned aerial vehicle (UAV) communications are expected to alleviate the load of ground base stations in a cost-effective way. Existing studies mainly focus on the deployment and resource allocation of a single IRS instead of multiple IRSs. We propose a new optimization algorithm for joint IRS-user association, trajectory optimization of UAVs, successive interference cancellation (SIC) decoding order scheduling and power allocation.
  arXiv  Detail & Related papers  (2023-12-08T01:57:10Z)
• Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
  We propose a non-orthogonal multiple access (NOMA) enabled HFL system under semi-synchronous cloud model aggregation. We show that the proposed scheme outperforms the considered benchmarks regarding HFL performance improvement and total cost reduction.
  arXiv  Detail & Related papers  (2023-11-03T13:34:44Z)
• Movement Penalized Bayesian Optimization with Application to Wind Energy Systems [84.7485307269572]
  Contextual Bayesian optimization (CBO) is a powerful framework for sequential decision-making given side information. In this setting, the learner receives context (e.g., weather conditions) at each round, and has to choose an action (e.g., turbine parameters) Standard algorithms assume no cost for switching their decisions at every round, but in many practical applications, there is a cost associated with such changes, which should be minimized.
  arXiv  Detail & Related papers  (2022-10-14T20:19:32Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• 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)
• 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)
• Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method [0.0]
  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.
  arXiv  Detail & Related papers  (2020-03-08T15:04:57Z)

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.