CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems

• URL: http://arxiv.org/abs/2501.02977v2
• Date: Tue, 04 Feb 2025 09:21:37 GMT
• Title: CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems
• Authors: Chuanbo Hua, Federico Berto, Jiwoo Son, Seunghyun Kang, Changhyun Kwon, Jinkyoo Park,
• Abstract summary: 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.
• Score: 15.136899433821894
• License:
• Abstract: The profiled vehicle routing problem (PVRP) is a generalization of the heterogeneous capacitated vehicle routing problem (HCVRP) in which the objective is to optimize the routes of vehicles to serve client demands subject to different vehicle profiles, with each having a preference or constraint on a per-client basis. While existing learning methods have shown promise for solving the HCVRP in real-time, no learning method exists to solve the more practical and challenging PVRP. In this paper, we propose a Collaborative Attention Model with Profiles (CAMP), a novel approach that learns efficient solvers for PVRP using multi-agent reinforcement learning. CAMP employs a specialized attention-based encoder architecture to embed profiled client embeddings in parallel for each vehicle profile. We design a communication layer between agents for collaborative decision-making across profiled embeddings at each decoding step and a batched pointer mechanism to attend to the profiled embeddings to evaluate the likelihood of the next actions. We evaluate CAMP on two variants of PVRPs: PVRP with preferences, which explicitly influence the reward function, and PVRP with zone constraints with different numbers of agents and clients, demonstrating that our learned solvers achieve competitive results compared to both classical state-of-the-art neural multi-agent models in terms of solution quality and computational efficiency. We make our code openly available at https://github.com/ai4co/camp.

Related papers

• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications. We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately. By introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• Exact algorithms and heuristics for capacitated covering salesman problems [0.0]
  This paper introduces the Capacitated Covering Salesman Problem (CCSP) The objective is to service customers through a fleet of vehicles in a depot, minimizing the total distance traversed by the vehicles. optimization methodologies are proposed for the CCSP based on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Routing) metaheuristic.
  arXiv  Detail & Related papers  (2024-03-03T07:50:29Z)
• Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy [24.91781032046481]
  Many neural construction methods for Vehicle Routing Problems(VRPs) focus on synthetic problem instances with specified node distributions and limited scales. We design an auxiliary policy that learns from the local transferable topological features, named local policy, and integrate it with a typical construction policy to form an ensemble policy. With joint training, the aggregated policies perform cooperatively and complementarily to boost generalization.
  arXiv  Detail & Related papers  (2023-08-27T13:22:50Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem [13.389057146418056]
  Vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed) We propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step.
  arXiv  Detail & Related papers  (2021-10-06T10:05:19Z)
• 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)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• Vehicular Cooperative Perception Through Action Branching and Federated Reinforcement Learning [101.64598586454571]
  A novel framework is proposed to allow reinforcement learning-based vehicular association, resource block (RB) allocation, and content selection of cooperative perception messages (CPMs) A federated RL approach is introduced in order to speed up the training process across vehicles. Results show that federated RL improves the training process, where better policies can be achieved within the same amount of time compared to the non-federated approach.
  arXiv  Detail & Related papers  (2020-12-07T02:09:15Z)
• 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)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.