An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems

Larsson, Torbjörn; Patriksson, Michael · 1995 · OpenAlex-citations

DOI: 10.1016/0191-2615(95)00016-7

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the computational challenges of solving capacitated traffic assignment problems, where upper bounds are imposed on link flows to more accurately model real-world congestion and traffic control policies. While basic traffic assignment models are efficiently solvable, introducing explicit capacity constraints destroys the problem’s inherent Cartesian product structure, making standard algorithms like Frank-Wolfe computationally burdensome due to the need to solve complex multicommodity flow subproblems. The authors propose an efficient solution strategy using an augmented Lagrangean dual algorithm, which transforms the capacitated problem into a sequence of uncapacitated subproblems. These subproblems are solved using the disaggregate simplicial decomposition method, which exploits the underlying problem structure and offers favorable reoptimization capabilities. The study establishes that solutions to the capacitated model can be characterized as Wardrop equilibria in terms of generalized travel costs, defined as the sum of actual travel times and queueing delays on saturated links. The Lagrange multipliers associated with the capacity constraints are interpreted as these equilibrium queueing delays or as tolls that would reduce flows on overloaded links. The proposed algorithm combines the augmented Lagrangean scheme, which avoids the numerical ill-conditioning of pure penalty methods and achieves faster multiplier convergence, with the disaggregate simplicial decomposition method for the subproblems. To address the issue that augmented Lagrangean schemes typically yield feasible solutions only in the limit, the authors incorporate a heuristic procedure to construct feasible solutions from slightly infeasible primal solutions. Computational experiments on capacitated versions of well-known test problems demonstrate the efficiency of the proposed method. The results indicate that the introduction of link capacities increases computing times by no more than a factor of four compared to the uncapacitated case, proving that the model remains computationally tractable. The algorithm exhibits a linear rate of convergence under standard nondegeneracy assumptions. The significance of this work lies in providing a viable, efficient tool for traffic engineers to model complex flow restrictions, such as speed limits or signal cycle times, and to derive price-directive traffic control schemes, such as tolls, to manage overloaded links. The approach also serves as a foundation for solving other side-constrained traffic assignment models.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• traffic density