Q-Learning Based Framework for Solving the Stochastic E-waste Collection Problem

Dang Viet Anh Nguyen, Aldy Gunawan, Mustafa Misir, Pieter Vansteenwegen

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

Abstract

Electrical and Electronic Equipment (EEE) has evolved into a gateway for accessing technological innovations. However, EEE imposes substantial pressure on the environment due to the shortened life cycles. E-waste encompasses discarded EEE and its components which are no longer in use. This study focuses on the e-waste collection problem and models it as a Vehicle Routing Problem with a heterogeneous fleet and a multi-period planning problem with time windows as well as stochastic travel times. Two different Q-learning-based methods are designed to enhance the search procedure for finding solutions. The first method involves utilizing the state-action value to determine the order of multiple improvement operators within the GRASP framework. The second one involves a hyperheuristic that extracts a stochastic policy to select heuristic operators during the search. Computational experiments demonstrate that both methods perform competitively with state-of-the-art methods in newly-generated small-sized instances, while the performance gap widens as the size of the problem instances increases.
BibTeX
@inproceedings{nguyen2024q,
  author = {Dang Viet Anh Nguyen and Aldy Gunawan and Mustafa Misir and Pieter Vansteenwegen},
  title = {{Q-Learning Based Framework for Solving the Stochastic E-waste Collection Problem}},
  booktitle = {EvoStar},
  year = {2024},
  doi = {10.1007/978-3-031-57712-3\_4},
}
Figure