Neural Combinatorial Optimization for the Context-Aware Travelling Salesman Problem

Neural Combinatorial Optimization (NCO) has emerged in recent years as a useful paradigm for solving combinatorial optimization problems, especially when the problem size makes the use of exact methods impractical. The application of NCO in dynamic settings, particularly in routing problems, is still limited, despite the fact that Machine Learning (ML) — and especially Deep Reinforcement Learning (DRL) — offers predictive capabilities that are particularly valuable for problems evolving over time. This thesis presents a tutorial on NCO in general, with a particular focus on its application to the Travelling Salesman Problem (TSP). It then analyzes the use of ML for dynamic routing problems, highlighting that DRL is the most widely adopted paradigm. Finally, it intro- duces our proposed approach, which defines a new model for the Dynamic TSP, called the Context-Aware TSP. This model aims to better reflect real-world conditions, as the dynamics of edge travel times depend on external factors such as traffic, weather, day, and time of the week. A major contribution of this work is the implementation of the model using a traffic simulator, creating a realistic environment for the agent to interact with. The problem is then solved using a NCO approach based on DRL, specifically the Proximal Policy Optimization algorithm. The results show that NCO can learn a policy capable of generating high-quality solutions in very short computation times. However, in scenarios where traffic conditions remain relatively stable over time, a MILP-based method using static but contextually accurate data can achieve comparable or even better performance.

La Neural Combinatorial Optimization (NCO) è emersa negli anni recenti come un paradigma utile per risolvere problemi di ottimizzazione combinatoria, soprattutto quando la dimensione del problema rende impraticabile l'uso di metodi esatti. L'applicazione della NCO in contesti dinamici, in particolare nei problemi di routing, è ancora limitata, nonostante il Machine Learning (ML) — e soprattutto il Deep Reinforcement Learning (DRL) — offra capacità predittive particolarmente preziose per i problemi che evolvono nel tempo. Questa tesi presenta un tutorial sulla NCO in generale, con un focus particolare sulla sua applicazione al Problema del Commesso Viaggiatore (TSP). Analizza poi l'uso dell'ML per problemi di routing dinamico, evidenziando che il DRL è il paradigma più ampiamente adottato. Infine, introduce l'approccio da noi proposto, che definisce un nuovo modello per il TSP Dinamico (Dynamic TSP), denominato Context-Aware TSP. Questo modello mira a riflettere meglio le condizioni reali, in cui l'evoluzione dei tempi di percorrenza degli archi dipende da fattori esterni come traffico, meteo, giorno e ora della settimana. Un contributo importante di questo lavoro è l'implementazione del modello usando un simulatore di traffico, che crea un ambiente realistico con cui l'agente interagisce. Il problema viene quindi risolto utilizzando un approccio NCO basato sul DRL, e in particolare utilizzando l'algoritmo Proximal Policy Optimization. I risultati mostrano che la NCO può apprendere una policy capace di generare soluzioni di qualità in tempi di calcolo molto ridotti. Tuttavia, in scenari in cui le condizioni del traffico rimangono relativamente stabili nel tempo, un metodo basato sulla MILP che utilizza dati statici ma contestualmente accurati può ottenere prestazioni comparabili o persino migliori.