Solving the traffic signaling problem using the iterated local search metaheuristic

Traffic lights are pivotal for urban mobility in large cities, with optimal scheduling at intersections being a complex task. This encompasses determining the optimal duration for green light signaling, assigning the sequence of signaling times for individual streets, and establishing the length of the signaling cycle for all streets, with these signaling times repeating over the assigned simulation period. In this paper, we present a meta-heuristic approach for the traffic signaling problem from the Google Hash Code Competition 2021. Our approach, based on the Iterated Local Search (ILS) algorithm, employs a tailored neighborhood structure designed for the selected solution encoding. This structure includes two basic moves, each extended into four additional variants, which can be applied in either a guided or greedy format. Additionally, it integrates a mechanism for search space exploitation, embedding Hill Climbing in individual algorithm iterations, and an exploration mechanism through a perturbation operator. Empirical studies were conducted on 48 challenging instances, including five from the Google Hash Code competition and 43 additional cases for extensive testing. The results highlight the competitiveness of our ILS approach compared to state-of-the-art solvers, achieving top rankings in 8 specific instances within a 30-minute execution timeframe, underscoring its potential for real-life applications.