{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T15:52:48Z","timestamp":1776441168792,"version":"3.51.2"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62106096"],"award-info":[{"award-number":["62106096"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003453","name":"Natural Science Foundation of Guangdong Province","doi-asserted-by":"crossref","award":["2024A1515011759"],"award-info":[{"award-number":["2024A1515011759"]}],"id":[{"id":"10.13039\/501100003453","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Natural Science Foundation of Shenzhen","award":["JCYJ20220530113013031"],"award-info":[{"award-number":["JCYJ20220530113013031"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    Neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorial optimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(50{,}000\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.\n                  <\/jats:p>","DOI":"10.1145\/3694690","type":"journal-article","created":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T06:31:46Z","timestamp":1728628306000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Rethinking Supervised Learning-Based Neural Combinatorial Optimization for Routing Problem"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0427-2217","authenticated-orcid":false,"given":"Shunyu","family":"Yao","sequence":"first","affiliation":[{"name":"School of System Design and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China and City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5298-6893","authenticated-orcid":false,"given":"Xi","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1616-7453","authenticated-orcid":false,"given":"Jiashu","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0786-0671","authenticated-orcid":false,"given":"Qingfu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1152-6780","authenticated-orcid":false,"given":"Zhenkun","family":"Wang","sequence":"additional","affiliation":[{"name":"School of System Design and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,6]]},"reference":[{"key":"e_1_3_2_2_1","unstructured":"David Applegate Ribert Bixby Vasek Chvatal and William Cook. 2006. Concorde TSP solver."},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585888"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aei.2004.07.001"},{"key":"e_1_3_2_5_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR) Workshops","author":"Bello Irwan","year":"2017","unstructured":"Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2017. Neural combinatorial optimization with reinforcement learning. In Proceedings of the International Conference on Learning Representations (ICLR) Workshops."},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_3_2_7_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"32","author":"Chen Xinyun","year":"2019","unstructured":"Xinyun Chen and Yuandong Tian. 2019. Learning to perform local rewriting for combinatorial optimization. In Proceedings of the Advances in Neural Information Processing Systems,Vol. 32."},{"key":"e_1_3_2_8_1","first-page":"465","volume-title":"Proceedings of the Asian Conference on Machine Learning.","author":"Costa Paulo R. d O.","year":"2020","unstructured":"Paulo R. d O. Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. 2020. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Proceedings of the Asian Conference on Machine Learning. PMLR, 465\u2013480."},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"e_1_3_2_10_1","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1109\/CEC.1999.782657","volume-title":"Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)","volume":"2","author":"Dorigo Marco","year":"1999","unstructured":"Marco Dorigo and Gianni Di Caro. 1999. Ant colony optimization: A new meta-heuristic. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Vol. 2. IEEE, 1470\u20131477."},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2021.findings-acl.84"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i8.16916"},{"key":"e_1_3_2_13_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR \u201922)","author":"Geisler Simon","year":"2022","unstructured":"Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2022. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In Proceedings of the International Conference on Learning Representations (ICLR \u201922)."},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D"},{"key":"e_1_3_2_15_1","unstructured":"Gurobi Optimization LLC. 2022. Gurobi Optimizer Reference Manual. Retrieved from https:\/\/www.gurobi.com"},{"key":"e_1_3_2_16_1","unstructured":"Joshua Hare. 2019. Dealing with sparse rewards in reinforcement learning. arXiv:1910.09281. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1910.09281"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_3_2_18_1","first-page":"24","volume-title":"An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems","author":"Helsgaun Keld","year":"2017","unstructured":"Keld Helsgaun. 2017. An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Roskilde: Roskilde University, 24\u201350."},{"key":"e_1_3_2_19_1","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Hottung Andr\u00e9","year":"2020","unstructured":"Andr\u00e9 Hottung, Bhanu Bhandari, and Kevin Tierney. 2020. Learning a latent search space for routing problems using variational autoencoders. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103786"},{"key":"e_1_3_2_21_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR \u201922)","author":"Hudson Benjamin","year":"2022","unstructured":"Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. 2022. Graph neural network guided local search for the traveling salesperson problem. In Proceedings of the International Conference on Learning Representations (ICLR \u201922)."},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-022-09327-y"},{"key":"e_1_3_2_23_1","unstructured":"Chaitanya K. Joshi Thomas Laurent and Xavier Bresson. 2019. An efficient graph convolutional network technique for the travelling salesman problem. arXiv:1906.01227. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1906.01227"},{"key":"e_1_3_2_24_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"30","author":"Khalil Elias","year":"2017","unstructured":"Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 30."},{"key":"e_1_3_2_25_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201921)","author":"Kim Minsu","year":"2021","unstructured":"Minsu Kim and Jinkyoo Park. 2021. Learning collaborative policies to solve NP-hard routing problems. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201921)."},{"key":"e_1_3_2_26_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201922)","author":"Kim Minsu","year":"2022","unstructured":"Minsu Kim, Junyoung Park, and Jinkyoo Park. 2022. Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201922)."},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.09.003"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-08011-1_14"},{"key":"e_1_3_2_29_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR \u201919)","author":"Kool Wouter","year":"2019","unstructured":"Wouter Kool, Herke Van Hoof, and Max Welling. 2019. Attention, learn to solve routing problems! In Proceedings of the International Conference on Learning Representations (ICLR \u201919)."},{"key":"e_1_3_2_30_1","volume":"1","author":"Korte Bernhard H.","year":"2011","unstructured":"Bernhard H. Korte, Jens Vygen, B. Korte, and J. Vygen. 2011. Combinatorial Optimization. Vol. 1. Springer.","journal-title":"Combinatorial Optimization"},{"key":"e_1_3_2_31_1","first-page":"24981","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"34","author":"Kotary James","year":"2021","unstructured":"James Kotary, Ferdinando Fioretto, and Pascal Van Hentenryck. 2021. Learning hard optimization problems: A data generation perspective. In Proceedings of the Advances in Neural Information Processing Systems,Vol. 34, 24981\u201324992."},{"key":"e_1_3_2_32_1","first-page":"21188","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"33","author":"Kwon Yeong-Dae","year":"2020","unstructured":"Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. 2020. POMO: Policy optimization with multiple optima for reinforcement learning. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 33, 21188\u201321198."},{"key":"e_1_3_2_33_1","first-page":"19884","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"33","author":"Laskin Misha","year":"2020","unstructured":"Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. 2020. Reinforcement learning with augmented data. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 33, 19884\u201319895."},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1975.151"},{"key":"e_1_3_2_35_1","unstructured":"Fei Liu Chengyu Lu Lin Gui Qingfu Zhang Xialiang Tong and Mingxuan Yuan. 2023. Heuristics for vehicle routing problem: A survey and recent advances. arXiv:2303.04147. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2303.04147"},{"key":"e_1_3_2_36_1","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Lu Hao","year":"2019","unstructured":"Hao Lu, Xingwen Zhang, and Shuang Yang. 2019. A learning-based iterative method for solving vehicle routing problems. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_37_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"36","author":"Luo Fu","year":"2024","unstructured":"Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. 2024. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 36."},{"key":"e_1_3_2_38_1","unstructured":"Qiang Ma Suwen Ge Danyang He Darshan Thaker and Iddo Drori. 2019. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv:1911.04936. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1911.04936"},{"key":"e_1_3_2_39_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence","author":"Milan Anton","year":"2017","unstructured":"Anton Milan, S. Hamid Rezatofighi, Ravi Garg, Anthony Dick, and Ian Reid. 2017. Data-driven approximations to NP-hard problems. In Proceedings of the 31st AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_2_40_1","first-page":"9861","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201918)","author":"Nazari Mohammadreza","year":"2018","unstructured":"Mohammadreza Nazari, Afshin Oroojlooy, Martin Tak\u00e1\u010d, and Lawrence V. Snyder. 2018. Reinforcement learning for solving the vehicle routing problem. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS \u201918), 9861\u20139871."},{"issue":"4","key":"e_1_3_2_41_1","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/s42979-024-02689-5","article-title":"Generalization in deep RL for TSP problems via equivariance and local search","volume":"5","author":"Ouyang Wenbin","year":"2024","unstructured":"Wenbin Ouyang, Yisen Wang, Paul Weng, and Shaochen Han. 2024. Generalization in deep RL for TSP problems via equivariance and local search. SN Computer Science 5, 4 (2024), 369.","journal-title":"SN Computer Science"},{"key":"e_1_3_2_42_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou Christos H.","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation."},{"key":"e_1_3_2_43_1","unstructured":"Laurent Perron and Vincent Furnon. [n. d.]. OR-Tools. Google. Retrieved from https:\/\/developers.google.com\/optimization\/"},{"issue":"2","key":"e_1_3_2_44_1","first-page":"359","article-title":"Comparison of eight evolutionary crossover operators for the vehicle routing problem","volume":"18","author":"Pulji\u0107 Krunoslav","year":"2013","unstructured":"Krunoslav Pulji\u0107 and Robert Manger. 2013. Comparison of eight evolutionary crossover operators for the vehicle routing problem. Mathematical Communications 18, 2 (2013), 359\u2013375.","journal-title":"Mathematical Communications"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"e_1_3_2_46_1","first-page":"9323","volume-title":"Proceedings of the International Conference on Machine Learning (ICML \u201921)","author":"Satorras Vi\u0307ctor Garcia","year":"2021","unstructured":"Vi\u0307ctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. 2021. E (n) equivariant graph neural networks. In Proceedings of the International Conference on Machine Learning (ICML \u201921), 9323\u20139332."},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-019-0197-0"},{"key":"e_1_3_2_48_1","unstructured":"Nathaniel Thomas Tess Smidt Steven Kearnes Lusann Yang Li Li Kai Kohlhoff and Patrick Riley. 2018. Tensor field networks: Rotation-and translation-equivariant neural networks for 3D point clouds. arXiv:1802.08219. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1802.08219"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.08.012"},{"issue":"7","key":"e_1_3_2_50_1","first-page":"1717","article-title":"A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator","volume":"13","author":"Kumar S. G. Varun","year":"2017","unstructured":"S. G. Varun Kumar and R. Panneerselvam. 2017. A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator. International Journal of Computational Intelligence Research 13, 7 (2017), 1717\u20131733.","journal-title":"International Journal of Computational Intelligence Research"},{"key":"e_1_3_2_51_1","unstructured":"Mel Vecerik Todd Hester Jonathan Scholz Fumin Wang Olivier Pietquin Bilal Piot Nicolas Heess Thomas Roth\u00f6rl Thomas Lampe and Martin Riedmiller. 2017. Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards. arXiv:1707.08817."},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105643"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1048"},{"key":"e_1_3_2_54_1","first-page":"28","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Vinyals Oriol","year":"2015","unstructured":"Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 28."},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","unstructured":"Yaoxin Wu Wen Song Zhiguang Cao Jie Zhang and Andrew Lim. 2022. Learning Improvement Heuristics for Solving Routing Problems. 33 9 (Sep 2022) 5057\u20135069. DOI: 10.1109\/TNNLS.2021.3068828","DOI":"10.1109\/TNNLS.2021.3068828"},{"key":"e_1_3_2_56_1","first-page":"12042","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence","author":"Xin Liang","year":"2021","unstructured":"Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. 2021. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 12042\u201312049."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T12:26:24Z","timestamp":1765023984000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,6]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3694690"],"URL":"https:\/\/doi.org\/10.1145\/3694690","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,6]]},"assertion":[{"value":"2023-10-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}