Equilibrium Characterizations of Solutions to Side Constrained Asymmetric Traffic Assignment Models

Torbjörn Larsson Division of Optimization Department of Mathematics Linköping Institute of Technology S-581 83 Linköping, Sweden

Michael Patriksson Department of Mathematics, GN–50 University of Washington Seattle, WA 98195, USA

Abstract

In order to refine the basic model of traffic assignment to capture supplementary flow relationships, the traditional modelling strategy is to modify the travel cost mapping. This strategy is well suited for capturing relationships such as interactions among vehicles on different road links and turning priorities in junctions, and it usually results in nonseparable and asymmetric travel cost functions. It is, however, not the proper approach for incorporating traffic flow restrictions such as those imposed by joint capacities on two-way streets or in junctions, or the presence of a traffic control policy. We consider the introduction of side constraints to describe those flow relationships that have more natural interpretations as flow restrictions than as additional travel costs. Such a refinement should be easier to construct and calibrate as well as lead to more reliable traffic models than that using the traditional refinement strategy only.

The utilization of the appropriate combination of these two modelling strategies results, in general, in a variational inequality model of the traffic assignment problem augmented with a set of side constraints. We establish characterizations of its solutions as Wardrop and queueing delay equilibria in terms of well-defined and natural generalized travel costs, and derive stability results for the model. The results obtained may, for example, be applied to derive link tolls for achieving traffic management goals without using centralized traffic control.

Keywords: Traffic Assignment, User Equilibrium, Variational Inequalities, Side Constraints, Generalized Wardrop Conditions, Queue Equilibrium, Queue Dynamics, Duality.

1 Introduction and motivation

Traffic assignment models have been thoroughly studied in the context of urban transportation network analysis; they are constructed with the main purpose of describing, predicting or prescribing a pattern of traffic flow in a road network model with flow-dependent travel costs. The flow pattern is determined according to a given performance criterion, which, in turn, is based on a principle of traveller behaviour. The two performance criteria most often used are based on the behavioural principles attributed to Wardrop [31]. The first of these principles is that each traveller tries to minimize his/her own travel time irrespective of the other travellers; this principle is known as the user optimal or user equilibrium principle. The second is based on the assumption that the total travel time in the network is minimized; this is known as the system optimum principle. The first principle is often regarded to be the one more closely describing the flows observed in a traffic network, while the second is used in modelling centrally controlled networks and in the study of the potentials of traffic management and route guidance schemes; the first principle is the basis for our development.

To introduce the problem under study, we let G = (N , A) be a strongly connected transportation network, where N and A are the sets of nodes and directed links (arcs), respectively. For certain ordered pairs of nodes, (p, q) ∈ C, where node p is an origin, node q is a destination, and C is a subset of N × N, there are positive travel demands d_{pq} (which we for simplicity shall assume to be fixed) which give rise to a link traffic flow pattern when distributed through the network. Further, for each link a ∈ A there is a positive travel cost function t_{a} : ℜ_{+}^{|A|} ↦ ℜ_{++}.

Wardrop’s user equilibrium principle states that for every origin-destination (O-D) pair (p, q) ∈ C, the travel costs of the routes utilized are equal and minimal. We denote by R_{pq} the set of simple (loop-free) routes in O-D pair (p, q), by h_{pqr} the flow on route r ∈ R_{pq}, and by c_{pqr} = c_{pqr}(h) the travel cost on the route given the vector h of route flows; with this notation, an equilibrium flow is defined by the conditions

(1.1a)  h_{pqr} > 0 ⟹ c_{pqr} = π_{pq},  ∀r ∈ R_{pq},
(1.1b)  h_{pqr} = 0 ⟹ c_{pqr} ≥ π_{pq},  ∀r ∈ R_{pq},

where the value of π_{pq} is the minimal (or equilibrium) route cost in O-D pair (p, q). An equilibrium state is reached precisely when no traveller can decrease his/her travel cost by shifting to another route in the O-D pair. Further, when the travel cost on each link is independent of the flows on the other links, i.e., when each function t_{a} is separable, then the Wardrop conditions (1.1) describe the solution set of a non-cooperative game among the O-D pairs, i.e., a Wardrop equilibrium flow h is a Nash equilibrium point of the game (e.g., Charnes and Cooper [7]). In this game, each O-D pair chooses a strategy (that is, a commodity flow) which, given the strategies of the other O-D pairs, distributes its travel demand so that the routes utilized are among the least-cost ones.

A Wardrop equilibrium may be interpreted as a steady-state evolving after a transient (disequilibrium) state in which the travellers adjust their route choices to reduce travel costs under the prevailing traffic conditions, until a stable situation is reached (e.g., Friesz et al. [8]).

In the case of separable travel costs, a solution to the Wardrop conditions (1.1) can be found by solving the network optimization problem (e.g., Beckmann et al. [2])

[TAP]

(1.2a) minimize T (f) =^{def} ∑_{a∈A} ∫_{0}^{f_{a}} t_{a}(s) ds,

subject to

(1.2b)  ∑_{r∈R_{pq}} h_{pqr} = d_{pq},  ∀(p, q) ∈ C,
(1.2c)  h_{pqr} ≥ 0,  ∀r ∈ R_{pq}, ∀(p, q) ∈ C,
(1.2d)  ∑_{(p,q)∈C} ∑_{r∈R_{pq}} δ_{pqra}h_{pqr} = f_{a},  ∀a ∈ A,

where

δ_{pqra} =^{def} \{ \begin{matrix}1, & if route r ∈ R_{pq} uses link a, \\ 0, & otherwise, \end{matrix} ∀a ∈ A, ∀r ∈ R_{pq}, ∀(p, q) ∈ C,

is the link-route incidence matrix, and f_{a} denotes the total flow on link a.

This model is well studied and frequently applied, and its special structure and the size of real-world instances have attracted the attention of many researchers to develop efficient algorithms for its solution; we note in passing that all efficient algorithms for [TAP] exploit the Cartesian product structure of the set of feasible flows (e.g., Larsson and Patriksson [17]). (See Patriksson [24] for a thorough review of [TAP] and other traffic assignment models, as well as methods for their solution.) The popularity of this model among practitioners is partially explained by its simplicity and nice interpretations, which makes it easy to access and apply.

The validity of the model [TAP] for use in a practical assignment situation rests on the assumption that it provides a description of the real-world traffic flows which is accurate enough with respect to the model’s purpose; further, it presumes that the situation modelled is in a steady-state and that sufficiently accurate and stable estimates of the data of the model’s components (e.g., functional form and parameters of the link travel cost functions) are available. If these assumptions are not met in a practical application, then the model is invalid and its data needs to be modified or the use of the model restricted to some situations only.^{1}

The assignment model [TAP] may, however, also be invalid due to its structural limitations, that is, its inherent simplicity makes it inapplicable to more complex traffic problems (e.g., Sender and Netter [28]); an example of such limitations is that there is no discrimination between different types of vehicles. Hearn [11] discusses another serious deficiency of the model, namely that every road is (implicitly) presumed to be able to carry arbitrarily large volumes of traffic; the model may hence fail to produce reasonable predictions of traffic flows, which, in turn, has the effect that the traffic engineer either ignores its predictions or, more often, perturbs components of the model (e.g., the parameters of the travel cost functions) in attempting to make it provide an output more in line with the expected one. In order to avoid such heuristic tampering with components of the model available, traffic planners must be supplied with analysis tools whose underlying traffic models are sufficiently general, reliable and accurate; much research has been devoted to the task of refining the basic traffic assignment model [TAP] in various respects.

Flow relationships such as interactions between the flows on intersecting links or between vehicles of different types, and delays at priority junctions may be captured through the cost functions. The resulting costs often become nonseparable and asymmetric, and a solution to the Wardrop conditions can then not be formulated as an optimization model of the form [TAP]; instead, they are stated as variational inequality problems of finding an f^{∗} ∈ F such that

[TAP-VIP-F]

t(f^{∗})^{T}(f − f^{∗}) ≥ 0, ∀f ∈ F,

where F = { f ∈ ℜ^{|A|} | f satisfies (1.2b)–(1.2d) } and t : ℜ_{+}^{|A|} ↦ ℜ_{++}^{|A|} is the vector of link travel cost functions. In some applications, for example when the travel cost of a route can not be assumed to be additive (that is, the route cost is not the sum of the travel costs of the links defining the route), asymmetric models are formulated in terms of the route flow variables only; in this case, the problem is to find an h^{∗} ∈ H such that

[TAP-VIP-H]

c(h^{∗})^{T}(h − h^{∗}) ≥ 0, ∀h ∈ H,

where H = { h ∈ ℜ^{|R|} | h satisfies (1.2b)–(1.2c) }, c : ℜ_{+}^{|R|} ↦ ℜ_{++}^{|R|} is the vector of route travel cost functions, and |R| is the total number of simple routes in the network. This class of models has been extensively studied from both a theoretical and algorithmical point of view (see, e.g., Nagurney [23] and Patriksson [24]). Real-world applications of asymmetric models are still scarce, however, and, seemingly, the interest in these models is largely due to their mathematical elegance and nice interpretations.

1A combination of these two countermeasures is to introduce time-slices to capture variations in the real-world traffic system, especially the variations in travel demands and travel time characteristics.

Although the utilization of nonseparable cost functions may improve the basic model’s ability to accurately describe, reproduce, or predict a real-world traffic situation, it is not the natural and adequate means for handling supplementary traffic flow restrictions such as those imposed by a traffic control policy (typically arising as link flow capacities; see Yang and Yagar [32]), or joint capacities on two-way streets or in junctions or roundabouts. Such restrictions are often required to be fulfilled exactly and it is generally difficult to estimate travel cost functions which yield a traffic flow pattern in agreement with this requirement.^{2} This is a fundamental reason for the inadequacy of utilizing travel cost functions for describing this type of restrictions.

The adequate approach for describing and capturing such traffic flow restrictions is to introduce side constraints. Under the presumption that the traffic flow restrictions to be modelled have well-defined physical meanings, this will also be the case for the resulting side constraints, and it may thus be relatively easy for the traffic engineer to identify and calibrate a suitable set of side constraints (that is, their functional forms and the proper values of their parameters), as compared to the task of making proper estimates of the values of the parameters in travel cost functions. Hence, we believe this approach to be appealing from a practical point of view. (In the situation described by Hearn [11], a proper model refinement is to introduce link capacity constraints corresponding to the engineer’s anticipation of reasonable levels of traffic flow.)

So far, the utilization of side constraints in the context of traffic assignment has been considered to a very limited extent; the main reason for this is that the solutions to the resulting models can no longer be given characterizations as Wardrop equilibria in the classical sense. Moreover, as a result of the addition of the side constraints, the Cartesian product structure of the feasible set of the basic model (and therefore its non-cooperative game interpretation) is lost, thus obtaining a computationally more demanding model.

However, one class of side constrained extensions of [TAP] is well studied: link capacities have been introduced as a means for modelling congestion effects (e.g., Charnes and Cooper [7] and Jorgensen [13]) and then represent the saturation link flows. When a link is saturated, congestion effects result in queueing and any excess flow will accumulate in the queue; in an equilibrium state, the saturated links may therefore carry stationary queues (e.g., Smith [29]). Link capacities also arise naturally when links are signal-controlled (e.g., [29, 32]).

For this model, it is known that solutions can be characterized as Wardrop equilibria in terms of well-defined generalized route (or, link) travel costs (Jorgensen [13], Hearn [11], and Inouye [12]). Further, the Lagrange multipliers for the capacity constraints can be given interesting interpretations. First, they are the link tolls that the travellers are willing to pay for being allowed to use the links ([13]), and, second, they may be interpreted as the delays in steady-state link queues (Payne and Thompson [25] and Miller et al. [21]); the link queueing interpretation also provides a queue equilibrium characterization of solutions to the model ([21]). In Larsson and Patriksson [14] we review these results and show that the model can be efficiently dealt with computationally. Larsson and Patriksson [15, 16] give natural extensions of these results to a general side constrained model extending [TAP]; this paper offers a further generalization to a side constrained model extending [TAP-VIP-F].

Supplementary constraints on traffic flows may be introduced in order to (1) improve the quality of an available assignment model by incorporating into the model additional information about the actual real-world traffic situation, for example link flow observations, (2) capture dynamic effects in time-sliced traffic assignment, e.g., to describe the coupling between the assignment problems in successive time-slices, or (3) derive the link tolls that should be introduced to reach some traffic management goal, e.g., to limit some volumes of traffic to levels that are acceptable, without imposing a centralized traffic control.

The side constraints introduced may differ significantly with respect to their purposes and properties; we may, however, distinguish two principally different types: prescriptive (hard) and descriptive (weak). The former are imposed upon the travellers by traffic management and control policies (e.g., through speed limit regulations and traffic signals), are known exactly and can (or may) never be violated; examples include link capacities which are used to model saturation flows and side constraints introduced to derive link tolls. Prescriptive constraints may be binding at a steady-state flow and cause stationary link queues to appear (cf. Section 3). Descriptive side constraints are introduced as a means to bring the calculated flow in better agreement with the anticipated one (e.g., observed flows on some links), as a means to refine the model by including additional (maybe approximate) traffic flow restrictions into the model (e.g., joint capacities in roundabouts), or as a (rough) means for modelling congestion effects. Clearly, because of the nature of the descriptive constraints they do not need to be satisfied exactly, and this fact may also be taken into account in solution procedures (cf. Section 4).

2Travel cost functions with asymptotes at the link flows’ upper bounds have been proposed to describe capacities of flow; such functions, however, have the disadvantage of numerical instabilities as well as resulting in unrealistic travel times and assignments of trips; see Boyce et al. [5].

We consider a general side constrained extension of the equilibrium model [TAP-VIP-F] and characterize its solutions. These may be interpreted as a generalization of the Wardrop equilibrium principle in terms of travel costs and queueing delays, that is, in terms of the natural costs to be minimized by the individual travellers in a network with queueing. Solutions to side constrained traffic equilibrium models thus comply with the basic assumption of rational traveller behaviour. With multipliers for the side constraints at hand, the side constrained problem may be equivalently solved as a traffic equilibrium problem with a well-defined adjusted travel cost function. Any convergent algorithm for finding the values of these multipliers may be viewed as a systematic way of calibrating the proper travel cost functions, as opposed to the heuristic tampering described in the example of Hearn [11].

The results obtained in this paper extend those of Larsson and Patriksson [15, 16] for link capacitated and general convexly side constrained versions of [TAP], respectively. To a large extent, the presentation in this paper parallels that of [16], where the complete background and motivation for the modelling strategy using side constraints may be found.

2 Characterizations of solutions to a side constrained assignment model

Consider the problem of formulating and solving a traffic assignment model which is to take into account a given set of flow relationships and restrictions, by utilizing the two modelling approaches outlined in Section 1. Assume that the resulting travel cost function t : ℜ_{+}^{|A|} ↦ ℜ_{++}^{|A|} is positive and continuous, and that the supplementary flow restrictions that were found to be better represented by a set of side constraints are described by the constraints

g_{k}(f) ≤ 0, ∀k ∈ K, (2.1)

where the functions g_{k} : ℜ_{+}^{|A|} ↦ ℜ, k ∈ K, are continuously differentiable.^{3} We denote by G the set of solutions to the system (2.1) of inequalities.

The side constrained traffic equilibrium problem then is to find an f^{∗} ∈ F ∩ G such that

[TAP-VIP-SC-F]

t(f^{∗})^{T}(f − f^{∗}) ≥ 0, ∀f ∈ F ∩ G.

Henceforth, we assume that the intersection of F and G is nonempty, and that a constraint qualification (e.g., Bazaraa et al. [1, Chapter 5]) holds for G. (In the case where all functions g_{k} are affine, the latter requirement is fulfilled automatically.) It follows immediately from the assumptions that the set F ∩ G is a nonempty, closed and bounded set; we shall further always assume that a solution to [TAP-VIP-SC-F] exists, and denote by F^{∗} the link flow solution set.^{4}

3The index set K may, for example, consist of the index set of the links, nodes, routes, or O-D pairs, or any combination of subsets of them.

A solution f^{∗} to [TAP-VIP-SC-F] also solves

(2.2)  minimize_{f∈F ∩G} t(f^{∗})^{T}f

(Tobin [30]); when referring to a vector of multipliers for constraints in [TAP-VIP-SC-F] we then (implicitly) refer to a vector of multipliers for the corresponding constraints in (2.2).

We begin by showing that the solutions to [TAP-VIP-SC-F] are Wardrop equilibrium flows in terms of well-defined generalized route travel costs.

Theorem 2.1 (solutions to [TAP-VIP-SC-F] are generalized Wardrop equilibria). Suppose that (h^{∗}, f^{∗}) solves [TAP-VIP-SC-F] and that π^{∗} ∈ ℜ^{|C|} and β^{∗} ∈ ℜ^{|K|} are vectors of multipliers for the constraints (1.2b) and (2.1), respectively. Let generalized route travel costs be given by

\overline{c}_{pqr} =^{def} c_{pqr}(h^{∗}) + ∑_{k∈K} β_{k}^{∗} ∑_{a∈A} δ_{pqra} \frac{∂g_{k}(f^{∗})}{∂f_{a}}, ∀r ∈ R_{pq}, ∀(p, q) ∈ C. (2.3)

Then

(2.4a)  h_{pqr}^{∗} > 0 ⟹ \overline{c}_{pqr} = π_{pq}^{∗},  ∀r ∈ R_{pq},
(2.4b)  h_{pqr}^{∗} = 0 ⟹ \overline{c}_{pqr} ≥ π_{pq}^{∗},  ∀r ∈ R_{pq},

holds for all O-D pairs (p, q) ∈ C.

Proof. As noted above, if the vector f^{∗} solves [TAP-VIP-SC-F], it then also solves the nonlinear program (2.2). Since a constraint qualification is assumed to hold for G, the solution (h^{∗}, f^{∗}) satisfies the Karush–Kuhn–Tucker conditions for this problem (e.g., Tobin [30]); hence,

(2.5a)  h_{pqr}^{∗} (\overline{c}_{pqr} − π_{pq}^{∗}) = 0,  ∀r ∈ R_{pq}, ∀(p, q) ∈ C,
(2.5b)  \overline{c}_{pqr} − π_{pq}^{∗} ≥ 0,  ∀r ∈ R_{pq}, ∀(p, q) ∈ C,
(2.5c)  ∑_{r∈R_{pq}} h_{pqr}^{∗} = d_{pq},  ∀(p, q) ∈ C,
(2.5d)  h_{pqr}^{∗} ≥ 0,  ∀r ∈ R_{pq}, ∀(p, q) ∈ C,
(2.5e)  ∑_{(p,q)∈C} ∑_{r∈R_{pq}} δ_{pqra}h_{pqr}^{∗} = f_{a}^{∗},  ∀a ∈ A,
(2.5f)  β_{k}^{∗}g_{k}(f^{∗}) = 0,  ∀k ∈ K,
(2.5g)  g_{k}(f^{∗}) ≤ 0,  ∀k ∈ K,
(2.5h)  β_{k}^{∗} ≥ 0,  ∀k ∈ K.

The condition (2.5b), together with (2.5a) and (2.5c), implies that the value of the multiplier π_{pq}^{∗} is the minimum generalized travel cost \overline{c}_{pqr} in O-D pair (p, q) and, further, the condition (2.5a) states that these costs are equal for all routes utilized in the O-D pair. Hence, the necessary conditions (2.5a)–(2.5b) imply the generalized Wardrop conditions (2.4). □

The converse conclusion is invalid since the complementarity conditions for the side constraints are not necessarily satisfied whenever the Wardrop-type conditions of the theorem hold; however, a partial converse will be established in the next section.

It follows from the conditions (2.5a)–(2.5d) that the minimal generalized route travel cost in O-D pair (p, q) ∈ C provides the multiplier values π_{pq}^{∗}; this relation is the reason for using the same notation as in the Wardrop conditions (1.1). In some applications, for example in traffic management through link tolls, it may actually be the multiplier values β^{∗} that are primarily sought for, rather than the equilibrium link flows. In Section 3 we consider a queueing network and establish a close relationship between the multiplier values β^{∗} and the link queueing delays.

4Whenever F ∩ G is convex, a solution is guaranteed to exist (e.g., Hartman and Stampacchia [10]).

We may deduce from (1.2d) that

c_{pqr}(h) = ∑_{a∈A} δ_{pqra}t_{a}(f), ∀r ∈ R_{pq}, ∀(p, q) ∈ C; (2.6)

we then obtain from (2.3) that the generalized route travel costs may be stated as

\overline{c}_{pqr} = ∑_{a∈A} δ_{pqra} (t_{a}(f^{∗}) + ∑_{k∈K} β_{k}^{∗} \frac{∂g_{k}(f^{∗})}{∂f_{a}}) , ∀r ∈ R_{pq}, ∀(p, q) ∈ C.

Hence, these route costs are sums of generalized link travel costs

\overline{t}_{a}(f^{∗}) =^{def} t_{a}(f^{∗}) + ∑_{k∈K} β_{k}^{∗} \frac{∂g_{k}(f^{∗})}{∂f_{a}}, ∀a ∈ A. (2.7)

The reader should note that the link cost mapping \overline{t} is obtained from taking the side constraints into account only through a penalization of their first-order terms into the original cost mapping t with multiplier values β_{k}^{∗}, k ∈ K. The link costs \overline{t}_{a}(f^{∗}) may also be derived as the partial derivatives with respect to the link flow variables of the Lagrangean function

L(f, β) =^{def} t(f^{∗})^{T}f + ∑_{k∈K} β_{k}g_{k}(f),

evaluated at (f^{∗}, β^{∗}), that is, the function which is obtained from the objective of (2.2) after a Lagrangean dualization of the side constraints with multiplier values β_{k}^{∗}, k ∈ K. Hence, the generalized link and route travel costs (2.7) and (2.3), respectively, are composed by actual costs and penalty costs, and include in a Lagrangean fashion the impact of the side constraints on the equilibrium problem. The Lagrangean viewpoint is further analyzed and exploited in Section 4.

In general, the multipliers for the side constraints are not unique, and the sets of least-cost routes (in the sense of the generalized equilibrium travel cost) are not the same for different values of these multipliers; consequently, neither the generalized equilibrium link and route travel costs \overline{t} and \overline{c}, respectively, nor the values of the multipliers π_{pq} are unique.^{5} The uniqueness of the multipliers and the sets of least-cost routes is, however, a natural criterion for the well-posedness of the model, in the sense that it describes a stability property.

We shall below establish the uniqueness of the generalized equilibrium travel costs as well as the invariance of the sets of least-cost routes on the solution set of [TAP-VIP-SC-F]. First, we give a sufficient condition for the generalized equilibrium travel costs to be constant on the solution set of [TAP-VIP-SC-F] for any fixed value of the multipliers β. A slightly stronger condition ensures that the equilibrium generalized least-cost routes are the same for every solution to [TAP-VIP-SC-F] and vector β of multipliers; finally, we establish the uniqueness of these multipliers under an additional condition on the side constraints. We then need to introduce the following concept.

Definition 2.2 (co-coercivity). Let X be a nonempty, closed and convex set in ℜ^{n}. A mapping T : X ↦ ℜ^{n} is co-coercive on X if there exists a positive constant α_{T} such that

[T (x^{1}) − T (x^{2})]^{T}(x^{1} − x^{2}) ≥ α_{T} ∥T (x^{1}) − T (x^{2})∥^{2}, ∀x^{1}, x^{2} ∈ X.

5This is in contrast to the basic model [TAP], where convexity of the objective T defined by (1.2a) is sufficient for the equilibrium travel times to be unique; see, e.g., Patriksson [24, Theorem 2.5.a].

Whenever the travel cost mapping t has this property, the travel costs are constant on the solution set of [TAP-VIP-SC-F]; this is a consequence of the following general result. (We believe that this result appears in the doctoral dissertation of Mataoui [19], but have not access to it; a simple proof is therefore given.)

Lemma 2.3 (invariance of the cost mapping on the solution set of a variational inequality). Consider the variational inequality problem of finding an x^{∗} ∈ X such that

[VIP]

T (x^{∗})^{T}(x − x^{∗}) ≥ 0, ∀x ∈ X,

where X is a nonempty, closed and convex set in ℜ^{n} and T : X ↦ ℜ^{n} is a continuous and co-coercive mapping on X. Then, whenever the problem [VIP] has a nonempty set of solutions, the mapping T is constant on this set.

Proof. Let x^{∗} and x^{∗∗} be two arbitrary solutions to [VIP]. Then, T (x^{∗})^{T}(x^{∗∗} − x^{∗}) ≥ 0 and T (x^{∗∗})^{T}(x^{∗} − x^{∗∗}) ≥ 0 holds, and hence, by the co-coercivity of T,

α_{T} ∥T (x^{∗}) − T (x^{∗∗})∥^{2} ≤ [T (x^{∗}) − T (x^{∗∗})]^{T}(x^{∗} − x^{∗∗})
= T (x^{∗})^{T}(x^{∗} − x^{∗∗}) + T (x^{∗∗})^{T}(x^{∗∗} − x^{∗})
≤ 0,

and the result follows. □

If also the gradients of the side constraint functions g_{k}, k ∈ K, are co-coercive, then for any given multiplier vector β^{∗} it follows that the generalized equilibrium travel costs are constant on the solution set. This result is established next.

Lemma 2.4 (uniqueness of the generalized equilibrium route costs for any given multipliers). Let t and ∇g_{k}, k ∈ K, be co-coercive on F. Then for any given vector β^{∗} ∈ ℜ^{|K|} of multipliers for the side constraints (2.1), the generalized link and route travel costs (2.7) and (2.3), respectively, are constant on the solution set of [TAP-VIP-SC-F].

Proof. By Theorem 2.1, any solution (h^{∗}, f^{∗}) to [TAP-VIP-SC-F] solves the variational inequality [TAP-VIP-F] with link cost mapping \overline{t} given by

\overline{t} = t + ∇g(·)^{T}β^{∗} (2.8)

and the (equivalent) problem [TAP-VIP-H] with route cost mapping \overline{c}, which is defined by

H × F ∋ (h, f) ↦ c(h) + Δ^{T}∇g(f)^{T}β^{∗},

where Δ = (δ_{pqra}) is the link-route incidence matrix. The mapping \overline{t} is co-coercive on F since it is a linear transformation of the co-coercive mappings t and ∇g_{k}, k ∈ K (cf. Zhu and Marcotte [33]). The mapping \overline{c} is then co-coercive on H × F, since it is the result of a linear transformation of \overline{t}. The result then follows by appealing to Lemma 2.3 with the problem [TAP-VIP-F] with link cost mapping \overline{t} given by (2.8) taking the role of [VIP]. □

The co-coercivity assumption on the side constraint functions is actually needed only for those side constraints that are active at a solution f^{∗}, i.e., for the indices K(f^{∗}) ⊂ K with

K(f^{∗}) = { k ∈ K | g_{k}(f^{∗}) = 0 },

since β_{k}^{∗} = 0 for all k ∉ K(f^{∗}). The co-coercivity assumption in the theorem may also be replaced by a strict monotonicity assumption on t, i.e., that

[t(f^{1}) − t(f^{2})]^{T}(f^{1} − f^{2}) > 0,  ∀f^{1}, f^{2} ∈ F,  f^{1} ≠ f^{2},

since it then follows that the link flow solution is unique.

We remark that all affine constraint functions have co-coercive gradients; this is thus true in particular for link capacity constraints [cf. (2.12)].

We next establish that the sets of generalized least-cost routes are the same for every solution (h^{∗}, f^{∗}) and vector β of multipliers for the side constraints; in other words, regardless of the flow solution and the multiplier values obtained, the same routes are perceived as being the shortest. This is the first stability result established.

We then need to introduce the following assumption to hold at all link flow solutions f^{∗} ∈ F^{∗} to [TAP-VIP-SC-F].

Assumption 2.5 (nondecreasing side constraint functions). At the flow f ∈ F,

\frac{∂g_{k}(f)}{∂f_{a}} ≥ 0, ∀a ∈ A, ∀k ∈ K.

We remark that if this assumption holds for any flow f ∈ F, then an increase in the flow on a link can never result in any side constraint being more strictly satisfied.

We also need to introduce a strict complementarity assumption on the Wardrop conditions (2.4) for every route flow solution to [TAP-VIP-SC-F].

Theorem 2.6 (uniqueness of the sets of generalized equilibrium shortest routes). Suppose that Assumption 2.5 holds at all link flow solutions f^{∗} to [TAP-VIP-SC-F], and that either there is a unique link flow solution or both t and ∇g_{k}, k ∈ K, are co-coercive on F. Further, assume that for every route flow solution h^{∗} and vectors β ∈ ℜ^{|K|} and π^{∗} ∈ ℜ^{|C|} satisfying (2.5),

(2.9a)  h_{pqr}^{∗} > 0 ⟹ \overline{c}_{pqr} = π_{pq}^{∗},  ∀r ∈ R_{pq},
(2.9b)  h_{pqr}^{∗} = 0 ⟹ \overline{c}_{pqr} > π_{pq}^{∗},  ∀r ∈ R_{pq},

holds for all O-D pairs (p, q) ∈ C. Then the generalized equilibrium shortest routes are the same for every solution (h^{∗}, f^{∗}) to [TAP-VIP-SC-F] and every vector β of multipliers for the side constraints.

Proof. We first define

\overline{c}(β) = c(h^{∗}) + Δ^{T}∇g(f^{∗})^{T}β,

and note that, by Lemma 2.4 and the subsequent remarks, the value of \overline{c}(β), as indicated by the notation, does not depend on the choice of either link nor route flow solution.

Let

H = {h ∈ ℜ^{|R|} | Γh = d; h ≥ 0 }

be the polyhedral description of the set of route flows satisfying (1.2b)–(1.2c), where Γ is the route-O-D pair incidence matrix, H^{∗} denote the set of route flow solutions to [TAP-VIP-SC-F], and choose an arbitrary solution (h^{∗}, f^{∗}) with h^{∗} ∈ rint H^{∗} (rint denotes relative interior) and vector β of multipliers.

Let route r ∈ R_{pq} be any route in an O-D pair (p, q) ∈ C. If h_{pqr}^{∗} = 0 holds, then, since h^{∗} ∈ rint H^{∗}, it follows that

H^{∗} ⊆ { h ∈ H | h_{pqr}^{∗} = 0 },

i.e., every route flow solution h^{∗} satisfies h_{pqr}^{∗} = 0. Using the strict complementarity in (2.9), it then follows that the route r cannot be a least-cost route (in the sense of the generalized travel cost). If h_{pqr}^{∗} > 0 holds, then, by (2.9), it follows that it is a least-cost route (in the sense of the generalized travel cost).

Observing that the above holds for an arbitrary choice of β, we have hence established that the generalized equilibrium shortest routes are the same for any vector of multipliers for the side constraints. Also, since the value of \overline{c}(β) does not depend on the choice of h^{∗} ∈ H^{∗} (cf. Lemma 2.4) these routes are the same for every choice of route flow solution. This completes the proof. □

The proof establishes that the generalized equilibrium shortest routes are precisely those that have a positive flow in some route flow solution to [TAP-VIP-SC-F]. The result established has a strong connection to the notion of exposed faces (e.g., Burke and Moré [6]). In fact, the theorem is equivalent to the result that the face of H exposed by the vector −\overline{c}(β), i.e., the face

arg max_{h∈H} −\overline{c}(β)^{T}h,

is the same for every choice of multiplier β; the face in question may be calculated to be

H^{F} = H ∩ {h ∈ ℜ^{|R|} | h_{pqr} = 0 if h_{pqr}^{∗} = 0 } ,

for any route flow solution h^{∗} ∈ rint H^{∗}. (Note that the above result implies that the total generalized travel cost is constant on the primal-dual solution set.) Further, the face may be characterized by the equivalent (e.g., [6, Th. 2.4]) result that

−\overline{c}(β) ∈ rint N(H^{F})

holds for all vectors β of multipliers, where N(H^{F}) is the normal cone to H at any point in rint H^{F}, and

rint N_{H}(h) = { α ∈ ℜ^{|R|} | α = Γ^{T}μ − γ; γ ∈ ℜ_{+}^{|R|}; h^{T}γ = 0;
γ_{pqr} > 0 if h_{pqr} = 0, ∀r ∈ R_{pq}, ∀(p, q) ∈ C }

is the normal cone to H at h ∈ H.

We finally note that the co-coercivity condition on the gradient mappings ∇g_{k} need only be imposed for

k ∈ K(F^{∗}) =^{def} ⋃_{f^{∗}∈F^{∗}} K(f^{∗}).

Consider an arbitrary solution f^{∗} to [TAP-VIP-SC-F] and two vectors, β^{1} and β^{2}, of multipliers for the side constraints. We then have that

[t(f^{∗}) + ∇g(f^{∗})^{T}β^{1}] − [t(f^{∗}) + ∇g(f^{∗})^{T}β^{2}] = ∇g(f^{∗})^{T}(β^{1} − β^{2}).

Assuming that either the solution is unique or the mappings t and ∇g_{k}, k ∈ K(F^{∗}), are cocoercive on F (so that these mappings are invariant on F^{∗}), and further that the vectors ∇g_{k}(f^{∗}), k ∈ K(F^{∗}), are linearly independent, then from the above relationship it follows that the generalized equilibrium link costs are unique if and only if the multipliers for the side constraints are unique. [An example of linearly independent vectors ∇g_{k}(f^{∗}) is given by the capacity constraints (2.12).] We establish below that the multipliers β for the side constraints are unique under a condition that implies the linear independence condition stated above. To this end, we need to introduce some new notation.

Given a route flow solution h^{∗} to [TAP-VIP-SC-F] we denote by Δ_{+} the link-route incidence matrix obtained from Δ by deleting the rows corresponding to routes with a zero flow in h^{∗}. Similarly, we denote by Γ_{+} the route-O-D pair incidence matrix obtained from Γ. The network thus constructed is, by the positivity of the demand vector d, strongly connected, and therefore the matrix Γ_{+} has full row rank. The consequence of this is that the orthogonal projection onto the null space of Γ_{+} is well-defined. (The null space of Γ_{+} is a subspace of the circulation space (Rockafellar [27, p. 13]) of the network G given h^{∗}.)

Lemma 2.7 (uniqueness of the multipliers). Let f^{∗} ∈ F^{∗}, and assume that for some route flow solution h^{∗} consistent with f^{∗} the orthogonal projections of the vectors

Δ_{+}^{T}∇g_{k}(f^{∗}), k ∈ K(f^{∗})

onto the null space of Γ_{+} are linearly independent. Then the values of the multipliers β for the side constraints are unique.

Proof. Let c_{+}(h^{∗}) be the subvector of c(h^{∗}) obtained by removing all indices for which h_{pqr}^{∗} = 0, and let β be a vector of multipliers.

By the generalized Wardrop condition (2.4a) there is a vector π^{∗} ∈ ℜ^{|C|} such that

c_{+}(h^{∗}) + Δ_{+}^{T}∇g(f^{∗})^{T}β = Γ_{+}^{T}π^{∗}.

Define the projection matrix

P = I − Γ_{+}^{T}(Γ_{+}Γ_{+}^{T})^{−1}Γ_{+},

where I is the identity matrix of order equal to the number of routes with positive flow in the route flow solution considered. (The inverse of the matrix Γ_{+}Γ_{+}^{T} exists since Γ_{+} has full row rank.)

Multiplying the above system of equations with the projection matrix yields

P Δ_{+}^{T}∇g(f^{∗})^{T}β = −P c_{+}(h^{∗}).

Using that, according to the condition (2.5f),

β_{k} = 0, k ∉ K(f^{∗}),

we obtain the equation system

∑_{k∈K(f^{∗})} P Δ_{+}^{T}∇g_{k}(f^{∗})β_{k} = −P c_{+}(h^{∗}). (2.10)

By assumption, the vectors

P Δ_{+}^{T}∇g_{k}(f^{∗}), k ∈ K(f^{∗}),

are linearly independent; the vector β of multipliers considered is therefore the only possible solution to (2.10). □

The second stability result sought is now easily established.

Theorem 2.8 (uniqueness of the generalized equilibrium travel costs). Let f^{∗} ∈ F^{∗}, and assume that for some route flow solution h^{∗} consistent with f^{∗} the orthogonal projections of the vectors

Δ_{+}^{T}∇g_{k}(f^{∗}), k ∈ K(f^{∗})

onto the null space of Γ_{+} are linearly independent. In addition, let either t be strictly monotone on F or both t and ∇g_{k}, k ∈ K(f^{∗}), be co-coercive on F. Then, the generalized equilibrium link and route travel costs (2.7) and (2.3), respectively, are unique.

Proof. Under the strict monotonicity assumption, the link flow solution f^{∗} is unique, and the result follows immediately from Lemma 2.7. The result under the co-coercivity assumption follows from Lemmas 2.4 and 2.7. □

By Theorem 2.1, solutions to [TAP-VIP-SC-F] satisfy the Wardrop equilibrium conditions in terms of the generalized travel costs (2.3), but one can, in general, not relate the actual travel costs of the unused routes to those of the used ones; for example, the least-cost route in an O-D pair may be unused because its generalized cost is too high. However, if Assumption 2.5 holds at a link flow solution to [TAP-VIP-SC-F], then a Wardrop-type principle in terms of actual travel costs may be established.

We also introduce the notions of links and routes that are unsaturated with respect to the side constraints.

Definition 2.9 (unsaturated link and route). A link a ∈ A is said to be unsaturated at the flow f ∈ F if for all k ∈ K,

\frac{∂g_{k}(f)}{∂f_{a}} > 0 ⟹ g_{k}(f) < 0.

A route r ∈ R_{pq}, (p, q) ∈ C, is said to be unsaturated at the flow f ∈ F if all the links a ∈ A on route r are unsaturated.

The following result extends that of Theorem 2.2 in [16], stated for a symmetric model, and is established by using the same arguments.

Theorem 2.10 (Wardrop-type results). Suppose that Assumption 2.5 holds at a link flow solution f^{∗} to [TAP-VIP-SC-F]. Consider an arbitrary route flow solution h^{∗} consistent with f^{∗} and any O-D pair (p, q) ∈ C.

(a) The routes utilized in the O-D pair have equal and minimal generalized route costs.

(b) Assume, with no loss of generality, that the first l routes are utilized in the O-D pair and that m of these are unsaturated. Then the routes may be ordered so that

c_{pq1} = … = c_{pqm} ≥ c_{pq,m+1} ≥ … ≥ c_{pql}.

(c) For any pair of routes r, s ∈ R_{pq},

(2.11) \begin{matrix}route r is unsaturated \\ c_{pqs} > c_{pqr} \end{matrix}\} ⟹ h_{pqs}^{∗} = 0.

(d) For any pair of routes r, s ∈ R_{pq},

\begin{matrix}route r is utilized \\ c_{pqs} < c_{pqr} \end{matrix}\} ⟹ route s is saturated.

If the implication in either of the results (c) and (d) was not fulfilled for some pair of routes, then some traveller would shift to a less costly and unsaturated alternative route; hence, these results are quite natural. As noted above, the O-D routes that are unused in a solution to [TAP-VIP-SC-F] are not necessarily more costly (in actual travel cost) than those used in the O-D pair; this is implied by the result (d) since a route may be saturated at zero flow. Maugeri [20] uses the implication (2.11) as the definition of a generalized user equilibrium solution for an assignment problem of the form [TAP-VIP-SC-F] with route flow capacity side constraints. He also draws the conclusion of the result (d), by relating the travel cost of route s to that of the most costly route among those used in the O-D pair (which does not cause any loss of generality) and making the additional assumption that route s is utilized (i.e., the conclusion is somewhat less general than our result). Clearly, the Assumption 2.5 is crucial for the results (b), (c), and (d) to hold; this assumption is however believed to be quite reasonable in practical applications.

The above result extends that in [16] for the symmetric case, and those stated in Larsson and Patriksson [14] for the link flow capacity side constrained assignment model, i.e., for

K = A,  g_{a}(f) = f_{a} − u_{a},  u_{a} ∈ [0, +∞],  ∀a ∈ A. (2.12)

Clearly, in capacitated traffic assignment problems, the constraint functions g_{a} are nondecreasing (cf. Assumption 2.5), an unsaturated link has a flow which is strictly less than its capacity, and an unsaturated route contains no saturated links (cf. Definition 2.9).

Further, in this case the generalized link travel cost (2.7) reduces to the simple expression

\overline{t}_{a}(f^{∗}) = t_{a}(f^{∗}) + β_{a}^{∗}, ∀a ∈ A, (2.13)

which has been given nice interpretations in the separable case (e.g., Jorgensen [13] and Beckmann and Golob [3]).

3 Equilibrium link queueing delays

In the capacitated case, a steady-state link flow can be considered to be in two distinct regimes. In the first part of the link (which includes its entrance), one observes a moving traffic stream; in the second part of the link (which includes its exit), one observes a steady-state queue whenever the link is saturated.^{6} It is then natural to interpret the value t_{a}(f^{∗}) as being the travel time of the moving traffic stream and the value of the multiplier term in (2.13) as the waiting time in the queue at the link’s exit, i.e., the link queueing delay.

Payne and Thompson [25] (see also Smith [29]) use the notion of queue equilibrium to establish a complete equilibrium characterization of solutions to the capacitated problem for the special case of link travel times being constant regardless of the link flows; their result is extended to the case of non-constant link travel times by Miller et al. [21] (see also Inouye [12]). In these results, a feasible link flow solution f to a capacitated traffic assignment problem together with a vector q ∈ ℜ_{+}^{|A|} of link queueing delays is defined to be a queue equilibrium if the links unsaturated at f carry no queues. (This definition is a restatement of the complementarity condition (2.5f) for the special case of capacity side constraints.) It then follows that a feasible solution f is a solution to [TAP-VIP-SC-F] if and only if there is a vector β of multipliers for the capacity constraints such that f is a Wardrop equilibrium with respect to the generalized link travel costs (2.13) and (f, β) is a queue equilibrium.

Hence, for the link capacity side constrained problem, the values of the multipliers β may be interpreted as equilibrium link queueing delays, and, further, a steady-state solution has a characterization as a Wardrop equilibrium flow in terms of the sum of travel times and steadystate queueing delays on saturated links. This generalized travel cost is, of course, the natural one to be minimized by the individual travellers in a capacitated network with queueing.

In the following, we will establish a complete equilibrium characterization of solutions to [TAP-VIP-SC-F], based on the distributed queue equilibrium concept introduced in [16]; henceforth, we shall then assume that the functions g_{k} are convex on F. (Convexity ensures that a solution to (2.5) is a solution to [TAP-VIP-SC-F]; cf. [30].)

When a supplementary traffic flow restriction (side constraint) involves several link flows, it may cause a queue which, in general, is physically distributed on all the links that are affected by the restriction. Hence, each of the traffic flow restrictions may give rise to a distributed queue.

Definition 3.1 (distributed queue equilibrium). Let f ∈ F ∩ G and let r ∈ ℜ_{+}^{|K|} be a vector of delays in distributed queues. Then (f, r) is a distributed queue equilibrium if the traffic flow restrictions which are unsaturated at f have no distributed queues.

6The length of the queue is assumed to be small compared to that of the entire link, so that the travel time in the moving stream can be considered to be unaffected by the presence of the queue.

This definition restates the complementarity condition (2.5f), and an immediate implication is the following characterization of solutions to [TAP-VIP-SC-F] which corresponds to the equilibrium characterization of solutions to the capacitated model, and includes the partial converse to Theorem 2.1.

Theorem 3.2 (equilibrium characterization of solutions to [TAP-VIP-SC-F]). Let f ∈ F ∩ G. It then satisfies the variational inequality [TAP-VIP-SC-F] if and only if there is a vector β of multipliers for the side constraints (2.1) such that f is a Wardrop equilibrium with respect to the generalized link travel costs (2.7) and (f, β) is a distributed queue equilibrium.

The equilibrium notion should here be interpreted as a steady-state situation evolving after a disequilibrium state whose varying traffic flows eventually stabilize. During the process when the traffic flow gradually adjusts towards an equilibrium state, the travellers make route choice adjustments with the goal to minimize the sums of actual link travel costs and delays in distributed queues under the prevailing traffic conditions. Further, at any given moment a distributed queue will be building up or dissolving depending on whether or not the corresponding traffic flow restriction is violated by the current flow pattern; the generalized route travel costs and the route flows will of course also vary during the disequilibrium state.

We next establish that a solution to [TAP-VIP-SC-F] is also a generalized Wardrop equilibrium and a link queue equilibrium to a capacitated assignment model; in this model, each link capacity can be viewed as the aggregate effect of all traffic flow restrictions (side constraints) on the link’s capability of carrying flow, and, further, each link queue is composed by contributions from distributed queues. The theorem extends that of Theorem 3.3 in [16], stated for a symmetric model, and is established by using the same arguments.

Theorem 3.3 (solutions to [TAP-VIP-SC-F] are link queue equilibria). Let f^{∗} ∈ F ∩ G satisfy the variational inequality [TAP-VIP-SC-F] and suppose that Assumption 2.5 holds at f^{∗}. Further, let β^{∗} be a vector of multipliers for the side constraints (2.1), and let

q_{a}^{∗} =^{def} ∑_{k∈K} β_{k}^{∗} \frac{∂g_{k}(f^{∗})}{∂f_{a}}, ∀a ∈ A. (3.1)

Then f^{∗} is a Wardrop equilibrium with respect to the generalized link travel costs

\overline{t}_{a}(f) = t_{a}(f) + q_{a}^{∗}, ∀a ∈ A, (3.2)

and (f^{∗}, q) is a queue equilibrium with the respect to the link capacity constraints

f_{a} ≤ u_{a}, ∀a ∈ A,

where

u_{a} \{ \begin{matrix}= f_{a}^{∗}, & if q_{a}^{∗} > 0, \\ ≥ f_{a}^{∗}, & if q_{a}^{∗} = 0. \end{matrix}

Combining the above result with that of Theorem 3.2 establishes that distributed queue equilibria for [TAP-VIP-SC-F] are also link queue equilibria for a capacitated model. Further, the equilibrium link queueing delays q^{∗} are then the multipliers for the link capacity constraints.

In the case of capacitated traffic assignment, we obtain the formula

q_{a}^{∗} = β_{a}^{∗}, ∀a ∈ A,

as expected. Also, the capacitated problem constructed in the above result is then equivalent to the original one, in the sense that the link capacities that are binding (i.e., link capacity constraints with β_{a}^{∗} > 0) coincide in the two problems.

According to Theorem 3.3, the penalty term of the generalized link travel cost (2.7) may thus be interpreted as the equilibrium link queueing delay caused by the traffic flow restrictions which are described by the side constraints (2.1). The generalized route cost (2.3) is then the sum of actual travel costs and link queueing delays along the route, and the value of a multiplier π_{pq} is the minimal value of these sums over the routes in the O-D pair (p, q). Further, the delay formula (3.1) states that the queue on a link may be decomposed into contributions from queueing effects arising from several traffic flow restrictions (side constraints), and thus provides an equilibrium link queue representation result.^{7}

As a consequence of Theorem 3.2, there is an equivalence between solutions to [TAP-VIP-SC-F] and the link flow pattern in the traffic network, provided that the latter is a Wardrop equilibrium with respect to generalized travel costs and a distributed queue equilibrium. It is therefore of interest to establish conditions under which these equilibria will arise; specifically, we need to make assumptions on the travellers’ behaviour and on the nature of the traffic flow restrictions which are described by the side constraints. Clearly, a Wardrop equilibrium with respect to the generalized travel costs may be guaranteed through the traditional assumption that the travellers have a rational route choice behaviour. We shall next give conditions on the nature of the traffic flow restrictions described by the side constraints which imply that a distributed queue equilibrium arise in the traffic network. These conditions involve the link distribution and dynamical behaviour of the queues.

First, we assume that each traffic flow restriction may cause a queue which is distributed among the links as stated below.

Assumption 3.4 (delays in distributed queues). There exist parameters γ_{k} ≥ 0, k ∈ K, such that, for any flow f ∈ F and any traffic flow restriction k ∈ K, the portion of the distributed queue which is physically located on a link a ∈ A has queueing delay

γ_{k} \frac{∂g_{k}(f)}{∂f_{a}}.

Second, we assume that the traffic flow restrictions under consideration are prescriptive (hard) and can never be violated in a stationary state, and that each distributed queue appears only when the corresponding traffic flow restriction is active. Further, if the traffic flow is in a disequilibrium state and the travellers successively adjust their route choices with respect to the (varying) generalized travel costs (i.e., actual travel costs and delays in distributed queues), then at any given moment the distributed queue arising from a traffic flow restriction will be building up or dissolving depending on whether or not the restriction is violated.

Assumption 3.5 (distributed queue dynamics).

(a) (Stationary queueing delays) If a traffic flow restriction is saturated at some flow f ∈ F, i.e., g_{k}(f) = 0 for some k ∈ K, then the queueing delay of the distributed queue is in a stationary state, i.e., the parameter γ_{k} has a constant value.

(b) (Unlimited non-stationary queueing delays) If a traffic flow restriction is violated at some flow f ∈ F, i.e., g_{k}(f) > 0 for some k ∈ K, then the queueing delay of the distributed queue is non-stationary and will eventually become arbitrarily large, i.e., the parameter value γ_{k} tends to infinity.

7Interpreting each of the partial derivatives in the expression (3.1) as a measure of the contribution of the flow on a link a to the saturation of the k:th side constraint, in the sense that it is a force towards violating the constraint, this expression also states that the distribution of the queue is proportional to these forces.

(c) (Vanishing non-stationary queueing delays) If a traffic flow restriction is unsaturated at some flow f ∈ F, i.e., g_{k}(f) < 0 for some k ∈ K, then the queueing delay of the distributed queue is non-stationary and will eventually vanish, i.e., the parameter value γ_{k} tends to zero.

As seen from the below theorem, the parameters γ_{k}, k ∈ K, play the role of multipliers. (The result is established by showing that f and β_{k} = γ_{k}, k ∈ K, satisfy the conditions (2.5); the proof parallels that of Theorem 4.1 of [16], and is therefore omitted.)

Theorem 3.6 (stationary flows satisfy [TAP-VIP-SC-F]). Let the link flow f ∈ F and suppose that Assumption 2.5 holds at f. If, in addition, it is a stationary flow with respect to the link travel costs t_{a}(f), a ∈ A, and the link queueing delays, then, under Assumptions 3.4 and 3.5, it also satisfies the variational inequality [TAP-VIP-SC-F].

Hence, under Assumptions 2.5, 3.4 and 3.5, any stationary flow in the transportation network also satisfies [TAP-VIP-SC-F], and we have thus established that the set H^{∗} of solutions to [TAP-VIP-SC-F] then coincides with the steady-state flows in the transportation network.

We conclude this section with the important observation that the characterization of solutions to [TAP-VIP-SC-F] as being Wardrop equilibria with respect to generalized travel costs and distributed queue equilibria suggests that the utilization of side constraints in a traffic equilibrium model is consistent with the basic assumption of rational traveller behaviour.

4 A solution principle for the side constrained model

Whenever side constraints are introduced into a traffic equilibrium model, the classical solution methods, such as the projection and simplicial decomposition algorithms (see, e.g., [23, 24] for overviews), either become inapplicable or their efficiency is seriously degraded. In particular, the linear programming subproblem of a simplicial decomposition algorithm does not separate into a number of shortest route calculations.^{8} In addition, the existing algorithm implementations (research codes mostly) do not possess the ability to take side constraints into account.

When considering possible solution principles for the side constrained model [TAP-VIP-SC-F], it is, however, most natural to aim at exploiting existing algorithms that are available for the basic variational inequality problem [TAP-VIP-F]. This immediately leads us to a classical approach for handling complicating constraints: the pricing strategy (see, e.g., Lasdon [18, Chapter 8] for discussions on this topic in the case of convex optimization).

We associate with the side constraints (2.1) nonnegative prices β_{k}, k ∈ K, for violating them. Given certain values of these prices, the side constraints are priced-out, i.e., handled implicitly in the following way. We consider the problem of finding a flow f(β) ∈ F such that

[TAP-VIP-F, β]

[t(f(β)) + ∇g(f(β))^{T}β]^{T}(f − f(β)) ≥ 0, ∀f ∈ F,

which is a traffic equilibrium problem with link travel cost functions of the form (2.7) [see also (2.8)] and which is solvable with standard methods for the model [TAP-VIP-F]. If the travel cost mapping t is strictly monotone, then the solution f(β) is unique, since the cost mapping of [TAP-VIP-F, β] is then strictly monotone.

In the next result it is established that equivalence between the priced-out problem [TAP-VIP-F, β] and the original problem [TAP-VIP-SC-F] is obtained when choosing the price vector β equal to a vector of multipliers for the side constraints (2.1), under the assumption that the link travel cost mapping t is strictly monotone.

8In the simple special case of link capacity side constraints the subproblem becomes a linear multicommodity network flow problem, which is prohibitively expensive to solve repeatedly.

Theorem 4.1 (an equivalent equilibrium model). Let t be strictly monotone on F. Let β^{∗} be an arbitrary vector of multipliers for the side constraints (2.1). Then the unique solution to the equilibrium model [TAP-VIP-F] with link travel cost mapping \overline{t} given by (2.8) equals that of [TAP-VIP-SC-F].

Proof. We know, by Theorem 2.2 of Tobin [30], that f^{∗} solves [TAP-VIP-SC-F] if and only if it solves the program (2.2). Similarly, f(β^{∗}) solves [TAP-VIP-F, β^{∗}] if and only if it solves

(4.1)  minimize_{f∈F} t(f(β^{∗}))^{T}f + ∑_{k∈K} β_{k}^{∗}g_{k}(f).

Comparing the optimality conditions (2.5) of the program (2.2) with those of (4.1), we find that f^{∗} must be a solution to (4.1) and therefore also to [TAP-VIP-F, β^{∗}]. But by the strict monotonicity of the cost mapping of [TAP-VIP-F, β^{∗}], f(β^{∗}) is the unique solution to [TAP-VIP-F, β^{∗}]. It must therefore be the case that f(β^{∗}) = f^{∗}. □

Hence, the side constrained equilibrium model [TAP-VIP-SC-F] may be solved as an equivalent traffic equilibrium problem with appropriately chosen travel cost functions. Moreover, the link travel cost mapping (2.8) is a precise description of the influence of the supplementary traffic flow restrictions on the travel cost perception of the users of the traffic network and of their route choice behaviour.

This pricing strategy leads, by the result of Theorem 4.1, to a solution approach for [TAP-VIP-SC-F] once a systematic means for finding optimal values of the prices (i.e., multipliers) has been devised. One possible means is to solve the (implicitly defined) dual variational inequality problem of finding a β^{∗} ∈ ℜ_{+}^{|K|} such that (e.g., Mosco [22])

[DTAP-VIP-SC-F]

f(β^{∗})^{T}(β − β^{∗}) ≥ 0, ∀β ∈ ℜ_{+}^{|K|},

where the mapping ℜ_{+}^{|K|} ∋ β ↦ f(β) is defined through the solution of [TAP-VIP-F, β].^{9}

Since the constraints of [DTAP-VIP-SC-F] are very simple, one may solve it using an iterative search method for (essentially) unconstrained problems. As the values of the prices tend to a vector of multipliers in the dual solution procedure, the primal solution f(β) will simultaneously approach feasibility with respect to the side constraints and tend to a solution to [TAP-VIP-SC-F]; a near-feasible solution with respect to the side constraints will, in many cases, be satisfactory considering the uncertainties in the input data; near-feasibility is also satisfactory when the side constraints are weak, that is, when they do not need to be fulfilled exactly. Note, however, that there is no need to consider the problem [DTAP-VIP-SC-F] explicitly in order to obtain the multipliers β^{∗} (see below for an alternative algorithm that provides β^{∗}); further, the dual problem [DTAP-VIP-SC-F] is well-defined only under assumptions that may be overly restrictive in a practical application (e.g., [22]).

An alternative to the above approach is to utilize nonlinear pricing, that is, to penalize a violation of a side constraint k ∈ K by means of a nonlinear function of g_{k} (as opposed to the use of constant prices, i.e., a linear penalty function, as described above). The advantages of using such an approach are that a nonlinear penalty function enforces proximity to feasibility with respect to the side constraint stronger than a linear penalty function does (cf. [TAP-VIP-F, β]), and that the resulting algorithm may be convergent under weaker monotonicity properties of the link cost mapping. One such scheme is the (proximal) method of multipliers (e.g., Rockafellar [26]), in which the mapping \overline{t} of [TAP-VIP-F, β] is replaced by

9Here, we are assuming that the mapping ℜ_{+}^{|K|} ∋ β ↦ f(β) is a point-to-point mapping, which in general requires t to be strictly monotone on F.

t̃(f) = t(f) + ∑_{k∈K} max\{0, β̃ + c̃g_{k}(f)\}∇g_{k}(f) + \frac{μ^{2}}{c̃} (f − f̃),

where c̃ > 0 is a penalty parameter, μ ≥ 0 is a parameter used to control the nonlinearity of the mapping t̃, and f̃ and β̃ are current estimates of the link flow and dual solutions to [TAP-VIP-SC-F] respectively. In this scheme, at some iteration k a variational inequality [TAP-VIP-F] with t^{k} ≡ t̃ as the link cost mapping is solved (with f^{k} = f̃ and so on as iterates), which gives the unique solution f^{k+1}, after which a simple updating step is performed on the dual estimate (resulting in β^{k+1}), and possibly also on the penalty parameter. If the original link travel cost mapping t is monotone, then this algorithm generates a sequence of flows and multiplier estimates that converges at least linearly to a pair (f^{∗}, β^{∗}) of solutions to [TAP-VIP-SC-F], although there may be more than one solution pair (cf. [26]).

For a symmetric link capacitated model Larsson and Patriksson [14] develop and evaluate an augmented Lagrangean dualization technique. (The augmented Lagrangean scheme is, in fact, the specialization to the nonlinear program describing that model of the above described multiplier method with μ = 0.) They establish the efficiency of this technique for finding the values of the multipliers β and for solving the capacitated model, and also conclude that this dualization scheme is in both these respects more efficient than traditional Lagrangean dualization (which corresponds to using constant prices as discussed above).

The result of Theorem 4.1 implies that the solution of a side constrained traffic assignment model can be used as a means for guiding a traffic engineer how to refine tentative travel time functions in order to bring the flow pattern into agreement with the anticipated results (cf. Hearn [11]), provided that he/she can identify reasonable traffic flow characteristics or restrictions that are violated by the traffic flow obtained when using the tentative travel time functions. Further, the application of an iterative solution procedure to the dual problem [DTAP-VIP-SC-F] (or the one corresponding to nonlinearly priced-out side constraints) can then be given the nice interpretation of an automatized process of adjusting the travel time functions towards more appropriate ones, which are reached in the limit.

Further, the dual problem [DTAP-VIP-SC-F] has the interpretation of being the problem of finding a distributed queue equilibrium (and also a link queue equilibrium), under the implicit presumption that the traffic flow patterns considered are generalized Wardrop equilibria with respect to actual travel costs and link queueing delays; specifically, the evaluation of the problem mapping of [DTAP-VIP-SC-F] for a given value of β then amounts to finding a generalized Wardrop equilibrium with respect to link travel costs of the form (3.2) and link queueing delays of the form (3.1).

We conclude this section by discussing the derivation of price-directive traffic management schemes through the solution of the side constrained equilibrium problem. Consider a situation in which the managers of a traffic system wish to reach certain goals with respect to the performance of the system; typical examples of performance goals are maximal travel times and traffic volumes on certain links. Further, the tool to be used for reaching these goals is the introduction of link tolls, which divert the travellers’ route-choices from the travel-time minimizing ones.^{10} The levels of aspiration of the goals are then formulated as a set of side constraints, and the solution of the side constrained problem is the means for calculating the proper link tolls [that is, the penalty cost terms of the generalized link travel costs (2.7)], which, when imposed upon the individual travellers, change their route-choice behaviour so that the traffic management goals are reached, without the need to resort to a more direct or centralized traffic control.

The proper link tolls can alternatively be determined through the solution of the dual problem [DTAP-VIP-SC-F] (which may be viewed as the problem of finding the tolls which make the side constraints satisfied and optimally utilized). Moreover, the solution of the dual problem using an iterative search procedure may be interpreted as a mathematical simulation of a real-life process in which a traffic engineer attempts to enforce some traffic management goals by introducing link tolls and modifying them until the travellers’ behavioural response is the intended one.^{11}

10See Bernstein and Smith [4] and the references cited therein for an overview of the use of pricing in networks.

5 Conclusions and further research

In the process of constructing a refinement of a traffic assignment model by incorporating some supplementary flow relationships or restrictions one faces the problem of deciding which one of two, fundamentally different, modelling strategies to use. The traditional approach has been to redefine the travel cost functions, while the alternative is to include a set of side constraints. Which one of these two strategies to apply to a particular refinement should, of course, be determined by its nature (for example, by its physical properties); fairly natural criteria are by which strategy the resulting model becomes more easily formulated and calibrated.

Suppose that a model is to be refined through the inclusion of some traffic flow relationships that are best represented explicitly by side constraints, but that one instead attempts to capture them implicitly through modifications of the travel cost functions, without first identifying the proper side constraints; we then notice the following: (1) the proper travel cost mapping to be used has the form (2.8), (2) this travel cost mapping involves gradients of the side constraint functions, which however are unknown since the side constraints have not been formulated explicitly, and (3) the appropriate values of the parameters β are unknown, since the side constrained problem is not solved. We believe that these observations at least partially explain why traffic assignment models with complex travel cost functions may be difficult to calibrate (see also Harker and Pang [9, Section 7]). In contrast, the refinement of an assignment model through the inclusion of side constraints constitutes a very direct approach, which is also very flexible since the side constraints may be nonlinear as well as nonseparable; further, their physical interpretations may facilitate the estimation of the proper values of their coefficients. Hence, we believe that this approach is appealing from the practical viewpoint.

Whenever side constraints are utilized in a refinement of the traffic equilibrium model [TAP-VIP-F], the solution of the resulting model automatically produces the travel cost mapping (2.7) of an equivalent traffic equilibrium model of the form [TAP-VIP-F]. Hence, through a process in which one or more side constrained models are solved, one may derive the functional forms of (i.e., determine the appropriate side constraints) and calibrate (i.e., find the proper coefficients β) adjusted travel cost functions which indirectly take into account the relationships that are described by the side constraints. Further, the solution of a dual problem for finding the multiplier values may then be viewed as a systematic means for calibrating these cost functions. This principle for deriving refined descriptions of the actual travel costs may be to prefer to the traditional way of calibrating them, since, for the reasons given above, it may be comparably easy to identify and calibrate a set of appropriate side constraints.

Effective and efficient computational tools for the solution of side constrained models can be based on the application of the proximal multiplier/augmented Lagrangean principle, which was in Larsson and Patriksson [14] successfully applied to the separable link capacitated model. The results obtained in that study suggest that also other classes of side constrained traffic assignment models can be efficiently dealt with computationally, although the side constraints will in general destroy the Cartesian product structure of the traditional assignment models. Further, this solution principle does not impose any significant limitations on the design of the model since it can handle both nonlinear and nonseparable side constraints.

Another subject for continued research is a further investigation of price-directive traffic management schemes based on link tolls which are obtained through the solution of a side constrained traffic equilibrium model. This technique for deriving link tolls is appealing since it is quite natural to formulate traffic management goals in terms of side constraints, so that, in fact, it supports the process of identifying the proper goals to be formulated, and, further, since it is quite flexible with respect to which goals that can be considered.

11This strategy for finding suitable link tolls can certainly not be implemented in the real-life traffic system.

It is our conviction that it should in many traffic assignment contexts, and for different purposes, be beneficial to utilize side constraints for refining a model, especially since the side constraints may in many situations be relatively easy to derive and calibrate. The results presented in this paper and in [14, 15, 16] provide a theoretical justification for the utilization of side constraints as a means for refining traffic equilibrium models, as well as a basis and a motivation for a continued, theoretical and practical, exploration of this modelling strategy.

Acknowledgements

An earlier version of this report was presented at the Workshop on Equilibrium Problems with Side Constraints, Lagrangean Theory and Duality, in Catania, Italy, December 9–10, 1994. The authors wish to thank Professor Antonino Maugeri for organizing this event and inviting the second author to present this work at the Workshop. During the completion of the report, the first author was sponsored by the Swedish Transport and Communications Research Board (Grant TFB 92-128-63), and the second author by a postdoctoral scholarship from the Swedish Research Council for Engineering Sciences (TFR) (Grant 282-93-1195).

References

[1] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, New York, NY, second ed., 1993.

[2] M. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, New Haven, CT, 1956.

[3] M. J. Beckmann and T. F. Golob, Traveler decisions and traffic flows: a behavioral theory of network equilibrium, in Transportation and Traffic Theory, Proceedings of the 6th International Symposium on Transportation and Traffic Theory, Sydney, August 26–28, 1974, D. J. Buckley, ed., Elsevier, New York, NY, 1974, pp. 453–482.

[4] D. Bernstein and T. E. Smith, Equilibria for networks with lower semicontinuous costs: with an application to congestion pricing, Transportation Science, 28 (1994), pp. 221–235.

[5] D. E. Boyce, B. N. Janson, and R. W. Eash, The effect on equilibrium trip assignment of different link congestion functions, Transportation Research, 15A (1981), pp. 223–232.

[6] J. V. Burke and J. J. Moré, Exposing constraints, SIAM Journal on Optimization, 4 (1994), pp. 573–595.

[7] A. Charnes and W. W. Cooper, Multicopy traffic network models, in Theory of Traffic Flow, Proceedings of the Symposium on the Theory of Traffic Flow Held at the General Motors Research Laboratories, Warren, MI, December 7–8, 1959, R. Herman, ed., Elsevier, Amsterdam, 1961, pp. 85–96.

[8] T. L. Friesz, D. Bernstein, N. J. Mehta, R. L. Tobin, and S. Ganjalizadeh, Day-to-day dynamic network disequilibria and idealized traveler information systems, Operations Research, 42 (1994), pp. 1120–1136.

[9] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), pp. 161–220.

[10] P. Hartman and G. Stampacchia, On some non-linear elliptic differential-functional equations, Acta Mathematica, 115 (1966), pp. 271–310.

[11] D. W. Hearn, Bounding flows in traffic assignment models, Research Report 80-4, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 1980.

[12] H. Inouye, Traffic equilibria and its solution in congested road networks, in Proceedings of the IFAC Conference on Control in Transportation Systems, Vienna, 1986, R. Genser, ed., Pergamon Press, Oxford, 1987, pp. 267–272.

[13] N. O. Jorgensen, Some aspects of the urban traffic assignment problem, graduate report, Institute of Transportation and Traffic Engineering, University of California, Berkeley, CA, 1963.

[14] T. Larsson and M. Patriksson, An augmented Lagrangean dual algorithm for link capacity side constrained traffic assignment problems, Transportation Research, B (to appear).

[15] T. Larsson and M. Patriksson, On side constrained models of traffic equilibria, in Variational Inequalities and Network Equilibrium Problems, Proceedings of the 19th Course, Variational Inequalities and Network Equilibrium Problems, of the International School of Mathematics “G. Stampacchia,” Erice, Italy, June 19–25, 1994, F. Giannessi and A. Maugeri, eds., Plenum Press, New York, NY, 1995 (to appear).

[16] T. Larsson and M. Patriksson, On side constrained traffic assignment models—equilibrium characterizations of solutions and an algorithm principle, under revision for possible publication in Transportation Research, B.

[17] T. Larsson and M. Patriksson, Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transportation Science, 26 (1992), pp. 4–17.

[18] L. S. Lasdon, Optimization Theory for Large Systems, Macmillan, New York, NY, 1970.

[19] M. A. Mataoui, Contributions à la Décomposition et à l’Agrégation des Problèmes Variationnels, Doctoral dissertation, École des Mines de Paris, Paris, 1990.

[20] A. Maugeri, Optimization problems with side constraints and generalized equilibrium principles. Paper presented at the Workshop on Equilibrium Problems with Side Constraints, Lagrangean Theory and Duality, Catania, Italy, December 9–10, 1994.

[21] S. D. Miller, H. J. Payne, and W. A. Thompson, An algorithm for traffic assignment on capacity constrained transportation networks with queues. Paper presented at the Johns Hopkins Conference on Information Sciences and Systems, The Johns Hopkins University, Baltimore, MD, April 2–4, 1975.

[22] U. Mosco, Dual variational inequalities, Journal of Mathematical Analysis and Applications, 40 (1972), pp. 202–206.

[23] A. Nagurney, Network Economics: A Variational Inequality Approach, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1993.

[24] M. Patriksson, The Traffic Assignment Problem: Models and Methods, Topics in Transportation Series, VSP, Utrecht, The Netherlands, 1994.

[25] H. J. Payne and W. A. Thompson, Traffic assignment on transportation networks with capacity constraints and queueing. Paper presented at the 47th National ORSA Meeting/TIMS 1975 North-American Meeting, Chicago, IL, April 30–May 2, 1975.

[26] R. T. Rockafellar, Monotone operators and augmented Lagrangian methods in nonlinear programming, in Nonlinear Programming 3, Proceedings of the Nonlinear Programming Symposium 3, University of Wisconsin–Madison, Madison, WI, July 11–13, 1977, O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds., Academic Press, New York, NY, 1978, pp. 1–25.

[27] R. T. Rockafellar, Network Flows and Monotropic Optimization, John Wiley & Sons, New York, NY, 1984.

[28] J. G. Sender and M. Netter, Équilibre offre-demande et tarification sur un réseau de transport, Rapport de recherche 3, Département Economie, Institut de Recherche des Transports, Arcueil, France, 1970.

[29] M. J. Smith, Traffic control and traffic assignment in a signal-controlled network with queueing, in Proceedings of the 10th International Symposium on Transportation and Traffic Theory, Boston, MA, 1987.

[30] R. L. Tobin, Sensitivity analysis for variational inequalities, Journal of Optimization Theory and Applications, 48 (1986), pp. 191–204.

[31] J. G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institute of Civil Engineers, Part II, (1952), pp. 325–378.

[32] H. Yang and S. Yagar, Traffic assignment and traffic control in general freeway-arterial corridor systems, Transportation Research, 28B (1994), pp. 463–486.

[33] D. L. Zhu and P. Marcotte, Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities, Publication CRT-926, Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, 1993.