Large-Scale Traffic Signal Offset Optimization

Yi Ouyang

doi:10.1109/TCNS.2020.2966588

Large-Scale Traffic Signal Offset Optimization

2020-09-01

5

OA

AI

DOI：10.1109/TCNS.2020.2966588

原文链接

查看原文

摘要

En 中文

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.

Keyword:

Optimization

Delays

Mathematical model

Control systems

Time complexity

Standards

Convex relaxation

offset optimization

semidefinite programming

traffic control

traffic signal timing

tree decomposition

Large-Scale Traffic Signal Offset Optimization

摘要

AI总结

期刊

机构