دورية أكاديمية
BiGNN: Bipartite graph neural network with attention mechanism for solving multiple traveling salesman problems in urban logistics
العنوان: | BiGNN: Bipartite graph neural network with attention mechanism for solving multiple traveling salesman problems in urban logistics |
---|---|
المؤلفون: | Haojian Liang, Shaohua Wang, Huilai Li, Liang Zhou, Xueyan Zhang, Shaowen Wang |
المصدر: | International Journal of Applied Earth Observations and Geoinformation, Vol 129, Iss , Pp 103863- (2024) |
بيانات النشر: | Elsevier, 2024. |
سنة النشر: | 2024 |
المجموعة: | LCC:Physical geography LCC:Environmental sciences |
مصطلحات موضوعية: | Bipartite graph, Graph neural network, Attention mechanism, Multiple traveling salesman problem, Branch-and-bound, Physical geography, GB3-5030, Environmental sciences, GE1-350 |
الوصف: | The multiple traveling salesman problems (MTSP), which arise from real world problems, are essential in urban logistics. Variations such as MinMax-MTSP and Bounded-MTSP aim to distribute workload evenly among salesmen and impose constraints on visited cities, respectively. Branch-and-bound (B&B) provides an exact algorithm solution for these problems. The Learn to Branch (L2B) approach guides branch node selection through deep learning. In this study, we utilize mathematical modeling of Bipartite Graph Neural Network (BiGNN) and an attention mechanism to support B&B in exploring solution spaces through imitation learning. The problems are framed to formulate mixed integer linear programming, which is different from conventional algorithms. It is proposed that a bipartite graph network approach makes a feature representation by setting a structure of constraints and variables. Experimental results showed that our model can generate more accurate solutions than three benchmark models. The BiGNN model can effectively learn the strong branch strategy, which reduces solution time by replacing complex calculations with fast approximations. Additionally, the small-scale instances model can be applied to larger-scale ones. |
نوع الوثيقة: | article |
وصف الملف: | electronic resource |
اللغة: | English |
تدمد: | 1569-8432 |
Relation: | http://www.sciencedirect.com/science/article/pii/S1569843224002176; https://doaj.org/toc/1569-8432 |
DOI: | 10.1016/j.jag.2024.103863 |
URL الوصول: | https://doaj.org/article/edc7fc9021f84b0485bea376f0b6294e |
رقم الأكسشن: | edsdoj.7fc9021f84b0485bea376f0b6294e |
قاعدة البيانات: | Directory of Open Access Journals |
تدمد: | 15698432 |
---|---|
DOI: | 10.1016/j.jag.2024.103863 |