Specialized optimization algorithms for the design/routing traveling salesman problem

The Traveling Salesman Problem with Generalized Latency (TSP-GL) is a combinatorial optimization problem that extends the classical Traveling Salesman Problem by incor- porating routing costs associated with origin-destination demands. This problem arises in applications such as semi-flexible transit systems, logistics, and network design, where minimizing both infrastructure costs and passenger or data transit times is crucial. This thesis presents a Benders decomposition-based approach for solving the TSP-GL efficiently. Benders decomposition splits the problem into a master problem, which de- termines the Hamiltonian circuit, and subproblems, which handle the routing of origin- destination demands as independent minimum-cost flow problems. The decomposition framework allows for a significant reduction in computational complexity compared to solving the full mixed-integer formulation directly. We develop and compare three algorithmic strategies: Benders Branch-and-Cut (BBC), which iteratively refines the master problem with feasibility and optimality cuts; Parallel Benders Branch-and-Cut (PBBC), which accelerates the method by solving subproblems in parallel; and Cutting Plane (CP), which introduces violated constraints dynamically to refine the solution space. Extensive computational experiments on benchmark instances from the TSPGL2 dataset demonstrate the efficiency of these methods in obtaining high- quality solutions within practical time limits. The results highlight the effectiveness of Benders decomposition for large-scale network design problems, particularly in scenarios where traditional optimization techniques strug- gle due to problem size and complexity.

Il Traveling Salesman Problem with Generalized Latency (TSP-GL) è un problema di ottimizzazione combinatoria che estende il classico Problema del Commesso Viaggiatore introducendo costi di instradamento associati a coppie origine-destinazione. Questo prob- lema trova applicazione in settori come i sistemi di trasporto semi-flessibili, la logistica e la progettazione di reti, dove è fondamentale minimizzare sia i costi infrastrutturali sia i tempi di transito di passeggeri o dati. Questa tesi propone un approccio basato sulla decomposizione di Benders per risolvere il TSP-GL in modo efficiente. La decomposizione di Benders suddivide il problema in un master problem, che determina il circuito hamiltoniano, e in sottoproblemi, che gestiscono l’instradamento delle richieste origine-destinazione come problemi indipendenti di flusso a costo minimo. Questo schema di decomposizione consente una significativa riduzione della complessità computazionale rispetto alla risoluzione diretta della formulazione misto- intera completa. Abbiamo sviluppato e confrontato tre strategie algoritmiche: Benders Branch-and-Cut (BBC), che affina iterativamente il master problem con tagli di fattibilità e ottimalità; Parallel Benders Branch-and-Cut (PBBC), che accelera la risoluzione risolvendo i sotto- problemi in parallelo; e Cutting Plane (CP), che introduce vincoli violati dinamicamente per rifinire lo spazio delle soluzioni. Esperimenti computazionali su istanze di benchmark del dataset TSPGL2 dimostrano l’efficienza di questi metodi nell’ottenere soluzioni di alta qualità entro limiti di tempo praticabili. I risultati evidenziano l’efficacia della decomposizione di Benders per problemi di proget- tazione di reti su larga scala, specialmente in scenari in cui le tecniche di ottimizzazione tradizionali risultano inefficaci a causa della dimensione e della complessità del problema.