Abstract: 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.
Introduction
In the rapidly evolving landscape of urban logistics, the Multi-Vehicle Routing Problem with Soft Time Windows (MVRPSTW) stands as a critical challenge. Logistics providers must manage fleets of vehicles to deliver goods to diverse customer locations, each with specific temporal requirements. Traditional approaches often struggle to balance the need for high-quality solutions with the necessity for real-time computational speed. Researchers from Tsinghua University have addressed this gap by developing the Multi-Agent Attention Model (MAAM), a deep reinforcement learning framework designed to solve complex routing problems in seconds.
Problem Definition: Soft Time Windows
The core of the MVRPSTW involves a fleet of $M$ vehicles starting from a central depot to serve a set of customers. Each customer $i$ is defined by a coordinate $x_i$, a demand $d_i$, and a preferred time window $[e_i, l_i]$.
Unlike "hard" time windows, where deliveries outside the specified interval are strictly forbidden, "soft" time windows allow for flexibility at the cost of a mathematical penalty. This approach more accurately reflects real-world scenarios where minor delays are acceptable but undesirable. As illustrated in the figure below, the penalty cost is zero when a vehicle arrives within the window $[e_i, l_i]$. Arriving before $e_i$ incurs an early penalty (coefficient $\alpha_i$), while arriving after $l_i$ incurs a late penalty (coefficient $\beta_i$).
The Multi-Agent Attention Model (MAAM)
The proposed MAAM architecture treats the routing problem as a sequential decision-making process. Its primary innovation lies in combining an encoder-decoder framework with multi-agent coordination:
- Encoder-Decoder Framework: The encoder creates high-dimensional embeddings of the depot and customers, capturing their spatial and temporal characteristics. The decoder then iteratively selects the next customer for each vehicle to visit.
- Multi-Head Attention (MHA): This mechanism allows the model to dynamically "attend" to different parts of the network, understanding the complex relationships between customer locations, remaining demands, and time windows.
- Multi-Agent Coordination: Each vehicle is treated as an individual agent. By utilizing a "multiple vehicles context embedding," the model ensures that vehicles account for the current status (location and remaining capacity) of other agents in the fleet, preventing redundant visits and optimizing the global objective.
- Training via REINFORCE: The model is trained offline using a policy gradient algorithm. Once trained, the model can generate near-optimal routes "instantly" for new problem instances without requiring further optimization.
Experimental Results and Insights
The researchers evaluated MAAM against industry standards, including Google OR-Tools, Genetic Algorithms (GA), and Iterated Local Search (ILS), across various scales (20 to 150 customers).
Efficiency and Scalability
One of the most significant advantages of MAAM is its computational speed. For a problem involving 100 customers, MAAM generated solutions in approximately 5 seconds. In contrast, ILS required over an hour, and GA took over five hours to reach a solution. This makes MAAM uniquely suited for real-time logistics applications where delivery demands change rapidly.
Solution Quality
In large-scale scenarios (100-150 customers), MAAM consistently achieved lower total costs than the benchmark methods. While Google OR-Tools remained highly competitive in minimizing raw travel distance, MAAM proved superior at balancing distance with the complex non-linear penalties associated with soft time windows.
Robustness
The model demonstrated remarkable "zero-shot" robustness. A model trained on 50 customers could effectively solve problems with 40 or 48 customers by introducing "virtual" customers with zero demand. It also handled variations in vehicle capacity without needing retraining, highlighting its practical utility in dynamic fleet management.
Conclusion
The Multi-Agent Attention Model represents a significant step forward in solving vehicle routing problems. By learning heuristics through deep reinforcement learning, MAAM bypasses the computational bottlenecks of traditional solvers while maintaining high solution quality. Future research will focus on adapting the model for heterogeneous fleets and integrating real-world road network data to further enhance its applicability in urban logistics.
Summary updated