Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/CDC.2018.8619739 | 2018 IEEE Conference on Decision and Control (CDC) |
Keywords | Field | DocType |
traffic signal offset optimization,π /4-approximation algorithm,near-globally optimal guarantee,real-world traffic network,reduced-complexity SDP,large-scale problem,semidefinite program relaxation,traffic networks,signalized intersections | Mathematical optimization,Computer science,Tree decomposition,Treewidth,Quadratic programming,Time complexity,Conic section,Optimization problem,Offset (computer science),Bounded function | Conference |
ISSN | ISBN | Citations |
0743-1546 | 978-1-5386-1396-2 | 0 |
PageRank | References | Authors |
0.34 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi Ouyang | 1 | 43 | 10.16 |
| Richard Y. Zhang | 2 | 10 | 6.92 |
| Javad Lavaei | 3 | 587 | 71.90 |
| Pravin Varaiya | 4 | 2543 | 298.93 |