An Efficient Encoder-Decoder Network for the Capacitated Vehicle Routing Problem

The capacitated vehicle routing problem (CVRP) is of great importance to intelligent transportation systems. Recently, deep reinforcement learning (DRL) approaches have shown great potential in solving the CVRP. Specifically, encoder-decoder frameworks are trained by reinforcement learning with different schemes to produce routing decisions. However, these frameworks usually conduct embedding with a set of separate node information without the full graph features of a CVRP and learn only one policy to generate the solution. In this paper, we develop an efficient encoder-decoder network, termed the residual graph convolutional encoder and multiple attention-based decoders (RGCMA), which is trained by a rollout baseline reinforcement learning method on the CVRP. The encoder generates as powerful as possible node representations while being dedicated to aggregating neighborhood features by a fitted dense residual edge and node feature updating block. Furthermore, compared to a single decoder strategy, our multiple decoder mechanism incrementally constructs multiple solutions for a CVRP instance to improve the candidate solution’s quality, by focusing on the diversified solution space which is beneficial for exploration. Extensive experiments demonstrate that the proposed RGCMA performs competitively with the state-of-the-art methods on the CVRP, and has an especially big advantage on large-scale tasks when a pretrained model is used on small-scale data