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.
2020
7th IEEE International Conference on Industrial Engineering and Applications, ICIEA 2020
Paris
14-15 January 2020
170
176
Mele, Umberto Junior; Chou, Xiaochen; Gambardella, Luca Maria; Montemanni, Roberto
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].
File in questo prodotto:
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

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1203460
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact