Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2403.00026v1
• Date: Wed, 28 Feb 2024 16:02:29 GMT
• Title: Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem
• Authors: Samuel J. K. Chin, Matthias Winkenbach, Akash Srivastava
• Abstract summary: We present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP) FM-MCVRP is a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Vehicle Routing Problem (CVRP) We show that FM-MCVRP produces better MCVRP solutions than the training data and generalizes to larger sized problem instances not seen during training.
• Score: 5.295700401553376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Vehicle Routing Problem (CVRP) that characterizes many real-world applications. The so-called Montreal Capacitated Vehicle Routing Problem (MCVRP), first formally described by Bengio et al. (2021), is defined on a fixed and finite graph, which is analogous to a city. Each MCVRP instance is essentially the sub-graph connecting a randomly sampled subset of the nodes in the fixed graph, which represent a set of potential addresses in a real-world delivery problem on a given day. Our work exploits this problem structure to frame the MCVRP as an analogous Natural Language Processing (NLP) task. Specifically, we leverage a Transformer architecture embedded in a Large Language Model (LLM) framework to train our model in a supervised manner on computationally inexpensive, sub-optimal MCVRP solutions obtained algorithmically. Through comprehensive computational experiments, we show that FM-MCVRP produces better MCVRP solutions than the training data and generalizes to larger sized problem instances not seen during training. Even when compared to near-optimal solutions from state-of-the-art heuristics, FM-MCVRP yields competitive results despite being trained on inferior data. For instance, for 400-customer problems, FM-MCVRP solutions on average fall within 2% of the benchmark. Our results further demonstrate that unlike prior works in the literature, FM-MCVRP is a unified model, which performs consistently and reliably on a range of problem instance sizes and parameter values such as the vehicle capacity.

Related papers

• MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts [26.790392171537754]
  We propose a multi-task vehicle routing solver with mixture-of-experts (MVMoE) We develop a hierarchical gating mechanism for the MVMoE, delivering a good trade-off between empirical performance and computational complexity. Experimentally, our method significantly promotes zero-shot generalization performance on 10 unseen VRP variants.
  arXiv  Detail & Related papers  (2024-05-02T06:02:07Z)
• Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
  Vehicle routing problems (VRPs) can be found in numerous real-world applications. In this work, we make the first attempt to tackle the crucial challenge of cross-problem generalization. Our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner.
  arXiv  Detail & Related papers  (2024-02-23T13:25:23Z)
• Transforming Image Super-Resolution: A ConvFormer-based Efficient Approach [58.57026686186709]
  We introduce the Convolutional Transformer layer (ConvFormer) and propose a ConvFormer-based Super-Resolution network (CFSR) CFSR inherits the advantages of both convolution-based and transformer-based approaches. Experiments demonstrate that CFSR strikes an optimal balance between computational cost and performance.
  arXiv  Detail & Related papers  (2024-01-11T03:08:00Z)
• MOTO: Offline Pre-training to Online Fine-tuning for Model-based Robot Learning [52.101643259906915]
  We study the problem of offline pre-training and online fine-tuning for reinforcement learning from high-dimensional observations. Existing model-based offline RL methods are not suitable for offline-to-online fine-tuning in high-dimensional domains. We propose an on-policy model-based method that can efficiently reuse prior data through model-based value expansion and policy regularization.
  arXiv  Detail & Related papers  (2024-01-06T21:04:31Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
  This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an model with the capability of fast adaptation to new tasks during inference.
  arXiv  Detail & Related papers  (2023-05-31T06:14:34Z)
• On Continual Model Refinement in Out-of-Distribution Data Streams [64.62569873799096]
  Real-world natural language processing (NLP) models need to be continually updated to fix the prediction errors in out-of-distribution (OOD) data streams. Existing continual learning (CL) problem setups cannot cover such a realistic and complex scenario. We propose a new CL problem formulation dubbed continual model refinement (CMR)
  arXiv  Detail & Related papers  (2022-05-04T11:54:44Z)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  The Electric Conflict-Free Vehicle Routing Problem (CF-EVRP) involves constraints such as limited operating range of the vehicles, time windows on the delivery to the customers, and limited capacity on the number of vehicles the road segments can accommodate. We develop a compositional model that breaks down the problem into smaller and simpler sub-problems and provides sub-optimal, feasible solutions.
  arXiv  Detail & Related papers  (2021-06-10T20:37:46Z)
• MMCGAN: Generative Adversarial Network with Explicit Manifold Prior [78.58159882218378]
  We propose to employ explicit manifold learning as prior to alleviate mode collapse and stabilize training of GAN. Our experiments on both the toy data and real datasets show the effectiveness of MMCGAN in alleviating mode collapse, stabilizing training, and improving the quality of generated samples.
  arXiv  Detail & Related papers  (2020-06-18T07:38:54Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  We propose a practical online method for solving a class of online distributionally robust optimization (DRO) problems. Our studies demonstrate important applications in machine learning for improving the robustness of networks.
  arXiv  Detail & Related papers  (2020-06-17T20:19:25Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)

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.