{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T21:17:36Z","timestamp":1783113456803,"version":"3.54.6"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["628.009.012"],"award-info":[{"award-number":["628.009.012"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent works using deep learning to solve routing problems such as the traveling salesman problem (TSP) have focused on learning construction heuristics. Such approaches find good quality solutions but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which can be easily extended to more general<jats:italic>k<\/jats:italic>-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions faster than previous state-of-the-art deep learning methods for the TSP. We also show we can adapt the proposed method to two extensions of the TSP: the multiple TSP and the Vehicle Routing Problem, achieving results on par with classical heuristics and learned methods.<\/jats:p>","DOI":"10.1007\/s42979-021-00779-2","type":"journal-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T15:02:35Z","timestamp":1627052555000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":77,"title":["Learning 2-Opt Heuristics for Routing Problems via Deep Reinforcement Learning"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0509-8724","authenticated-orcid":false,"given":"Paulo","family":"da Costa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jason","family":"Rhuggenaath","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yingqian","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alp","family":"Akcay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uzay","family":"Kaymak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"issue":"4","key":"779_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0893-6080(88)90002-0","volume":"1","author":"B Angeniol","year":"1988","unstructured":"Angeniol B, Vaubois GDLC, Le Texier JY. Self-organizing feature maps and the travelling salesman problem. Neural Netw. 1988;1(4):289\u201393.","journal-title":"Neural Netw"},{"key":"779_CR2","volume-title":"The traveling salesman problem: a computational study","author":"DL Applegate","year":"2006","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ. The traveling salesman problem: a computational study. Princeton: Princeton University Press; 2006."},{"issue":"5","key":"779_CR3","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM. 1998;45(5):753\u201382.","journal-title":"J ACM"},{"issue":"3","key":"779_CR4","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega. 2006;34(3):209\u201319.","journal-title":"Omega"},{"key":"779_CR5","unstructured":"Bello I, Pham H. Neural combinatorial optimization with reinforcement learning. In: Proceedings of the 5th international conference on learning representations (ICLR), 2017."},{"key":"779_CR6","unstructured":"Bengio Y, Lodi A, Prouvost A. Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. 2018. Available from: arXiv:1811.06128"},{"key":"779_CR7","doi-asserted-by":"crossref","unstructured":"Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM. Learning heuristics for the tsp by policy gradient. In: Proceedings of the 15th international conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR); 2018. pp. 170\u2013181.","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"779_CR8","doi-asserted-by":"crossref","unstructured":"Duan L, Zhan Y, Hu H, Gong Y, Wei J, Zhang X, Xu Y. Efficiently solving the practical vehicle routing problem: a novel joint learning approach. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining; 2020. pp. 3054\u20133063.","DOI":"10.1145\/3394486.3403356"},{"key":"779_CR9","unstructured":"Gurobi\u00a0Optimization L. Gurobi optimizer reference manual. 2021. http:\/\/www.gurobi.com. Accessed Jan 2021."},{"key":"779_CR10","doi-asserted-by":"crossref","unstructured":"Hansen P, Mladenovi\u0107 N. First vs. best improvement: an empirical study. Discrete Appl Math. 2006;154(5):802\u2013817.","DOI":"10.1016\/j.dam.2005.05.020"},{"issue":"2\u20133","key":"779_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","volume":"1","author":"K Helsgaun","year":"2009","unstructured":"Helsgaun K. General k-opt submoves for the Lin\u2013Kernighan tsp heuristic. Math Program Comput. 2009;1(2\u20133):119\u201363.","journal-title":"Math Program Comput"},{"key":"779_CR12","volume-title":"An extension of the Lin\u2013Kernighan\u2013Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems","author":"K Helsgaun","year":"2017","unstructured":"Helsgaun K. An extension of the Lin\u2013Kernighan\u2013Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University; 2017."},{"issue":"8","key":"779_CR13","doi-asserted-by":"publisher","first-page":"1735","DOI":"10.1162\/neco.1997.9.8.1735","volume":"9","author":"S Hochreiter","year":"1997","unstructured":"Hochreiter S, Schmidhuber J. Long short-term memory. Neural Comput. 1997;9(8):1735\u201380.","journal-title":"Neural Comput"},{"issue":"3","key":"779_CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00339943","volume":"52","author":"JJ Hopfield","year":"1985","unstructured":"Hopfield JJ, Tank DW. Neural computation of decisions in optimization problems. Biol Cybern. 1985;52(3):141\u201352.","journal-title":"Biol Cybern"},{"key":"779_CR15","unstructured":"Hottung A, Tierney K. Neural large neighborhood search for the capacitated vehicle routing problem. 2019. Available from: arXiv:1911.09539."},{"key":"779_CR16","doi-asserted-by":"crossref","unstructured":"Hu Y, Yao Y, Lee WS. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowl Based Syst. 2020;204:106244.","DOI":"10.1016\/j.knosys.2020.106244"},{"key":"779_CR17","unstructured":"Jia X, Song S, He W, Wang Y, Rong H, Zhou F, Xie L, Guo Z, Yang Y, Yu L, et\u00a0al. Highly scalable deep learning training system with mixed-precision: training imagenet in four minutes. 2018. Available from: arXiv:1807.11205."},{"key":"779_CR18","unstructured":"Joshi CK, Laurent T, Bresson X. An efficient graph convolutional network technique for the travelling salesman problem. 2019. Available from: arXiv:1906.01227."},{"key":"779_CR19","unstructured":"Kaempfer Y, Wolf L. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. 2018. Available from: arXiv:1803.09621."},{"key":"779_CR20","unstructured":"Khalil E, Dai H, Zhang Y, Dilkina B, Song L. Learning combinatorial optimization algorithms over graphs. In: Proceedings of the 31st conference on neural information processing systems (NIPS); 2017. pp. 6348\u20136358."},{"key":"779_CR21","unstructured":"Kingma DP, Ba J. Adam: a method for stochastic optimization. In: International conference on machine learning; 2015."},{"key":"779_CR22","unstructured":"Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th international conference on learning representations (ICLR); 2017."},{"key":"779_CR23","doi-asserted-by":"crossref","unstructured":"Kool W, van Hoof H, Gromicho J, Welling M. Deep policy dynamic programming for vehicle routing problems. 2021. Available from: arXiv:2102.11756.","DOI":"10.1007\/978-3-031-08011-1_14"},{"key":"779_CR24","unstructured":"Kool W, van Hoof H, Welling M. Attention, learn to solve routing problems! In: Proceedings of the 7th international conference on learning representations (ICLR); 2019."},{"key":"779_CR25","doi-asserted-by":"crossref","unstructured":"La\u00a0Maire BF, Mladenov VM. Comparison of neural networks for solving the travelling salesman problem. In: 11th symposium on neural network applications in electrical engineering. IEEE; 2012. pp. 21\u201324.","DOI":"10.1109\/NEUREL.2012.6419953"},{"issue":"2","key":"779_CR26","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin S, Kernighan BW. An effective heuristic algorithm for the traveling-salesman problem. Oper Res. 1973;21(2):498\u2013516.","journal-title":"Oper Res"},{"key":"779_CR27","doi-asserted-by":"crossref","unstructured":"Lombardi M, Milano M. Boosting combinatorial problem modeling with machine learning. In: Proceedings of the 27th international joint conference on artificial intelligence (IJCAI); 2018. pp. 5472\u20135478.","DOI":"10.24963\/ijcai.2018\/772"},{"key":"779_CR28","unstructured":"Lu H, Zhang X, Yang S. A learning-based iterative method for solving vehicle routing problems. In: International conference on learning representations; 2019."},{"key":"779_CR29","unstructured":"Ma Q, Ge S, He D, Thaker D, Drori I. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. 2019. Available from: arXiv:1911.04936."},{"key":"779_CR30","unstructured":"Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K. Asynchronous methods for deep reinforcement learning. In: Proceedings of the 33rd international conference on machine learning (ICML); 2016. pp. 1928\u20131937."},{"key":"779_CR31","unstructured":"Nazari M, Oroojlooy A, Snyder LV, Tak\u00e1c M. Reinforcement learning for solving the vehicle routing problem. In: NeurIPS; 2018."},{"key":"779_CR32","doi-asserted-by":"crossref","unstructured":"d\u00a0O\u00a0Costa PR, Rhuggenaath J, Zhang Y, Akcay A. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Asian conference on machine learning. PMLR; 2020. pp. 465\u2013480.","DOI":"10.1007\/s42979-021-00779-2"},{"issue":"3","key":"779_CR33","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH. The Euclidean travelling salesman problem is np-complete. Theor Comput Sci. 1977;4(3):237\u201344.","journal-title":"Theor Comput Sci"},{"key":"779_CR34","doi-asserted-by":"crossref","unstructured":"Peng B, Wang J, Zhang Z. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In: International symposium on intelligence computation and applications. Springer; 2019. pp. 636\u2013650.","DOI":"10.1007\/978-981-15-5577-0_51"},{"key":"779_CR35","unstructured":"Perron L, Furnon V. OR-Tools. https:\/\/developers.google.com\/optimization\/. Accessed Oct 2020."},{"issue":"4","key":"779_CR36","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G. Tsplib\u2014a traveling salesman problem library. ORSA J Comput. 1991;3(4):376\u201384.","journal-title":"ORSA J Comput"},{"key":"779_CR37","doi-asserted-by":"crossref","unstructured":"Toth P, Vigo D. Vehicle routing: problems, methods, and applications. SIAM; 2014.","DOI":"10.1137\/1.9781611973594"},{"key":"779_CR38","unstructured":"Vinyals O, Fortunato M, Jaitly N. Pointer networks. In: Proceedings of the 29th conference on neural information processing systems (NIPS); 2015. pp. 2692\u20132700."},{"issue":"3\u20134","key":"779_CR39","first-page":"229","volume":"8","author":"RJ Williams","year":"1992","unstructured":"Williams RJ. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach Learn. 1992;8(3\u20134):229\u201356.","journal-title":"Mach Learn"},{"key":"779_CR40","unstructured":"Wu Y, Song W, Cao Z, Zhang J, Lim A. Learning improvement heuristics for solving the travelling salesman problem. 2019. Available from: arXiv:1912.05784."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00779-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00779-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00779-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,5]],"date-time":"2023-01-05T09:12:18Z","timestamp":1672909938000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00779-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,23]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["779"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00779-2","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,23]]},"assertion":[{"value":"23 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"388"}}