Deep Reinforcement Learning for the Heterogeneous Capacitated Vehicle Routing Problem

Yuanyumeng Zhu

Co-Presenters: Individual Presentation

College: College of Business and Public Management

Major: Accounting

Faculty Research Mentor: Dan Liu

Abstract:

Abstract:The Heterogeneous Capacitated Vehicle Routing Problem (HCVRP) is a significant area of research invehicle routing optimization, particularly in supply chains with fluctuating demands and complextransportation conditions, such as fresh food delivery and pharmaceutical logistics. Effectivelyaddressing HCVRP can improve delivery efficiency, reduce costs, lower carbon emissions, andenhance customer satisfaction. However, traditional optimization methods often lack the flexibility andcomputational efficiency needed to manage the dynamic and complex nature of HCVRP. This studypresents a novel deep learning-based model that leverages modern optimization techniques to enhancerouting efficiency and address complex dynamic constraints.The study introduces two key innovations. First, a deep reinforcement learning (DRL) framework isdeveloped to tackle dynamic demands and diverse constraints, such as vehicle capacities, speeds, andorder priorities. By continuously interacting with a simulated environment, the model learns optimalrouting strategies, improving adaptability to changing demands and conditions. A hierarchical DRLarchitecture further enhances performance by decomposing tasks into global route planning and localdynamic adjustments, reducing training and inference times. Second, the study integrates the Linformerattention mechanism with multi-relational modeling to improve computational efficiency for high-dimensional problems. By incorporating a multi-relational node selection decoder, the modeleffectively unifies constraints such as vehicle capacities, service time windows, order priorities, anddynamic demands. This approach captures intricate relationships within delivery networks, improvingthe reliability and practical applicability of routing solutions, particularly in dynamic and complexlogistics scenarios.This study validates the Deep Reinforcement Learning (DRL) framework for solving theHeterogeneous Capacitated Vehicle Routing Problem (HCVRP) using a simulated environment withfixed constraints like vehicle capacity, time windows, and order priorities. Training involveshierarchical global planning and local adjustments to enhance adaptability. The model's performance isevaluated on fixed constraints for routing efficiency, computational efficiency, constraint satisfaction,and responsiveness. Comparative analysis by removing key components (e.g., Linformer or multi-relational decoder) highlights each innovation's contribution. The framework demonstratesoptimization effectiveness and practical value in real-world logistics.

Keywords: Heterogeneous Capacitated Vehicle Routing Problem, Deep Reinforcement Learning, AttentionMechanism, Linformer, Multi-Relational Decoder, Supply Chain Resilience