Source-linked AI summary
Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
Ke Zhang, Meng Li, Zhengchao Zhang, Xi Lin, Fang He
TL;DR
MVRPSTW is an NP-hard multi-vehicle logistics-routing problem arising amid rapidly growing demand and requiring suitable methods. The paper proposes a Multi-Agent Attention Model trained with multi-agent reinforcement learning, reporting better solution quality and efficiency than Google OR-Tools and traditional methods with little computation time, while identifying real-time requests and stochastic traffic as future directions.
Problem
MVRPSTW is an NP-hard logistics-routing problem whose multiple vehicles require suitable methodological development amid rapidly growing logistics demand.
Method
The Multi-Agent Attention Model uses a reinforcement-learning architecture for vehicle-tour generation, with vehicle interactions and customers represented in the model.
Results
MAAM consistently outperforms Google OR-Tools and traditional methods with negligible computation time, achieving superior solution quality and efficiency.
Takeaways & Limitations
The reported combination of solution quality and efficiency supports using MAAM for routing after lengthy offline training.
Takeaways & Limitations
Future research should address real-time requests and stochastic traffic conditions.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
MVRPSTW is an NP-hard urban logistics problem made more difficult by growing delivery demand, multiple vehicles, soft time windows, and the need for fast, high-quality solutions. The paper proposes MAAM, a multi-agent reinforcement learning architecture using attention-based route generation and reports stronger performance than OR-Tools and classical heuristics.
- Motivation: Growing logistics demand makes fast and reliable routing increasingly important for large-scale applications.Heuristic algorithms struggle to solve high-demand scenarios quickly enough to support large-scale systems.
- Problem setting: MVRPSTW is an NP-hard vehicle-routing problem in which multiple vehicles serve customers under capacity and soft time-window constraints.Soft time-window violations are allowed but incur penalties such as customer compensation or negative evaluations.
- Prior methods: Existing heuristics include iterated local search, genetic algorithms, tabu search, and adaptive large neighborhood search, but fast and reliable solutions remain challenging.Mixed-integer programming is also poorly suited because soft-window penalties introduce nonlinearity requiring many binary variables.
- Research gap: Few machine-learning studies address VRPs with multiple vehicles and soft time windows simultaneously.The paper identifies multi-agent coordination, soft-window integration, scalability, and acceptable computational effort as key difficulties.
- Proposed approach: MAAM uses an encoder-decoder with multi-head attention to iteratively develop vehicle routes and a multi-agent reinforcement learning method based on multiple-vehicle context embeddings.The model is trained offline and can be deployed on new problems without further training.
- Results: Experiments report significantly better performance than Google OR-Tools and classical MVRPSTW heuristics, while varying customer numbers and vehicle capacities does not require retraining.The framework is evaluated through numerical experiments and robustness case studies.
2 PROBLEM DEFINITION
The MVRPSTW assigns capacitated vehicles to serve each customer once through disjoint depot-to-depot routes, minimizing travel cost plus soft time-window penalties. It assumes Euclidean distances, identical vehicle speeds, and no vehicle overload.
- A problem instance specifies the depot, customer coordinates, demands, time windows, and early- and late-arrival penalty coefficients.
- The problem assigns M capacitated vehicles to serve all customer requests and find a minimum-cost set of routes.
- Each vehicle follows a disjoint route that starts and ends at depot v0, while each customer is served once within its time window.
- Distances are Euclidean, vehicle speeds are identical, and remaining capacity must stay positive so vehicles cannot be overloaded.The model uses one unit of travel time per unit of distance.
- Routes are evaluated by total Euclidean travel cost plus a penalty based on customer arrival times.The arrival-time penalty is piecewise linear and distinguishes early from late service.
3 MULTI-AGENT ATTENTION MODEL
The Multi-Agent Attention Model (MAAM) treats MVRPSTW solution construction as sequential multi-vehicle route generation using an attention-based encoder-decoder and reinforcement learning. Vehicles act as agents that iteratively select customers under routing constraints, while training uses policy gradients with a baseline.
- Overview: MAAM is an attention-based encoder-decoder that regards MVRPSTW as a dynamic route-generation problem represented by sequential decisions.The encoder embeds depot and customer information, while the decoder generates vehicle tours iteratively.
- Overview: The decoder produces one input customer for each vehicle at each timestep and continues until all customers have been served.It uses encoder outputs, constraint masks, and context embeddings to select customers.
- Training Method: Unlike instance-specific policy training, the method is intended to perform on randomly generated instances from given distributions and produce solutions without retraining each new instance.The paper describes this as enabling high-quality route generation in a short time after offline training.
- Encoder Framework: Multi-head self-attention augments customer representations by combining information from different representation subspaces and positions.The attention mechanism is interpreted as weighted message passing between customers, with weights determined by query-key compatibility.
- Decoder Framework: Vehicle agents use current locations, remaining capacities, visited-customer information, and shared context to choose feasible next customers.Customers already visited or whose demand exceeds remaining capacity are masked from selection.
- Training Method: The model samples solutions during training, uses greedy decoding during testing, and optimizes a policy-gradient estimator against a greedy rollout baseline.The baseline is replaced only when the current model improves significantly under a paired t-test.
4 CASE STUDY
The case study evaluates MAAM against heuristic baselines and Google OR-Tools on synthetic MVRPSTW instances of several scales. MAAM achieves strong solution quality with low computation time, while trained models remain robust to moderate changes in problem instances.
- Baselines: MAAM is compared directly with two classical heuristic methods and the commonly used Google OR-Tools solver.The classical baselines include genetic algorithms and iterated local search with specified population or iteration settings.
- Comparative results: MAAM achieves the best performance among the baselines in both solution quality and computation efficiency across the reported scenarios.On small-scale problems, methods obtain similar results, whereas genetic algorithms perform worse as problem size grows and OR-Tools is second to MAAM.
- Comparative results: ILS fails to find even sub-optimal solutions on large-scale problems, whereas MAAM produces high-quality solutions within only a few seconds.The reported comparison identifies a substantial scalability difference between the learned model and iterative heuristics.
- Computational efficiency: MAAM computation time remains almost unchanged as problem size increases, while heuristic and OR-Tools runtimes increase exponentially.The framework reuses information learned offline, whereas classical heuristics re-solve each instance from the beginning.
- Robustness: Well-trained MAAM models consistently outperform OR-Tools and ILS1 in solution quality and computation time when customer numbers or vehicle capacities vary moderately.The model also adapts when customer demands or locations change, including demand cancellations and adjusted vehicle capacity.
5 CONCLUSIONS
The multi-agent attention model (MAAM) addresses MVRPSTW and consistently outperforms Google OR-Tools and traditional methods with negligible computation time. The trained model also shows robustness to varying customer numbers and vehicle capacities, while future work targets broader problem settings and online conditions.
- MAAM is proposed as a reinforcement learning algorithm for solving MVRPSTW.
- MAAM consistently outperforms Google OR-Tools and traditional methods with negligible computation time on four synthetic networks of different scales.
- The method achieves superior solution quality and efficiency compared with time-consuming classical heuristics.
- The well-trained model is robust to fluctuations in customer numbers and vehicle capacities.
- This robustness extends the model's applicability to more realistic cases.
- Future research includes very large-scale problems, additional vehicle-routing settings, and online problems with real-time requests and stochastic traffic conditions.