Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems

• URL: http://arxiv.org/abs/2012.10638v1
• Date: Sat, 19 Dec 2020 09:32:13 GMT
• Title: Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems
• Authors: Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
• Abstract summary: We present a novel deep reinforcement learning method to learn constructions for vehicle routing problems. In particular, we propose a Multi-Decoder Attention Model (MDAM) to train multiple diverse policies. A customized beam search strategy is designed to fully exploit the diversity of MDAM.
• Score: 14.605192361813454
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel deep reinforcement learning method to learn construction heuristics for vehicle routing problems. In specific, we propose a Multi-Decoder Attention Model (MDAM) to train multiple diverse policies, which effectively increases the chance of finding good solutions compared with existing methods that train only one policy. A customized beam search strategy is designed to fully exploit the diversity of MDAM. In addition, we propose an Embedding Glimpse layer in MDAM based on the recursive nature of construction, which can improve the quality of each policy by providing more informative embeddings. Extensive experiments on six different routing problems show that our method significantly outperforms the state-of-the-art deep learning based models.

Related papers

• Progressive Multimodal Reasoning via Active Retrieval [64.74746997923967]
  Multi-step multimodal reasoning tasks pose significant challenges for large language models (MLLMs) We propose AR-MCTS, a universal framework designed to progressively improve the reasoning capabilities of MLLMs. We show that AR-MCTS can optimize sampling diversity and accuracy, yielding reliable multimodal reasoning.
  arXiv  Detail & Related papers  (2024-12-19T13:25:39Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Mirror Gradient: Towards Robust Multimodal Recommender Systems via Exploring Flat Local Minima [54.06000767038741]
  We analyze multimodal recommender systems from the novel perspective of flat local minima. We propose a concise yet effective gradient strategy called Mirror Gradient (MG) We find that the proposed MG can complement existing robust training methods and be easily extended to diverse advanced recommendation models.
  arXiv  Detail & Related papers  (2024-02-17T12:27:30Z)
• Delving into Multi-modal Multi-task Foundation Models for Road Scene Understanding: From Learning Paradigm Perspectives [56.2139730920855]
  We present a systematic analysis of MM-VUFMs specifically designed for road scenes. Our objective is to provide a comprehensive overview of common practices, referring to task-specific models, unified multi-modal models, unified multi-task models, and foundation model prompting techniques. We provide insights into key challenges and future trends, such as closed-loop driving systems, interpretability, embodied driving agents, and world models.
  arXiv  Detail & Related papers  (2024-02-05T12:47:09Z)
• Not All Tasks Are Equally Difficult: Multi-Task Deep Reinforcement Learning with Dynamic Depth Routing [26.44273671379482]
  Multi-task reinforcement learning endeavors to accomplish a set of different tasks with a single policy. This work presents a Dynamic Depth Routing (D2R) framework, which learns strategic skipping of certain intermediate modules, thereby flexibly choosing different numbers of modules for each task. In addition, we design an automatic route-balancing mechanism to encourage continued routing exploration for unmastered tasks without disturbing the routing of mastered ones.
  arXiv  Detail & Related papers  (2023-12-22T06:51:30Z)
• Efficient Domain Coverage for Vehicles with Second-Order Dynamics via Multi-Agent Reinforcement Learning [9.939081691797858]
  We present a reinforcement learning (RL) approach for the multi-agent efficient domain coverage problem involving agents with second-order dynamics. Our proposed network architecture includes the incorporation of LSTM and self-attention, which allows the trained policy to adapt to a variable number of agents.
  arXiv  Detail & Related papers  (2022-11-11T01:59:12Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  Multiobjective optimization (MOCO) problems can be found in many real-world applications. We develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. Our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiconditioned vehicle routing problem and multi knapsack problem in terms of solution quality, speed, and model efficiency.
  arXiv  Detail & Related papers  (2022-03-29T09:26:22Z)
• A review of approaches to modeling applied vehicle routing problems [77.34726150561087]
  We review the approaches for modeling vehicle routing problems. We formulate several criteria for evaluating modeling methods. We discuss several future research avenues in the field of modeling VRP domains.
  arXiv  Detail & Related papers  (2021-05-23T14:50:14Z)
• 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)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems. Traditional methods incur the dilemma between computational efficiency and solution quality. We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
  arXiv  Detail & Related papers  (2020-02-13T14:26:27Z)

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.