Studio e implementazione di algoritmi per la stima delle frequenze di conflitti tra veicoli sincronizzati su grafi a griglia

The Fleet Quickest Routing Problem on a Grid graph (FQRP-G), the subject of this thesis, is a vehicle routing problem. In said problem, some vehicles are initially placed on the first level of a grid and are to cross it to reach their destination on the opposite side. All the vehicles start at the same time and move at the same speed. The most efficient way for each vehicle to move is along one of the shortest paths between its starting point end its destination, without any stop in between. Such paths must be chosen carefully in order to avoid any collision on nodes or arcs of the grid. This thesis is about analysis and classification of conflicts, i.e. pairs of vehicles which may collide. The conflicts have been classified and divided into many types. The applicability and efficiency of possible solutions depend on which types of conflicts are present. For this reason, the study of the frequency in which each type of conflict occurs may be interesting. Thus the frequency of each conflict type will be analysed, theoretically. Then three algorithms to calculate such frequencies will be discussed. In particular, the algorithms will: calculate the number of conflicts in a given FQRP-G instance, calculate the exact average number of conflicts and their statistical distribution given the problem size and, lastly, estimate the average number of conflicts and their statistical distribution given the problem size.

Il Fleet Quickest Routing Problem su grafo a Griglia (FQRP-G) è un problema di instradamento su grafi, oggetto di questa tesi. Nel problema in esame alcuni veicoli sono inizialmente posti su un lato di una griglia e devono attraversarla per raggiungere le loro destinazioni, poste sul lato opposto. I veicoli partono tutti contemporaneamente e si muovono con la stessa velocità. Il modo più efficiente per movimentare ciascun veicolo suggerisce di utilizzare un percorso di lunghezza minima tra l'origine e la destinazione, senza fermate intermedie. Tali percorsi vanno però scelti in modo accurato, per evitare collisioni sui nodi o sugli archi della rete. Questa tesi si basa sull'analisi e classificazione dei conflitti, ovvero delle coppie di veicoli i cui percorsi minimi possono generare collisioni. I conflitti sono stati classificati e suddivisi in tipologie. L'applicabilità e l'efficienza dei modelli e delle procedure di soluzione del FQRP-G dipendono dalla presenza o meno di specifiche tipologie. Risulta pertanto interessante effettuare uno studio per valutare le frequenze dei conflitti, distinguendo tra le tipologie. Verrà analizzata teoricamente la frequenza delle varie categorie di conflitto. Successivamente verranno presentati degli algoritmi volti a una stima empirica delle stesse frequenze. In particolare, verranno presentati: un algoritmo per il calcolo del numero dei conflitti in una data istanza di FQRP-G; un algoritmo per il calcolo esatto del numero medio di conflitti, per tipo, in funzione della dimensione del problema e la determinazione della loro distribuzione statistica; per il calcolo stimato del numero medio di conflitti, per tipo, in funzione della dimensione del problema e la determinazione della loro distribuzione statistica.