Abstract
Real-world logistics often involve complex temporal constraints where customers are available only during specific, disjoint intervals. This paper addresses the Vehicle Routing Problem with Multiple Time Windows (VRPMTW) by introducing RL-AVNS, a hybrid optimization framework. RL-AVNS integrates a Transformer-based policy network with Variable Neighborhood Search (VNS) to dynamically select search operators based on the current route state. By incorporating a runtime-aware reward function and a novel temporal fitness metric for route perturbation, the proposed method achieves significant improvements in both solution quality and computational efficiency compared to traditional adaptive heuristics.
Introduction
The Vehicle Routing Problem (VRP) is a foundational challenge in combinatorial optimization. However, the standard formulation often fails to capture the nuances of urban logistics, such as the restocking of unmanned vending machines in restricted-access environments like schools or office complexes. In these scenarios, a customer may have multiple distinct windows of availability (e.g., a morning window and an evening window), leading to the Vehicle Routing Problem with Multiple Time Windows (VRPMTW).
As the number of time windows increases, the search space expands exponentially. Traditional exact solvers, such as Gurobi, struggle to find even feasible solutions for small-scale instances (N=20) within reasonable time limits. While metaheuristics like Variable Neighborhood Search (VNS) are more scalable, they often rely on rigid rules or simple historical averages to select search operators, leading to inefficient exploration of the solution space. This paper proposes RL-AVNS, a reinforcement learning-driven approach that learns to navigate these complex constraints intelligently.
Methodology
RL-Based Operator Selection
The core of RL-AVNS is a Transformer-based policy network that replaces the fixed selection logic of traditional Adaptive VNS (AVNS). At each iteration, the RL agent observes the current state of the route—encoded using multi-head attention to capture spatial and temporal dependencies between nodes—and selects the most appropriate local search operator (e.g., 2-opt, swap, or relocate).
Unlike traditional AVNS, which weights operators based on their historical success, the RL agent evaluates the contextual utility of an operator. This prevents the algorithm from becoming stuck using computationally expensive operators in late-stage search phases where marginal gains are minimal.
Runtime-Aware Training
The agent is trained using Proximal Policy Optimization (PPO). To ensure the algorithm remains practical for real-time logistics, the authors implemented a runtime-aware reward function. This function explicitly penalizes excessive computational time, incentivizing the agent to balance the trade-off between route shortening and CPU consumption.
Temporal Fitness for Shaking
VNS algorithms utilize a "shaking" phase to escape local optima by perturbing the current solution. RL-AVNS introduces a custom temporal fitness metric to guide this process. By calculating the "temporal flexibility" of each customer—measuring how much a visit can be shifted within its available windows—the algorithm selectively disrupts nodes with high flexibility. This strategy preserves the fragile, highly constrained segments of the route while re-optimizing the more adaptable portions.
Experimental Evaluation
Dataset Generation
Due to the lack of standard VRPMTW benchmarks, the authors generated synthetic datasets reflecting real-world patterns. These datasets feature clustered time windows (e.g., 06:00-09:00, 11:00-14:00, and 17:00-20:00) rather than uniformly random intervals. Testing was conducted on instances ranging from 10 to 100 nodes, with varying numbers of time windows per customer.
Performance Results
RL-AVNS demonstrated superior performance across several metrics:
- Efficiency: The method reduced computational time by 65% to 77% compared to traditional AVNS.
- Solution Quality: RL-AVNS achieved route length reductions between 3.3% and 14.5% over AVNS.
- Generalization: An agent trained on 50-node instances with three time windows successfully generalized to 100-node instances and mixed-window scenarios without retraining, showcasing the robustness of the Transformer-based encoding.
- Comparison to Neural Solvers: In single-window benchmarks, RL-AVNS outperformed state-of-the-art neural constructive solvers like JAMPR and AM in both route quality and solving speed.
Discussion and Conclusion
The results highlight a critical flaw in traditional adaptive heuristics: historical performance is often a "trap" that leads to computational inefficiency in the final stages of optimization. By using a state-aware RL agent, RL-AVNS avoids this pitfall. Furthermore, the failure of exact solvers at N=20 underscores the necessity of high-performance heuristics for VRPMTW.
While RL-AVNS shows a slight performance gap compared to highly specialized C++ solvers like LKH3 in single-window scenarios—largely due to the overhead of Python-based heuristic operators—its flexibility and speed in multi-window environments make it a powerful tool for modern logistics. Future work will focus on optimizing the implementation and extending the framework to other VRP variants with complex constraints.
Summary updated