Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer

• URL: http://arxiv.org/abs/2110.02544v1
• Date: Wed, 6 Oct 2021 07:21:41 GMT
• Title: Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• Authors: Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, Jing Tang
• Abstract summary: 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.
• Score: 14.680514752270375
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its positional encoding (PE) method is not suitable in representing VRP solutions. This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately, instead of fusing them together as done in existing ones, so as to avoid potential noises and incompatible correlations. Moreover, 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 (i.e., cyclic sequences). We train DACT using Proximal Policy Optimization and design a curriculum learning strategy for better sample efficiency. We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively.

Related papers

• Joint Transmit and Pinching Beamforming for PASS: Optimization-Based or Learning-Based? [89.05848771674773]
  A novel antenna system ()-enabled downlink multi-user multiple-input single-output (MISO) framework is proposed. It consists of multiple waveguides, which equip numerous low-cost antennas, named (PAs) The positions of PAs can be reconfigured to both spanning large-scale path and space.
  arXiv  Detail & Related papers  (2025-02-12T18:54:10Z)
• CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems [15.136899433821894]
  The profiled vehicle routing problem (PVRP) is a generalization of the heterogeneous capacitated vehicle routing problem (HCVRP) We propose a novel approach that learns efficient solvers for PVRP using multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2025-01-06T12:37:56Z)
• PearSAN: A Machine Learning Method for Inverse Design using Pearson Correlated Surrogate Annealing [66.27103948750306]
  PearSAN is a machine learning-assisted optimization algorithm applicable to inverse design problems with large design spaces. It uses a Pearson correlated surrogate model to predict the figure of merit of the true design metric. It achieves a state-of-the-art maximum design efficiency of 97%, and is at least an order of magnitude faster than previous methods.
  arXiv  Detail & Related papers  (2024-12-26T17:02:19Z)
• Adaptive Step-size Perception Unfolding Network with Non-local Hybrid Attention for Hyperspectral Image Reconstruction [0.39134031118910273]
  We propose an adaptive step-size perception unfolding network (ASPUN), a deep unfolding network based on FISTA algorithm. In addition, we design a Non-local Hybrid Attention Transformer(NHAT) module for fully leveraging the receptive field advantage of transformer. Experimental results show that our ASPUN is superior to the existing SOTA algorithms and achieves the best performance.
  arXiv  Detail & Related papers  (2024-07-04T16:09:52Z)
• Cross-Problem Learning for Solving Vehicle Routing Problems [24.212686893913826]
  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.
  arXiv  Detail & Related papers  (2024-04-17T18:17:50Z)
• Efficient Adaptation of Large Vision Transformer via Adapter Re-Composing [8.88477151877883]
  High-capacity pre-trained models have revolutionized problem-solving in computer vision. We propose a novel Adapter Re-Composing (ARC) strategy that addresses efficient pre-trained model adaptation. Our approach considers the reusability of adaptation parameters and introduces a parameter-sharing scheme.
  arXiv  Detail & Related papers  (2023-10-10T01:04:15Z)
• 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)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Full Stack Optimization of Transformer Inference: a Survey [58.55475772110702]
  Transformer models achieve superior accuracy across a wide range of applications. The amount of compute and bandwidth required for inference of recent Transformer models is growing at a significant rate. There has been an increased focus on making Transformer models more efficient.
  arXiv  Detail & Related papers  (2023-02-27T18:18:13Z)
• Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
  State-of-the-art approaches learn a policy using reinforcement learning, and the learnt policy acts as a pseudo solver. These approaches have demonstrated good performance in some cases, but given the large search space typical of routing problem, they can converge too quickly to poor policy. We propose entropy regularised reinforcement learning (ERRL) that supports exploration by providing more policies.
  arXiv  Detail & Related papers  (2020-12-24T14:18:56Z)
• Optimization-driven Deep Reinforcement Learning for Robust Beamforming in IRS-assisted Wireless Communications [54.610318402371185]
  Intelligent reflecting surface (IRS) is a promising technology to assist downlink information transmissions from a multi-antenna access point (AP) to a receiver. We minimize the AP's transmit power by a joint optimization of the AP's active beamforming and the IRS's passive beamforming. We propose a deep reinforcement learning (DRL) approach that can adapt the beamforming strategies from past experiences.
  arXiv  Detail & Related papers  (2020-05-25T01:42: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.