A comprehensive literature on the Traveling Salesman Problem (TSP) is available, and this problem has become a valuable benchmark to test new heuristic methods for general Combinatorial Optimisation problems. For this reason, recently developed Deep Learning-driven heuristics have been tried on the TSP. These Deep Learning frameworks use the city coordinates as inputs, and are trained using reinforcement learning to predict a distribution over the TSP feasible solutions. The aim of the present work is to show how easy-to-calculate Combinatorial Optimization concepts can improve the performances of such systems. In particular, we show how passing Minimum Spanning Tree information during training can lead to significant improvements to the quality of TSP solutions.As a side result, we also propose a Deep Learning architecture able to predict in real time the optimal length of a TSP instance.The proposed architectures have been tested on random 2D Euclidean graphs with 50 and 100 nodes, showing significant results.
Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem / Mele, Uj; Chou, Xc; Gambardella, Lm; Montemanni, R. - (2021), pp. 198-204. (Intervento presentato al convegno 8th International Conference on Industrial Engineering and Applications, ICIEA 2021-Europe tenutosi a esp nel 2021) [10.1145/3463858.3463885].
Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem
Montemanni, R
2021
Abstract
A comprehensive literature on the Traveling Salesman Problem (TSP) is available, and this problem has become a valuable benchmark to test new heuristic methods for general Combinatorial Optimisation problems. For this reason, recently developed Deep Learning-driven heuristics have been tried on the TSP. These Deep Learning frameworks use the city coordinates as inputs, and are trained using reinforcement learning to predict a distribution over the TSP feasible solutions. The aim of the present work is to show how easy-to-calculate Combinatorial Optimization concepts can improve the performances of such systems. In particular, we show how passing Minimum Spanning Tree information during training can lead to significant improvements to the quality of TSP solutions.As a side result, we also propose a Deep Learning architecture able to predict in real time the optimal length of a TSP instance.The proposed architectures have been tested on random 2D Euclidean graphs with 50 and 100 nodes, showing significant results.File | Dimensione | Formato | |
---|---|---|---|
3463858.3463885.pdf
Accesso riservato
Tipologia:
Versione pubblicata dall'editore
Dimensione
775.31 kB
Formato
Adobe PDF
|
775.31 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris