Urban Road Network Maintenance Scheduling Using Ant Colony Optimization

AKSOY, İlyas Cihan; MUTLU, Mehmet Metin; ALVER, Yalçın · 2021 · Crossref

DOI: 10.35378/gujs.789519

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This study addresses the challenge of scheduling urban road maintenance to minimize the negative impacts on traffic flow, specifically the increase in total travel time caused by road closures. When multiple road links require repair simultaneously under crew constraints, the resulting network topology changes force users to alter their routes, leading to congestion and higher travel times across the entire network. The authors formulate this as a bi-level optimization problem: the upper level determines the maintenance schedule, while the lower level calculates the resulting traffic flows and travel times using a deterministic user equilibrium assignment model. Because this problem is NP-hard with an exponentially expanding solution space, the authors employ a modified Ant Colony Optimization (ACO) metaheuristic to find near-optimal schedules. The methodology assumes that each maintenance crew repairs one link per day, all lanes of a repaired link are closed, and maintenance duration is less than one day. The modified ACO algorithm distributes a set of road links to be repaired across different days, subject to a fixed number of available crews. In each iteration, the algorithm generates a candidate schedule, closes the corresponding links in the network, and calculates the total travel time using the Frank-Wolfe algorithm for traffic assignment and the Bureau of Public Roads (BPR) function for link travel times. The pheromone trails in the ACO are updated based on the total travel time cost, guiding the search toward schedules that minimize user delay. The model was tested on a hypothetical 4x4 grid network consisting of 16 nodes and 48 links. Twelve specific links were designated for repair by three maintenance crews over a four-day period, resulting in 15,400 feasible schedules. The authors compared the performance of the ACO-generated schedules against ten randomly generated schedules. The baseline total travel time for the network without any closures was approximately 13.2 million minutes over the four-day period. Random schedules resulted in average total travel times of roughly 51.6 million minutes, with increases ranging from 39% to over 500% compared to the baseline. In contrast, the ACO model, executed 30 times, consistently produced superior results. The best schedule found by the model yielded a total travel time of 16,810,173 minutes, representing a 27.67% increase over the baseline. The significance of these findings lies in the substantial reduction in travel time achieved by the optimization model compared to random scheduling. The best ACO solution reduced total travel time by approximately 9% compared to the best random schedule. The results demonstrate that the modified ACO algorithm is effective at navigating the complex combinatorial space of maintenance scheduling to identify efficient solutions. The study concludes that careful scheduling is crucial for mitigating congestion during maintenance periods and suggests future work should incorporate mobilization costs and test the model on larger-scale networks.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• work zones