RESILIENT AND PREDICTIVE MULTI-DEPOT ARC ROUTING FOR RECHARGEABLE AND CAPACITY-CONSTRAINED VEHICLES WITH UNCERTAIN FAILURES

Abstract

The deployment of battery-operated Unmanned Aerial Vehicles (UAVs) has steadily expanded for the surveillance and inspection of critical infrastructure, driven by their flexibility, cost-effectiveness, and capability for repeated missions. One vital application is the continuous monitoring of hazardous winter road conditions, such as black ice formation, which poses severe risks to public safety. However, utilizing autonomous UAVs for large-scale, time-sensitive monitoring introduces substantial operational and logistical complexities. This dissertation formally models these challenges as the Multi-Depot Rural Postman Problem with Rechargeable and Reusable Vehicles (MD-RPP-RRV), wherein UAVs with finite battery capacities must be dispatched from multiple bases to inspect spatially distributed road segments selected based on expert-recommendations, undergo frequent recharging, and ensure timely data collection. Beyond the core deterministic routing problem, real-world operational conditions introduce critical layers of disruption and uncertainty. In practice, UAVs operate in harsh environments where prolonged exposure leads to stochastic in-mission vehicle failures. Such disruptions sever planned routes and leave critical road segments uninspected, severely compromising system reliability. To address this, this research develops robust reactive rescheduling strategies, specifically introducing centralized and peer-to-peer auction algorithms. By enabling the surviving UAVs to dynamically bid on and autonomously reallocate abandoned tasks, these auction mechanisms facilitate efficient, real-time schedule recovery and maintain high coverage levels despite unexpected vehicle losses. Furthermore, while traditional routing models rely on static inputs, real-world hazard formation is inherently dynamic and governed by significant meteorological uncertainty. Relying on static historical data often leads to inefficient inspections that prioritize safe roads while active hazards remain undetected. To effectively manage this spatio-temporal uncertainty, this dissertation proposes a comprehensive closed-loop predictive routing framework that tightly integrates machine learning with combinatorial optimization. A Temporal Graph Neural Network (TGNN) processes sequential weather data to estimate time-varying hazard probabilities for specific road segments. These updated probabilities subsequently drive a memory-augmented Simulated Annealing metaheuristic, which dynamically generates inspection routes to maximize expected hazard coverage while adhering to strict operational vehicle constraints. The primary contributions of this research advance the field of autonomous monitoring by bridging the critical gap between static routing models and dynamic operational uncertainties. First, it expands the theoretical boundaries of arc routing by formulating the MD-RPP-RRV to explicitly integrate multiple depots, finite battery capacities, and periodic recharging constraints, simultaneously providing scalable metaheuristics that overcome the computational limitations of exact solvers on large networks. Second, it contributes novel reactive rescheduling frameworks utilizing centralized and peer-to-peer auction mechanisms. Unlike traditional methods that require complete global rescheduling, these algorithms guarantee real-time mission recovery and establish theoretical performance bounds during stochastic mid-flight vehicle failures. Finally, it introduces a closed-loop predictive routing framework that integrates machine learning forecasts directly with combinatorial optimization. Unlike traditional routing frameworks restricted by static networks, this framework continuously predicts dynamic environmental risks and adapts vehicle routes in response to changing weather forecasts. By developing and integrating memory-based routing techniques to bypass redundant calculations, the framework ensures computational tractability while managing rapidly evolving and uncertain environments.