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

• Aiding Global Convergence in Federated Learning via Local Perturbation and Mutual Similarity Information [6.767885381740953]
  Federated learning has emerged as a distributed optimization paradigm. We propose a novel modified framework wherein each client locally performs a perturbed gradient step. We show that our algorithm speeds convergence up to a margin of 30 global rounds compared with FedAvg.
  arXiv  Detail & Related papers  (2024-10-07T23:14:05Z)
• Federated Learning with Projected Trajectory Regularization [65.6266768678291]
  Federated learning enables joint training of machine learning models from distributed clients without sharing their local data. One key challenge in federated learning is to handle non-identically distributed data across the clients. We propose a novel federated learning framework with projected trajectory regularization (FedPTR) for tackling the data issue.
  arXiv  Detail & Related papers  (2023-12-22T02:12:08Z)
• Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining [119.89373423433804]
  Area Under Precision-Recall (AUPRC) was introduced as an effective metric. Serverless multi-party collaborative training can cut down the communications cost by avoiding the server node bottleneck. We propose a new ServerLess biAsed sTochastic gradiEnt (SLATE) algorithm to directly optimize the AUPRC.
  arXiv  Detail & Related papers  (2023-08-06T06:51:32Z)
• 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.