Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/12/340 |
| _version_ | 1827700126787829760 |
|---|---|
| author | Gianpaolo Ghiani Tommaso Adamo Pierpaolo Greco Emanuela Guerriero |
| author_facet | Gianpaolo Ghiani Tommaso Adamo Pierpaolo Greco Emanuela Guerriero |
| author_sort | Gianpaolo Ghiani |
| collection | DOAJ |
| description | 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 <inline-formula><math display="inline"><semantics><mrow><mn>5</mn><mo>%</mo></mrow></semantics></math></inline-formula> for London, and about <inline-formula><math display="inline"><semantics><mrow><mn>4</mn><mo>%</mo></mrow></semantics></math></inline-formula> for Paris. |
| first_indexed | 2024-03-10T14:05:59Z |
| format | Article |
| id | doaj.art-86fcf640e04f4c939e58395b3d83161b |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T14:05:59Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-86fcf640e04f4c939e58395b3d83161b2023-11-21T00:39:56ZengMDPI AGAlgorithms1999-48932020-12-01131234010.3390/a13120340Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine LearningGianpaolo Ghiani0Tommaso Adamo1Pierpaolo Greco2Emanuela Guerriero3Dipartimento di Ingegneria dell’Innovazione, Università del Salento, via per Monteroni, 73100 Lecce, ItalyDipartimento di Ingegneria dell’Innovazione, Università del Salento, via per Monteroni, 73100 Lecce, ItalyDipartimento di Ingegneria dell’Innovazione, Università del Salento, via per Monteroni, 73100 Lecce, ItalyDipartimento di Ingegneria dell’Innovazione, Università del Salento, via per Monteroni, 73100 Lecce, ItalyIn 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 <inline-formula><math display="inline"><semantics><mrow><mn>5</mn><mo>%</mo></mrow></semantics></math></inline-formula> for London, and about <inline-formula><math display="inline"><semantics><mrow><mn>4</mn><mo>%</mo></mrow></semantics></math></inline-formula> for Paris.https://www.mdpi.com/1999-4893/13/12/340machine learningtravelling salesman problemtime-dependent travel times |
| spellingShingle | Gianpaolo Ghiani Tommaso Adamo Pierpaolo Greco Emanuela Guerriero Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning Algorithms machine learning travelling salesman problem time-dependent travel times |
| title | Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning |
| title_full | Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning |
| title_fullStr | Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning |
| title_full_unstemmed | Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning |
| title_short | Lifting the Performance of a Heuristic for the Time-Dependent Travelling Salesman Problem through Machine Learning |
| title_sort | lifting the performance of a heuristic for the time dependent travelling salesman problem through machine learning |
| topic | machine learning travelling salesman problem time-dependent travel times |
| url | https://www.mdpi.com/1999-4893/13/12/340 |
| work_keys_str_mv | AT gianpaologhiani liftingtheperformanceofaheuristicforthetimedependenttravellingsalesmanproblemthroughmachinelearning AT tommasoadamo liftingtheperformanceofaheuristicforthetimedependenttravellingsalesmanproblemthroughmachinelearning AT pierpaologreco liftingtheperformanceofaheuristicforthetimedependenttravellingsalesmanproblemthroughmachinelearning AT emanuelaguerriero liftingtheperformanceofaheuristicforthetimedependenttravellingsalesmanproblemthroughmachinelearning |