Paths and Tours on Graphs: variants and extensions in the context of autonomous vehicles

Abstract: Human beings have always tried to find the best possible path to move from one location to another. Often, the best path means the shortest one. Even if the transport system never stopped changing, the problem of finding a shortest path is still valid and widely discussed. Nowadays, we are looking at a rapid diffusion of autonomous vehicles, such as drones, robots, forklifts, and cars. In this context, the problem of finding, in a reasonable amount of time several paths or tours, is becoming extremely important in various fields. The Shortest Path Problem (SPP) and the Vehicle Routing Problem (VRP) are defined to formalize these scenarios. The SPP aims to find a minimum length path that connects a source node s and a target node d. The SPP is known to be solvable in polynomial time using various algorithms [62]. Nevertheless, several variants of the problem, which have many practical applications in the real world, are NP-Hard [69]. Furthermore, another interesting application field concerns the definition of a tour of minimum length that allows, for example, a carrier to serve all its clients and then go back to its deposit. For this reason, problems such as the Vehicle Routing Problem (VRP)[70], Travelling Salesman Problem (TSP)[65] [74], Arc Routing Problem (ARP)[56], and so on, have growing interest in the community of researchers. In this thesis, we propose an overview of path and tour problems in the context of autonomous vehicles. In particular, concerning the definition of paths of minimum length, we present a new variant of the Shortest Path Problem, namely the Concurrent Shortest Path Problem which considers the possibility of having a set of autonomous vehicles that tries to find a path of minimum length while avoiding collisions. Then we present an exact reduction technique for the k-Colour Shortest Path Problem that considers the possibility of having a multi-modal transport system. For both of them, we propose exact and heuristic algorithms. Furthermore, while focusing on the definition of tours for drones, we present a new variant of the TSP, that is the Close-Enough Generalized Routing Problem, that combines the properties of the Close-Enough Travelling Salesman Problem (CETSP) and the Close-Enough Arc Routing Problem (CEARP).

Abstract: Gli esseri umani hanno sempre cercato di trovare il miglior percorso possibile per spostarsi da un luogo all'altro. Spesso, per percorso migliore si intende quello più breve. Anche se il sistema dei trasporti non ha mai smesso di cambiare, il problema di trovare il percorso più breve è ancora valido e ampiamente discusso. Oggi si assiste a una rapida diffusione di veicoli autonomi, come droni, robot, carrelli elevatori e automobili. In questo contesto, il problema di trovare, in un tempo ragionevole, diversi percorsi o itinerari, sta diventando estremamente importante in vari campi. Il problema dei cammini minimi (Shortest Path Problem, SPP) e il problema dell'instradamento dei veicoli (Vehicle Routing Problem, VRP) sono stati definiti per formalizzare questi scenari. Lo SPP mira a trovare un percorso di lunghezza minima che colleghi un nodo sorgente s e un nodo destinazione d. È noto che lo SPP è risolvibile in tempo polinomiale utilizzando vari algoritmi. Tuttavia, diverse varianti del problema, che hanno molte applicazioni pratiche nel mondo reale, sono NP-Hard. Un altro campo di applicazione interessante riguarda la definizione di un tour di lunghezza minima che permetta, per esempio, a un fornitore di servire tutti i suoi clienti e poi tornare al suo deposito. Per questo motivo, problemi come il Vehicle Routing Problem (VRP), il Travelling Salesman Problem (TSP), l'Arc Routing Problem (ARP), e così via, stanno riscontrando un interesse crescente nella comunità dei ricercatori. In questa tesi, proponiamo una panoramica dei problemi di definizione di percorsi e tour nel contesto dei veicoli autonomi. In particolare, per quanto riguarda la definizione di percorsi di lunghezza minima, presentiamo una nuova variante del problema dei cammini minimi, definito come Concurrent Shortest Path Problem, che considera la possibilità di avere un insieme di veicoli autonomi che cercano di trovare un percorso di lunghezza minima evitando collisioni. Presentiamo una tecnica esatta di riduzione del grafo per il k-Colour Shortest Path Problem che prende in considerazione la possibilità di avere un sistema di trasporto multimodale definito su grafi colorati. Per entrambi proponiamo algoritmi esatti ed euristici. Infine, concentrandoci sulla definizione di tour per i droni, presentiamo una nuova variante del TSP, ovvero il Close-Enough Generalized Routing Problem, che combina le proprietà del Close-Enough Travelling Salesman Problem (CETSP) e del Close-Enough Arc Routing Problem (CEARP).