Progressive lower bound evaluation for urban road renovation scheduling

Urban infrastructure degrades over time, necessitating periodic renovation to maintain functionality and safety. When renovation is delayed beyond the infrastructure’s remaining lifespan, costly emergency interventions become necessary to prevent failure. Decision-makers must therefore balance expected emergency intervention costs against traffic congestion impacts. We formalize this trade-off as a road network maintenance scheduling problem with uncertain deadlines, which presents optimization challenges including computationally expensive evaluation and an exponentially growing solution space. To address these challenges, this paper contributes a hybrid optimization approach combining machine learning with genetic algorithms for large-scale infrastructure renovation scheduling under uncertainty. We formulate the problem as a bi-level multi-objective optimization problem that explicitly accounts for uncertain infrastructure lifespans through probabilistic failure models. We develop a progressive lower bound evaluation method: candidate schedules receive quick, optimistic estimates of their traffic impact from machine learning based surrogate models, and these estimates are refined by exact traffic simulation only for promising candidates, so that full evaluation is reserved almost exclusively for schedules that can advance the Pareto front. Embedded in a multi-objective genetic algorithm, this evaluation strategy improves solution quality by enabling many more iterations within a fixed computational budget. We demonstrate the method’s effectiveness and scalability on substantially larger problem instances than previously addressed in the literature: 76 and 80 projects on the Sioux Falls and Anaheim networks, respectively. Under an identical 24-hour computational budget across 30 random seeds, the method completes up to 87 times as many optimization iterations as standard NSGA-II and achieves statistically significant improvements across multiple performance metrics over both standard NSGA-II and a surrogate-assisted baseline. For road agencies, these gains make city-scale renovation programming tractable within a single day of computation: planners obtain a Pareto front of implementable schedules that quantifies the trade-off between the risk of late renovations and network congestion, from which a preferred schedule can be selected and defended, or adjustments explored with their consequences quantified.