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

Felix G. König ()
Additional contact information
Felix G. König: Technische Universität Berlin

A chapter in Operations Research Proceedings 2006, 2007, pp 53-59 from Springer

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

Keywords: Lagrangian Relaxation; Query Point; Short Path Problem; User Equilibrium; Path Constraint (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-69995-8_8

Ordering information: This item can be ordered from
http://www.springer.com/9783540699958

DOI: 10.1007/978-3-540-69995-8_8

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().