Large-Scale Traffic Signal Offset Optimization
Large-Scale Traffic Signal Offset Optimization
复制标题
DOI：
10.1109/tcns.2020.2966588
复制
发表时间：
2019-11
影响因子：
4.2
通讯作者：
Yi Ouyang;Richard Y. Zhang;J. Lavaei;P. Varaiya
中科院分区：
文献类型：
--
作者：
Yi Ouyang;Richard Y. Zhang;J. Lavaei;P. Varaiya
偏移优化问题寻求在整个网络中协调和同步交通信号的定时，以增强交通流量并减少停止和延迟。近年来，通过将交通流建模为正弦曲线，将偏移优化问题转化为一个不含整数变量的连续优化问题。在这篇文章中，我们提出了一种新的算法来解决这个新的制定近全局最优的大规模。具体来说，我们解决了一个凸松弛的非凸问题，使用树分解减少，并使用随机舍入恢复一个近全局的解决方案。我们证明了该算法总是提供的解决方案的期望值至少为0.785倍的全局最优值。此外，假设交通网络的拓扑结构是“树状”的，我们证明了该算法具有近线性的时间复杂度的交叉口的数量。这些理论保证在伯克利、曼哈顿和洛杉矶的交通网络上得到了实验验证。在我们的数值结果中，该算法的经验时间复杂度是线性的，并且解决方案的目标在全局最优值的0.99倍之内。
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.