{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T15:41:48Z","timestamp":1740152508371,"version":"3.37.3"},"reference-count":40,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:00:00Z","timestamp":1607904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"In recent years, there have been several attempts to use machine learning techniques to improve the performance of exact and approximate optimization algorithms. Along this line of research, the present paper shows how supervised and unsupervised techniques can be used to improve the quality of the solutions generated by a heuristic for the Time-Dependent Travelling Salesman Problem with no increased computing time. This can be useful in a real-time setting where a speed update (or the arrival of a new customer request) may lead to the reoptimization of the planned route. The main contribution of this work is to show how to reuse the information gained in those settings in which instances with similar features have to be solved over and over again, as it is customary in distribution management. We use a method based on the nearest neighbor procedure (supervised learning) and the K-means algorithm with the Euclidean distance (unsupervised learning). In order to show the effectiveness of this approach, the computational experiments have been carried out for the dataset generated based on the real travel time functions of two European cities: Paris and London. The overall average improvement of our heuristic over the classical nearest neighbor procedure is about 5% for London, and about 4% for Paris.<\/jats:p>","DOI":"10.3390\/a13120340","type":"journal-article","created":{"date-parts":[[2020,12,15]],"date-time":"2020-12-15T02:25:08Z","timestamp":1607999108000},"page":"340","source":"Crossref","is-referenced-by-count":2,"title":["Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning"],"prefix":"10.3390","volume":"13","author":[{"given":"Gianpaolo","family":"Ghiani","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Innovazione, Universit\u00e0 del Salento, via per Monteroni, 73100 Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9505-5869","authenticated-orcid":false,"given":"Tommaso","family":"Adamo","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Innovazione, Universit\u00e0 del Salento, via per Monteroni, 73100 Lecce, Italy"}]},{"given":"Pierpaolo","family":"Greco","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Innovazione, Universit\u00e0 del Salento, via per Monteroni, 73100 Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8959-5017","authenticated-orcid":false,"given":"Emanuela","family":"Guerriero","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria dell\u2019Innovazione, Universit\u00e0 del Salento, via per Monteroni, 73100 Lecce, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,14]]},"reference":[{"key":"ref_1","unstructured":"Michel, G., and Potvin, J.Y. (2010). Handbook of Metaheuristics, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.cor.2017.01.021","article-title":"MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration","volume":"83","author":"Adamo","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1109\/TII.2017.2786782","article-title":"Nature inspired methods and their industry applications\u2014Swarm intelligence algorithms","volume":"14","author":"Slowik","year":"2018","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Brezo\u010dnik, L., Fister, I., and Podgorelec, V. (2018). Swarm intelligence algorithms for feature selection: A review. Appl. Sci., 8.","DOI":"10.3390\/app8091521"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1016\/j.compeleceng.2017.09.016","article-title":"A bio-inspired swarm intelligence technique for social aware cognitive radio handovers","volume":"71","author":"Umamaheswari","year":"2018","journal-title":"Comput. Electr. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1016\/j.renene.2018.11.061","article-title":"Research and application based on the swarm intelligence algorithm and artificial intelligence for wind farm decision system","volume":"134","author":"Zhao","year":"2019","journal-title":"Renew. Energy"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Dulebenets, M.A., Kavoosi, M., Abioye, O., and Pasha, J. (2018). A self-adaptive evolutionary algorithm for the berth scheduling problem: Towards efficient parameter control. Algorithms, 11.","DOI":"10.3390\/a11070100"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"134743","DOI":"10.1109\/ACCESS.2020.3010176","article-title":"An Optimization Model and Solution Algorithms for the Vehicle Routing Problem With a \u201cFactory-in-a-Box\u201d","volume":"8","author":"Pasha","year":"2020","journal-title":"IEEE Access"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s11750-017-0451-6","article-title":"On learning and branching: A survey","volume":"25","author":"Lodi","year":"2017","journal-title":"Top"},{"key":"ref_10","unstructured":"Bengio, Y., Lodi, A., and Prouvost, A. (2018). Machine learning for combinatorial optimization: A methodological tour d\u2019horizon. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1137\/S0363012991196414","article-title":"Continuous-time shortest path problems and linear programming","volume":"32","author":"Philpott","year":"1994","journal-title":"SIAM J. Control. Optim."},{"key":"ref_12","unstructured":"Uslan, V., and Bucak, I.O. (2010, January 12\u201314). A comparative study of machine learning heuristic algorithms to solve the traveling salesman problem. Proceedings of the 3rd International Conference on the Applications of Digital Information Web Technologies (ICADIWT), Istanbul, Turkey."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","article-title":"Time-dependent routing problems: A review","volume":"64","author":"Gendreau","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_14","first-page":"185","article-title":"Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms","volume":"26","author":"Malandraki","year":"1992","journal-title":"Transp. Ence"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0377-2217(94)00299-1","article-title":"A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem","volume":"90","author":"Malandraki","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","unstructured":"Sharda, R., Vo\u00df, S., Golden, B., Raghavan, S., and Wasil, E. (2005). Solving the time dependent traveling salesman problem. The Next Wave in Computing, Optimization, and Decision Technologies, Springer."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0378-4371(02)01078-6","article-title":"The time-dependent traveling salesman problem","volume":"314","author":"Schneider","year":"2002","journal-title":"Phys. Stat. Mech. Appl."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1057\/jors.2012.17","article-title":"Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs","volume":"64","author":"Harwood","year":"2013","journal-title":"J. Oper. Res. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cordeau, J.-F., Ghiani, G., and Guerriero, E. (2014). Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem. Transp. Sci.","DOI":"10.1287\/trsc.1120.0449"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1002\/net.21830","article-title":"A branch-and-bound algorithm for the time-dependent travelling salesman problem","volume":"72","author":"Arigliano","year":"2018","journal-title":"Networks"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"104795","DOI":"10.1016\/j.cor.2019.104795","article-title":"An enhanced lower bound for the time-dependent travelling salesman problem","volume":"113","author":"Adamo","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Melgarejo, P.A., Laborie, P., and Solnon, C. (2015). A time-dependent no-overlap constraint: Application to urban delivery problems. International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems, Springer.","DOI":"10.1007\/978-3-319-18008-3_1"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/j.ejor.2006.09.099","article-title":"An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation","volume":"189","author":"Albiach","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.dam.2018.09.017","article-title":"Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm","volume":"261","author":"Arigliano","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_25","unstructured":"Hewitt, M., Boland, N., Vu, M.D., and Savelsbergh, M. (2020, November 30). Solving Time Dependent Traveling Salesman with Time Windows Problems. Available online: http:\/\/www.optimization-online.org\/DB_FILE\/2018\/05\/6640.pdf."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.cor.2017.06.026","article-title":"An integer programming approach for the time-dependent traveling salesman problem with time windows","volume":"88","author":"Isabel","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0196-6774(03)00075-0","article-title":"The moving-target traveling salesman problem","volume":"49","author":"Helvig","year":"2003","journal-title":"Algorithms"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1287\/trsc.1060.0181","article-title":"The robust traveling salesman problem with interval data","volume":"41","author":"Montemanni","year":"2007","journal-title":"Transp. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","article-title":"A classification of formulations for the (time-dependent) traveling salesman problem","volume":"83","author":"Gouveia","year":"1995","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1287\/opre.28.4.1018","article-title":"An n-constraint formulation of the (time-dependent) traveling salesman problem","volume":"28","author":"Fox","year":"1980","journal-title":"Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.dam.2011.11.019","article-title":"Natural and extended formulations for the time-dependent traveling salesman problem","volume":"164","author":"Godinho","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.endm.2010.05.045","article-title":"An integer programming approach for the time-dependent TSP","volume":"36","author":"Zabala","year":"2010","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/opre.26.1.86","article-title":"The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling","volume":"26","author":"Picard","year":"1978","journal-title":"Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2635","DOI":"10.1016\/j.cor.2006.12.021","article-title":"A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times","volume":"35","author":"Stecco","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1002\/(SICI)1520-6750(199609)43:6<797::AID-NAV2>3.0.CO;2-#","article-title":"An exact solution approach for the time-dependent traveling-salesman problem","volume":"43","author":"Wiel","year":"1996","journal-title":"Nav. Res. Logist."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1287\/trsc.2013.0491","article-title":"A Note on the Ichoua, Gendreau, and Potvin (2003) Travel Time Model","volume":"48","author":"Ghiani","year":"2014","journal-title":"Transp. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Adamo, T., Ghiani, G., and Guerriero, E. (2020). On path ranking in time-dependent graphs. arXiv.","DOI":"10.1016\/j.cor.2021.105446"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Aggarwal, C. (2018). Neural Networks and Deep Learning, Springer.","DOI":"10.1007\/978-3-319-94463-0"},{"key":"ref_39","unstructured":"MacQueen, J. (July, January 21). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Oakland, CA, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1002\/col.1049","article-title":"The development of the cie 2000 colour-difference formula: Ciede2000","volume":"26","author":"Luo","year":"2001","journal-title":"Color Res. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/340\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T11:09:48Z","timestamp":1720264188000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,14]]},"references-count":40,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120340"],"URL":"https:\/\/doi.org\/10.3390\/a13120340","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,12,14]]}}}