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

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%.