Partial outer convexification for traffic light optimization in road networks

• Verfasst von: Göttlich, Simone [VerfasserIn]
• Verfasst von: Potschka, Andreas [VerfasserIn]
• Verfasst von: Ziegler, Ute [VerfasserIn]
• Titel: Partial outer convexification for traffic light optimization in road networks
• Verf.angabe: SimoneGöttlich, Andreas Potschka, and Ute Ziegler
• E-Jahr: 2017
• Jahr: February 1, 2017
• Umfang: 23 S.
• Teil: volume:39
• Teil: year:2017
• Teil: number:1
• Teil: pages:B53-B75
• Teil: extent:23
• Fussnoten: Gesehen am 13.09.2018
• Titel Quelle: Enthalten in: Society for Industrial and Applied MathematicsSIAM journal on scientific computing
• Ort Quelle: Philadelphia, Pa. : SIAM, 1993
• Jahr Quelle: 2017
• Band/Heft Quelle: 39(2017), 1, Seite B53-B75
• ISSN Quelle: 1095-7197
• DOI: doi:10.1137/15M1048197
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1580943586

Abstract

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 are investigated. 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 amount of time by global state-of-the-art mixed-integer nonlinear programming solvers. The two-stage solution candidates are not only better than results obtained by global optimization of piecewise linearized traffic flow models but also can be computed at a faster rate.