Il problema del commesso viaggiatore asimmetrico
Creators: name: Utrilla Y Más, Ignacio
Publisher: name: Scuola Universitaria della Svizzera Italiana (SUPSI)
Year: 2023

description: Il problema del commesso viaggiatore asimmetrico rappresenta una delle principali sfide nel campo dell'ottimizzazione combinatoria. L'obiettivo del problema è trovare il percorso di costo minimo che inizia da un punto u, attraversa tutti gli altri punti una sola volta, per poi ritornare al punto di partenza. È fondamentale considerare che, essendo asimmetrico, i costi per andare da u a v possono differire da quelli per andare da v a u. Il lavoro si propone di studiare, riprodurre e implementare parte del lavoro presentato nella tesi di dottorato di Paul Elliot-Magwood. In tale tesi, viene introdotto un metodo euristico, analogo al metodo del simplesso, per esplorare i vertici del politopo associato all'Asymmetric Subtour Elimination Problem (ASEP), che rappresenta la versione rilassata del problema del commesso viaggiatore asimmetrico. L'approccio utilizza l'algoritmo del Depth-First Search (DFS). Uno degli obiettivi primari di questo lavoro è riprodurre i risultati della tesi in esame, in particolare per identificare i vertici che presentano delle “unique cobases”, un concetto fondamentale per l'efficacia dell'algoritmo DFS. Il lavoro 2/3 include anche l'inizializzazione dell'algoritmo e la costruzione della struttura del progetto. I risultati ottenuti confermano i valori presentati dalla tesi in esame riguardo le “unique cobases” per n = {4; 5; 6}, anche se per n = 6 solo 58 dei 59 vertici sono stati identificati per questioni di tempo di elaborazione. Inoltre si è implementato con successo una parte dell'algoritmo DFS in C++. Questi risultati rappresentano un significativo passo avanti nella validazione e nell'applicazione pratica dei concetti teorici esplorati nella tesi di Elliot-Magwood. ____ The asymmetric traveling salesperson problem is well recognized as a significant obstacle within the realm of combinatorial optimization. The objective of the problem is to determine the path with the lowest cost that initiates at a place u, visits all other points exactly once, and ultimately returns to the initial point. It is imperative to acknowledge that, due to their asymmetry, the costs associated with traveling from point u to point v may vary in comparison to the expenses of traveling from point v to point u. This study focus to examine, replicate, and apply certain aspects of the research outlined in Paul Elliot-Magwood's PhD thesis. The thesis presents a heuristic approach that has resemblance to the simplex method. This approach is employed to investigate the vertices of the Asymmetric Subtour Elimination Problem (ASEP) Polytope, which serves as the relaxed variant of the asymmetric traveling salesperson problem. The methodology employs the Depth-First Search (DFS) algorithm. The main objective of this study is to replicate the findings of the mentioned thesis, with a specific focus on the identification of vertices with “unique cobases”. This idea is crucial for the efficacy of the Depth-First Search (DFS) algorithm. The study also encompasses the initiation of the algorithm and the establishment of the project structure. The findings obtained validate the assertions made in this thesis on the existence of “unique cobases” for values of n = {4;5;6}. However, it should be noted that for n = 6, only 58 out of the total 59 vertices were successfully detected due to limitations in processing time. Furthermore, a component of the Depth-First Search (DFS) algorithm was effectively implemented using the C++ programming language. The findings presented herein signify a substantial advancement in the verification and pragmatic implementation of the theoretical principles investigated inside the Elliot-Magwood dissertation.