{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T18:44:20Z","timestamp":1775328260459,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T00:00:00Z","timestamp":1735862400000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"name":"the Ningbo Philosophy and Social Science Research Base","award":["JD6-025"],"award-info":[{"award-number":["JD6-025"]}]},{"name":"the Scientific Research Start-up Fund of Ningbo University of Technology","award":["No. 2023KQ041"],"award-info":[{"award-number":["No. 2023KQ041"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s40747-024-01716-5","type":"journal-article","created":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T06:42:39Z","timestamp":1735886559000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph attention, learning 2-opt algorithm for the traveling salesman problem"],"prefix":"10.1007","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7680-7271","authenticated-orcid":false,"given":"Jia","family":"Luo","sequence":"first","affiliation":[]},{"given":"Herui","family":"Heng","sequence":"additional","affiliation":[]},{"given":"Geng","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,3]]},"reference":[{"key":"1716_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/9781119005384","volume-title":"Applications of combinatorial optimization","author":"VT Paschos","year":"2014","unstructured":"Paschos VT (2014) Applications of combinatorial optimization. Wiley, London"},{"key":"1716_CR2","first-page":"359","volume-title":"Robotics, and information processing","author":"C Smutnicki","year":"2021","unstructured":"Smutnicki C (2021) Discrete Optimization in the Industrial Computer Science. In: Control A (ed) Robotics, and information processing. Springer, Cham, pp 359\u2013385"},{"issue":"1","key":"1716_CR3","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ejor.2020.10.035","volume":"292","author":"JF Campbell","year":"2021","unstructured":"Campbell JF, Corber\u00e1n \u00c1, Plana I et al (2021) Solving the length constrained K-drones rural postman problem. Eur J Oper Res 292(1):60\u201372","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1716_CR4","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1016\/j.ejor.2019.11.046","volume":"283","author":"V Cacchiani","year":"2020","unstructured":"Cacchiani V, Contreras-Bolton C, Toth P (2020) Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times. Eur J Oper Res 283(3):825\u2013843","journal-title":"Eur J Oper Res"},{"issue":"9\u201312","key":"1716_CR5","first-page":"2505","volume":"85","author":"R P\u00e9rez-Rodr\u00edguez","year":"2015","unstructured":"P\u00e9rez-Rodr\u00edguez R, Hern\u00e1ndez-Aguirre A (2015) Simulation optimization for the vehicle routing problem with time windows using a Bayesian network as a probability model. Int J Adv Manuf Technol 85(9\u201312):2505\u20132523","journal-title":"Int J Adv Manuf Technol"},{"issue":"5\u20138","key":"1716_CR6","doi-asserted-by":"publisher","first-page":"2325","DOI":"10.1007\/s00170-017-0247-8","volume":"92","author":"Z Lin","year":"2017","unstructured":"Lin Z, Fu J, Sun Y et al (2017) Non-retraction toolpath generation for irregular compound freeform surfaces with the LKH TSP solver. Int J Adv Manuf Technol 92(5\u20138):2325\u20132339","journal-title":"Int J Adv Manuf Technol"},{"key":"1716_CR7","volume-title":"Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics","author":"J Hromkovi\u010d","year":"2013","unstructured":"Hromkovi\u010d J (2013) Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. Springer Science & Business Media, Berlin"},{"key":"1716_CR8","doi-asserted-by":"crossref","unstructured":"Festa P (2014) A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In: Paper presented at the 16th International Conference on Transparent Optical Networks (ICTON), Graz, Austria","DOI":"10.1109\/ICTON.2014.6876285"},{"key":"1716_CR9","doi-asserted-by":"publisher","DOI":"10.1201\/EBK0824740993","volume-title":"Dynamic programming: foundations and principles","author":"M Sniedovich","year":"2010","unstructured":"Sniedovich M (2010) Dynamic programming: foundations and principles. CRC Press, London, Hoboken"},{"issue":"2","key":"1716_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2021.125811","volume":"507","author":"J Graczyk","year":"2022","unstructured":"Graczyk J, Mihalache N (2022) Optimal bounds for the analytical traveling salesman problem. J Math Anal Appl 507(2):125811","journal-title":"J Math Anal Appl"},{"key":"1716_CR11","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.swevo.2018.05.006","volume":"44","author":"I Khan","year":"2019","unstructured":"Khan I, Maiti MK (2019) A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem. Swarm Evol Comput 44:428\u2013438","journal-title":"Swarm Evol Comput"},{"key":"1716_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2021.101454","volume":"55","author":"K Panwar","year":"2021","unstructured":"Panwar K, Deep K (2021) Transformation operators based grey wolf optimizer for travelling salesman problem. J Comput Sci 55:101454","journal-title":"J Comput Sci"},{"key":"1716_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.114639","volume":"172","author":"Y Saji","year":"2021","unstructured":"Saji Y, Barkatou M (2021) A discrete bat algorithm based on L\u00e9vy flights for Euclidean traveling salesman problem. Expert Syst Appl 172:114639","journal-title":"Expert Syst Appl"},{"key":"1716_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107439","volume":"107","author":"Y Wang","year":"2021","unstructured":"Wang Y, Han Z (2021) Ant colony optimization for traveling salesman problem based on parameters optimization. Appl Soft Comput 107:107439","journal-title":"Appl Soft Comput"},{"key":"1716_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2020.101288","volume":"49","author":"G Bocewicz","year":"2021","unstructured":"Bocewicz G, Banaszak Z, Rudnik K et al (2021) An ordered-fuzzy-numbers-driven approach to the milk-run routing and scheduling problem. J Comput Sci 49:101288","journal-title":"J Comput Sci"},{"issue":"12","key":"1716_CR16","doi-asserted-by":"publisher","first-page":"4529","DOI":"10.1007\/s10489-020-01799-w","volume":"50","author":"K Yang","year":"2020","unstructured":"Yang K, You X, Liu S et al (2020) A novel ant colony optimization based on game for traveling salesman problem. Appl Intell 50(12):4529\u20134542","journal-title":"Appl Intell"},{"issue":"6","key":"1716_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3459664","volume":"54","author":"E-G Talbi","year":"2021","unstructured":"Talbi E-G (2021) Machine learning into metaheuristics: a survey and taxonomy. ACM Comput Surv 54(6):1\u201332","journal-title":"ACM Comput Surv"},{"key":"1716_CR18","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological Tour d\u2019Horizon. Eur J Oper Res 290:405\u2013421","journal-title":"Eur J Oper Res"},{"key":"1716_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104798","volume":"113","author":"I Markov","year":"2020","unstructured":"Markov I, Bierlaire M, Cordeau J-F et al (2020) Waste collection inventory routing with non-stationary stochastic demands. Comput Oper Res 113:104798","journal-title":"Comput Oper Res"},{"issue":"6","key":"1716_CR20","doi-asserted-by":"publisher","first-page":"1955","DOI":"10.1080\/00207543.2022.2056540","volume":"61","author":"L van Hezewijk","year":"2022","unstructured":"van Hezewijk L, Dellaert N, Van Woensel T et al (2022) Using the proximal policy optimisation algorithm for solving the stochastic capacitated lot sizing problem. Int J Prod Res 61(6):1955\u20131978","journal-title":"Int J Prod Res"},{"issue":"1","key":"1716_CR21","doi-asserted-by":"publisher","first-page":"19623","DOI":"10.1038\/s41598-021-98643-z","volume":"11","author":"YL Tsai","year":"2021","unstructured":"Tsai YL, Rastogi C, Kitanidis PK et al (2021) Routing algorithms as tools for integrating social distancing with emergency evacuation. Sci Rep 11(1):19623","journal-title":"Sci Rep"},{"key":"1716_CR22","unstructured":"Kool W, Hoof HV, Welling M (2018) Attention, learn to solve routing problems. . In: Paper Presented at the International Conference on Learning Representations, Vancouver, BC."},{"issue":"7","key":"1716_CR23","doi-asserted-by":"publisher","first-page":"4861","DOI":"10.1109\/TII.2020.3031409","volume":"17","author":"L Xin","year":"2021","unstructured":"Xin L, Song W, Cao Z et al (2021) Step-Wise Deep Learning Models for Solving Routing Problems. IEEE Trans Industr Inf 17(7):4861\u20134871","journal-title":"IEEE Trans Industr Inf"},{"key":"1716_CR24","unstructured":"Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. In: Paper Presented at the Neural Information Processing Systems, Montr\u00e9al, Canada"},{"key":"1716_CR25","doi-asserted-by":"crossref","unstructured":"Zhao J, Mao M, Zhao X, et al (2020) A hybrid of deep reinforcement learning and local search for the vehicle routing problems. In: IEEE Trans Intell Transport Syst, pp 1\u201311","DOI":"10.1109\/TITS.2020.3003163"},{"key":"1716_CR26","unstructured":"Chen X, Tian Y (2019) Learning to perform local rewriting for combinatorial optimization. In: Paper presented at the NeurIPS"},{"key":"1716_CR27","unstructured":"Lu H, Zhang X, Yang S (2020) A Learning-based iterative method for solving vehicle routing problems. . In: Paper Presented at the International Conference on learning representation"},{"issue":"9","key":"1716_CR28","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 et al (2021) Learning Improvement Heuristics for Solving Routing Problems. IEEE Trans Neural Netw Learn Sys 33(9):5057\u20135069","journal-title":"IEEE Trans Neural Netw Learn Sys"},{"key":"1716_CR29","unstructured":"Bello I, Pham H, Le QV, et al (2017) Neural combinatorial optimization with reinforcement learning. In: Paper presented at the International Conference on Learning Representations, Toulon, France"},{"key":"1716_CR30","unstructured":"Vaswani A, Shazeer NM, Parmar N, et al (2017) Attention is all you need. . In: Paper Presented at the Neural Information Processing Systems, Long Beach, CA."},{"key":"1716_CR31","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 et al (2020) Multi-vehicle routing problems with soft time windows: a multi-agent reinforcement learning approach. Transport Res Part C Emerg Technol 121:102861","journal-title":"Transport Res Part C Emerg Technol"},{"key":"1716_CR32","doi-asserted-by":"crossref","unstructured":"Deudon, M., Cournut, P., Lacoste, A., et al. (2018). Learning Heuristics for the TSP by Policy Gradient. In: Paper Presented at the International Conference on the integration of constraint programming, artificial intelligence, and operations research, Delft, The Netherlands","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"1716_CR33","unstructured":"Duvenaud DK, Maclaurin D, Iparraguirre J, et al (2015) Convolutional networks on graphs for learning molecular fingerprints. In: Paper Presented at the Advances in Neural Information Processing Systems."},{"key":"1716_CR34","unstructured":"Hamilton WL, Ying R, Leskovec J (2017) Inductive representation learning on large graphs. In: Paper presented at the Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach, CA."},{"issue":"1","key":"1716_CR35","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","volume":"20","author":"F Scarselli","year":"2008","unstructured":"Scarselli F, Gori M, Tsoi AC et al (2008) The graph neural network model. IEEE Trans Neural Networks 20(1):61\u201380","journal-title":"IEEE Trans Neural Networks"},{"key":"1716_CR36","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A, et al (2018) Graph attention networks. In: Paper Presented at the International Conference on Learning Representations, Vancouver, BC."},{"key":"1716_CR37","unstructured":"Gilmer J, Schoenholz SS, Riley PF, et al. (2017) Neural message passing for quantum chemistry. In: Paper Presented at the International Conference on machine learning, Sydney, Australia"},{"key":"1716_CR38","unstructured":"Dai H, Khalil EB, Zhang Y, et al (2017) Learning combinatorial optimization algorithms over graphs. In: Paper presented at the Neural Information Processing Systems, Long Beach, CA."},{"key":"1716_CR39","doi-asserted-by":"publisher","unstructured":"Ma Q, Ge S, He D, et al (2019) Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint, arXiv:1911.04936. https:\/\/doi.org\/10.48550\/arXiv.1911.04936","DOI":"10.48550\/arXiv.1911.04936"},{"key":"1716_CR40","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 et al (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"},{"key":"1716_CR41","unstructured":"Nowak A, Folqu\u00e9 D, Bruna J (2018) Divide and conquer networks. In: Paper presented at the 6th International Conference on Learning Representations, Vancouver, Canada"},{"key":"1716_CR42","doi-asserted-by":"publisher","unstructured":"Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint, arXiv:1906.01227. https:\/\/doi.org\/10.48550\/arXiv.1906.01227","DOI":"10.48550\/arXiv.1906.01227"},{"key":"1716_CR43","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF00992696","volume":"8","author":"RJ Williams","year":"1992","unstructured":"Williams RJ (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach Learn 8:229\u2013256","journal-title":"Mach Learn"},{"key":"1716_CR44","unstructured":"Applegate D, Bixby R, Chvatal V, et al (2006) Concorde TSP Solver. https:\/\/www.math.uwaterloo.ca\/tsp\/concorde\/"},{"key":"1716_CR45","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/s10601-022-09327-y","volume":"27","author":"CK Joshi","year":"2021","unstructured":"Joshi CK, Cappart Q, Rousseau L et al (2021) Learning the travelling salesperson problem requires rethinking generalization. Constraints 27:70\u201398","journal-title":"Constraints"},{"key":"1716_CR46","unstructured":"Perron L, Furnon V (2020) OR-Tools. https:\/\/developers.google.com\/optimization\/"},{"issue":"5","key":"1716_CR47","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1016\/j.dam.2005.05.020","volume":"154","author":"P Hansen","year":"2006","unstructured":"Hansen P, Mladenovi\u0107 N (2006) First vs. best improvement: an empirical study. Discrete Appl Math 154(5):802\u2013817","journal-title":"Discrete Appl Math"}],"container-title":["Complex & Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01716-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-024-01716-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-024-01716-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T20:22:21Z","timestamp":1738268541000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-024-01716-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1716"],"URL":"https:\/\/doi.org\/10.1007\/s40747-024-01716-5","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"7 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We declare that we have no financial and personal relationships with other people or organizations that can inappropriately influence our work, there is no professional or other personal interest of any nature or kind in any product, service and\/or company that could be construed as influencing the position presented in, or the review of, the manuscript entitled, \u201cGraph attention, learning 2-opt algorithm for the traveling salesman problem\u201d.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"117"}}