Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation

• URL: http://arxiv.org/abs/2010.00134v1
• Date: Wed, 30 Sep 2020 22:38:47 GMT
• Title: Machine Learning in Airline Crew Pairing to Construct Initial Clusters for Dynamic Constraint Aggregation
• Authors: Yassine Yaakoubi, Fran\c{c}ois Soumis, Simon Lacoste-Julien
• Abstract summary: 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.
• Score: 23.980050729253612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The crew pairing problem (CPP) is generally modelled as a set partitioning problem where the flights have to be partitioned in pairings. A pairing is a sequence of flight legs separated by connection time and rest periods that starts and ends at the same base. Because of the extensive list of complex rules and regulations, determining whether a sequence of flights constitutes a feasible pairing can be quite difficult by itself, making CPP one of the hardest of the airline planning problems. In this paper, we first propose to improve the prototype Baseline solver of Desaulniers et al. (2020) by adding dynamic control strategies to obtain an efficient solver for large-scale CPPs: Commercial-GENCOL-DCA. These solvers are designed to aggregate the flights covering constraints to reduce the size of the problem. Then, we use machine learning (ML) to produce clusters of flights having a high probability of being performed consecutively by the same crew. The solver combines several advanced Operations Research techniques to assemble and modify these clusters, when necessary, to produce a good solution. We show, on monthly CPPs with up to 50 000 flights, that Commercial-GENCOL-DCA with clusters produced by ML-based heuristics outperforms Baseline fed by initial clusters that are pairings of a solution obtained by rolling horizon with GENCOL. The reduction of solution cost averages between 6.8% and 8.52%, which is mainly due to the reduction in the cost of global constraints between 69.79% and 78.11%.

Related papers

• Capacity-Aware Planning and Scheduling in Budget-Constrained Monotonic MDPs: A Meta-RL Approach [7.385321178884467]
  Many real-world sequential repair problems can be effectively modeled using monotonic Markov Decision Processes (MDPs) This work addresses the problem of solving multi-component monotonic MDPs with both budget and capacity constraints.
  arXiv  Detail & Related papers  (2024-10-28T17:48:45Z)
• Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
  We develop a single stage approach named Alignment with Integrated Human Feedback (AIHF) to train reward models and the policy. The proposed approach admits a suite of efficient algorithms, which can easily reduce to, and leverage, popular alignment algorithms. We demonstrate the efficiency of the proposed solutions with extensive experiments involving alignment problems in LLMs and robotic control problems in MuJoCo.
  arXiv  Detail & Related papers  (2024-06-11T01:20:53Z)
• Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
  Efficiently solving a vehicle routing problem in a practical runtime is a critical challenge for delivery management companies. This paper explores both a theoretical and experimental connection between the Capacitated Vehicle Problem (CVRP) and the Constrainedid-Based Clustering (CCBC) The proposed framework consists of three stages. At the first step, a constrained centroid-based clustering algorithm generates feasible clusters of customers.
  arXiv  Detail & Related papers  (2024-03-20T22:24:36Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art. With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
  arXiv  Detail & Related papers  (2020-06-05T13:48:26Z)
• 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)
• 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.