CoSIGN: A parallel algorithm for coordinated traffic signal control

Abstract — The problem of finding optimal coordinated signal timing plans for a large number of traffic signals is a challenging problem because of the exponential growth in the number of joint timing plans that need to be explored as the network size grows. In this paper, we employ the game-theoretic paradigm of fictitious play to iteratively search for a coordinated signal timing plan that improves a system-wide performance criterion for a traffic network. The algorithm is robustly scalable to realistic-size networks modelled with high fidelity simulations. We report results of a case study for the the city of Troy, Michigan, where there are 75 signalized intersections. Under normal traffic conditions, savings in average travel time of more than 20 percent are experienced against a static timing plan, and even against an aggressively tuned automatic signal re-timing algorithm, savings of more than 10 percent are achieved. The efficiency of the algorithm stems from its parallel nature. With a thousand parallel CPUs available, our algorithm finds the plan above in under 10 minutes, while a version of a hill-climbing algorithm makes virtually no progress in the same amount of wall-clock computational time. Index Terms — Coordinated traffic signal control, optimization, area traffic control I