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

https://doi.org/10.1016/S0191-2615(03)00010-9Get rights and content

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.

Introduction

Determining equilibrium flow patterns in a transportation network given origin–destination demands, commonly referred to as the traffic assignment problem (TAP), is a classical problem in transportation analyses and applications. Modeling and solution techniques for this problem have been extensively studied since Wardrop’s two optimality principles (Wardrop, 1952), user equilibrium (UE) and system optimal (SO), were first published.

It has been shown (Beckmann et al., 1956) that the link traffic flow pattern in agreement with the UE principle could be uniquely determined by solving a convex mathematical program, if link travel times on a road network are separable/integrable, convex and monotonically increasing functions of link traffic flows. Estimating these link cost functions (or link performance functions) is a non-trivial task that involves choosing appropriate functional forms and calibrating corresponding parameters. Most link performance functions used in practice, including the well-known Bureau of Public Roads (BPR) function, are polynomials whose degree and coefficients are specified from statistical analysis of real data. However, the polynomial type link performance functions may lead to unrealistically high link flows since travel times given by such functions remain finite whenever link flows are finite. As a result, the equilibrium solution may contain quite a few over-saturated links which in some cases even take flows more than 2–3 times of the observed capacities. Such solutions are quite unsatisfactory because in reality each road segment has an empirical capacity that bounds flow from above. Observed link flows thus never exceed the capacity of the link. When traffic demand to a link exceeds its capacity, queue will form at adjacent upstream links and flows into that link would be capacity flow so long as queues persist on upstream links. To correctly model this process would call for a dynamic approach, which is still an active area of research. An intermediate, and natural solution to curtail the appearance of higher than capacity flows is to impose capacity constraints on link flows. This “static” fix would not fully address the issues of an essentially dynamic problem. It nevertheless is an improvement over the basic TAP in properly distributing traffic in a congested network.

It is well recognized that the standard TAP can be solved efficiently with a Frank–Wolfe type algorithm in which the linearized subproblem is finding shortest paths for each O–D pair. The presence of capacity constraints, unfortunately, destroys the Cartesian product structure of the feasible set in classic TAP and results in a more complex model. The critical difficulty in solving the capacitated traffic assignment problem (CTAP) is that the subproblem becomes a multi-commodity minimum cost flow problem, whose computation is considerably more expensive than the shortest path problem. Therefore, most solution methods proposed for CTAP have been motivated to avoid getting entangled in the minimum cost flow problem. There are two classical approaches to achieve this: one is using asymptotical link performance functions, and the other is converting the capacitated problem into a sequence of uncapacitated problems through penalty/dual schemes.

Daganzo, 1977a, Daganzo, 1977b first proposed to adopt asymptotical link performance functions instead of polynomials so that link capacity is incorporated into the assignment procedure implicitly. Although it effectively reduces the capacity constrained problem to an unconstrained problem, introducing asymptotic cost functions gives rise to some new problems and difficulties, such as producing unrealistically high travel times, devious rerouting of trips (Boyce et al., 1981) and numerical difficulties near capacity flow.

Methods in the second approach, which are much more popular, set out to relax the capacitated problem through the use of penalties or Lagrangian multipliers. The earliest application of penalty-type algorithm for CTAP is credited to Hearn (1980), who proposed an exterior penalty method that minimizes a sequence of uncapacitated problems using the Frank–Wolfe algorithm. Inouye (1987) devised an interior penalty scheme through the use of the asymptotical penalty function. Although uncapacitated problems in this approach are also solved with the Frank–Wolfe algorithm, the introduction of the asymptotical term makes significant difference in algorithmic behaviors. For instance, the step size will be bounded from above to guarantee that the solution for each uncapacitated problem is strictly feasible. Inouye’s method is commonly known as the inner penalty function (IPF) method, or Barrier method as Luenberger puts it (1973). Yang and Yagar (1994) applied the IPF method to deal with traffic assignment as well as signal control in a general freeway-arterial corridor system. Moreover, Yang and Yagar (1995) extended the model to handle congested urban networks and provided numerical results on a small network. Recently, Prashker and Toledo (2001) used the gradient projection (GP) algorithm to solve unconstrained subproblems under the framework of the IPF method, and compared their results with those given by Yang and Yagar’s algorithm for the Sioux Falls network.

Another notable dual/penalty approach is the augmented Lagrange multiplier (ALM) method (or Lagrange multiplier method). Originally designed by Hestenes (1969) and Powell (1969) for the classical non-linear programming problem, the algorithm combines the attractive features of the exterior penalty and primal–dual methods while curtailing the disadvantages of both. Hearn and Ribera (1980) applied the ALM method for the solution of CTAP, in which uncapacitated subproblems are solved with the Frank–Wolfe algorithm. The overall performance of their ALM method was demonstrated through small-size networks. Larsson and Patriksson (1995) proposed a similar ALM method and reported numerical results for small- to mid-size networks. The major distinction in Larsson and Patriksson’s algorithm is that subproblems are solved with the disaggregate simplicial decomposition (DSD) algorithm, which was due to Larsson and Patriksson (1992).

This paper is motivated to study solution techniques for the CTAP with efficient implementations and comparisons between two dual/penalty methods for CTAP: the IPF method and the ALM method. These two special methods are chosen for fulfilling such a purpose given their good reputation both in theory and in practice: ALM is theoretically desirable due to the combined advantages of the penalty and Lagrangian philosophies, and IPF is distinguished in its inner penalty strategy and relatively numerous applications compared with other methods.

We present a new IPF algorithm in which the independent initialization is combined into the main iterative procedure. Also, a dynamic strategy is adopted in our IPF algorithm in order to form a pseudo-feasible set before an initial feasible solution is obtained, and to gain approximate projection whenever feasibility is violated. The ALM algorithm presented in this paper has a similar basic structure to the ones previously studied (Hearn, 1980; Larsson and Patriksson, 1995), but with some efficient implementations. A distinct feature of the two presented algorithms is the use of the GP method for solving uncapacitated subproblems. This path-based algorithm was originally designed by Bertsekas and Gafni (1983) for the multi-commodity network flow problem and implemented in solving the standard TAP by Jayakrishnan et al. (1994). The main reason of employing GP as the subproblem solver is its fast convergence speed in the near-optimum neighborhood, as reported in many previous studies (Jayakrishnan et al., 1994; Chen et al., 2000; Chen et al., in press; Lee et al., in press). Solving subproblems to a desirable accuracy is, as we will see later, inherently difficult because of the inevitable ill-conditioning encountered in the penalty scheme. A slow convergence subproblem solver, such as Frank–Wolfe, will incur prohibitively expensive overhead to equilibrate subproblems, thereby worsening the overall algorithmic performance. Another advantage that GP can offer is the reoptimization capability coming with the storage of paths (Larsson and Patriksson, 1995). Moreover, identifying the set of paths before hand helps maintain the feasibility more conveniently in the IPF approach.

Through several numerical examples, we show that solving CTAP is computationally tractable even for large-scale networks by combining either the IPF or ALM approach with the GP algorithm. The paper further explores the computational efficiency of IPF and ALM algorithms and their sensitivity to different algorithmic factors like the solution accuracy of subproblems and the choice of penalty parameters.

The remainder of this paper is structured as follows: Section 2.1 introduces the formulation of CTAP and states its optimal condition that resembles Wardrop principles. The IPF approach for solving CTAP is presented in Section 2.2 while the ALM solution approach is introduced in Section 2.3. Section 3 discusses the implementation of algorithms in the two approaches and gives complete solution procedures. Computational results are reported in 4 Computational results, 5 Conclusions presents conclusions and directions for future development.

Section snippets

Problem formulation

Given a traffic network represented as a graph G(N,A) where N and A are the set of nodes and links, respectively. Let R be the set of origins and S be the set of destinations. The UE TAP with link capacity constraints is given by the following non-linear programming program:

Problem [CTAP]minz(x)=∑a0xata(w)dwsubjectto:kfkrs=qrs∀r∈R,s∈Sfkrs⩾0∀k∈Krs,r∈R,s∈Sxa=∑rskfkrsδa,krs∀a∈A,k∈Krs,r∈R,s∈Sxa⩽Ca∀a∈Awhere z is the objective function; xa, the total flow on link a; ta, the link cost function

Efficient implementations of IPF and ALM

Now, we present two efficient implementations of IPF and ALM discussed in the last section. The GP algorithm, used as the common solver for the uncapacitated subproblem in both schemes, is first presented, followed by other implementation details and the complete algorithmic steps.

Solving uncapacitated problems with GP: the reasons to prefer GP over other algorithms for solving uncapacitated subproblems, as we have addressed in the introduction, are mainly due to its excellent convergence

Computational results

A given CTAP problem may have an empty feasible set. In that case, the penalty function (hence the objective function values of uncapacitated problems) in both schemes will diverge to infinity. In practice, the infeasibility can be detected once the penalty function value exceeds a given threshold. Although the presented algorithms are able to manage infeasible CTAP, our reported experiments concern only feasible CTAP in order to show algorithmic behaviors more clearly.

To produce a feasible

Conclusions

We studied two penalty/dual approaches for solving the CTAP: the IPF approach (IPF) and ALMs approach. Representing a compromise between the Lagrangian method and the exterior penalty method, the ALM approach has been widely recognized for its success in computational practices of mathematical programming. On the other hand, IPF is unique for its interior penalty strategy in which the solution of the uncapacitated problem approaches the solution to the CTAP from inside the feasible region.

Acknowledgements

The authors wish to thank two anonymous referees for their constructive comments.

References (25)

  • D.P. Bertsekas et al.

    Projected Newton methods and optimization of multicommondity flows

    IEEE Transactions on Automatic Control

    (1983)
  • D.P. Bertsekas

    Network Optimization: Continuous and Discrete Models

    (1998)
  • Cited by (0)

    View full text