Joint Approach for Vehicle Routing Problems Based on Genetic Algorithm and Graph Convolutional Network

Dingding Qi, Yingjun Zhao, Zhengjun Wang, Wei Wang, Li Pi and Longyue Li ()
Additional contact information
Dingding Qi: Air Defense and Anti-Missile College, Air Force Engineering University, Xi’an 710043, China
Yingjun Zhao: Air Defense and Anti-Missile College, Air Force Engineering University, Xi’an 710043, China
Zhengjun Wang: School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
Wei Wang: Air Defense and Anti-Missile College, Air Force Engineering University, Xi’an 710043, China
Li Pi: Air Defense and Anti-Missile College, Air Force Engineering University, Xi’an 710043, China
Longyue Li: Air Defense and Anti-Missile College, Air Force Engineering University, Xi’an 710043, China

Mathematics, 2024, vol. 12, issue 19, 1-18

Abstract: The logistics demands of industries represented by e-commerce have experienced explosive growth in recent years. Vehicle path-planning plays a crucial role in optimization systems for logistics and distribution. A path-planning scheme suitable for an actual scenario is the key to reducing costs and improving service efficiency in logistics industries. In complex application scenarios, however, it is difficult for conventional heuristic algorithms to ensure the quality of solutions for vehicle routing problems. This study proposes a joint approach based on the genetic algorithm and graph convolutional network for solving the capacitated vehicle routing problem with multiple distribution centers. First, we use the heuristic method to modularize the complex environment and encode each module based on the constraint conditions. Next, the graph convolutional network is adopted for feature embedding for the graph representation of the vehicle routing problem, and multiple decoders are used to increase the diversity of the solution space. Meanwhile, the REINFORCE algorithm with a baseline is employed to train the model, ensuring quick returns of high-quality solutions. Moreover, the fitness function is calculated based on the solution to each module, and the genetic algorithm is employed to seek the optimal solution on a global scale. Finally, the effectiveness of the proposed framework is validated through experiments at different scales and comparisons with other algorithms. The experimental results show that, compared to the single decoder GCN-based solving method, the method proposed in this paper improves the solving success rate to 100% across 15 generated instances. The average path length obtained is only 11% of the optimal solution produced by the GCN-based multi-decoder method.

Keywords: vehicle routing problem; genetic algorithm; graph convolutional network; reinforcement learning; joint approach (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/19/3144/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/19/3144/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:19:p:3144-:d:1493913

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().