Optimizing Heterogeneous Capacitated Vehicle Routing with Linformer and Multi-Relationship Decoding: A Deep Reinforcement Learning Approach

Abstract

The heterogeneous capacitated vehicle routing problem (HCVRP) presents a pivotal challenge in urban grocery delivery, requiring the optimization of routes for a diverse fleet of vehicles with varying capacities and speeds to meet diverse customer demands efficiently. Traditional approaches, particularly exact and heuristic algorithms, encounter significant computational hurdles when scaled to larger problem sizes. To address these challenges, this study introduces a new neural network architecture that incorporates advanced attention mechanisms specifically tailored for the HCVRP. Our approach features two main innovations: incorporation of Linformer, to substantially reduce computational demands, and a multi-relational node selection decoder, designed to enhance the accuracy and efficiency of decision-making processes. Through extensive experiments, our deep reinforcement learning (DRL) framework consistently surpasses both traditional heuristics and existing DRL models in delivering superior solution quality and computational efficiency across diverse problem scales and objectives. This research underscores the transformative potential of integrating cutting-edge machine learning techniques to refine and expedite solutions in complex transportation and logistics operations.