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.
Notice of Removal: Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem / Mele, Umberto Junior; Chou, Xiaochen; Gambardella, Luca Maria; Montemanni, Roberto. - (2020), pp. 170-176. (Intervento presentato al convegno 7th IEEE International Conference on Industrial Engineering and Applications, ICIEA 2020 tenutosi a Paris nel 14-15 January 2020) [10.1109/ICIEA49774.2020.9101981].
Notice of Removal: Reinforcement Learning and Additional Rewardsfor the Traveling Salesman Problem
Montemanni, Roberto
2020
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 | |
---|---|---|---|
iciea2021europe-27.pdf
Accesso riservato
Tipologia:
VOR - Versione pubblicata dall'editore
Dimensione
722.08 kB
Formato
Adobe PDF
|
722.08 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