Problema di Pattugliamento Automobilistico: Algoritmi per un'Applicazione Reale

This Ph.D. thesis addresses a Car Patrolling Problem derived from a real-world application faced by a large Italian service provider, by developing a number of optimization algorithms. In summary, the car patrolling problem that we face is a generalization of the well-known team orienteering problem. A set of customers requires a variety of security related services that they want to be performed in their properties according to a weekly planning. On the basis of the customers’ demands, the company deploys patrols that will perform the requested services. The goal of the research is to optimize and improve the service provision using algorithmic methods, possibly improving both customers satisfaction and reducing company costs. The research was conducted sequentially as requirements appeared during its development, and hence the overall original problem was divided into three problems. The first problem involves the routing of the patrols in their original territories. It is a deterministic variant of the team orienteering problem, where not all the vertices are required to be visited and may induce a profit when visited. The problem was mathematically formalized using integer linear programming, and subsequentially a metaheuristic algorithm based on Variable Neighborhood Search (VNS) was developed in order to effectively address the company's real-world instances. Then, we moved to the territory division component by extending the previous problem. In particular, we considered the option of changing the original territories, by proposing new partitions of the customers, in order to obtain a subsequent better routing of the patrols. Here, we explored several methods based on clustering algorithms as well as on integer linear programming models, with the aim to generate alternative territory divisions from the ones already in use by the company. For each possible clustering solution, the routing was performed with variants of the MILP model and VNS developed for this first problem. By means of extensive computational results, we demonstrate that changing the territory configuration might be beneficial in terms of better customers satisfaction and reduced costs. Lastly, the third problem still considers territory division and patrol routing, but is also takes into account the stochastic nature of the demands for alarm's triggering response. Using a two-phase stochastic modelling, we consider a set of scenarios that represent the possible stochastic realizations of the alarm triggers, in order to define routes that are resilient to such occurrences. The scenarios are created by considering a large historical database of alarms. The problem was solved both with a MILP and with a heuristic. This final algorithm encloses the entirety of the company operations, and makes the decision process for the managers more efficient. Overall, this thesis has positively addressed a very general real-world problem with numerous practical challenges, providing efficient optimization algorithms and leading to improved problem solutions.

Questa tesi di dottorato affronta un problema di pattugliamento automobilistico derivato da un'applicazione reale affrontata da un grande fornitore di servizi italiano, sviluppando una serie di algoritmi di ottimizzazione. In sintesi, il problema del pattugliamento automobilistico che affrontiamo è una generalizzazione del noto problema di orienteering a squadre. Un insieme di clienti richiede una varietà di servizi legati alla sicurezza che desiderano vengano eseguiti nelle loro proprietà secondo una pianificazione settimanale. Sulla base delle richieste dei clienti, l'azienda schiera pattuglie che eseguono i servizi richiesti. L'obiettivo della ricerca è ottimizzare e migliorare la fornitura del servizio utilizzando metodi algoritmici, migliorando possibilmente sia la soddisfazione dei clienti che riducendo i costi aziendali. La ricerca è stata condotta in modo sequenziale man mano che i requisiti emergevano durante il suo sviluppo, e quindi il problema originale è stato suddiviso in tre problemi. Il primo problema riguarda l'instradamento delle pattuglie nei loro territori originali. Si tratta di una variante deterministica del problema di orienteering a squadre, in cui non tutti i vertici devono essere visitati e possono generare un profitto quando visitati. Il problema è stato formalizzato matematicamente utilizzando la programmazione lineare intera, e successivamente è stato sviluppato un algoritmo metaeuristico basato sulla Ricerca a Vicinato Variabile (VNS) per affrontare in modo efficace le istanze reali dell'azienda. Successivamente, siamo passati al componente di divisione del territorio estendendo il problema precedente. In particolare, abbiamo considerato l'opzione di modificare i territori originali, proponendo nuove partizioni dei clienti, al fine di ottenere un migliore instradamento delle pattuglie. Qui, abbiamo esplorato diversi metodi basati su algoritmi di clustering e modelli di programmazione lineare intera, con l'obiettivo di generare divisioni territoriali alternative rispetto a quelle già utilizzate dall'azienda. Per ciascuna possibile soluzione di clustering, l'instradamento è stato eseguito con varianti del modello MILP e del VNS sviluppati per il primo problema. Attraverso risultati computazionali estensivi, dimostriamo che cambiare la configurazione del territorio può essere vantaggioso in termini di migliore soddisfazione dei clienti e riduzione dei costi. Infine, il terzo problema considera ancora la divisione del territorio e l'instradamento delle pattuglie, ma tiene conto anche della natura stocastica delle richieste di risposta agli allarmi. Utilizzando una modellazione stocastica a due fasi, consideriamo un insieme di scenari che rappresentano le possibili realizzazioni stocastiche degli allarmi, al fine di definire percorsi resilienti a tali occorrenze. Gli scenari sono creati considerando un ampio database storico di allarmi. Il problema è stato risolto sia con un modello MILP che con una soluzione euristica. Questo algoritmo finale racchiude l'intera operazione aziendale e rende il processo decisionale per i dirigenti più efficiente. Nel complesso, questa tesi ha affrontato positivamente un problema reale molto generale con numerose sfide pratiche, fornendo algoritmi di ottimizzazione efficienti e portando a soluzioni migliorate del problema.