The split delivery vehicle routing optimization with the residual graph convolutional network and deep reinforcement learning
The split delivery vehicle routing problem(SDVRP)occurred in most delivery tasks is of great significance.Efficient optimization algorithms can maximize loading space and reduce distribution cost.To improve the performance of the SDVRP optimization algorithms,we propose a deep reinforcement learning algorithm based on the residual graph convolutional network and multi-head attention to construct the sequence incrementally.Specifically,we firstly build the Markov decision process model for the SDVRP,such as the environment state,action space and transition function of generating sequence.Secondly,an encoder-decoder network is proposed to represent the stochastic policy to select the node.The residual graph convolutional network takes the relationship between nodes and node features into account to generate powerful embeddings.The attention mechanism is utilized to execute the decoding task based on the embeddings fused the remaining vehicle capacity and customer demands,which can produce multiple solutions for any instance.Thirdly,the parameters of the proposed model are updated by the improved REINFORCE algorithm based on the average baseline.Through experiments using the synthetical datasets with variable problem scales,standard SDVRP benchmark and Jingdong logistics tasks,the results validate the performance of the proposed algorithm.
国家科技期刊平台
NSTL
万方数据
