A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks

• URL: http://arxiv.org/abs/2005.08636v4
• Date: Fri, 2 Jul 2021 11:48:45 GMT
• Title: A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks
• Authors: Divyam Aggarwal, Dhish Kumar Saxena, Saaju Pualose, Thomas B\"ack, Michael Emmerich
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 cover all scheduled flights, at minimum cost, while satisfying several legality constraints. The state-of-the-art heavily relies on relaxing the underlying Integer Programming Problem into a Linear Programming Problem, which in turn is solved through the Column Generation (CG) technique. However, with the alarmingly expanding airlines' operations, CPO is marred by the curse of dimensionality, rendering the exact CG-implementations obsolete, and necessitating the heuristic-based CG-implementations. Yet, in literature, the much prevalent large-scale complex flight networks involving multiple { crew bases and/or hub-and-spoke sub-networks, largely remain uninvestigated. This paper proposes a novel CG heuristic, which has enabled the in-house development of an Airline Crew Pairing Optimizer (AirCROP). The efficacy of the heuristic/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 (resulting in billion-plus possible pairings). Notably, this paper has a dedicated focus on the proposed CG heuristic (not the entire AirCROP framework) based on balancing random exploration of pairings; exploitation of domain knowledge (on optimal solution features); and utilization of the past computational & search effort through archiving. Though this paper has an airline context, the proposed CG heuristic may find wider applications across different domains, by serving as a template on how to utilize domain knowledge to better tackle combinatorial optimization problems.

Related papers

• The Perfect Blend: Redefining RLHF with Mixture of Judges [68.58426626501883]
  Reinforcement learning from human feedback (RLHF) has become the leading approach for fine-tuning large language models (LLM) Applying RLHF for MTL currently requires careful tuning of the weights for reward model and data combinations. We introduce a novel post-training paradigm which we called Constrained Generative Policy Optimization (CGPO)
  arXiv  Detail & Related papers  (2024-09-30T15:06:53Z)
• A Graph-based Adversarial Imitation Learning Framework for Reliable & Realtime Fleet Scheduling in Urban Air Mobility [5.19664437943693]
  This paper presents a comprehensive optimization formulation of the fleet scheduling problem. It also identifies the need for alternate solution approaches. The new imitative approach achieves better mean performance and remarkable improvement in the case of unseen worst-case scenarios.
  arXiv  Detail & Related papers  (2024-07-16T18:51:24Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• ADAPT: An Open-Source sUAS Payload for Real-Time Disaster Prediction and Response with AI [55.41644538483948]
  Small unmanned aircraft systems (sUAS) are becoming prominent components of many humanitarian assistance and disaster response operations. We have developed the free and open-source ADAPT multi-mission payload for deploying real-time AI and computer vision onboard a sUAS. We demonstrate the example mission of real-time, in-flight ice segmentation to monitor river ice state and provide timely predictions of catastrophic flooding events.
  arXiv  Detail & Related papers  (2022-01-25T14:51:19Z)
• Efficient UAV Trajectory-Planning using Economic Reinforcement Learning [65.91405908268662]
  We introduce REPlanner, a novel reinforcement learning algorithm inspired by economic transactions to distribute tasks between UAVs. We formulate the path planning problem as a multi-agent economic game, where agents can cooperate and compete for resources. As the system computes task distributions via UAV cooperation, it is highly resilient to any change in the swarm size.
  arXiv  Detail & Related papers  (2021-03-03T20:54:19Z)
• 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)
• 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)
• 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.