Heuristic Algorithms for the Min-Max Traveling Salesman Problem

L’ottimizzazione gioca un ruolo fondamentale nella risoluzione di problemi decisionali del mondo reale, in cui l’obiettivo è massimizzare l’efficienza minimizzando i costi. Il problema del commesso viaggiatore (TSP) è un classico problema di ottimizzazione combinatoria che trova numerose applicazioni nella logistica, nella produzione e nella progettazione di reti. Estendendo questo caso a più agenti, il Multiple Travelling Salesman Problem (mTSP) assegna un insieme di destinazioni (nodi di un grafico) a più venditori, introducendo ulteriore complessità in termini di distribuzione e coordinamento del carico di lavoro. Una variante di questo problema è il Min-Max mTSP, dove l'obiettivo è quello di ridurre al minimo la lunghezza del tour più lungo fra quelli generati per i vari operatori. Questa formulazione è particolarmente rilevante negli scenari che richiedono un’allocazione equilibrata dei compiti, come il routing di veicoli, la robotica e l’assegnazione dei posti di lavoro. A differenza del classico TSP, dove la minimizzazione del costo totale del percorso ha portato ad euristiche ben consolidate, l’obiettivo Min-Max richiede tecniche specializzate per garantire un buon risultato, l’equità tra i tour e l’efficienza computazionale. Questa tesi esplora nuovi approcci per affrontare il Min-Max mTSP, concentrandosi su due aspetti chiave: la distribuzione iniziale dei nodi tra i sotto-tour ed il miglioramento iterativo delle soluzioni verso la convergenza. I metodi di partizionamento tradizionali, come il clustering, non si adattano bene a questo caso, portando a soluzioni iniziali altamente sbilanciate. Per risolvere questo problema, verranno introdotte nuove strategie per costruire configurazioni di nodi più strutturate. Inoltre, saranno sviluppati nuovi metodi di ottimizzazione euristica per esplorare e perfezionare in modo iterativo le soluzioni. In conclusione, combinando l'analisi teorica con la sperimentazione computazionale, questo lavoro mira a fornire metodologie ed idee innovative per risolvere in modo efficiente il Min-Max mTSP. Le tecniche proposte saranno valutate in termini di qualità della soluzione, stabilità e scalabilità.