Traffic Optimization Under Route Constraints with Lagrangian Relaxation and Cutting Plane Methods

The optimization of traffic flow in congested urban road networks faces a well-known dilemma: Optimizing system performance is unfair with respect to the individual drivers’ travel times; and a fair user equilibrium may result in bad system performance. As a remedy, computing a system optimum with fairness conditions, realized by length constraints on the routes actually used by drivers, has been suggested in [5]. This poses interesting mathematical challenges, namely the nonlinearity of the objective function and the necessity to deal with path constraints in large networks. While the authors present results suggesting that solutions to this constrained system optimum problem (CSO) are indeed equally good and fair, they rely on a standard Frank-Wolfe/Partan-algorithm to obtain them. In this paper, we present a Lagrangian relaxation of the CSO problem for which the Lagrangian dual function can be evaluated by a decomposition into constrained shortest path problems which we solve exactly employing state-of-the-art acceleration techniques. The Lagrangian dual problem is then solved by a special cutting plane method. Finally, we obtain test results which suggest that this approach outperforms previously described solution schemes for the CSO problem.