Towards Omni-generalizable Neural Methods for Vehicle Routing Problems

• URL: http://arxiv.org/abs/2305.19587v2
• Date: Tue, 20 Jun 2023 05:07:58 GMT
• Title: Towards Omni-generalizable Neural Methods for Vehicle Routing Problems
• Authors: Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang
• Abstract summary: 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.
• Score: 14.210085924625705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning heuristics for vehicle routing problems (VRPs) has gained much attention due to the less reliance on hand-crafted rules. However, existing methods are typically trained and tested on the same task with a fixed size and distribution (of nodes), and hence suffer from limited generalization performance. 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 initialized model with the capability of fast adaptation to new tasks during inference. We further develop a simple yet efficient approximation method to reduce the training overhead. Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. The code is available at: https://github.com/RoyalSkye/Omni-VRP.

Related papers

• Prompt Learning for Generalized Vehicle Routing [17.424910810870273]
  This work investigates an efficient prompt learning approach in Neural optimization for cross-distribution adaptation. The proposed model learns a set of prompts among various distributions and then selects the best-matched one to prompt a pre-trained attention model for each problem instance. It also outperforms existing generalized models on both in-distribution prediction and zero-shot generalization to a diverse set of new tasks.
  arXiv  Detail & Related papers  (2024-05-20T15:42:23Z)
• 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)
• Towards Seamless Adaptation of Pre-trained Models for Visual Place Recognition [72.35438297011176]
  We propose a novel method to realize seamless adaptation of pre-trained models for visual place recognition (VPR) Specifically, to obtain both global and local features that focus on salient landmarks for discriminating places, we design a hybrid adaptation method. Experimental results show that our method outperforms the state-of-the-art methods with less training data and training time.
  arXiv  Detail & Related papers  (2024-02-22T12:55:01Z)
• InferAligner: Inference-Time Alignment for Harmlessness through Cross-Model Guidance [56.184255657175335]
  We develop textbfInferAligner, a novel inference-time alignment method that utilizes cross-model guidance for harmlessness alignment. Experimental results show that our method can be very effectively applied to domain-specific models in finance, medicine, and mathematics. It significantly diminishes the Attack Success Rate (ASR) of both harmful instructions and jailbreak attacks, while maintaining almost unchanged performance in downstream tasks.
  arXiv  Detail & Related papers  (2024-01-20T10:41:03Z)
• CLUTR: Curriculum Learning via Unsupervised Task Representation Learning [130.79246770546413]
  CLUTR is a novel curriculum learning algorithm that decouples task representation and curriculum learning into a two-stage optimization. We show CLUTR outperforms PAIRED, a principled and popular UED method, in terms of generalization and sample efficiency in the challenging CarRacing and navigation environments.
  arXiv  Detail & Related papers  (2022-10-19T01:45:29Z)
• Accelerated Policy Learning with Parallel Differentiable Simulation [59.665651562534755]
  We present a differentiable simulator and a new policy learning algorithm (SHAC) Our algorithm alleviates problems with local minima through a smooth critic function. We show substantial improvements in sample efficiency and wall-clock time over state-of-the-art RL and differentiable simulation-based algorithms.
  arXiv  Detail & Related papers  (2022-04-14T17:46:26Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  Three simple ideas allow us to train models with DRO using a broader class of parametric likelihood ratios. We find that models trained with the resulting parametric adversaries are consistently more robust to subpopulation shifts when compared to other DRO approaches.
  arXiv  Detail & Related papers  (2022-04-13T12:43:12Z)
• Efficient Few-Shot Object Detection via Knowledge Inheritance [62.36414544915032]
  Few-shot object detection (FSOD) aims at learning a generic detector that can adapt to unseen tasks with scarce training samples. We present an efficient pretrain-transfer framework (PTF) baseline with no computational increment. We also propose an adaptive length re-scaling (ALR) strategy to alleviate the vector length inconsistency between the predicted novel weights and the pretrained base weights.
  arXiv  Detail & Related papers  (2022-03-23T06:24:31Z)
• Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing [9.995347522610674]
  We develop a framework for value-function-based deep reinforcement learning with a reinforcement action space. We present an application of this framework to the capacitated vehicle routing problem (CVRP) On each instance, we model an action as the construction of a single route, and consider a deterministic policy which is improved through a simple policy algorithm.
  arXiv  Detail & Related papers  (2020-10-22T19:32:21Z)
• Using Deep Reinforcement Learning Methods for Autonomous Vessels in 2D Environments [11.657524999491029]
  In this work, we used deep reinforcement learning combining Q-learning with a neural representation to avoid instability. Our methodology uses deep q-learning and combines it with a rolling wave planning approach on agile methodology. Experimental results show that the proposed method enhanced the performance of VVN by 55.31 on average for long-distance missions.
  arXiv  Detail & Related papers  (2020-03-23T12:58:58Z)

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.