基于图注意力的烟草零售店监管路线优化研究

Research on Tobacco Retail Store Regulatory Route Optimization Algorithm Based on Graph Attention Mechanism for Node Selection

由于城市烟草零售店较为密集,传统路径规划算法求解最优监管路径将耗费大量的运算时间,在规定时间内无法保证运算效果。并且,现有方法较少考虑求解问题的网络特性及候选子集的可解释性。鉴于此,提出一种基于图注意力的节点选择及路径优化算法(GA-SGPO),迭代选择最优坐标节点子集,在子集上进行求解以减少计算时间。此外,通过计算节点间的结构相似性,降低子集样本稀疏性。实验数据包括东莞市4万家零售店的地理坐标。实验结果显示,所提出的GA-SGPO模型在保证求解精度的同时,求解时间平均提升48%。GA-SGPO算法可显著节省计算时间,更贴近实际应用场景。而注意力机制和节点相似度计算,可为最优节点选择提供可视化依据。

Since the tobacco retail stores in cities are dense,traditional path planning algorithms for solving the optimal supervision path will consume a lot of time,and cannot guarantee the effect within the specified time.In addition,existing methods seldom consider the network characteristics and the explainability of the candidate subset.This study proposes a graph attention-based node selection and path optimization algorithm(GA-SGPO),which iteratively selects the optimal coordinate node subset and performs calculation on the subset to reduce computation time.In addition,the structural similarity between nodes is calculated to reduce the sparsity of training samples.The experimental data includes the coordinates of 40,000 retail stores in Dongguan City.The experimental results show that the GA-SGPO model ensures the solution accuracy while the solution time is reduced by an average of 48%.The GA-SGPO can significantly save computational time and is closer to practical application scenarios.The attention mechanism and node similarity calculation can provide visualization basis for optimal node selection.