Machine-learning-based arc selection for constrained shortest path problems in column generation

• URL: http://arxiv.org/abs/2201.02535v1
• Date: Fri, 7 Jan 2022 16:49:12 GMT
• Title: Machine-learning-based arc selection for constrained shortest path problems in column generation
• Authors: Mouad Morabit, Guy Desaulniers, Andrea Lodi
• Abstract summary: In this work, we propose a new pricing algorithm based on machine learning. The objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows.
• Score: 5.08128537391027
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a master problem, and one or more pricing problems (PP). The total computing time taken by the method is divided between these two parts. In routing or scheduling applications, the problems are mostly defined on a network, and the PP is usually an NP-hard shortest path problem with resource constraints. In this work, we propose a new heuristic pricing algorithm based on machine learning. By taking advantage of the data collected during previous executions, the objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows. Reductions in computational time of up to 40% can be obtained.

Related papers

• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
  arXiv  Detail & Related papers  (2023-10-22T02:46:37Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  We introduce a novel temporal decomposition scheme for solving a class of offline PDPTWs. Our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty.
  arXiv  Detail & Related papers  (2023-03-06T20:07:05Z)
• 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)
• An Information Theory-inspired Strategy for Automatic Network Pruning [88.51235160841377]
  Deep convolution neural networks are well known to be compressed on devices with resource constraints. Most existing network pruning methods require laborious human efforts and prohibitive computation resources. We propose an information theory-inspired strategy for automatic model compression.
  arXiv  Detail & Related papers  (2021-08-19T07:03:22Z)
• Learned upper bounds for the Time-Dependent Travelling Salesman Problem [0.0]
  Time-Dependent Travelling Salesman Problem consists in finding a Hamiltonian tour of at least total duration covering the vertices of the graph. We devise an upper bounding technique based on the solution of a classical (and simpler) time-independent Asymmetric Travelling Salesman Problem. The effectiveness of this approach has been assessed through a computational campaign on the real travel time functions of two European cities.
  arXiv  Detail & Related papers  (2021-07-28T20:54:59Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  We present two novel dual algorithms for tight and efficient neural network bounding. Both methods recover the strengths of the new relaxation: tightness and a linear separation oracle. We can obtain better bounds than off-the-shelf solvers in only a fraction of their running time.
  arXiv  Detail & Related papers  (2021-01-14T19:45:17Z)
• 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)
• Modeling and solving the multimodal car- and ride-sharing problem [0.0]
  We introduce the multimodal car- and ride-sharing problem (MMCRP) A pool of cars is used to cover a set of ride requests while uncovered requests are assigned to other modes of transport. We propose a two-layer decomposition algorithm based on column generation.
  arXiv  Detail & Related papers  (2020-01-15T09:43:55Z)

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.