{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:53:46Z","timestamp":1773932026055,"version":"3.50.1"},"reference-count":55,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T00:00:00Z","timestamp":1631577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200020-182360"],"award-info":[{"award-number":["200020-182360"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. A CL is defined as a subset of all the edges linked to a given vertex such that it contains mainly edges that are believed to be found in the optimal tour. The initialization procedure that identifies a CL for each vertex in the TSP aids the solver by restricting the search space during solution creation. It results in a reduction of the computational burden as well, which is highly recommended when solving large TSPs. So far, ML was engaged to create CLs and values on the elements of these CLs by expressing ML preferences at solution insertion. Although promising, these systems do not restrict what the ML learns and does to create solutions, bringing with them some generalization issues. Therefore, motivated by exploratory and statistical studies of the CL behavior in multiple TSP solutions, in this work, we rethink the usage of ML by purposely employing this system just on a task that avoids well-known ML weaknesses, such as training in presence of frequent outliers and the detection of under-represented events. The task is to confirm inclusion in a solution just for edges that are most likely optimal. The CLs of the edge considered for inclusion are employed as an input of the neural network, and the ML is in charge of distinguishing when such edge is in the optimal solution from when it is not. The proposed approach enables a reasonable generalization and unveils an efficient balance between ML and optimization techniques. Our ML-Constructive heuristic is trained on small instances. Then, it is able to produce solutions\u2014without losing quality\u2014for large problems as well. We compare our method against classic constructive heuristics, showing that the new approach performs well for TSPLIB instances up to 1748 cities. Although ML-Constructive exhibits an expensive constant computation time due to training, we proved that the computational complexity in the worst-case scenario\u2014for the solution construction after training\u2014is O(n2logn2), n being the number of vertices in the TSP instance.<\/jats:p>","DOI":"10.3390\/a14090267","type":"journal-article","created":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T21:47:21Z","timestamp":1631656041000},"page":"267","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8464-1889","authenticated-orcid":false,"given":"Umberto Junior","family":"Mele","sequence":"first","affiliation":[{"name":"Dalle Molle Institute for Artificial Intelligence (IDSIA), USI-SUPSI, 6962 Lugano, Switzerland"}]},{"given":"Luca Maria","family":"Gambardella","sequence":"additional","affiliation":[{"name":"Dalle Molle Institute for Artificial Intelligence (IDSIA), USI-SUPSI, 6962 Lugano, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0229-0465","authenticated-orcid":false,"given":"Roberto","family":"Montemanni","sequence":"additional","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,14]]},"reference":[{"key":"ref_1","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., and Cook, W.J. (2006). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_2","unstructured":"Matai, R., Singh, S.P., and Mittal, M.L. (2021, September 08). Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches. Available online: https:\/\/www.intechopen.com\/chapters\/12736."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0303-2647(97)01708-5","article-title":"Ant colonies for the travelling salesman problem","volume":"43","author":"Dorigo","year":"1997","journal-title":"Biosystems"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Dell\u2019Amico, M., Montemanni, R., and Novellani, S. (2021). Modeling the flying sidekick traveling salesman problem with multiple drones. Networks.","DOI":"10.1002\/net.22022"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.dam.2012.08.025","article-title":"A hybrid algorithm for the DNA sequencing problem","volume":"163","author":"Caserta","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Montemanni, R., and Gambardella, L.M. (2004). Minimum power symmetric connectivity problem in wireless networks: A new approach. Mobile and Wireless Communication Networks, Proceedings of the IFIP International Conference on Mobile and Wireless Communication Networks, Paris, France, 25\u201327 October 2004, Springer.","DOI":"10.1007\/0-387-23150-1_42"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"527","DOI":"10.3758\/BF03213088","article-title":"Human performance on the traveling salesman problem","volume":"58","author":"MacGregor","year":"1996","journal-title":"Percept. Psychophys."},{"key":"ref_10","unstructured":"Mele, U.J., Gambardella, L.M., and Montemanni, R. (2021, January 23\u201326). Machine Learning Approaches for the Traveling Salesman Problem: A Survey. Proceedings of the IEEE 8th International Conference on Industrial Engineering and Applications, Kyoto, Japan."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","article-title":"Machine learning for combinatorial optimization: A methodological tour d\u2019horizon","volume":"290","author":"Bengio","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","unstructured":"Kool, W., Van Hoof, H., and Welling, M. (2018). Attention, learn to solve routing problems!. arXiv."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mele, U.J., Chou, X., Gambardella, L.M., and Montemanni, R. (2020, January 16\u201318). Reinforcement Learning and Additional Rewards for the Traveling Salesman Problem. Proceedings of the IEEE 7th International Conference on Industrial Engineering and Applications, Bangkok, Thailand.","DOI":"10.1109\/ICIEA49774.2020.9101981"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"da Costa, P.R., Rhuggenaath, J., Zhang, Y., and Akcay, A. (2020, January 18\u201320). Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. Proceedings of the 12th Asian Conference on Machine Learning, Bangkok, Thailand.","DOI":"10.1007\/s42979-021-00779-2"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Zheng, J., He, K., Zhou, J., Jin, Y., and Li, C.M. (2020). Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem. arXiv.","DOI":"10.1609\/aaai.v35i14.17476"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Fu, Z.H., Qiu, K.B., and Zha, H. (2020). Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances. arXiv.","DOI":"10.1609\/aaai.v35i8.16916"},{"key":"ref_17","first-page":"241","article-title":"Deep learning limitations and flaws","volume":"2","author":"Zohuri","year":"2020","journal-title":"Mod. Approaches Mater. Sci."},{"key":"ref_18","unstructured":"Marcus, G. (2018). Deep learning: A critical appraisal. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2014A traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"Orsa J. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"He, K., Zhang, X., Ren, S., and Sun, J. (2016, January 27\u201330). Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA.","DOI":"10.1109\/CVPR.2016.90"},{"key":"ref_21","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"J. Oper. Res. Soc. Am."},{"key":"ref_22","unstructured":"Steiglitz, K. (1968). Some improved algorithms for computer solution of the traveling salesman problem. Proceedings of the 6th Annual Allerton Conference on Communication, Control, and Computing, Department of Electrical Engineering and the Coordinated Science Laboratory, University of Illinois. Available online: https:\/\/www.researchgate.net\/publication\/201976955_Some_Improved_Algorithms_for_Computer_Solution_of_the_Traveling_Salesman_Problem."},{"key":"ref_23","unstructured":"Bentley, J.L. (1990, January 22\u201324). Experiments on traveling salesman heuristics. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., and McGeoch, L.A. (2007). Experimental Analysis of Heuristics for the STSP. The Traveling Salesman Problem and Its Variations, Springer.","DOI":"10.1007\/0-306-48213-4_9"},{"key":"ref_26","unstructured":"Reinelt, G. (2003). The Traveling Salesman: Computational Solutions for TSP Applications, Springer."},{"key":"ref_27","unstructured":"Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer networks. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.M. (2018). Learning heuristics for the tsp by policy gradient. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer.","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"ref_29","unstructured":"Dai, H., Khalil, E.B., Zhang, Y., Dilkina, B., and Song, L. (2017). Learning combinatorial optimization algorithms over graphs. arXiv."},{"key":"ref_30","unstructured":"Ma, Q., Ge, S., He, D., Thaker, D., and Drori, I. (2019). Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.ejor.2018.06.039","article-title":"POPMUSIC for the travelling salesman problem","volume":"272","author":"Taillard","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF00977785","article-title":"Two algorithms for constructing a Delaunay triangulation","volume":"9","author":"Lee","year":"1980","journal-title":"Int. J. Comput. Inf. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Fitzpatrick, J., Ajwani, D., and Carroll, P. (2021). Learning to Sparsify Travelling Salesman Problem Instances. arXiv.","DOI":"10.1007\/978-3-030-78230-6_26"},{"key":"ref_34","unstructured":"Bello, I., Pham, H., Le, Q.V., Norouzi, M., and Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"105400","DOI":"10.1016\/j.cor.2021.105400","article-title":"Reinforcement learning for combinatorial optimization: A survey","volume":"134","author":"Mazyavkina","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_36","unstructured":"Konda, V.R., and Tsitsiklis, J.N. (2000). Actor-critic algorithms. Advances in Neural Information Processing Systems, Citeseer."},{"key":"ref_37","unstructured":"Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group. Technical Report."},{"key":"ref_38","unstructured":"Joshi, C.K., Cappart, Q., Rousseau, L.M., Laurent, T., and Bresson, X. (2020). Learning TSP requires rethinking generalization. arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Miki, S., and Ebara, H. (2019, January 4\u20139). Solving Traveling Salesman Problem with Image-Based Classification. Proceedings of the IEEE 31st International Conference on Tools with Artificial Intelligence, Portland, OR, USA.","DOI":"10.1109\/ICTAI.2019.00156"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Miki, S., Yamamoto, D., and Ebara, H. (2018, January 16\u201317). Applying deep learning and reinforcement learning to traveling salesman problem. Proceedings of the International Conference on Computing, Electronics & Communications Engineering (iCCECE 2018), Southend, UK.","DOI":"10.1109\/iCCECOME.2018.8659266"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","article-title":"Fast algorithms for geometric traveling salesman problems","volume":"4","author":"Bentley","year":"1992","journal-title":"Orsa J. Comput."},{"key":"ref_42","first-page":"1","article-title":"A distance matrix based algorithm for solving the traveling salesman problem","volume":"20","author":"Wang","year":"2018","journal-title":"Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1108\/JDAL-09-2020-0018","article-title":"Comparing greedy constructive heuristic subtour elimination methods for the traveling salesman problem","volume":"4","author":"Jackovich","year":"2020","journal-title":"J. Def. Anal. Logist."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1109\/72.870040","article-title":"The annealing robust backpropagation (ARBP) learning algorithm","volume":"11","author":"Chuang","year":"2000","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1039\/AN9931800455","article-title":"Tutorial review\u2014Outliers in experimental data and their treatment","volume":"118","author":"Miller","year":"1993","journal-title":"Analyst"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/pam.20000","article-title":"The extrapolation problem: How can we learn from the experience of others?","volume":"23","author":"Bardach","year":"2004","journal-title":"J. Policy Anal. Manag."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Hougardy, S., and Schroeder, R.T. (2014). Edge elimination in TSP instances. International Workshop on Graph-Theoretic Concepts in Computer Science, Springer.","DOI":"10.1007\/978-3-319-12340-0_23"},{"key":"ref_48","first-page":"559","article-title":"Imbalanced-learn: A python toolbox to tackle the curse of imbalanced datasets in machine learning","volume":"18","author":"Nogueira","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref_49","unstructured":"Applegate, D. (2021, September 08). Concorde\u2014A Code for Solving Traveling Salesman Problems. Available online: http:\/\/www.math.princeton.edu\/tsp\/concorde.html."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"171085","DOI":"10.1098\/rsos.171085","article-title":"The reproducibility of research and the misinterpretation of p-values","volume":"4","author":"Colquhoun","year":"2017","journal-title":"R. Soc. Open Sci."},{"key":"ref_51","unstructured":"Vitali, T., Mele, U.J., Gambardella, L.M., and Montemanni, R. (2021). Machine Learning Constructives and Local Searches for the Travelling Salesman Problem. arXiv."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10479-005-5724-z","article-title":"A tutorial on the cross-entropy method","volume":"134","author":"Kroese","year":"2005","journal-title":"Ann. Oper. Res."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00992696","article-title":"Simple statistical gradient-following algorithms for connectionist reinforcement learning","volume":"8","author":"Williams","year":"1992","journal-title":"Mach. Learn."},{"key":"ref_54","unstructured":"Van Rossum, G., and Drake, F.L. (1995). Python Tutorial, Centrum voor Wiskunde en Informatica Amsterdam."},{"key":"ref_55","unstructured":"Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. (2017, January 8). Automatic differentiation in pytorch. Proceedings of the 31st Conference on Neural Information Processing System, Long Beach, CA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/9\/267\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:02:35Z","timestamp":1760166155000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/9\/267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,14]]},"references-count":55,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["a14090267"],"URL":"https:\/\/doi.org\/10.3390\/a14090267","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,14]]}}}