Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer

• URL: http://arxiv.org/abs/2009.12501v2
• Date: Tue, 2 Mar 2021 22:30:17 GMT
• Title: Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer
• Authors: Yassine Yaakoubi, Fran\c{c}ois Soumis, Simon Lacoste-Julien
• Abstract summary: 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.
• Score: 23.980050729253612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 small savings of as little as 1% translate to increasing annual revenue by dozens of millions of dollars in a large airline. Under the imitation learning framework, we focus on the problem of predicting the next connecting flight of a crew, framed as a multiclass classification problem trained from historical data, and design an adapted neural network approach that achieves high accuracy (99.7% overall or 82.5% on harder instances). We demonstrate the usefulness of our approach by using simple heuristics to combine the flight-connection predictions to form initial crew-pairing clusters that can be fed in the GENCOL solver, yielding a 10x speed improvement and up to 0.2% cost saving.

Related papers

• A Graph-Enhanced Deep-Reinforcement Learning Framework for the Aircraft Landing Problem [0.0]
  The Aircraft Landing Problem (ALP) is one of the challenging problems in aircraft transportation and management. This paper presents a novel deep reinforcement learning framework that combines graph neural networks with actor-critic architectures to address the ALP. Results show that the trained algorithm can be tested on different problem sets and the results are competitive to operation research algorithms.
  arXiv  Detail & Related papers  (2025-02-18T08:02:17Z)
• Optimizing Pretraining Data Mixtures with LLM-Estimated Utility [52.08428597962423]
  Large Language Models improve with increasing amounts of high-quality training data. We find token-counts outperform manual and learned mixes, indicating that simple approaches for dataset size and diversity are surprisingly effective. We propose two complementary approaches: UtiliMax, which extends token-based $200s by incorporating utility estimates from reduced-scale ablations, achieving up to a 10.6x speedup over manual baselines; and Model Estimated Data Utility (MEDU), which leverages LLMs to estimate data utility from small samples, matching ablation-based performance while reducing computational requirements by $simx.
  arXiv  Detail & Related papers  (2025-01-20T21:10:22Z)
• Over-the-Air Fair Federated Learning via Multi-Objective Optimization [52.295563400314094]
  We propose an over-the-air fair federated learning algorithm (OTA-FFL) to train fair FL models. Experiments demonstrate the superiority of OTA-FFL in achieving fairness and robust performance.
  arXiv  Detail & Related papers  (2025-01-06T21:16:51Z)
• Tackling Computational Heterogeneity in FL: A Few Theoretical Insights [68.8204255655161]
  We introduce and analyse a novel aggregation framework that allows for formalizing and tackling computational heterogeneous data. Proposed aggregation algorithms are extensively analyzed from a theoretical, and an experimental prospective.
  arXiv  Detail & Related papers  (2023-07-12T16:28:21Z)
• Personalizing Federated Learning with Over-the-Air Computations [84.8089761800994]
  Federated edge learning is a promising technology to deploy intelligence at the edge of wireless networks in a privacy-preserving manner. Under such a setting, multiple clients collaboratively train a global generic model under the coordination of an edge server. This paper presents a distributed training paradigm that employs analog over-the-air computation to address the communication bottleneck.
  arXiv  Detail & Related papers  (2023-02-24T08:41:19Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• SPATL: Salient Parameter Aggregation and Transfer Learning for Heterogeneous Clients in Federated Learning [3.5394650810262336]
  Efficient federated learning is one of the key challenges for training and deploying AI models on edge devices. Maintaining data privacy in federated learning raises several challenges including data heterogeneity, expensive communication cost, and limited resources. We propose a salient parameter selection agent based on deep reinforcement learning on local clients, and aggregating the selected salient parameters on the central server.
  arXiv  Detail & Related papers  (2021-11-29T06:28:05Z)
• Structured Convolutional Kernel Networks for Airline Crew Scheduling [22.520832696173738]
  We introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework. Our experiments demonstrate that this approach yields significant improvements for the large-scale crew pairing problem.
  arXiv  Detail & Related papers  (2021-05-25T03:47:06Z)
• 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)
• Adaptive Serverless Learning [114.36410688552579]
  We propose a novel adaptive decentralized training approach, which can compute the learning rate from data dynamically. Our theoretical results reveal that the proposed algorithm can achieve linear speedup with respect to the number of workers. To reduce the communication-efficient overhead, we further propose a communication-efficient adaptive decentralized training approach.
  arXiv  Detail & Related papers  (2020-08-24T13:23: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)

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.