Conic Approximation with Provable Guarantee for Traffic Signal Offset Optimization

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the offset optimization problem that coordinates the offsets of signalized intersections to reduce vehicle queues in large-scale signalized traffic networks. We adopt a recent approach that transforms the offset optimization problem into a complex-valued quadratically-constrained quadratic program (QCQP). Using the special structure of the QCQP, we provide a π /4-approximation algorithm to find a near-global solution based on the optimal solution of a semidefinite program (SDP) relaxation. Although large-scale SDPs are generally hard to solve, we exploit sparsity structures of traffic networks to propose a numerical algorithm that is able to efficiently solve the SDP relaxation of the offset optimization problem. The developed algorithm relies on a tree decomposition to reformulate the large-scale problem into a reduced-complexity SDP. Under the practical assumption that a real-world traffic network has a bounded treewidth, we show that the complexity of the overall algorithm scales near-linearly with the number of intersections. The results of this work, including the bounded treewidth property, are demonstrated on the Berkeley, Manhattan, and Los Angeles networks. From numerical experiments it is observed that the algorithm has a linear empirical time complexity, and the solutions of all cases achieve a near-globally optimal guarantee of more than 0.99.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages229-236
Number of pages8
ISBN (Electronic)9781538613955
DOIs
StatePublished - Jan 18 2019
Externally publishedYes
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2018-December
ISSN (Print)0743-1546

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
CountryUnited States
CityMiami
Period12/17/1812/19/18

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Conic Approximation with Provable Guarantee for Traffic Signal Offset Optimization'. Together they form a unique fingerprint.

  • Cite this

    Ouyang, Y., Zhang, R. Y., Lavaei, J., & Varaiya, P. (2019). Conic Approximation with Provable Guarantee for Traffic Signal Offset Optimization. In 2018 IEEE Conference on Decision and Control, CDC 2018 (pp. 229-236). [8619739] (Proceedings of the IEEE Conference on Decision and Control; Vol. 2018-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2018.8619739