Abstract
Electronic waste (e-waste) collection presents a complex logistical challenge characterized by heterogeneous vehicle fleets, varying time windows, and significant travel time uncertainty. This paper proposes a Q-learning-based framework to optimize collection routes under these stochastic conditions. By integrating reinforcement learning with the Greedy Randomized Adaptive Search Procedure (GRASP), we develop a hyperheuristic (HH-Q) that dynamically selects search operators. Experimental results demonstrate that HH-Q significantly outperforms traditional metaheuristics, particularly as problem complexity increases, offering a robust solution for urban e-waste management.
Introduction
As global electronic consumption rises, the efficient collection of e-waste has become a critical environmental and logistical priority. Unlike standard delivery services, e-waste logistics must manage a "heterogeneous fleet" of vehicles with different capacities and costs, while adhering to "multiple time windows"—ranging from strict household pickup slots to flexible e-bin collection windows.
Central to this challenge is the inherent uncertainty of urban environments. Traffic congestion, weather, and accidents lead to stochastic travel times, rendering static route plans obsolete shortly after execution. This study addresses the Heterogeneous Vehicle Routing Problem with Multiple Time Windows and Stochastic Travel Time (HVRP-MTWSTT), aiming to maximize profit by balancing pickup revenue against operating costs, idle time penalties, and late-arrival fees.
Methodology
To solve the HVRP-MTWSTT, the research introduces two primary methods for embedding Q-learning into the Greedy Randomized Adaptive Search Procedure (GRASP):
1. GRASP-Q
In this approach, a pre-trained Q-table is utilized to establish a fixed, optimal sequence of local search operators (e.g., node swapping or re-routing). This sequence is applied during the improvement phase of the GRASP algorithm to refine initial solutions systematically.
2. HH-Q (Q-learning based Hyperheuristic)
HH-Q represents a more dynamic integration of reinforcement learning. The search process is modeled as a Markov Decision Process (MDP) where:
- State: Defined simply as the index of the previously applied heuristic operator.
- Action: The selection of the next search operator.
- Policy: A stochastic "Roulette Wheel" selection based on Q-values.
Traditional tabular Q-learning often struggles in routing optimization because agents can become trapped in "cycles" between two operators. The key innovation in HH-Q is the transition from a deterministic "greedy" policy to a stochastic one. This allows the agent to maintain exploration and escape local optima, leading to more diverse and effective solution paths.
Experimental Design
The framework was evaluated using a comprehensive benchmark suite derived from established deterministic models:
- Main Benchmark: 600 instances categorized by size (20, 50, and 100 nodes), split evenly between training and testing sets.
- Scalability Set: 14 additional instances (8 to 110 nodes) designed to test the model's ability to generalize to unseen graph structures and problem scales.
- Operational Parameters: The model accounted for two vehicle types with distinct capacities and a four-day collection horizon.
Key Results and Discussion
The experimental results highlight the advantages of adaptive learning in complex logistics:
- Scalability and Performance: While simple simulation-based methods (SimGRASP) are effective for small-scale problems (20 nodes), their performance degrades as complexity grows. In contrast, HH-Q outperformed SimGRASP by approximately 20% in terms of total profit for the largest (100-node) instances.
- Computational Efficiency: GRASP-Q proved highly efficient for large-scale operations. For 100-node instances, it achieved an average CPU time of 53.64 seconds, compared to 82.7 seconds for the standard GRASP with Path Relinking (GRASP-PR).
- Generalization: The scalability tests confirmed that the Q-table learned on smaller instances remains highly effective when applied to larger, unseen maps. HH-Q consistently outperformed all baseline methods for any problem size exceeding 30 nodes.
Conclusion and Future Work
This research demonstrates that a Q-learning-based hyperheuristic can effectively navigate the complexities of stochastic e-waste collection. By using a simple yet effective state definition and a stochastic selection policy, the HH-Q framework provides a scalable and adaptable solution for urban logistics.
Future research will explore moving beyond tabular Q-learning to Deep Reinforcement Learning (DRL), which would allow the inclusion of more complex state features such as real-time vehicle load and remaining time windows. Additionally, the authors plan to test the framework against real-world logistics data and incorporate dynamic pickup requests that emerge after routes have already commenced.
Summary updated