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