Optimal network-level traffic signal control: A benders decomposition-based solution algorithm

Rasool Mohebifard

doi:10.1016/j.trb.2019.01.012

2019-03-01

Rasool Mohebifard

Ali Hajbabaie *

DOI：10.1016/j.trb.2019.01.012

原文链接

查看原文

摘要

En 中文

This paper formulates the network-level traffic signal timing optimization problem as a Mixed-Integer Non-Linear Program (MINLP) and presents a customized methodology to solve it with a tight optimality gap. The MINLP is based on the Cell Transmission Model (CTM) network loading concept and captures the fundamental flow-density diagram of the CTM explicitly by considering closed-form constraints in the model and thus, eliminates the flow holding-back problem. The proposed solution algorithm is based on the Benders decomposition technique and decomposes the original MINLP to an equivalent Integer Program (IP) (Master problem), and a new MINLP (Primal problem). We will show that the new MINLP has only one optimal non-holding-back solution that can be found by a CTM simulation run. We will prove that the proposed solution technique guarantees convergence to optimal solutions with a finite number of iterations. Furthermore, we propose a dual estimation algorithm for the new MINLP (the Primal problem), which utilizes a simulation-based approach to generate Benders cuts instead of solving a complex optimization program. We applied the proposed solution technique to a simulated network of 20 intersections under various demand patterns and observed an optimality gap of at most 2% under all tested conditions. We compared the solutions of the proposed algorithm with two benchmark algorithms and found reductions in total travel time ranging from 7.0% to 35.7%. (C) 2019 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license. (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Keyword:

Traffic signal control

Cell transmission model

Benders decomposition

Flow holding-back problem