On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization

• URL: http://arxiv.org/abs/2004.13714v3
• Date: Sat, 2 May 2020 11:46:35 GMT
• Title: On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization
• Authors: Divyam Aggarwal, Yash Kumar Singh, Dhish Kumar Saxena
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 mathematical programming technique for guided search-space exploration. CG exploits the interdependencies between the current and the preceding CG-iteration for generating new variables (pairings) during the optimization-search. However, with the unprecedented scale and complexity of the emergent flight networks, it has become imperative to learn higher-order interdependencies among the flight-connection graphs, and utilize those to enhance the efficacy of the CPO. In first of its kind and what marks a significant departure from the state-of-the-art, this paper proposes a novel adaptation of the Variational Graph Auto-Encoder for learning plausible combinatorial patterns among the flight-connection data obtained through the search-space exploration by an Airline Crew Pairing Optimizer, AirCROP (developed by the authors and validated by the research consortium's industrial sponsor, GE Aviation). The resulting flight-connection predictions are combined on-the-fly using a novel heuristic to generate new pairings for the optimizer. 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-spoke subnetworks and several crew bases.

Related papers

• UAV-enabled Collaborative Beamforming via Multi-Agent Deep Reinforcement Learning [79.16150966434299]
  We formulate a UAV-enabled collaborative beamforming multi-objective optimization problem (UCBMOP) to maximize the transmission rate of the UVAA and minimize the energy consumption of all UAVs. We use the heterogeneous-agent trust region policy optimization (HATRPO) as the basic framework, and then propose an improved HATRPO algorithm, namely HATRPO-UCB.
  arXiv  Detail & Related papers  (2024-04-11T03:19:22Z)
• 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)
• GraphDAC: A Graph-Analytic Approach to Dynamic Airspace Configuration [24.461948296296274]
  The National Airspace System (NAS) is reaching capacity due to increased air traffic, and is based on outdated pre-tactical planning. This study proposes a more dynamic airspace configuration (DAC) approach that could increase throughput and accommodate fluctuating traffic.
  arXiv  Detail & Related papers  (2023-07-29T03:04:22Z)
• Vertical Federated Learning over Cloud-RAN: Convergence Analysis and System Optimization [82.12796238714589]
  We propose a novel cloud radio access network (Cloud-RAN) based vertical FL system to enable fast and accurate model aggregation. We characterize the convergence behavior of the vertical FL algorithm considering both uplink and downlink transmissions. We establish a system optimization framework by joint transceiver and fronthaul quantization design, for which successive convex approximation and alternate convex search based system optimization algorithms are developed.
  arXiv  Detail & Related papers  (2023-05-04T09:26:03Z)
• Wireless-Enabled Asynchronous Federated Fourier Neural Network for Turbulence Prediction in Urban Air Mobility (UAM) [101.80862265018033]
  Urban air mobility (UAM) has been proposed in which vertical takeoff and landing (VTOL) aircraft are used to provide a ride-hailing service. In UAM, aircraft can operate in designated air spaces known as corridors, that link the aerodromes. A reliable communication network between GBSs and aircraft enables UAM to adequately utilize the airspace.
  arXiv  Detail & Related papers  (2021-12-26T14:41:52Z)
• Rethinking Drone-Based Search and Rescue with Aerial Person Detection [79.76669658740902]
  The visual inspection of aerial drone footage is an integral part of land search and rescue (SAR) operations today. We propose a novel deep learning algorithm to automate this aerial person detection (APD) task. We present the novel Aerial Inspection RetinaNet (AIR) algorithm as the combination of these contributions.
  arXiv  Detail & Related papers  (2021-11-17T21:48:31Z)
• Deep Learning Aided Routing for Space-Air-Ground Integrated Networks Relying on Real Satellite, Flight, and Shipping Data [79.96177511319713]
  Current maritime communications mainly rely on satellites having meager transmission resources, hence suffering from poorer performance than modern terrestrial wireless networks. With the growth of transcontinental air traffic, the promising concept of aeronautical ad hoc networking relying on commercial passenger airplanes is potentially capable of enhancing satellite-based maritime communications via air-to-ground and multi-hop air-to-air links. We propose space-air-ground integrated networks (SAGINs) for supporting ubiquitous maritime communications, where the low-earth-orbit satellite constellations, passenger airplanes, terrestrial base stations, ships, respectively, serve as the space-, air-,
  arXiv  Detail & Related papers  (2021-10-28T14:12:10Z)
• Spatio-Temporal Data Mining for Aviation Delay Prediction [15.621546618044173]
  We present a novel aviation delay prediction system based on stacked Long Short-Term Memory (LSTM) networks for commercial flights. The system learns from historical trajectories from automatic dependent surveillance-broadcast (ADS-B) messages. Compared with previous schemes, our approach is demonstrated to be more robust and accurate for large hub airports.
  arXiv  Detail & Related papers  (2021-03-20T18:37:06Z)
• 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 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.