Optimizing inspection routes and schedules for infrastructure systems under stochastic decision-dependent failures
研究了多车辆（如无人机）巡检基础设施的路线与调度问题，考虑随机旅行时间、检查时长和决策依赖的失效风险，提出基于场景分解的算法，在大型网络上实现低于4%的最优性差距。
Effective monitoring is vital for maintaining interconnected infrastructure systems, where components are prone to failure without proper servicing. However, designing inspection routes remains computationally difficult due to high complexity and inherent uncertainties of large-scale infrastructure systems. This paper investigates the deployment of multi-vehicle fleets, such as unmanned aerial vehicles (UAVs), to inspect spatially distributed components subject to uncertain travel times, inspection durations, and failure risks. Notably, the probability of component failure depends on inspection timing, creating decision-dependent (endogenous) uncertainty. We model this as a variant of a stochastic multi-vehicle routing problem and formulate a two-stage stochastic mixed-integer program based on finite samples. We propose a scenario decomposition framework that integrates column generation and random coloring techniques to accelerate subproblem resolution. We further provide theoretical analyses of the algorithm’s finite convergence and optimality guarantees under a user-specified probabilistic error tolerance. Numerical experiments on networks of varying topologies, including IEEE and EPANET systems, demonstrate the computational efficiency and effectiveness of our approaches. Across all large instances, our algorithm achieves an optimality gap below 4% and consistently outperforms state-of-the-art optimization solvers and the adaptive large neighborhood search as a heuristic benchmark.