logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-02022023-160628


Tipo di tesi
Tesi di laurea magistrale
Autore
MARTELLI, ILARIA
URN
etd-02022023-160628
Titolo
Ant Colony Optimization for the Dubins Traveling Salesman Problem
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA ROBOTICA E DELL'AUTOMAZIONE
Relatori
relatore Pallottino, Lucia
Parole chiave
  • alternating algorithm
  • ant colony optimization
  • Dubins traveling salesman problem
  • pulley algorithm
Data inizio appello
23/02/2023
Consultabilità
Completa
Riassunto
La tesi presenta un programma che implementa l'algoritmo euristico Ant Colony Optimization (ACO) per la risoluzione del problema del commesso viaggiatore nella variante di Dubins (DTSP); esso unisce quindi la ricerca del percorso più breve che tocchi un set di punti con i vincoli cinematici della macchina di Dubins.
Per poter convertire un insieme ordinato di waypoints in un tour di Dubins, sono stati provati due diversi approcci, il semplice Alternating Algorithm (AA) e il più recente Pulley Algorithm (PA).
Infine viene effettuata un'analisi statistica per confrontare i risultati.

The thesis presents a program that implements the Ant Colony Optimization (ACO) heuristic algorithm for solving the traveling salesman problem in Dubins' variant (DTSP); it therefore combines the search for the shortest path touching a set of points with the kinematic constraints of the Dubins car.
In order to convert an ordered set of waypoints into a Dubins tour, two different approaches were tried, the simple Alternating Algorithm (AA) and the more recent Pulley Algorithm (PA).
Finally, a statistical analysis is performed to compare the results.
File