关键词: 异构带容量的车辆路径问题, 分层解码器模型, 路由分配解码器, 序列构建解码器, 注意力协作机制

Abstract: Existing deep reinforcement learning (DRL) methods for solving the capacitated vehicle routing problem (CVRP) are mainly designed for homogeneous fleets, where all vehicles have the same capacity. However, these DRL methods perform poorly when dealing with more realistic heterogeneous fleets. Aiming to minimize the route length, a novel DRL model is proposed to solve the heterogeneous capacitated vehicle routing problem (HCVRP) with different capacity constraints. Specifically, a hierarchical decoder model (HDM) consisting of two types of decoders is proposed: a routing  allocation decoder (RAD) and a sequence construction decoder (SCD). The RAD assigns nodes to appropriate vehicles to form several groups, while the SCD constructs the order of nodes within each group to minimize the total route length. In addition, an attention collaboration mechanism (ACM) is designed to promote information sharing among SCDs, optimizing the node order of each group and thus improving the quality of the overall solution. Experimental results show that the HDM model outperforms existing state-of-the-art deep learning methods and can provide solutions comparable to traditional optimization solvers within a reasonable time.

Key words: heterogeneous capacitated vehicle routing problem, hierarchical decoder model, routing allocation decoder, sequence construction decoder, attention collaboration mechanism