Models and algorithms for the traffic assignment problem with link capacity constraints

Abstract

This paper explores the models as well as solution techniques for the link capacitated traffic assignment problem (CTAP) that is capable of offering more realistic traffic assignment results. CTAP can be approximated by the uncapacitated TAP using different dual/penalty strategies. Two important and distinctive approaches in this category are studied and implemented efficiently. The inner penalty function (IPF) approach establishes a barrier on the boundary of the feasible set so that constraints are not violated in the solution process, and the augmented Lagrangian multiplier (ALM) approach combines the exterior penalty with primal-dual and Lagrangian multipliers concepts. In both implementations, a gradient projection (GP) algorithm was adopted as the uniform subproblem solver for its excellent convergence property and reoptimization capability. Numerous numerical results demonstrated through efficient implementations of either the IPF or the ALM approach that CTAP is computationally tractable even for large-scale problems. Moreover, the relative efficiency of IPF and ALM was explored and their sensitivity to different algorithmic issues was investigated. © 2003 Elsevier Ltd. All rights reserved.