We consider the problem of computing optimal traffic light programs for urban road intersections using traffic flow conservation laws on networks. Based on a Partial Outer Convexification approach, which has been successfully applied in the area of mixed-integer optimal control for systems of ordinary or differential algebraic equations, we develop a computationally tractable two-stage solution heuristic. The two-stage approach consists of the solution of a (smoothed) Nonlinear Programming Problem with dynamic constraints and a reconstruction Mixed-Integer Linear Program without dynamic constraints. The two-stage approach is founded on a discrete approximation lemma for Partial Outer Convexification, whose grid independence properties for (smoothed) conservation laws we investigate. We use the two-stage approach to compute traffic light programs for two scenarios on different discretizations and demonstrate that the solution candidates cannot be improved in a reasonable amout of time by global state-of-the art Mixed-Integer Nonlinear Programming Solvers. In addition, the two-stage solution candidates are better than results obtained by global optimization of piecewise linearized traffic flow models, in addition to being computed faster.
Citation
Interdisciplinary Center for Scientific Computing, Heidelberg University, Im Neuenheimer Feld 368, 69121 Heidelberg, Germany, Nov 2015