Large-Scale Traffic Signal Offset Optimization

Yi Ouyang, Richard Y. Zhang, Javad Lavaei, Pravin Varaiya

Research output: Contribution to journalArticlepeer-review


The offset optimization problem seeks to coordinate and synchronize the timing of traffic signals throughout a network in order to enhance traffic flow and reduce stops and delays. Recently, offset optimization was formulated into a continuous optimization problem without integer variables by modeling traffic flow as sinusoidal. In this article, we present a novel algorithm to solve this new formulation to near-global optimality on a large scale. Specifically, we solve a convex relaxation of the nonconvex problem using a tree decomposition reduction, and use randomized rounding to recover a near-global solution. We prove that the algorithm always delivers solutions of expected value at least 0.785 times the globally optimal value. Moreover, assuming that the topology of the traffic network is 'tree-like,' we prove that the algorithm has near-linear time complexity with respect to the number of intersections. These theoretical guarantees are experimentally validated on the Berkeley, Manhattan, and Los Angeles traffic networks. In our numerical results, the empirical time complexity of the algorithm is linear, and the solutions have objectives within 0.99 times the globally optimal value.

Original languageEnglish (US)
Article number8959313
Pages (from-to)1176-1187
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Issue number3
StatePublished - Sep 2020


  • Convex relaxation
  • offset optimization
  • semidefinite programming
  • traffic control
  • traffic signal timing
  • tree decomposition

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'Large-Scale Traffic Signal Offset Optimization'. Together they form a unique fingerprint.

Cite this