Accelerating Quadratic Unconstrained Binary Optimization Solution for Logistics Distribution Routing Problem with Graph Attention Network
Yanyu Zhang, Yanhao Li, Hengji Li, Feixiang Jiao, Zhiming Zhang, Xibeng Zhang · 2024
The logistics vehicle routing optimization problem is a widely discussed combinatorial optimization(CO) problem with broad application prospects. Graph Neural Network(GNN) is extensively used in this context due to their suitability for the graph structure of transportation networks. However, existing methods lack interpretability for CO problem models and do not offer a generalized and unified modeling process. Additionally, traditional neural networks face shortcomings when handling dynamic graphs and directed graph problems, with suboptimal node information aggregation capabilities. Therefore, designing a method for the logistics vehicle routing optimization problem that features a unified and concise problem model, rapid solution speed, and accurate results is crucial. This paper proposes a framework for accelerating the solution of the logistics vehicle routing optimization problem using a Graph Attention Network (GAT) based on quadratic unconstrained binary op-timization(QUBO) modeling methods. The framework aims to abstract practical problems into QUBO form, and it constructs a concise and unified model for the problem while utilizing Multi-Head Attention mechanisms to aggregate node information in graph-structured problems. These are then solved using GNN. Comparing this method with actual results and traditional GNN solving methods demonstrates that, in cases with a higher number of nodes, this method has certain advantages in solution speed and accuracy.