Esplorazione delle soluzioni al problema del commesso viaggiatore: dagli algoritmi esatti al Red-Black Ant Colony System

This thesis embarks on a comprehensive exploration of the Travelling Salesman Problem (TSP), a cornerstone problem in the field of computational optimization, known for its straightfor- ward premise yet complex resolution. At the core of this investigation lies a dual objective: to dissect the intricate nature of TSP through various algorithmic lenses and to introduce a variant of the Ant Colony Optimization (ACO) technique, termed the Red-Black Ant Colony System, aimed at enhancing solution efficiency and accuracy.

Questa tesi intraprende un'esplorazione approfondita del Problema del Commesso Viaggiatore (TSP), un problema fondamentale nel campo dell'ottimizzazione computazionale, noto per la sua premessa semplice ma risoluzione complessa. Al centro di questa indagine c'è un duplice obiettivo: analizzare la natura intricata del TSP attraverso varie prospettive algoritmiche e introdurre una variante della tecnica di Ottimizzazione a Colonia di Formiche (ACO), denominata Sistema a Colonia di Formiche Rosso-Nero, mirata a migliorare l'efficienza e l'accuratezza della soluzione.