Cross-Problem Learning for Solving Vehicle Routing Problems

• URL: http://arxiv.org/abs/2404.11677v3
• Date: Tue, 18 Jun 2024 09:03:08 GMT
• Title: Cross-Problem Learning for Solving Vehicle Routing Problems
• Authors: Zhuoyi Lin, Yaoxin Wu, Bangjian Zhou, Zhiguang Cao, Wen Song, Yingqian Zhang, Senthilnath Jayavelu,
• Abstract summary: Existing neurals often train a deep architecture from scratch for each specific vehicle routing problem (VRP) This paper proposes the cross-problem learning to empirically assists training for different downstream VRP variants.
• Score: 24.212686893913826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing neural heuristics often train a deep architecture from scratch for each specific vehicle routing problem (VRP), ignoring the transferable knowledge across different VRP variants. This paper proposes the cross-problem learning to assist heuristics training for different downstream VRP variants. Particularly, we modularize neural architectures for complex VRPs into 1) the backbone Transformer for tackling the travelling salesman problem (TSP), and 2) the additional lightweight modules for processing problem-specific features in complex VRPs. Accordingly, we propose to pre-train the backbone Transformer for TSP, and then apply it in the process of fine-tuning the Transformer models for each target VRP variant. On the one hand, we fully fine-tune the trained backbone Transformer and problem-specific modules simultaneously. On the other hand, we only fine-tune small adapter networks along with the modules, keeping the backbone Transformer still. Extensive experiments on typical VRPs substantiate that 1) the full fine-tuning achieves significantly better performance than the one trained from scratch, and 2) the adapter-based fine-tuning also delivers comparable performance while being notably parameter-efficient. Furthermore, we empirically demonstrate the favorable effect of our method in terms of cross-distribution application and versatility.

Related papers

• RouteFinder: Towards Foundation Models for Vehicle Routing Problems [21.3310292139361]
  RouteFinder is a framework to tackle different Vehicle Routing Problem (VRP) variants. Our core idea is that a foundation model for VRPs should be able to represent variants by treating each as a subset of a generalized problem equipped with different attributes.
  arXiv  Detail & Related papers  (2024-06-21T09:34:26Z)
• 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)
• Decision S4: Efficient Sequence-Based RL via State Spaces Layers [87.3063565438089]
  We present an off-policy training procedure that works with trajectories, while still maintaining the training efficiency of the S4 model. An on-policy training procedure that is trained in a recurrent manner, benefits from long-range dependencies, and is based on a novel stable actor-critic mechanism.
  arXiv  Detail & Related papers  (2023-06-08T13:03:53Z)
• 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)
• Emergent Agentic Transformer from Chain of Hindsight Experience [96.56164427726203]
  We show that a simple transformer-based model performs competitively with both temporal-difference and imitation-learning-based approaches. This is the first time that a simple transformer-based model performs competitively with both temporal-difference and imitation-learning-based approaches.
  arXiv  Detail & Related papers  (2023-05-26T00:43:02Z)
• Transformer in Transformer as Backbone for Deep Reinforcement Learning [43.354375917223656]
  We propose to design emphpure Transformer-based networks for deep RL. The Transformer in Transformer (TIT) backbone is proposed, which cascades two Transformers in a very natural way. Experiments show that TIT can achieve satisfactory performance in different settings consistently.
  arXiv  Detail & Related papers  (2022-12-30T03:50:38Z)
• Dual Vision Transformer [114.1062057736447]
  We propose a novel Transformer architecture that aims to mitigate the cost issue, named Dual Vision Transformer (Dual-ViT) The new architecture incorporates a critical semantic pathway that can more efficiently compress token vectors into global semantics with reduced order of complexity. We empirically demonstrate that Dual-ViT provides superior accuracy than SOTA Transformer architectures with reduced training complexity.
  arXiv  Detail & Related papers  (2022-07-11T16:03:44Z)
• Rich CNN-Transformer Feature Aggregation Networks for Super-Resolution [50.10987776141901]
  Recent vision transformers along with self-attention have achieved promising results on various computer vision tasks. We introduce an effective hybrid architecture for super-resolution (SR) tasks, which leverages local features from CNNs and long-range dependencies captured by transformers. Our proposed method achieves state-of-the-art SR results on numerous benchmark datasets.
  arXiv  Detail & Related papers  (2022-03-15T06:52:25Z)
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer [14.680514752270375]
  This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately. The positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions.
  arXiv  Detail & Related papers  (2021-10-06T07:21:41Z)
• Video Super-Resolution Transformer [85.11270760456826]
  Video super-resolution (VSR), with the aim to restore a high-resolution video from its corresponding low-resolution version, is a spatial-temporal sequence prediction problem. Recently, Transformer has been gaining popularity due to its parallel computing ability for sequence-to-sequence modeling. In this paper, we present a spatial-temporal convolutional self-attention layer with a theoretical understanding to exploit the locality information.
  arXiv  Detail & Related papers  (2021-06-12T20:00:32Z)
• UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers [108.92194081987967]
  We make the first attempt to explore a universal multi-agent reinforcement learning pipeline, designing one single architecture to fit tasks. Unlike previous RNN-based models, we utilize a transformer-based model to generate a flexible policy. The proposed model, named as Universal Policy Decoupling Transformer (UPDeT), further relaxes the action restriction and makes the multi-agent task's decision process more explainable.
  arXiv  Detail & Related papers  (2021-01-20T07:24:24Z)

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.