Optimization Online


Partial outer convexification for traffic light optimization in road networks

Simone Göttlich(goettlich***at***uni-mannheim.de)
Andreas Potschka(potschka***at***iwr.uni-heidelberg.de)
Ute Ziegler(ziegler***at***uni-mannheim.de)

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

Keywords: Partial outer convexification, traffic networks, discretized conservation laws, optimization, mixed-integer programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Optimization of Systems modeled by PDEs )

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: Interdisciplinary Center for Scientific Computing, Heidelberg University, Im Neuenheimer Feld 368, 69121 Heidelberg, Germany, Nov 2015

Download: [PDF]

Entry Submitted: 11/12/2015
Entry Accepted: 11/12/2015
Entry Last Modified: 11/12/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society