{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T05:46:17Z","timestamp":1782366377547,"version":"3.54.5"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T00:00:00Z","timestamp":1775174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T00:00:00Z","timestamp":1779840000000},"content-version":"vor","delay-in-days":54,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Artif Intell Rev"],"DOI":"10.1007\/s10462-026-11544-3","type":"journal-article","created":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T13:46:35Z","timestamp":1775223995000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Garnet: integrating random walk encoding and graph rewiring for routing optimization"],"prefix":"10.1007","volume":"59","author":[{"given":"Abdelaadim","family":"Khriss","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aissa Kerkour","family":"Elmiad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammed","family":"Badaoui","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toufik","family":"Mzili","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hamzah A.","family":"Alkhazaleh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,3]]},"reference":[{"issue":"10","key":"11544_CR1","doi-asserted-by":"publisher","first-page":"7207","DOI":"10.1007\/s13369-024-09369-9","volume":"50","author":"M Abid","year":"2025","unstructured":"Abid M, El Kafhali S, Amzil A, Hanini M (2025) Optimization of uav flight paths in multi-uav networks for efficient data collection. Arab J Sci Eng 50(10):7207\u20137232","journal-title":"Arab J Sci Eng"},{"key":"11544_CR2","unstructured":"Alon U, Yahav E (2020) On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205"},{"key":"11544_CR3","unstructured":"Arnaiz-Rodr\u00edguez A, Begga A, Escolano F, Oliver N (2022) Diffwire: Inductive graph rewiring via the lov$$\\backslash $$\u2019asz bound"},{"key":"11544_CR4","unstructured":"Arroyo \u00c1, Gravina A, Gutteridge B, Barbero F, Gallicchio C, Dong X, Bronstein M, Vandergheynst P (2025) On vanishing gradients, over-smoothing, and over-squashing in gnns: bridging recurrent and graph learning. arXiv preprint arXiv:2502.10818"},{"key":"11544_CR5","unstructured":"Barrett TD, Parsonson CW, Laterre A (2022) Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv preprint arXiv:2205.14105"},{"key":"11544_CR6","unstructured":"Bello I, Pham H, Le QV, Norouzi M, Bengio S (2016) Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940"},{"key":"11544_CR8","doi-asserted-by":"crossref","unstructured":"Chen D, Lin Y, Li W, Li P, Zhou J, Sun X (2020) Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In: Proceedings of the AAAI conference on artificial intelligence, vol. 34, pp 3438\u20133445","DOI":"10.1609\/aaai.v34i04.5747"},{"key":"11544_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2025.107132","volume":"185","author":"Q Cheng","year":"2025","unstructured":"Cheng Q, Long L, Xu J, Zhang M, Han S, Zhao C, Feng W (2025) A universal strategy for smoothing deceleration in deep graph neural networks. Neural Netw 185:107132","journal-title":"Neural Netw"},{"key":"11544_CR9","doi-asserted-by":"crossref","unstructured":"Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau L-M (2018) Learning heuristics for the tsp by policy gradient. In: Integration of constraint programming, artificial intelligence, and operations research: 15th international conference, CPAIOR 2018, Delft, The Netherlands, June 26\u201329, 2018, Proceedings 15. Springer, pp 170\u2013181","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"11544_CR10","unstructured":"Dwivedi VP, Bresson X (2020) A generalization of transformer networks to graphs"},{"key":"11544_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2024.127392","volume":"579","author":"G Fellek","year":"2024","unstructured":"Fellek G, Farid A, Fujimura S, Yoshie O, Gebreyesus G (2024) G-dganet: Gated deep graph attention network with reinforcement learning for solving traveling salesman problem. Neurocomputing 579:127392","journal-title":"Neurocomputing"},{"key":"11544_CR12","doi-asserted-by":"crossref","unstructured":"Fu Z-H, Qiu K-B, Zha H (2021) Generalize a small pre-trained model to arbitrarily large tsp instances. In: Proceedings of the AAAI conference on artificial intelligence, vol. 35, pp 7474\u20137482","DOI":"10.1609\/aaai.v35i8.16916"},{"key":"11544_CR13","doi-asserted-by":"crossref","unstructured":"Giraldo JH, Skianis K, Bouwmans T, Malliaros FD (2023) On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In: Proceedings of the 32nd ACM international conference on information and knowledge management, pp 566\u2013576","DOI":"10.1145\/3583780.3614997"},{"key":"11544_CR14","unstructured":"Glorot X, Bengio Y (2010) Understanding the difficulty of training deep feedforward neural networks. In: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp 249\u2013256. JMLR Workshop and Conference Proceedings"},{"issue":"8","key":"11544_CR15","doi-asserted-by":"publisher","first-page":"10085","DOI":"10.1007\/s13369-021-06430-9","volume":"47","author":"A G\u00fcrsoy","year":"2022","unstructured":"G\u00fcrsoy A (2022) Optimization of product switching processes in assembly lines. Arab J Sci Eng 47(8):10085\u201310100","journal-title":"Arab J Sci Eng"},{"issue":"4","key":"11544_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/MPRV.2008.80","volume":"7","author":"M Haklay","year":"2008","unstructured":"Haklay M, Weber P (2008) Openstreetmap: User-generated street maps. IEEE Pervasive Comput 7(4):12\u201318","journal-title":"IEEE Pervasive Comput"},{"key":"11544_CR17","unstructured":"Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227"},{"issue":"1","key":"11544_CR18","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/s10601-022-09327-y","volume":"27","author":"CK Joshi","year":"2022","unstructured":"Joshi CK, Cappart Q, Rousseau L-M, Laurent T (2022) Learning the travelling salesperson problem requires rethinking generalization. Constraints 27(1):70\u201398","journal-title":"Constraints"},{"key":"11544_CR19","unstructured":"Keles FD, Wijewardena PM, Hegde C (2023) On the computational complexity of self-attention. In: International conference on algorithmic learning theory. PMLR, pp 597\u2013619"},{"issue":"9","key":"11544_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11760-025-04319-w","volume":"19","author":"A Khriss","year":"2025","unstructured":"Khriss A, Elmiad AK, Badaoui M (2025) Qiot-wi: quantum-inspired weight initialization for convolutional neural networks. SIViP 19(9):1\u20139","journal-title":"SIViP"},{"key":"11544_CR21","unstructured":"Kinga D, Adam JB, et al (2015) A method for stochastic optimization. California 5(6)"},{"key":"11544_CR22","unstructured":"Kool W, Van\u00a0Hoof H, Welling M (2018) Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475"},{"key":"11544_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.neucom.2022.08.005","volume":"508","author":"K Lei","year":"2022","unstructured":"Lei K, Guo P, Wang Y, Wu X, Zhao W (2022) Solve routing problems with a residual edge-graph attention neural network. Neurocomputing 508:79\u201398","journal-title":"Neurocomputing"},{"key":"11544_CR24","unstructured":"Liao T, P\u00f3czos B (2024a) Graph attention with random rewiring. arXiv preprint arXiv:2407.05649"},{"key":"11544_CR25","unstructured":"Liao T, P\u00f3czos B (2024b) Greener grass: enhancing gnns with encoding, rewiring, and attention. arXiv preprint arXiv:2407.05649"},{"key":"11544_CR26","unstructured":"Lischka A, Wu J, Basso R, Chehreghani MH, Kulcs\u00e1r B (2024) Less is more\u2013on the importance of sparsification for transformers and graph neural networks for tsp. arXiv preprint arXiv:2403.17159"},{"key":"11544_CR27","unstructured":"Liu Y, Zhang P, Gao Y, Zhou C, Li Z, Chen H (2024) Combinatorial optimization with automated graph neural networks. arXiv preprint arXiv:2406.02872"},{"key":"11544_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2022.104848","volume":"112","author":"J Luo","year":"2022","unstructured":"Luo J, Li C, Fan Q, Liu Y (2022) A graph convolutional encoder and multi-head attention decoder network for tsp via reinforcement learning. Eng Appl Artif Intell 112:104848","journal-title":"Eng Appl Artif Intell"},{"issue":"1","key":"11544_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s40747-024-01716-5","volume":"11","author":"J Luo","year":"2025","unstructured":"Luo J, Heng H, Wu G (2025) Graph attention, learning 2-opt algorithm for the traveling salesman problem. Complex Intell Syst 11(1):117","journal-title":"Complex Intell Syst"},{"key":"11544_CR30","unstructured":"Ma Q, Ge S, He D, Thaker D, Drori I (2019) Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:1911.04936"},{"key":"11544_CR31","unstructured":"Ma L, Lin C, Lim D, Romero-Soriano A, Dokania PK, Coates M, Torr P, Lim S-N (2023) Graph inductive biases in transformers without message passing"},{"key":"11544_CR32","doi-asserted-by":"crossref","unstructured":"Mart\u00ed R, Reinelt G (2022) Exact and heuristic methods in combinatorial optimization. Appl Math Sci","DOI":"10.1007\/978-3-662-64877-3"},{"key":"11544_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105400","volume":"134","author":"N Mazyavkina","year":"2021","unstructured":"Mazyavkina N, Sviridov S, Ivanov S, Burnaev E (2021) Reinforcement learning for combinatorial optimization: a survey. Comput Operat Res 134:105400","journal-title":"Comput Operat Res"},{"key":"11544_CR34","doi-asserted-by":"crossref","unstructured":"O\u00a0Costa PR, Rhuggenaath J, Zhang Y, Akcay A (2020) Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Asian conference on machine learning. PMLR, pp 465\u2013480","DOI":"10.1007\/s42979-021-00779-2"},{"key":"11544_CR35","doi-asserted-by":"crossref","unstructured":"Ouyang W, Wang Y, Han S, Jin Z, Weng P (2021) Improving generalization of deep reinforcement learning-based tsp solvers. In: 2021 IEEE symposium series on computational intelligence (SSCI). IEEE, pp 01\u201308","DOI":"10.1109\/SSCI50451.2021.9659970"},{"key":"11544_CR36","doi-asserted-by":"publisher","unstructured":"Rabbouch B, Rabbouch H, Sa\u00e2daoui F, Mraihi R (2023) Chapter 22 - Foundations of combinatorial optimization, heuristics, and metaheuristics. In: Comprehensive metaheuristics. Academic Press, pp 407\u2013438. https:\/\/doi.org\/10.1016\/B978-0-323-91781-0.00022-3","DOI":"10.1016\/B978-0-323-91781-0.00022-3"},{"key":"11544_CR37","unstructured":"Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347"},{"key":"11544_CR38","doi-asserted-by":"crossref","unstructured":"Seyfi M, Banitalebi-Dehkordi A, Zhou Z, Zhang Y (2023) Exact combinatorial optimization with temporo-attentional graph neural networks. In: Joint European conference on machine learning and knowledge discovery in databases. Springer, pp 268\u2013283","DOI":"10.1007\/978-3-031-43421-1_16"},{"key":"11544_CR39","doi-asserted-by":"crossref","unstructured":"Smit IG, Zhou J, Reijnen R, Wu Y, Chen J, Zhang C, Bukhsh Z, Zhang Y, Nuijten W (2024) Graph neural networks for job shop scheduling problems: a survey. Comput Oper Res, 106914","DOI":"10.1016\/j.cor.2024.106914"},{"key":"11544_CR40","unstructured":"Topping J, Di\u00a0Giovanni F, Chamberlain BP, Dong X, Bronstein MM (2021) Understanding over-squashing and bottlenecks on graphs via curvature"},{"key":"11544_CR42","unstructured":"Tortorella D, Micheli A (2023) Is rewiring actually helpful in graph neural networks? arXiv preprint arXiv:2305.19717"},{"key":"11544_CR43","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2017) Graph attention networks"},{"key":"11544_CR44","unstructured":"Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst 28"},{"issue":"9","key":"11544_CR45","doi-asserted-by":"publisher","first-page":"318","DOI":"10.3390\/fi16090318","volume":"16","author":"AG Vrahatis","year":"2024","unstructured":"Vrahatis AG, Lazaros K, Kotsiantis S (2024) Graph attention networks: a comprehensive review of methods and applications. Future Internet 16(9):318","journal-title":"Future Internet"},{"issue":"9","key":"11544_CR46","doi-asserted-by":"publisher","first-page":"5057","DOI":"10.1109\/TNNLS.2021.3068828","volume":"33","author":"Y Wu","year":"2021","unstructured":"Wu Y, Song W, Cao Z, Zhang J, Lim A (2021) Learning improvement heuristics for solving routing problems. IEEE Trans Neural Netw Learn Syst 33(9):5057\u20135069","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"11544_CR47","unstructured":"Wu X, Wang D, Wen L, Xiao Y, Wu C, Wu Y, Yu C, Maskell DL, Zhou Y (2024) Neural combinatorial optimization algorithms for solving vehicle routing problems: a comprehensive survey with perspectives. arXiv preprint arXiv:2406.00415"},{"issue":"7","key":"11544_CR48","doi-asserted-by":"publisher","first-page":"4861","DOI":"10.1109\/TII.2020.3031409","volume":"17","author":"L Xin","year":"2020","unstructured":"Xin L, Song W, Cao Z, Zhang J (2020) Step-wise deep learning models for solving routing problems. IEEE Trans Ind Inf 17(7):4861\u20134871","journal-title":"IEEE Trans Ind Inf"},{"key":"11544_CR49","doi-asserted-by":"crossref","unstructured":"Xue J, Tan R, Ma J, Ukkusuri SV (2025) Data mining in transportation networks with graph neural networks: a review and outlook. arXiv preprint arXiv:2501.16656","DOI":"10.1007\/s42421-025-00124-6"},{"key":"11544_CR50","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.neunet.2023.02.014","volume":"161","author":"H Yang","year":"2023","unstructured":"Yang H, Zhao M, Yuan L, Yu Y, Li Z, Gu M (2023) Memory-efficient transformer-based network model for traveling salesman problem. Neural Netw 161:589\u2013597","journal-title":"Neural Netw"},{"key":"11544_CR51","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2020.102861","volume":"121","author":"K Zhang","year":"2020","unstructured":"Zhang K, He F, Zhang Z, Lin X, Li M (2020) Multi-vehicle routing problems with soft time windows: a multi-agent reinforcement learning approach. Transp Res Part C Emerg Technol 121:102861","journal-title":"Transp Res Part C Emerg Technol"},{"issue":"1","key":"11544_CR52","doi-asserted-by":"publisher","first-page":"166","DOI":"10.3390\/math14010166","volume":"14","author":"S Zhao","year":"2026","unstructured":"Zhao S, Duan Q (2026) Dynamic topology-aware linear attention network for efficient traveling salesman problem optimization. Mathematics 14(1):166. https:\/\/doi.org\/10.3390\/math14010166","journal-title":"Mathematics"},{"key":"11544_CR53","doi-asserted-by":"crossref","unstructured":"Zhuang B, Liu J, Pan Z, He H, Weng Y, Shen C (2023) A survey on efficient training of transformers. arXiv preprint arXiv:2302.01107","DOI":"10.24963\/ijcai.2023\/764"}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10462-026-11544-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-026-11544-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-026-11544-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T04:54:26Z","timestamp":1782363266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10462-026-11544-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,3]]},"references-count":52,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2026,7]]}},"alternative-id":["11544"],"URL":"https:\/\/doi.org\/10.1007\/s10462-026-11544-3","relation":{},"ISSN":["1573-7462"],"issn-type":[{"value":"1573-7462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,3]]},"assertion":[{"value":"29 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors state that there are no financial or personal conflict of interest that could have influenced the results, interpretations, or conclusions reported in this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"149"}}