Combining decomposition and graph capsule network for multi-objective vehicle routing optimization

Article type: Research Article

Authors: Zhang, Haifei^{a; b} | Ge, Hongwei^{a; b; *} | Li, Ting^{a; b} | Zhou, Lujie^c | Su, Shuzhi^d | Tong, Yubing^e

Affiliations: [a] School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi, Jiangsu, China | [b] Key Laboratory of Advanced Process Control for Light Industry (Jiangnan University), Ministry of Education, Wuxi, Jiangsu, China | [c] College of Automobile and Transportation, Tianjin University of Technology and Education, Tianjin, China | [d] School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan, Anhui, China | [e] Medical Image Processing Group, Department of Radiology, University of Pennsylvania, Philadelphia, PA, USA

Correspondence: [*] Corresponding author: Hongwei Ge, School of Artificial Intelligence and Computer Science, Jiangnan University, 1800 Lihu Avenue, Wuxi, Jiangsu 214122, China. Tel.: +86 13951512160; E-mail: [email protected].

Abstract: In order to alleviate urban congestion, improve vehicle mobility, and improve logistics delivery efficiency, this paper establishes a practical multi-objective and multi constraint logistics delivery mathematical model based on graphs, and proposes a solution algorithm framework that combines decomposition strategy and deep reinforcement learning (DRL). Firstly, taking into account the actual multiple constraints such as customer distribution, vehicle load constraints, and time windows in urban logistics distribution regions, a multi constraint and multi-objective urban logistics distribution mathematical model was established with the goal of minimizing the total length, cost, and maximum makespan of urban logistics distribution paths. Secondly, based on the decomposition strategy, a DRL framework for optimizing urban logistics delivery paths based on Graph Capsule Network (G-Caps Net) was designed. This framework takes the node information of VRP as input in the form of a 2D graph, modifies the graph attention capsule network by considering multi-layer features, edge information, and residual connections between layers in the graph structure, and replaces probability calculation with the module length of the capsule vector as output. Then, the baseline REINFORCE algorithm with rollout is used for network training, and a 2-opt local search strategy and sampling search strategy are used to improve the quality of the solution. Finally, the performance of the proposed method was evaluated on standard examples of problems of different scales. The experimental results showed that the constructed model and solution framework can improve logistics delivery efficiency. This method achieved the best comprehensive performance, surpassing the most advanced distress methods, and has great potential in practical engineering.

Keywords: Urban logistics distribution, multi objective optimization, deep reinforcement learning, decomposition strategy, graph capsule network, attention mechanism

DOI: 10.3233/IDA-230480

Journal: Intelligent Data Analysis, vol. Pre-press, no. Pre-press, pp. 1-28, 2024