# Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach

arXiv: https://arxiv.org/abs/2002.05513 · HTML: https://mlsanity.com/paper/2002.05513/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

## Built on by (most cited first, 30 of 30)

- [Reinforcement Learning for Ridesharing: An Extended Survey](https://mlsanity.com/paper/2105.01099/) (2021)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges](https://mlsanity.com/paper/2407.00092/) (2024)
- [Diaformer: Automatic Diagnosis via Symptoms Sequence Generation](https://mlsanity.com/paper/2112.10433/) (2021)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone](https://mlsanity.com/paper/2112.12545/) (2021)
- [Solve routing problems with a residual edge-graph attention neural network](https://mlsanity.com/paper/2105.02730/) (2021)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation](https://mlsanity.com/paper/2207.09860/) (2022)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)
- [Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II](https://mlsanity.com/paper/2407.13113/) (2024)
- [Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey](https://mlsanity.com/paper/2108.04462/) (2021)
- [Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT](https://mlsanity.com/paper/2206.06618/) (2022)
- [A Bibliometric Analysis and Review on Reinforcement Learning for Transportation Applications](https://mlsanity.com/paper/2210.14524/) (2022)
- [Reinforcement Learning for Scalable Train Timetable Rescheduling with Graph Representation](https://mlsanity.com/paper/2401.06952/) (2024)
- [Biological Pathway Guided Gene Selection Through Collaborative Reinforcement Learning](https://mlsanity.com/paper/2505.24155/) (2025)
- [Multi-Agent Path Planning Using Deep Reinforcement Learning](https://mlsanity.com/paper/2110.01460/) (2021)
- [Deep Reinforcement Learning for Traveling Purchaser Problems](https://mlsanity.com/paper/2404.02476/) (2024)
- [Resource Governance in Networked Systems via Integrated Variational Autoencoders and Reinforcement Learning](https://mlsanity.com/paper/2410.23393/) (2024)
- [Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems](https://mlsanity.com/paper/2511.17435/) (2025)
- [CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for Solving Traveling Salesman Problem](https://mlsanity.com/paper/2312.15412/) (2023)
- [Electric Vehicle Routing Problem for Emergency Power Supply: Towards Telecom Base Station Relief](https://mlsanity.com/paper/2404.02448/) (2024)
- [Multi-Agent Environments for Vehicle Routing Problems](https://mlsanity.com/paper/2411.14411/) (2024)
- [Deep Reinforcement Learning for Drone Route Optimization in Post-Disaster Road Assessment](https://mlsanity.com/paper/2509.01886/) (2025)
- [A Unified Model for Multi-Task Drone Routing in Post-Disaster Road Assessment](https://mlsanity.com/paper/2510.21525/) (2025)
- [An End-to-End Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drones](https://mlsanity.com/paper/2511.05265/) (2025)
- [A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing](https://mlsanity.com/paper/2607.16875/) (2026)

## Abstract (arXiv)

Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are based on heuristic rules that require a large amount of computation time. With the current rapid increase of logistics demands, traditional methods incur the dilemma between computational efficiency and solution quality. To efficiently solve the problem, we propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training. Specifically, the vehicle routing problem is regarded as a vehicle tour generation process, and an encoder-decoder framework with attention layers is proposed to generate tours of multiple vehicles iteratively. Furthermore, a multi-agent reinforcement learning method with an unsupervised auxiliary network is developed for the model training. By evaluated on four synthetic networks with different scales, the results demonstrate that the proposed method consistently outperforms Google OR-Tools and traditional methods with little computation time. In addition, we validate the robustness of the well-trained model by varying the number of customers and the capacities of vehicles.