Deep reinforcement learning approach to solving clustered vehicle routing problems

• Interactive MDP formulation models the constructive decision process for CluVRPs. • Cluster-aware attention captures customer-cluster interactions for richer representations. • Dual decoders jointly optimize inter-cluster sequencing and intra-cluster routing. • DRL approach outperforms existing CluVRP methods across diverse variants and scenarios. Clustered vehicle routing problems (CluVRPs) represent a complex class of combinatorial optimization problems with significant real-world relevance. They extend classic VRPs by introducing pre-specified customer clusters and requiring effective routing both between clusters and within each cluster. While numerous deep learning approaches have been developed to address the standard VRP, research on CluVRPs remains relatively limited, presenting opportunities and challenges for advancing solutions to more practical VRPs with cluster-related constraints. This paper offers a deep reinforcement learning (DRL) approach to solving CluVRPs. We propose a cluster-aware attention module in the encoder, along with inter-cluster and intra-cluster decoders to specialize the constructive policies within and between clusters. Symmetrical data augmentation is adopted in the training to improve the performance. Empirical results in different CluVRP variants manifest that the DRL method outperforms existing approaches, consistently offering advantages for various instances.