A mathematical model and descent algorithm for bilevel traffic management

Michael Patriksson^{∗} and R. Tyrrell Rockafellar^{†}

October 12, 2001

Abstract

We provide a new mathematical model for strategic traffic management, formulated and analyzed as a mathematical program with equilibrium constraints (MPEC). The model includes two types of control (upper-level) variables, which may be used to describe such traffic management actions as traffic signal setting, network design, and congestion pricing. The lower-level problem of the MPEC describes a traffic equilibrium model in the sense of Wardrop, in which the control variables enter as parameters in the travel costs. We consider a (small) variety of model settings, including fixed or elastic demands, the possible presence of side constraints in the traffic equilibrium system, and representations of traffic flows and management actions in both link–route and link–node space.

For this model, we also propose and analyze a descent algorithm. The algorithm utilizes a new reformulation of the MPEC into a constrained, locally Lipschitz minimization problem in the product space of controls and traffic flows. The reformulation is based on the Minty parameterization ([Min67]) of the graph of the normal cone operator for the traffic flow polyhedron. Two immediate advantages of making use of this reformulation are that the resulting descent algorithm can be operated and established to be convergent without requiring that the travel cost mapping is monotone, and without having to ever solve the lower-level equilibrium problem. We provide example realizations of the algorithm, establish their convergence, and interpret their workings in terms of the traffic network.

Key words: Traffic equilibrium; Stackelberg game; mathematical program with equilibrium constraints; bilevel programming; toll optimization; queueing model; network design; system optimal flow; subsidies; Minty map; locally Lipschitz minimization; directional derivative; Armijo line search; stationary point.

1 Introduction

The need for measures to reduce congestion in the metropolitan traffic areas is becoming more serious as citizens keep clustering in cities with the immediate side effect of an increase in traffic demand. A functioning society depends upon the mobility provided by the transportation network to enable its members to participate in essential activities such as production, consumption, communication and recreation. It is however necessary for society also to introduce congestion-relief measures in order for the quality of life and the environment, and the safety of the citizens, not to deteriorate.

Any well-founded traffic model recognizes the individual network user’s right to decide when, where and how to travel. The criteria by which the user makes these choices are selfish, and are therefore on the aggregate level not entirely in par with society’s goals of an efficient and safe utilization of the traffic network. A classical example of this conflict is that the typical traveller can be expected to choose a route between his/her origin and destination such that the combined travel time and cost is minimal given the network conditions when the travel is made; the aggregate effect of these decisions is a network flow which does not minimize the total system costs.

We may model this conflict in the traffic system as a noncooperative Stackelberg game, in which a traffic manager, represented as the leader, takes some action, such as a change in the infrastructure or in the traffic signal plans, so as to achieve some overall management goal with respect to the distribution of the traffic in the network and some measure of network performance. The travellers are then modelled as the followers; they react to the actions of the manager by modifying their behaviour, for example by adjusting their route choices, travel modes or time of day to travel. If the manager’s actions are adequate, then the travellers’ response is the desired one. Common means for achieving such a change in the traffic flows are to invest in traffic network capacity, to introduce or adjust traffic controls such as traffic lights, to introduce tolls on some links, or to supply the travellers with information about alternative routes. The common point in all these traffic management models is that the main control variable is the users’ travel costs (or, rather, travel cost adjustments), even though they may be influenced indirectly through the actions implemented.

∗Department of Mathematics, Chalmers University of Technology, S-412 96 Gothenburg, Sweden. E-mail:

mipat@math.chalmers.se

†Department of Mathematics, University of Washington, Seattle, WA 98195-4350, USA. E-mail:

rtr@math.washington.edu

Taking as the starting point a general Stackelberg model of the decision problem, we thereafter provide several examples of possible management goals and the corresponding model instances. Measures that one can model through this strategy are variations in traffic signal plans, alterations of the network infrastructure, also referred to as network design, and the introduction and setting of tolls in the network. We begin however with a short discussion on the equilibrium model which represents the behaviour of the network users given a network infrastructure. We stress already at this stage that we shall be concerned only with the case of static equilibrium conditions, thus ignoring in this work possible time-dependent (dynamic) effects.

2 Wardrop equilibrium

Let G = (N , A) be a 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 initially shall be assumed fixed) giving rise to a link traffic flow pattern. We assume that the network is strongly connected, that is, that at least one route joins each origin–destination (OD) pair.

Wardrop’s user equilibrium principle states that for every OD 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 for OD 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 ∈ ℜ^{|R|} of route flows, where |R| denotes the total number of routes in the network; with this notation, an equilibrium flow is defined by the conditions

h_{pqr} > 0 ⟹ c̄_{pqr} = π_{pq},  r ∈ R_{pq},  (p, q) ∈ C,  (1a)
h_{pqr} = 0 ⟹ c̄_{pqr} ≥ π_{pq},  r ∈ R_{pq},  (p, q) ∈ C,  (1b)

where the value of π_{pq} := π_{pq}(h) is the minimal (i.e., equilibrium) route cost in OD pair (p, q). By the nonnegativity of the route flows, the system (1) can more compactly be written as the complementarity system

0 ≤ h_{pqr} ⊥ (c̄_{pqr} − π_{pq}) ≥ 0,  r ∈ R_{pq},  (p, q) ∈ C,  (2)

where a ⊥ b, for two arbitrary vectors a, b ∈ ℜ^{n}, means that a^{T}b = 0. The Wardrop conditions state that an equilibrium state is reached precisely when no traveller can decrease his/her travel cost by unilaterally shifting to another route.

In order to cast the Wardrop conditions as a variational inequality problem, we need to decide in which space we wish to represent the flows and the flow feasibility requirements. A general form is obtained by describing the set of feasible, aggregate, link flows as the solution in f ∈ ℜ^{|A|} to the linear system

f = V v,  (3a)
W v = d,  (3b)
v ≥ 0,  (3c)

where v is the (disaggregated) vector of the commodity flows, V is an incidence matrix which describes the aggregation of these flows into a corresponding link flow f, and W is an incidence matrix which describes the feasibility requirements with respect to the demand, d, in the commodity flow space.

The most common representation of the Wardrop conditions as a variational inequality problem is in terms of the route flow variables h_{pqr}. We obtain this formulation by identifying v = h, d ∈ ℜ_{++}^{|C|} as the vector of each OD pair’s demand, and W = Γ^{T}, where Γ ∈ ℜ^{|R|×|C|} is the route–OD pair incidence matrix (i.e., the element γ_{rk} is 1 if route r joins OD pair k = (p, q) ∈ C, and 0 otherwise). In a disaggregated version of the Wardrop conditions, we consider only utilizing the part (3b)–(3c) of the system (3) above, thus describing the (bounded polyhedral) set

H := {h ∈ ℜ_{+}^{|R|} | Γ^{T}h = d }

of demand-feasible route flows. The condition (1) is equivalent to h satisfying

−c̄(h) ∈ N_{H}(h),  [VIP-H]

where c̄: ℜ_{+}^{|R|} ↦ ℜ_{++}^{|R|} is the vector of route travel cost functions, and N_{S}(s) denotes the normal cone to a nonempty, closed and convex set S ⊆ ℜ^{n} at s ∈ ℜ^{n}, that is, the set

N_{S}(s) := \begin{cases}\{ z ∈ ℜ^{n} | z^{T}(y − s) ≤ 0, ∀y ∈ S \}, & s ∈ S, \\ ∅, & s ∉ S. \end{cases}

To see this equivalence directly, we utilize the notation Γ to rewrite (2) as follows:

0 ≤ h ⊥ (c̄(h) − Γπ) ≥ 0.  (4)

Together with the feasibility requirement that Γ^{T}h = d must hold, the system (4) describes the optimality conditions for h solving the linear program to minimize c̄(h)^{T}y over y ∈ H; this is precisely [VIP-H].

We remark here that the existence of several groups of users or modes of transport is easily modelled within the above framework, by simply creating a copy of the network for each user group and mode, and relating their travel costs, if needed, through the vector c̄.

In the case where the travel cost of a route is the sum of the travel costs on the links defining it (i.e., the route costs are additive), then the above Wardrop conditions can be described in terms of link flows. We then further identify V = Λ in (3a), where Λ ∈ {0, 1}^{|A|×|R|} is the link–route incidence matrix (i.e., the element λ_{ar} equals 1 if route r utilizes link a, and 0 otherwise), and thus the (bounded polyhedral) set of demand-feasible link flows

F̂ := {f ∈ ℜ^{|A|} | ∃h ∈ H with f = Λh } .

Then, the problem [VIP-H] can be equivalently written as

−t̄(f) ∈ N_{F}(f),  [VIP-F̂]

where t̄: ℜ_{+}^{|A|} ↦ ℜ_{++}^{|A|} is the vector of link travel cost functions. (The link and route costs are related by c̄(h) = Λ^{T}t̄(f), for any pair (h, f) ∈ H × F̂.)

The set of feasible link flows can also be described by the OD-specific link flows that satisfy the demand for transportation and flow conservation constraints for all the nodes of the network; this is the second most popular representation of feasible flows. In the system (3), we then identify W as a block-diagonal matrix with |C| blocks W_{k}, with W_{k} = A, A ∈ {−1, 0, 1}^{|N |×|A|} being the node–link incidence matrix of the network. Further, d is a (|C| · |A|)-vector, with |C| vectors d_{k}, each being a vector of OD-specific demands, stacked on top of each other. (The elements of d_{k} sum to zero.) We also identify v as the (|C| · |A|)-vector of commodity link flows f_{ak}. Hence, (3b) corresponds to the commodity-specific flow conservation constraints

Af_{k} = d_{k}, k ∈ C.

Finally, V is the block-diagonal (|A| × |C|)-matrix which describes the aggregation of the commodity link flows f_{k} into f. Summarizing, then, the system (3) describes the (unbounded polyhedral) set of demand-feasible link flows

F := { f ∈ ℜ^{|A|} | ∃f_{k} ∈ ℜ_{+}^{|A|}, k ∈ C, with f = ∑_{k∈C} f_{k} and Af_{k} = d_{k} } .

In the present setting, of course, k is identified with an OD pair (p, q) ∈ C, and, further, each vector d_{k} has precisely two nonzeros. We may, however, consider k to denote a less disaggregated flow, such as flows from different origins, or different vehicle types, etc. The two representations that we have chosen here are in that sense at the two extremes in terms of level of aggregation. We also note that in more generality, we may consider different networks, that is, different matrices A_{k}, for each commodity k, or type k of traffic. This will necessarily also lead to a proper modification of the matrix V above.

Note that F̂ ⊂ F holds, because the latter contains cyclic flows, but due to the positivity assumption on t̄ no equilibrium flow will utilize any cyclic flow, so this alternative representation is, in that sense, equivalent. In the following, we shall always consider the version [VIP-F] whenever considering a link flow-based equilibrium system.

More general considerations, such as the possible presence of side constraints in the equilibrium system, or that the demand at equilibrium depends on the cost of the trip, is relegated to Section 7

3 A general Stackelberg model

3.1 The mathematical model

This section introduces a general Stackelberg model for the society’s traffic management problem. We introduce two vectors, ρ and β, of parameters denoting the actions taken by the traffic manager.

The parameter ρ is assumed to enter the travel cost function, leading to the parameterized (and presumed continuous) function t(ρ, f) (in the case of the equilibrium model [VIP-F]), or c(ρ, h) (in the case of the equilibrium model [VIP-H]). Further, ρ is constrained to a polyhedral set, which we denote by P ⊂ ℜ^{p}, and which may be determined by political, practical, environmental and economical constraints, and possibly other considerations as well. (The assumption that P is polyhedral is not essential to the results to be presented, but simplifies some parts of the algorithm.)

The parameter β enters the travel cost function as an additive term. So, given actions (ρ, β), the travel cost mapping takes the form f ↦ t(ρ, f) + β (respectively, h ↦ c(ρ, h) + β). We allow for no explicit constraints on β, since we wish for an equilibrium to always exist whatever the choice of ρ ∈ P. However, one could always include smooth penalties for any constraints one wishes to impose on β into the objective function φ, to be discussed next.

Among the possible actions, the manager optimizes a function, φ, defined over P × ℜ^{|A|} × ℜ^{|A|} (respectively, P × ℜ^{|R|} × ℜ^{|R|}), of the actions and traffic flows. This function may include some further measures of network performance as well as measures of the cost and/or benefits associated with a given action. We shall presume throughout that this function is continuously differentiable on P × ℜ^{|A|} × ℜ^{|A|}, but remark that in principle, piecewise differentiability would suffice.

Taking [VIP-F] as the underlying equilibrium model, the general problem then is to

[MPEC-F]

minimize φ(ρ, β, f)  (5a)
subject to ρ ∈ P,  (5b)
−t(ρ, f) − β ∈ N_{F} (f).  (5c)

For further reference, we shall denote the set f of solutions to (5c) by S(ρ, β). If the lower-level problem (5c) has unique solutions f, then the problem [MPEC-F] is well-defined, but in situations where there is more than one equilibrium solution, it is not clear how to interpret the minimization operation in [MPEC-F], since the value of φ(ρ, β, f) then is impossible to predict. We next turn to explain our proposal to resolve this issue.

3.2 Sensitivity analysis and well-posedness under lower-level nonuniqueness

In the case where the cost mapping f ↦ t(ρ, f) + β is positive and strictly monotone on F, the solution, f, to (5c) is uniquely determined by (ρ, β), that is, S(ρ, β) is a singleton set. We may, in the situation that this is true for every (ρ, β) ∈ P × ℜ^{|A|}, think of the problem [MPEC-F] as that to find the minimum of the function (ρ, β) ↦ φ(ρ, β, f(ρ, β)) over P × ℜ^{|A|}, where f(ρ, β) denotes the unique solution to (5c). This implicit function is continuous on P × ℜ^{|A|}.

For the development of efficient algorithms for finding a minimum of the function (ρ, β) ↦ φ(ρ, β, f(ρ, β)) over P × ℜ^{|A|} it is however detrimental that it has stronger differentiability properties. Much is of course known about the sensitivity and stability of solutions to perturbed variational problems (see, for example, the monographs [LPR96, RoW98, OKZ98, BoS00]), and specialized analyses have been conducted also for the case at hand. Important to note is that in traffic equilibrium models, the presence of variables at different levels of aggregation (total link flows together with commodity link flows or route flows) means that some of the traditional techniques in sensitivity analysis, such as the strong regularity results by Robinson [Rob80], are applicable only by vieweing the problem in terms of the aggregated variables (total link flows). In the sensitivity analysis of traffic equilibria, this possibility has most often been overlooked, and much (unnecessary) effort has been spent on the choice of an appropriate disaggregated flow (cf. [ToF88, QiM89, Yen95, CSF00]). The fact that the sensitivity analysis is independent of any such choice was demonstrated first in [PaR01] for the case of elastic demands. Patriksson [Pat01] provides a rather complete analysis of the sensitivity of traffic equilibria, and improves and extends the analyses made in [ToF88, QiM89, Yen95, Out97, CSF00, PaR01], including characterizations of the differentiability, and the generation of subgradients, of the mapping S at a reference point (ρ^{r}, β^{r}). An overview of the sensitivity analysis of the problem at hand follows.

Assume that the parameterization is rich enough so that the rank of the Jacobian matrix ∇_{ρ}t(ρ^{r}, f^{r}) is full (that is, p). (This condition can always be fulfilled through the introduction of dummy parameters.) We introduce the sensitivity problem as that of, given a perturbation (δρ, δβ), finding a solution to the variational inequality

DS((ρ^{r}, β^{r}) | f^{r})(δρ, δβ) := {δf ∈ ℜ^{|A|}| − r(δρ, δβ, δf) ∈ N_{K}(δf)} ,  (6)

where

r(δρ, δβ, δf) := ∇_{ρ}t(ρ^{r}, f^{r})δρ + δβ + ∇_{f}t(ρ^{r}, f^{r})δf  (7)

is the problem mapping, and where its feasible set is the critical cone,

K := T_{F} (f^{r}) ∩ [t(ρ^{r}, f^{r}) + β^{r}]^{⊥},  (8)

where T_{F} (f^{r}) is the tangent cone to F at f^{r}. Further, for any vector z ∈ ℜ^{n}, z^{⊥} := { y ∈ ℜ^{n} | z^{T}y = 0 } is the orthogonal subspace associated with the vector z. The problem (6) amounts to solving an affine variational inequality defined such that we retain first-order optimality and feasibility in the original model. (In [QiM89, PaR01, Pat01] it is shown that these types of problems are special affine traffic equilibrium problems over variations of the original traffic network.) The first result states that the mapping S is strongly regular in the sense of Robinson [Rob80, Rob85], that is, single-valued and locally Lipschitz continuous, at (ρ^{r}, β^{r}), if, and only if, the solution δf to the sensitivity problem (6) is unique for each choice of perturbation. Moreover, when this condition is satisfied, this unique value is the directional derivative of the equilibrium link flow solution at (ρ^{r}, β^{r}) in the direction of (δρ, δβ), and the mapping S is B-differentiable (in the sense of [Rob85]), and, equivalently, semi-differentiable (in the sense of [RoW98]). This property is important, in that it is exactly what is needed to apply a Newton-type algorithm for the problem to minimize (ρ, β) ↦ φ(ρ, β, f(ρ, β)) over P ×ℜ^{|A|}, a subject which has yet not found application in the context of traffic management. (See further the references [PaQ93, Qi93, QiS93], for more information about Newton methods for semi-smooth functions.) It is also enough to be able to devise bundle subgradient algorithms for the problem; see the further research section and [Pat01] for further details on that subject.

A sufficient, but not necessary, condition for strong regularity is that the partial Jacobian ∇_{f}t(ρ^{r}, f^{r}) satisfies the condition that

s^{T}∇_{f}t(ρ^{r}, f^{r})s > 0,  s ∈ K − K,  (9)

that is, a positive definiteness condition on the critical subspace associated with the problem (5c) at (ρ^{r}, β^{r}, f^{r}). This type of condition has been utilized in [QiM89, Yen95, Out97].

The mapping S is moreover differentiable at (ρ^{r}, β^{r}) if, and only if, for every choice of perturbation vector (δρ, δβ), it holds that if a route r or a link for a specific commodity is such that its flow in every equilibrium solution is zero, then it remains zero in every solution to the sensitivity problem. This result in [Pat01] improves upon those previously stated in [ToF88, CSF00], which assume that there is a strictly complementary equilibium link flow. Not only is it shown in [Pat01] that the strict complementarity condition is stronger than necessary, but that the computational formula in [ToF88, CSF00] may fail to produce a gradient value even if one exists, and even provide a value when no gradient exists. Patriksson [Pat01] also supplies a calculus formula for a subgradient of S at (ρ^{r}, β^{r}) in the absence of a gradient; the problem solved to obtain a subgradient is similar to that of calculating a directional derivative in each coordinate direction, but it contains only equality constraints.

In all events, the technical conditions stated above amount to some form of positive definiteness of the Jacobian of the travel cost function, which is naturally implied by some strict (or, strong) monotonicity assumption with respect to t(ρ, ·) on F for every ρ ∈ P. The assumption that the equilibrium solution is unique (which it will boil down to of course) is, however, often too strong to be accepted easily. We mention two such cases. If we wish to consider the underlying traffic equilibrium model [VIP-H] in our development of traffic management instruments, we must note that the equilibrium solution h is likely to never be uniquely determined by (ρ, β) even if f is, since a link flow is not uniquely decomposable into route flows in general. (A counterexample is however the stochastic user equilibrium (SUE) model of Fisk [Fis80], in whose solution the route flows are unique; a necessary condition for this to hold is that the route costs are not additive. See [Dav94] for an application of the SUE model in bilevel network design, and [Pat01] for a characterization of the gradient of the equilibrium link flow as an asymptotic result of SUE sensitivity analysis.) Further, if we model cost interactions between links, particularly for links joining the same intersection, it has been demonstrated (e.g., [Hey83]) that the appropriate travel cost mapping t will not even be monotone, whence the equilibrium link flow solution determined by the Wardrop conditions will not necessarily be unique either. (The same is true for multiclass user traffic equilibrium models; see [ToW96].) In our continued development, we will presume that the cost mappings t and c are continuously differentiable on their respective domains F and H, but we make no assumption about their monotonicity.

The effect of a nonuniqueness in the lower-level problem is of course that the value of φ becomes unpredictable (and may also in some cases imply the nonexistence of optimal solutions to the bilevel problem altogether; see, e.g., [BaF82]). We therefore need a finer rule for choosing one element in the set of solutions, S(ρ, β), to the equilibrium system (5c). [In the literature of Stackelberg games, this set is known as the rational reaction (or, response) set.] There are several approaches to this problem (see, e.g., [LoM92, DeS96, LoM96, Dem00]). The two most common ones are usually referred to as the optimistic (or, strong or cooperative) approach and the pessimistic (or, weak or noncooperative) approach. The optimistic approach is to asssume that the followers (travellers) in the game establish (or, choose) one equilibrium which minimizes φ(ρ, β, ·) over the set S(ρ, β), thereby assuming a kind of cooperation on the part of the followers. The resulting objective value for [MPEC-F] then is

φ̂(ρ, β) := min_{f∈S(ρ,β)} φ(ρ, β, f),

whenever the minimum is attained. The pessimistic approach is precisely the opposite assumption, leading to a kind of worst-case optimal solution wherein the damage resulting from an unwelcome choice of the followers is minimized. A third alternative ([Dem97]) is to introduce a perturbation of the optimistic solution in order to better try to reflect the behaviour of the followers. Finally, a completely different way out ([DeS96, Dem00]) is to introduce a strictly or strongly monotone regularizing term in the lower-level cost mapping, making the lower-level solution uniquely determined, and whose associated positive scaling factor is forced to zero in order to approach the original equilibrium problem.

The Minty parameterization of the equilibrium system (5c) provided in the next section leads to a one-level optimization problem, which we will show is equivalent to [MPEC-F] (in the sense that they have the same set of locally optimal solutions), provided that we take the optimistic approach, but not necessarily otherwise. In that section, we will also complete the discussion on the possible nonuniqueness of lower-level solutions with some remarks on its consequences for decentralized traffic control through link tolls.

3.3 Instances

We next illustrate the scope of the Stackelberg model [MPEC-F]. (An overview of bilevel optimization models in the field of transportation is found in [Mig95].)

Example 1 (network design). A familiar form of the equilibrium network design problem ([LeA79, Mar86]) is an instance of [MPEC-F]. Let ρ_{a} denote an investment in network capacity on link a; the effect of an investment is that of a reduced travel time; its form is often taken to be t_{a}(ρ, f) := t̄_{a}(f_{a}/ρ_{a}). An investment ρ_{a} is associated with an investment cost, ψ_{a}(ρ_{a}). The goal is to minimize the total travel time, at a user equilibrium flow [that is, φ(ρ, f) := ∑_{a∈A} c_{a}(ρ, f)f_{a}], while satisfying budget constraints on the investments made, ρ ∈ P := { ρ ∈ ℜ_{+}^{|A|} | ℓ ≤ ρ ≤ u; ψ(ρ) ≤ b; ∑_{a∈A} ρ_{a} ≤ U }.

The parameters ρ_{a} may also be associated with the lowering of capacity of a link, such as when a lane is narrowed to allow for the construction of a bicycle lane. The lowering of capacity on certain links then acts as an influence on the travellers to choose other routes, other modes, etc. If the lower-level model (5c) is a multi-modal model which allows for the demand d to differentiate between different modes of transport, then [MPEC-F] may be used, for example, to model an influence on the travellers to utilize public transport or the bicycle alternative through inducing an additional delay for cars.

Example 2 (signal control). A problem of a form similar to the equilibrium network design problem is the signal setting problem. The solution of this problem aims at finding a set of signal control parameter values which, under user equilibrium conditions, optimizes some measure of the performance of the network, such as the total queueing delay, but without altering the traffic infrastructure. In this case, then, the variables ρ are the signal control parameters, for example the portion of green times allocated to the signal controls, and the parameterized travel cost mapping f ↦ t(ρ, f) measures the sum of travel times and delays at intersections. (See Cantarella and Sforza [CaS87], and Smith and Van Vuren [SmV93], and references therein for examples of traffic control policies and mathematical models.) In this case, the set P is the unit simplex.

We note that the generality of the model allows for the introduction of queueing delays for private vehicles only, in order to favour public transport.

Example 3 (toll optimization). The actions discussed in the above examples lead indirectly to an adjustment in the travellers’ cost perception, through the increase or decrease in queueing delays, for example. It is also possible to associate the parameters with monetary expenses (although properly measured in time equivalents), such as link or route tolls. In such cases, we could let t(β, f) := t̄(f) + β. Larsson and Patriksson [LaP98] discuss several alternative interpretations and uses of such a model, for example to induce mode changes through changes in ticket prices, and indirect derivations of β so as to satisfy some flow side constraints in equilibrium. As an example, let φ denote the total travel costs, and let the equilibrium problem be [VIP-F]. The well-known marginal cost pricing solution (e.g., Dafermos and Sparrow [DaS71]) is one optimal solution to this problem. (See further Larsson and Patriksson [LaP98] and Bergendorff et al. [BHR97], for discussions about alternative pricing solutions.) In the case where the underlying traffic model is an elastic demand model (cf. the model [EVIP-H_{d}] of Section 7.1), the optimal solution is however the zero flow. We then note that toll optimization under constraints can be modelled through the framework of this paper by letting t(ρ, f) := t̄(f) + ρ, and by adding penalties in order to avoid a nonzero β.

4 A reformulation based on a Minty parameterization

4.1 The Minty parameterization

We will consider a reformulation of the problem [MPEC-F] into an equivalent (one-level) optimization problem in the space (ρ, f). The conversion is based on the Minty [Min67] parameterization of the graph of the normal cone operator N_{F}.

That f solves (5c) is equivalent to the existence of a vector v ∈ N_{F} (f) such that v = −[t(ρ, f) + β]. Recall the definition of the graph of N_{F}:

graph N_{F} = { (v, f) | v ∈ N_{F} (f) }.

Since N_{F} is maximal monotone, it has a Minty parameterization, that is,

(v, f) ∈ graph N_{F} ⟺ ∃f̂ ∈ ℜ^{|A|} with f = Proj_{F} (f̂) and v = (I − Proj_{F})[f̂] = f̂− f,

where Proj_{F} is the Euclidean projection operator for the convex set F. (This identity is in fact a very simple form of the Minty parameterization which utilizes the relation v ∈ N_{F} (f) ⟺ Proj_{F} (f + v) = f.)

We will utilize the Minty parameterization as follows. The condition (5c) may be viewed as the existence of a vector f̂ ∈ ℜ^{|A|} such that −t(ρ, Proj_{F} (f̂)) − β = f̂− Proj_{F} (f̂), or, in other words,

β = Proj_{F} (f̂) − f̂− t(ρ, Proj_{F} (f̂)).  (10)

We define the mapping Ψ : ℜ^{p} × ℜ^{|A|} ↦ ℜ^{|A|} by

Ψ(ρ, f̂) = Proj_{F} (f̂) − f̂− t(ρ, Proj_{F} (f̂)).  (11)

(This is a mapping which induces Proj_{F} (f̂) to become a traffic equilibrium by adjusting the value of β.) Thus, we recast the problem [MPEC-F] as the problem to

[P-F]

minimize Φ(ρ, f̂) := φ(ρ, Ψ(ρ, f̂), Proj_{F} (f̂)),  (12a)
subject to ρ ∈ P,  (12b)
f̂ ∈ ℜ^{|A|}.  (12c)

The corresponding parameterization of the normal cone operator N_{H} leads to a problem, [P-H], based on the equilibrium system [VIP-H]. We remark that the vector f̂ does not correspond to a network flow in general, whereas its projection onto F, Proj_{F} (f̂), certainly does.

4.2 Properties of the equivalent problem

We next turn to look at the equivalence between the two problems [MPEC-F] and [P-F], and the basic properties of the latter.

First, consider any feasible triple (ρ̄, β̄, f̄) in [MPEC-F], that is, a triple which satisfies (5c), φ̂(ρ̄, β̄) = φ(ρ̄, β̄, f̄), and is such that ρ̄ ∈ P. Let f̂:= f̄− t(ρ̄, f̄) − β̄. From the Minty parameterization, it follows immediately that f̄ = Proj_{F} (f̂) holds, and so, from (11),

Φ(ρ̄, f̂) = φ(ρ̄, β̄, f̄) = φ̂(ρ̄, β̄).

We conclude that every feasible solution to [MPEC-F] corresponds to a feasible solution to [P-F] with the same objective function value.

Second, consider any feasible pair (ρ̄, f̂) in [P-F], that is, one with ρ̄ ∈ P, and let the pair (β̄, f̄) be given by β̄ := Ψ(ρ̄, f̂) and f̄:= Proj_{F} (f̂). Then, again from the Minty parameterization, the triple (ρ̄, β̄, f̄) satisfies (5c), and so

φ̂(ρ̄, β̄) ≤ φ(ρ̄, β̄, f̄) = Φ(ρ̄, f̂)

holds, where the inequality follows from the fact that the equilibrium flow f̄ is not determined through any optimization over the set S(ρ̄, β̄). [Equality holds however if S(ρ̄, β̄) is a singleton set.] Since, for some values of the parameters (ρ̄, β̄), the two models may have different objective values, the two models are not equivalent in that sense. The optimistic approach is inherent in the setup of the problem [P-F], so embracing this approach in [MPEC-F] becomes necessary in order to achieve an equivalence at locally optimal solutions. We establish below that local minimizers of Φ does constitute local minimizers for φ̂.

Proposition 4 (the locally optimal solutions to [MPEC-F] and [P-F] coincide). The sets of constrained locally optimal solutions to [MPEC-F] and [P-F] are the same.

Proof. We establish that locally optimal solutions (ρ^{∗}, f̂^{∗}) to the problem [P-F] translate to locally optimal solutions (ρ^{∗}, β^{∗}, f^{∗}) to [MPEC-F]. The converse follows immediately from the correspondence between feasible solutions of [MPEC-F] and [P-F] established above.

Consider a locally optimal solution (ρ^{∗}, f̂^{∗}) to the problem [P-F], and let the triple (ρ^{∗}, β^{∗}, f^{∗}) be given by β^{∗} := Ψ(ρ^{∗}, f̂^{∗}) and f^{∗} := Proj_{F} (f̂^{∗}). Arguing by contradiction, we assume that there exists a triple (ρ̃, β̃, f̃), arbitrarily close to (ρ^{∗}, β^{∗}, f^{∗}), and satisfying ρ̃ ∈ P, (5c) and φ(ρ̃, β̃, f̃) < φ(ρ^{∗}, β^{∗}, f^{∗}).

Let f̄ := f̃ − t(ρ̃, f̃) − β̃ (which likewise can be made arbitrarily close to f̂^{∗}). Through the Minty parameterization, we then obtain that

Φ(ρ̃, f̄) := φ(ρ̃, Ψ(ρ̃, f̄), Proj_{F} (f̄)) = φ(ρ̃, β̃, f̃) < φ(ρ^{∗}, β^{∗}, f^{∗}) = Φ(ρ^{∗}, f̂^{∗}).

We have therefore reached a contradiction to the local optimality of (ρ^{∗}, f̂^{∗}) in [P-F]. This completes the proof.

This result has the interesting consequence that when we have at hand a locally optimal solution, (ρ^{∗}, f̂^{∗}), to the problem [P-F], a vector (ρ^{∗}, β^{∗}, f^{∗}) which locally minimizes φ̂ is (rather immediately) available. A final note on the nonuniqueness issue in association with the optimistic approach is the following: if we do not work under the assumption of an optimistic condition, then the optimal value φ̂(ρ^{∗}, β^{∗}) may not be achieved when the control (ρ^{∗}, β^{∗}) is implemented, since the equilibrium solution f^{∗} actually reached by the travellers then may be such that φ(ρ^{∗}, β^{∗}, f^{∗}) > φ̂(ρ^{∗}, β^{∗}).

The existence of optimal solutions to [MPEC-F] (and, simultaneously, to [P-F]), follows from standard existence results for nonlinear programs. We first recall an abstract result; the corollary then translates it into our problem setting. The abstract (cooperative) MPEC problem is given as follows:

[MPEC]

minimize ω(x, y)  (13a)
subject to (x, y) ∈ Z,  (13b)
y ∈ S(x),  (13c)

where ω : ℜ^{n} × ℜ^{m} ↦ ℜ ∪ {∞}, Z ⊆ ℜ^{n} × ℜ^{m}, and S : ℜ^{n} ↦ 2^{ℜ^{m}}.

We recall that a function ω : ℜ^{p} ↦ ℜ ∪ {∞} is proper if ω(x) > −∞ for every x ∈ dom ω, and finite for at least one x. Let

lev_{α} ω := { x ∈ ℜ^{p} | ω(x) ≤ α }

denote the lower level set of ω for the level α. We then say that ω is weakly coercive (or, level-bounded) if lev_{α} ω is bounded for every α ∈ ℜ. (This property is equivalent to lim_{∥x∥→∞} ω(x) = ∞.) Next, let the function δ_{X} denote the indicator function for X ⊆ ℜ^{p}, that is, δ_{X}(x) equals zero if x ∈ X, and ∞ otherwise. We then say that the function ω is inf-compact relative to the set X if ω+δ_{X} is lsc, proper and weakly coercive. The below result extends the famous Weierstrass Theorem, and has been established, for example, in [Zha94, Proposition 2.3].

Proposition 5 (existence of optimal solutions to [MPEC]). Let

graph S := { (x, y) ∈ ℜ^{n} × ℜ^{m} | y ∈ S(x) }

denote the graph of the mapping S. Suppose that the objective function ω is inf-compact relative to the feasible set Z ∩ graph S. Then, there exist globally optimal solutions to the problem [MPEC].

Corollary 6 (existence of optimal solutions to [MPEC-F]). Let Z := P × ℜ^{|A|} × ℜ^{|A|} and

graph S := { (ρ, β, f) ∈ ℜ^{p} × ℜ^{|A|} × ℜ^{|A|} | −t(ρ, f) − β ∈ N_{F} (f) }.  (14)

Suppose that the function φ : P × ℜ^{|A|} × ℜ^{|A|} is weakly coercive relative to the feasible set Z ∩ graph S. Then, there exist globally optimal solutions to the problem [MPEC-F].

Proof. Since F is polyhedral and t is continuous on ℜ^{p} × ℜ_{+}^{|A|}, graph S is closed. Further, since N_{F} (f) is nonempty for every f ∈ F, it is clear that for every pair (ρ, f) ∈ P × F, we can choose a vector β such that (ρ, β, f) ∈ graph S. Since P was assumed to be polyhedral, we may conclude that the feasible set Z ∩ graph S is closed as well as nonempty.

The function φ is in C^{1} on Z, and is hence both lsc and proper on the set Z ∩ graph S. The property which remains to be ascertained in order to be able to invoke Proposition 5 is the weak coercivity of φ on Z ∩ graph S, but this follows by the assumption. This completes the proof.

The weak coercivity assumption is rather natural. First, it is natural to assume that the controls ρ are confined to a bounded set P. (It is in particular true for Examples 1 and 2 in Section 3.3.) Second, it is also reasonable that the function φ is such that infinitely large (positive or negative) tolls β, or flows in infinite cycles, are discouraged in the minimization (as discussed in Example 3 in the same section). We remark that in the case of the problem [MPEC-H], the boundedness of H implies that φ always is weakly coercive in the flow space.

The problem [P-F] is obviously both nonsmooth and nonconvex. Since φ and t are smooth and the mapping Proj_{F} is piecewise affine (e.g., [RoW98, Proposition 12.30]), [P-F] however is a problem of minimizing the piecewise smooth and, in particular, locally Lipschitz continuous and subdifferentially regular [RoW98, Definition 7.25], hence semidifferentiable (or, B-differentiable) function Ψ over the polyhedral set Z, for which descent methods can be devised. We shall study such a method in the next section.

5 A descent algorithm for the traffic management model

5.1 Introduction

The algorithm to be developed starting in this section produces a stationary point for the problem [P-F], which in this context is a feasible point (ρ^{∗}, f̂^{∗}) such that

Φ′(ρ^{∗}, f̂^{∗}; δρ, δf̂) ≥ 0, δρ ∈ T_{P} (ρ^{∗}), δf̂ ∈ ℜ^{|A|},

where T_{P} denotes the tangent cone mapping for the set P.

Previous solution methods for traffic management models have mostly been heuristic (see, e.g., [Mig95, Fer97, LaP98]). In some cases (e.g., [Fri+90, YaL96]), a heuristic type of sensitivity analysis is applied to the solution f(ρ, β) to (5c), in order to find profitable search directions for the implicit objective function (ρ, β) ↦ φ(ρ, β, f(ρ, β)). Such a strategy—known as the implicit approach—as well as most of the other heuristics that have been proposed in the literature, forces one to solve for an equilibrium in each iteration, which is numerically challenging. It further presumes that the equilibrium link flow solution is uniquely determined, that is, that the link cost function t(ρ, ·) is (at least) strictly monotone.

Other complications which may arise, and which in some cases have been ignored in the construction of descent algorithms based on the calculation of “gradients,” stem from the fact that the equilibrium commodity flow (that is, commodity link flow or route flow) is however not unique (cf. the discussion in Section 3.2), but, more importantly, does not necessarily satisfy the conditions for differentiability, especially not those based on satisfying the Wardrop conditions (1) with strict complementarity [that is, with “>” in (1b)]; the calculus rules for the “directional derivatives” or “gradients” most often used include a procedure for the selection of a proper representative commodity flow in trying to achieve this. See [ToF88, QiM89, Out97, CSF00] for some such attempts, all of which require a positive definiteness property of the Jacobian of t(ρ, ·) at the equilibrium.

In contrast, our scheme for calculating descent directions for Φ relies not on the solution of traffic equilibrium problems but rather on the (simpler) solution of strictly convex quadratic network flow problems (in fact, projections onto either flow polyhedra or subsets of their circulation flow subspaces), and no monotonicity requirements are made on the travel cost function.

We note that the reformulation of a variational inequality problem into a system of nonsmooth equations through the application of the projection operation has been utilized in sensitivity analyses of parametric nonlinear programs and variational inequality problems (see, e.g., [Rob92, LPR96, PaR96] and references therein), and in algorithms for the solution of variational inequality problems (e.g., [FeR95]), but as far as we are aware the Minty parameterization has not previously been used directly to devise an algorithm for an MPEC problem.

In the next subsection, we investigate how to compute the directional derivative of Φ for the case where the underlying equilibrium problem is [VIP-F] or [VIP-H]. The main effort is to solve a strictly convex quadratic flow circulation problem over a subnetwork. Then, we consider the generation of a descent direction for Φ based, essentially, in the minimization of a quadratic regularization of this derivative over all feasible directions, and discuss how its computation can be performed. The main complication here is that the directional derivative is only piecewise linear as a function of the search direction, and the search direction problem is in fact a linear complementarity (LCP) constrained strictly convex quadratic optimization problem. (In the case that an iteration point is differentiable, however, it reduces to a system of equations.) In the following section, we then formalize the algorithm, and establish its convergence to a stationary point of [P-F] and [P-H] under some additional, technical assumptions. The algorithm and its convergence conditions are adapted from Pang et al. [PHR91] (see also [LPR96, Sections 4.2 and 6.3]). (Of course, also other approaches are possible to apply; we refer to the MPEC text books [LPR96, Bar98, OKZ98] for examples and references to other algorithms, and to the last section for a brief discussion on one such example.) All along, we discuss simultaneously how to perform computations and how to meet the technical conditions in practice, thus leading to a realization of the algorithm.

5.2 Computation of directional derivatives

5.2.1 The case of [P-F]

In order to compute the directional derivative of Φ at (ρ, f̂) in the direction of (δρ, δf̂), we need to analyze the derivative of the projection operator Proj_{F}. In terms of f := Proj_{F} (f̂), define the set

δF := { δf ∈ T_{F} (f) | δf ⊥ (f − f̂) }.

This set is a subset of the flow circulation subspace for the multi-commodity network, wherein some arcs are restricted in sign or direction for certain commodities. (Formulas for computing the cones T_{F} (f) and N_{F} (f) are discussed in detail in [PaR01, Pat01], and will be used henceforth.)

According to [RoW98, Corollary 13.43], we have that

Proj′_{F} (f̂; δf̂) = Proj_{δF} (δf̂).  (15)

The directional derivative of Φ at (ρ, f̂) in the direction of (δρ, δf̂) then is

Φ′(ρ, f̂; δρ, δf̂) = lim_{t↓0} \frac{1}{t}[Φ(ρ + tδρ, f̂+ tδf̂) − Φ(ρ, f̂)]  (16a)
= ∇_{ρ}φ(ρ, β, f)^{T}δρ + ∇_{β}φ(ρ, β, f)^{T}δβ + ∇_{f}φ(ρ, β, f)^{T}Proj_{δF} (δf̂),  (16b)

where β is given by the formula (10), and where

δβ = ∇_{ρ}Ψ(ρ, f̂)δρ + ∇f̂Ψ(ρ, f̂)δf̂  (16c)
= −∇_{ρ}t(ρ, f)δρ + Proj_{δF} (δf̂) − δf̂− ∇_{f}t(ρ, f)Proj_{δF} (δf̂).  (16d)

We note that the calculation of Φ′(ρ, f̂; δρ, δf̂) separates into simple calculations for each component of δρ, and that it is linear in this vector. The calculation of Proj_{δF} (δf̂) is analyzed next.

Clearly, Proj_{δF} (δf̂) constitutes a strictly convex quadratic programming problem over a subset of the circulation subspace of the flow polytope. In detail, then, the following problem provides Proj_{δF} (δf̂):

minimize_{z∈ℜ^{|A|}} \frac{1}{2}∥z − δf̂∥^{2},  (17a)
subject to  Az_{pq} = 0,  (p, q) ∈ C,  (17b)
∑_{(p,q)∈C} z_{pq} − z = 0,  (17c)
z_{apq} ≥ 0,  a ∈ A_{pq}^{0}, (p, q) ∈ C,  (17d)
z_{apq} = 0,  a ∈ A_{pq}^{>}, (p, q) ∈ C, with f_{a} ≠ f̂_{a},  (17e)

where, for each (p, q) ∈ C, π_{pq}^{p} is the vector of multipliers for the constraints Af_{pq} = d_{pq} in the definition of Proj_{F} (f̂), and A_{pq}^{0} := { a = (i, j) ∈ A | f_{apq} = 0 and f_{a} − f̂_{a} = π_{pqj}^{p} − π_{pqi}^{p} }, and A_{pq}^{>} := { a = (i, j) ∈ A | f_{apq} = 0 and f_{a} − f̂_{a} > π_{pqj}^{p} − π_{pqi}^{p} } denote the set of links where the commodity flow is zero while, respectively, it lies on a shortest route, and it does not. (Note that f̂, f, f_{pq}, (p, q) ∈ C, and δf̂ all are given |A|-vectors, and that the choice of disaggregate flow solution (f_{pq})_{(p,q)∈C} is immaterial to the definition of the feasible set of the problem (17) in terms of z, as established in [PaR01, Pat01].)

5.2.2 The case of [P-H]

In the case where [VIP-H] is the underlying traffic equilibrium model, we are instead interested in the calculation of Proj_{δH}(δĥ), where δH := { δh ∈ T_{H}(h) | δh ⊥ (h − ĥ) }. This projection separates over the different commodities (p, q) ∈ C to projection problems of the form Proj_{δH_{pq}}(δĥ_{pq}) for the respective commodity flow polyhedron H_{pq}. To be precise, Proj_{δH_{pq}}(δĥ_{pq}) is the unique solution to the problem to

minimize_{z_{pq}∈ℜ^{|Rpq |}}  \frac{1}{2}∥z_{pq} − δĥ_{pq}∥^{2},  (18a)
subject to ∑_{r∈R_{pq}} z_{pqr} = 0,  (18b)
z_{pqr} ≥ 0,  r ∈ R_{pq}^{0},  (18c)
z_{pqr} = 0,  r ∈ R_{pq}^{>} with h_{pqr} ≠ ĥ_{pqr},  (18d)

where π_{pq}^{p} is the Lagrange multiplier for the constraint ∑_{r∈R_{pq}} h_{pqr} = d_{pq} in the definition of Proj_{H_{pq}}(ĥ_{pq}), and R_{pq}^{0} := { r ∈ R_{pq} | h_{pqr} = 0 and h_{pqr}−ĥ_{pqr} = π_{pq}^{p} } and R_{pq}^{>} := { r ∈ R_{pq} | h_{pqr} = 0 and h_{pqr}−ĥ_{pqr} > π_{pq}^{p} } denote the set of routes where the flow is zero while, respectively, it is a shortest route, and it is not. (Note that ĥ_{pq}, h_{pq} and δĥ_{pq} all are given |R_{pq}|-vectors.)

As we are not really focusing on merely calculating Proj_{δF} (δf̂) [or, Proj_{δH}(δĥ)] for one fixed value of δf̂ (or, δĥ), we will not discuss their numerical computation by network optimization techniques, but refer to [QiM89, PaR01, Pat01] for numerical examples of related sensitivity problems.

We finally remark that Proj_{δF} (Proj_{δH}) is piecewise linear in δf̂ (δĥ) (see also [RoW98, Proposition 12.30]).

5.3 Computation of descent directions

5.3.1 The case of [P-F]

In order to construct descent directions for Φ, we consider applying the techniques of Pang et al. [PHR91] for the constrained minimization of locally Lipschitz continuous functions. In our notation, given an iteration point (ρ^{τ} , f̂^{τ}), the search direction is found by solving the problem to

minimize Φ′(ρ^{τ} , f̂^{τ}; δρ, δf̂) + (δρ, δf̂)^{T}B^{τ} (δρ, δf̂),  (19a)
subject to ρ^{τ} + δρ ∈ P,  (19b)
δf̂ ∈ ℜ^{|A|},  (19c)

where B^{τ} is a symmetric and positive definite matrix in ℜ^{(p+|A|)×(p+|A|)}. [Here, (19b) could be replaced with δρ ∈ T_{P} (ρ^{τ}).] As we shall see, the problem (19) can be interpreted as an LCP constrained quadratic optimization problem corresponding to the minimization of a quadratically regularized linear approximation of the original problem [P-F].

As has already been established, the computation of Φ′(ρ, f̂; δρ, δf̂) separates into independent problems for δρ and δf̂, and is furthermore linear and piecewise linear, respectively, in the respective arguments. From the standpoint of computational efficiency, this suggests choosing the matrix B^{τ} such that it is block-diagonal. On the other hand, the quality of the search direction suggests choosing the matrix so that a quasi-Newton type method is produced, which would require it to contain second-order information about the function φ about the point (ρ^{τ} , f̂^{τ}). Until this conflict has been resolved by performing numerical tests, we henceforth assume that B^{τ} is block-diagonal, as discussed above. The problem (19) then separates into one problem for δρ which is strictly convex, quadratic and linearly constrained, and whose solution is straightforward in comparison with that of the part in δf̂, and shall not be discussed further. The other separate problem is of the form

minimize_{δf̂} (α^{1,τ})^{T}Proj_{δF} (δf̂) + (α^{2,τ})^{T}δf̂+ δf̂^{T}Bτ ; f̂δf̂,  (20)

where α^{i,τ} are constant vectors in ℜ^{|A|}, i = 1, 2.

The difficulty of the problem (20) originates from the complementarity conditions arising from the inequalities (17d) which enter into the calculation of Proj_{δF} (δf̂). In order to analyze this problem further, we study the characterization of the projection in (17), that is, the system

Az_{pq} = 0,  (p, q) ∈ C,  (21a)
∑_{(p,q)∈C} z_{pq} − z = 0,  (21b)
z_{apq} − δf̂_{apq} + (A^{T}π_{pq})_{a} + v_{a} = 0,  a ∈ A, (p, q) ∈ C, with f_{apq} > 0,  (21c)
0 ≤ (z_{apq} − δf̂_{apq} + (A^{T}π_{pq})_{a} + v_{a}) ⊥ z_{apq} ≥ 0,  a ∈ A_{pq}^{0}, (p, q) ∈ C,  (21d)
z_{a} = 0,  a ∈ A_{pq}^{>}, (p, q) ∈ C, with f_{a} ≠ f̂_{a}, (21e)

where π_{pq} and v are the Lagrange multipliers for the constraints (17b) and (17c), respectively.

Replacing the vector Proj_{δF} (δf̂) with the (unique) vector z which solves this system, we obtain from (20) the LCP constrained quadratic program to

minimize_{z,δf̂} (α^{1,τ})^{T}z + (α^{2,τ})^{T}δf̂+ δf̂^{T}Bτ ; f̂δf̂,  (22a)
subject to (21),  (22b)
∑_{a∈A} δf̂_{pq} − δf̂ = 0.  (22c)

5.3.2 The case of [P-H]

One main difference between the computations of descent directions for the two problems [P-F] and [P-H], is that in the latter the computations can be made to separate into computations for each commodity, by choosing the matrix B^{τ} to have a corresponding further block-diagonal structure with respect to C. If this choice has been made, then the problem in δĥ separates into |C| problems of the form

minimize_{δĥ_{pq}} (α_{pq}^{1,τ})^{T}Proj_{δH_{pq}}(δĥ_{pq}) + (α_{pq}^{2,τ})^{T}δĥ_{pq} + δĥ_{pq}^{T}B_{pq}^{τ}δĥ_{pq},  (23)

where α_{pq}^{i,τ} are constant vectors in ℜ^{|R_{pq}|}, i = 1, 2. In order to analyze this problem further, we develop the optimality conditions for the projection problem (18). The projection operation is characterized by a vector z_{pq} satisfying the conditions

∑_{r∈R_{pq}} z_{pqr} = 0,  (24a)
z_{pqr} − δĥ_{pqr} + λ_{pq} = 0,  r ∈ R_{pq} with h_{pqr}^{τ} > 0,  (24b)
0 ≤ z_{pqr} − δĥ_{pqr} + λ_{pq} ⊥ z_{pqr} ≥ 0,  r ∈ R_{pq}^{0},  (24c)
z_{pqr} = 0,  r ∈ R_{pq}^{>} with h_{pqr}^{τ} ≠ ĥ_{pqr}^{τ},  (24d)

where λ_{pq} denotes the Lagrange multiplier for (18b). Replacing the vector Proj_{δH_{pq}}(δĥ_{pq}) with the (unique) vector z_{pq} which solves this system, we obtain from (23) the LCP constrained quadratic program to

minimize_{z_{pq},δĥ_{pq}} (α_{pq}^{1,τ})^{T}z_{pq} + (α_{pq}^{2,τ})^{T}δĥ_{pq} + δĥ_{pq}^{T}B_{pq}^{τ}δĥ_{pq},  (25a)
subject to (24).  (25b)

As (22), this is a nonconvex problem, but it is still possible to solve it efficiently given the realization of the algorithm. The reason why this problem is difficult lies in the presence of the complementarity constraints (24c). The number of such constraints is equal to the number of routes in the OD pair (p, q) for which the flow in h_{pq}^{τ} is degenerate, that is, belong to the set R_{pq}^{0}. (This also tells us that when the projected flow is differentiable, that is, when the variables associated with the set R_{pq}^{0} essentially can be removed, then the descent direction is found through the solution of a system of nonlinear equations. The same is the case with the sets A_{pq}^{0} for the problem [P-F].) First, we note that in the course of the algorithm, not all the routes in R_{pq} will be known. We will be using a technique which has proved to be successful when solving traffic equilibrium problems (see, e.g., [LaP92, Pat94]), wherein profitable routes in R_{pq} (that is, those for which h_{pqr}^{∗} > 0 can be expected to hold) are generated algorithmically, through the solution of shortest route problems given temporarily fixed link costs. By also occasionally dropping previously generated routes that have received a zero flow during several consecutive iterations, the number of known routes which will give rise to the complementarity conditions (24c) will therefore be expected to be very low. Nevertheless, when such routes are present, we propose to deal with the situation when solving the problem (25) through a complete enumeration of the cases where the values of the corresponding variables z_{pqr} are zero or not. (The approach of enumerating the complementarity conditions in the LCP system was proposed in [PHR91].) Each of these restrictions of the problem (25) is a strictly convex, linearly constrained quadratic program.

In the event that B^{τ} does not separate over commodities, the corresponding problem in z will be stated over the entire set of known routes and over all the restrictions (24), but will still be a quite manageable problem to solve, since the constraints are separable over the commodities.

We note, finally, that numerical tolerances may need to be introduced in the systems (21) and (24) to determine when a route is considered to be used [(24b)] and when two scalars are considered to be equal [(21e) and (24b)–(24d)].

6 The algorithm and its convergence

6.1 Descent properties

Before stating the algorithm, we establish a technical lemma which motivates the use of the search direction finding problem (19), as well as the step length rule proposed. We state it, as well as the complete algorithm, for the case of the equilibrium problem being [VIP-F], but remark that the derivation for the case of [VIP-H] is analogous.

Lemma 7 (descent property). Let (ρ, f̂) be feasible in [P-F]. Let the matrix B be symmetric and positive definite. Then, the problem (19) has a globally optimal solution with a nonpositive optimal value. This value is moreover zero if and only if (δρ, δf̂) = (0, 0) is the only global solution, which in turn is true if and only if (ρ, f̂) is stationary in [P-F].

If (δρ, δf̂) is nonzero, then for any σ ∈ (0, 1) there exists a scalar ℓ̄> 0 such that for every ℓ ∈ [0, ℓ̄],

Φ(ρ + ℓδρ, f̂+ ℓδf̂) − Φ(ρ, f̂) ≤ −\frac{σ}{2} ℓ(δρ, δf̂)^{T}B(δρ, δf̂)  (26)

holds.

Proof. As has been established previously, the function Φ is locally Lipschitz continuous on P × ℜ^{|A|}. So, for all (δρ, δf̂) with ρ + δρ ∈ P,

|Φ′(ρ, f̂; δρ, δf̂)| ≤ M_{Φ}∥(δρ, δf̂)∥  (27)

holds (cf. [LPR96, Proposition 4.2.2.b]), where M_{Φ} > 0 is the modulus of Lipschitz continuity at (ρ, f̂). Further, since B is positive definite, there exists an m > 0 such that

Φ′(ρ, f̂; δρ, δf̂) + \frac{1}{2}(δρ, δf̂)^{T}B(δρ, δf̂) ≥ −M_{Φ}∥(δρ, δf̂)∥ + \frac{m}{2}∥(δρ, δf̂)∥^{2}.

Hence, if ∥(δρ, δf̂)∥ tends to infinity, then so does the objective of (19), which thus is weakly coercive. The feasible set of (19) being closed as well as nonempty, the problem therefore has a globally optimal solution. Since the objective value is zero at zero, it must further have a nonpositive optimal value.

Assume next that (δρ, δf̂) is nonzero. Then,

Φ′(ρ, f̂; δρ, δf̂) < −\frac{1}{2}(δρ, δf̂)^{T}B(δρ, δf̂).  (28)

Suppose that a positive ℓ̄ such that (26) is satisfied does not exist. Then there must be a sequence ℜ_{++} ⊃ {ℓ_{s}} → 0 such that for each s,

Φ(ρ + ℓ_{s}δρ, f̂+ ℓ_{s}δf̂) − Φ(ρ, f̂) > −\frac{σ}{2} ℓ_{s}(δρ, δf̂)^{T}B(δρ, δf̂).

Dividing the inequality by ℓ_{s} and letting s → ∞ then yields that

Φ′(ρ, f̂; δρ, δf̂) ≥ −\frac{σ}{2} (δρ, δf̂)^{T}B(δρ, δf̂).

But this contradicts (28), as σ < 1.

It remains to establish that (δρ, δf̂) = (0, 0) is equivalent to (ρ, f̂) being stationary. Assume first that (δρ, δf̂) = (0, 0). Then, for all (δρ̄, δf̄) and λ > 0 with ρ + λδρ̄ ∈ P,

0 ≤ Φ′(ρ, f̂; λδρ̄, λδf̄) + λ^{2}(δρ̄, δf̄)^{T}B(δρ̄, δf̄).

Dividing the inequality by λ and letting it tend to zero then establishes that (ρ, f̂) indeed is stationary. Conversely, if (ρ, f̂) ≠ (0, 0), then the inequality (28) shows that Φ′(ρ, f̂; δρ, δf̂) < 0, which contradicts stationarity.

6.2 The algorithm

We are now ready to state the algorithm; it is given in Table 1.

We remark that the Armijo line search is only one among a large variety of step length rules that may be employed in the scheme of Table 1. For example, the algorithm of [PHR91] employs a nonmonotone line search, first analyzed in [GLL91], whose mechanism allows for unit steps to often be taken, in order to speed up convergence.

Table 1: A descent algorithm

0. (Initialization): Choose an initial point (ρ^{0}, f̂^{0}) ∈ P ×ℜ^{|A|}, let γ, σ ∈ (0, 1) be given, and let τ := 0.

1. (Search direction generation): Let B^{τ} be a positive definite, symmetric matrix. Let (δρ^{τ} , δf̂^{τ}) be a solution to (19). If the optimal value of (19) is zero, then terminate with (ρ^{τ} , f̂^{τ}) being a stationary point in [P-F]. Otherwise, continue.

2. (Armijo line search): Let i_{τ} be the smallest nonnegative integer i such that

Φ(ρ^{τ} + γ^{i}δρ^{τ} , f̂^{τ} + γ^{i}δf̂^{τ}) − Φ(ρ^{τ} , f̂^{τ}) ≤ −\frac{σ}{2} γ^{i}(δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ}).  (29)

The step length is ℓ_{τ} = γ^{i_{τ}}. Let (ρ^{τ+1}, f̂^{τ+1}) := (ρ^{τ} , f̂^{τ}) + ℓ_{τ} (δρ^{τ} , δf̂^{τ}).

3. (Termination criterion and iteration): If (ρ^{τ} , f̂^{τ}) is acceptable → Stop. Otherwise, go to Step 1 with τ := τ + 1.

6.3 Convergence conditions

When establishing the convergence of the algorithm, we must introduce first of all an assumption on the choice of the matrices B^{τ} such that they are bounded and uniformly positive definite:

∃m, M > 0 : m∥d∥^{2} ≤ d^{T}B^{τ} d ≤ M∥d∥^{2},  d ∈ ℜ^{p+|A|}.  (30)

The property of weak coercivity of φ which was introduced in Corollary 6 ensures that the sequence {(ρ^{τ} , f̂^{τ})} is bounded. We note however that the often used condition that for (ρ^{0}, f̂^{0}) ∈ P × ℜ^{|A|},

the set { (ρ, f̂) ∈ P × ℜ^{|A|} | Φ(ρ, f̂) ≤ Φ(ρ^{0}, f̂^{0}) } is bounded,  (31)

is implied by weak coercivity, and is enough to guarantee both the existence of a globally optimal solution to the problem [P-F] and the boundedness of the sequence {(ρ^{τ} , f̂^{τ})}.

Finally, when using the analysis of Pang et al. [PHR91], we need to assume that the function Φ is differentiable at the limit point. This is a restrictive assumption in general, and we will now explain how we will try to enforce it through our realization of the algorithm.

6.3.1 The case of [P-F]

We first observe that a nondifferentiability of Φ at a limit point (ρ^{∞}, f̂^{∞}) would be caused by a nondifferentiability of the projection operation Proj_{F} at f̂^{∞}. Although Proj_{F} is, as remarked before, piecewise linear, it may have kinks where the active constraints change. The condition that Φ is differentiable at (ρ^{∞}, f̂^{∞}) is equivalent to the condition that the variables δf_{apq} associated with the set A^{0} would be zero in the characterization (21) for any choice of perturbations in (ρ, β), and therefore also zero in the solution to the direction-finding problem (22). This condition is satisfied in particular if

f^{∞} is strictly complementary with respect to the cost f^{∞} − f̂^{∞}.  (32)

Although it is a restrictive assumption, given f^{∞}, the condition (32) can be checked, by solving an entropy maximization problem over the vectors f_{pq}; cf. [Aka97, Pat01].

6.3.2 The case of [P-H]

In the case of the problem [P-H], differentiability of Φ at a limit point (ρ^{∞}, ĥ^{∞}) is equivalent to the condition that the variables associated with the set R_{pq}^{0} essentially can be removed, as the corresponding values δh_{pqr} in the sensitivity problem (24) would be zero for any choice of (δρ, δβ), and therefore also in the optimal solution to (25). This condition is satisfied in particular if

h^{∞} is strictly complementary with respect to the cost h^{∞} − ĥ^{∞}.  (33)

In this case, then, the concern thus is which routes r in the sets R_{pq}, (p, q) ∈ C, will have a positive flow at h^{∞} := Proj_{H}(ĥ^{∞}), and whether we will be able to identify them finitely. We propose to deal with the situation as follows. As remarked before, not all routes will ever be known. Instead, we will solve shortest route problems at regular intervals with link costs based on the current variable values, and include the shortest routes in the set of variables. This way, only subsets R̂_{pq}^{τ} ⊂ R_{pq} of the routes will be known at any given iteration τ. In the course of the algorithm, some of these routes will also receive a zero flow. Such routes will be identified and removed from the corresponding sets R̂_{pq}^{τ}. (There is neither a guarantee that a generated route will always retain a positive flow, nor is it guaranteed that a discarded route will not be re-generated.) If we keep only routes in the subsets R̂_{pq}^{τ} having positive flow, then we will actually be visiting differentiable points of the corresponding restrictions of the problem [P-F] to the subsets R̂_{pq}^{τ}. For these restrictions, our algorithm will act as a scaled gradient projection algorithm. Interestingly, it is known that the active constraints at the limit point of a projection algorithm used to minimize a differentiable function over a polyhedral set will be identified after a finite number of iterations (e.g., the surveys in [Pat98, Ber99]). The following assumption that we make is therefore not so far-fetched: we assume that the route generation and deletion process is such that after a finite number of iterations, the subsets R̂_{pq}^{τ} stay constant and no route in these subsets has a zero flow at h^{∞}. (This way, we guarantee to obtain a stationary point to the restriction of the original problem [P-H] to the sets of routes that are retained in the limit.) In other words,

∃τ̄ : R̂_{pq}^{τ} = R̂_{pq} ⊂ R_{pq}, τ ≥ τ̄, and h_{pqr}^{∞} > 0,  r ∈ R̂_{pq},  (p, q) ∈ C.  (34)

6.4 Convergence theorem

We now state and prove the main result of this paper.

Theorem 8 (convergence of the algorithm). Consider the problem [P-F]. Suppose that the assumptions (30) and (31) hold. Let {(ρ^{τ} , f̂^{τ})} be the sequence of iterates produced by the algorithm of Table 1. Then, the sequence {(ρ^{τ} , f̂^{τ})} is bounded. Let (ρ^{∞}, f̂^{∞}) denote any of its accumulation points. If f̂^{∞} satisfies (32), then (ρ^{∞}, f̂^{∞}) is a stationary point for the problem [P-F]. Further, if the sequence {ℓ_{τ} } of step lengths is bounded away from zero, then each limit point of the sequence {(ρ^{τ} , f̂^{τ})} is stationary in [P-F] even without the assumption (32).

Proof. The sequence {(ρ^{τ} , f̂^{τ})} satisfies

Φ(ρ^{τ+1}, f̂^{τ+1}) ≤ Φ(ρ^{τ} , f̂^{τ}) − \frac{σ}{2} ℓ_{τ} (δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ}) < Φ(ρ^{τ} , f̂^{τ}),

so the sequence {Φ(ρ^{τ} , f̂^{τ})} is strictly decreasing. By the assumption (31), Φ is lower bounded on P ×ℜ^{|A|}, whence {Φ(ρ^{τ} , f̂^{τ})} converges. Then, by the above inequality, also {ℓ_{τ} (δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ})} → 0 holds. That the sequence {(ρ^{τ} , f̂^{τ})} is bounded also follows from the assumption (31).

Let {(δρ^{τ} , δf̂^{τ})} be the sequence of solutions to (19) generated by the algorithm. We next establish that this sequence is bounded. By the assumption (30), for each τ we have that

|Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ})| ≥ \frac{1}{2}(δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ}) ≥ \frac{m}{2}∥(δρ^{τ} , δf̂^{τ})∥^{2}.

Moreover, |Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ})| ≤ M_{Φ}∥(δρ^{τ} , δf̂^{τ})∥ holds by (27), so ∥(δρ^{τ} , δf̂^{τ})∥ ≤ \frac{2M_{Φ}}{m}. This implies that both the sequences {(δρ^{τ} , δf̂^{τ})} and {Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ})} are bounded.

We next turn to a subsequence T for which we assume that {ρ^{τ} , f̂^{τ} }_{τ∈T} → (ρ^{∞}, f̂^{∞}), {δρ^{τ} , δf̂^{τ} }_{τ∈T} → (δρ^{∞}, δf̂^{∞}), and {B^{τ} }_{τ∈T} → B^{∞}. By the assumption (30), B^{∞} is symmetric and positive definite. We may further assume that {Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ})}_{τ∈T} has a limit.

Suppose now that the sequence {ℓ_{τ} } of step lengths does not tend to zero, that is, lim inf_{τ→∞} ℓ_{τ} > 0. It then immediately follows that {(δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ})} → 0, whence (δρ^{∞}, δf̂^{∞}) = (0, 0) must hold by the positive definiteness of B^{∞}. Now, since (δρ^{τ} , δf̂^{τ}) is optimal in (19),

Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ}) + \frac{1}{2}(δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ}) ≤ Φ′(ρ^{τ} , f̂^{τ}; δρ, δf̂) + \frac{1}{2}(δρ, δf̂)^{T}B^{τ} (δρ, δf̂)

holds for all (δρ, δf̂) for which ρ^{τ} + δρ ∈ P. Taking limits on both sides of the inequality, we first note that {(δρ^{τ} , δf̂^{τ})}_{τ∈T} → (0, 0), so the left-hand side tends to zero. Further,

lim sup_{τ∈T} Φ′(ρ^{τ} , f̂^{τ}; δρ, δf̂) ≤ Φ′(ρ^{∞}, f̂^{∞}; δρ, δf̂),

so we find that

0 ≤ Φ′(ρ^{∞}, f̂^{∞}; δρ, δf̂) + \frac{1}{2}(δρ, δf̂)^{T}B^{∞}(δρ, δf̂)

holds for all (δρ, δf̂) for which ρ^{τ} + δρ ∈ P. As in the proof of Lemma 7, we may conclude that (ρ^{∞}, f̂^{∞}) is stationary.

Assume now instead that lim inf_{τ→∞} ℓ_{τ} = 0. Then it must be that

Φ(ρ^{τ} + (ℓ_{τ} /γ)δρ^{τ} , f̂^{τ} + (ℓ_{τ} /γ)δf̂^{τ}) − Φ(ρ^{τ} , f̂^{τ}) > −\frac{σ}{2} (ℓ_{τ} /γ)(δρ^{τ} , δf̂^{τ})^{T}B^{τ} (δρ^{τ} , δf̂^{τ})

holds for all sufficiently large τ. Dividing the inequality by ℓ_{τ} /γ and taking the limit on both sides in T yields

Φ′(ρ^{∞}, f̂^{∞}; δρ^{∞}, δf̂^{∞}) ≥ −\frac{σ}{2} (δρ^{∞}, δf̂^{∞})^{T}B^{∞}(δρ^{∞}, δf̂^{∞}).  (35)

On the other hand, from (28) follows that

lim_{τ∈T} Φ′(ρ^{τ} , f̂^{τ}; δρ^{τ} , δf̂^{τ}) ≤ −\frac{1}{2}(δρ^{∞}, δf̂^{∞})^{T}B^{∞}(δρ^{∞}, δf̂^{∞}).  (36)

By the assumption (32), Φ is differentiable at (ρ^{∞}, f̂^{∞}). Together with the fact that σ < 1 holds, the combination of the inequalities (35) and (36) implies that (δρ^{∞}, δf̂^{∞}) = (0, 0) must hold. We conclude that also under this circumstance, (ρ^{∞}, f̂^{∞}) is stationary in [P-F].

For the case of the problem [P-H], the only difference in the analysis is that the two assumptions (30) and (31) need to be translated into route flow space, and (32) need to be replaced by (33). Further, if we replace the assumption (33) with (34), then ĥ^{∞} will be of a dimension corresponding to the number of routes kept after iteration τ̄, and it will then be stationary for the restriction of the problem [P-H] to that corresponding subset of routes.

6.5 Comparison with previous work

Some comments on the convergence result are in order. Most sensitivity based heuristics for solving bilevel optimization problems in transportation planning (e.g., [Fri+90]) assume that the implicit function [in our case, (ρ, β) ↦ φ(ρ, β, f(ρ, β))] is differentiable everywhere. In contrast, the method of Pang et al.

[PHR91] applied to the minimization of this function assumes its differentiability only at the limit point. The assumptions that we make in our convergence result (a strictly complementary limit point) is slightly stronger than necessary, but checking for differentiability is not trivial. (Further characterizations that may be computationally viable to check are given in [Pat01].) Note also that our objective function is Φ, which does not involve the lower-level equilibrium problem, and ultimately does not require, in contrast to the other developments mentioned above, that the travel cost function is strictly or strongly monotone. Further, also in the implicit approach one uses LCP constrained quadratic programs to search for improving directions (see, e.g., [PHR91, LPR96, OKZ98]).

The main differences between the two approaches seem therefore to be (1) that the present one does not require the numerical calculation of Wardrop equilibria in each iteration, and (2) that the strict (or, strong) monotonicity requirements have been eliminated. These improvements have, seemingly, something more than a theoretical value, since they show that numerical approaches can be devised for a larger class of bilevel problems in traffic management and control, and the calculations can, also seemingly, be made simpler at the same time. The price to be paid for these improvements is the introduction of the differentiability assumptions (32) and (33) for the projection operation at the limit point, which we however hope to be able to relax.

7 Extensions and further research

We discuss in brief two extensions of the traffic equilibrium models [VIP-F] and [VIP-H] in the context of the traffic management models [MPEC-F] and [MPEC-H].

7.1 Elastic demands

Consider an extension of the model [VIP-H], in which the demand is not fixed, but given by a function of the cheapest-route costs. Specifically, we assume that the demands are given by functions g_{pq} : ℜ^{|C|} ↦ ℜ_{+} that are nonnegative, upper bounded and continuous on ℜ^{|C|} for each (p, q) ∈ C.

The elastic demand extension of [VIP-H] then is

−[c̄(h) − Γπ, Γ^{T}h − g(π)] ∈ N_{ℜ_{+}^{|R|}}(h) × N_{ℜ_{+}^{|C|}}(π).  [EVIP-H]

Under the additional assumption that −g strictly monotone on ℜ^{|C|}, −g is then also maximal ([RoW98, Example 12.7]), and the problem can further be written as

[−c̄(h), g^{−1}(d)] ∈ N_{H_{d}}(h, d),  [EVIP-H_{d}]

where

H_{d} := { (h, d) ∈ ℜ^{|R|+|C|} | ∃h ∈ ℜ_{+}^{|R|} with Γ^{T}h = d } .

For overviews of these models, see Nagurney [Nag93] and Patriksson [Pat94].

The corresponding extension of [MPEC-H] becomes

[MPEC-H_{d}]

minimize φ(ρ, β, h, d)  (37a)
subject to ρ ∈ P,  (37b)
[−c(ρ, h) − β, g^{−1}(d)] ∈ N_{H_{d}}(h, d).  (37c)

The analogous Minty parameterization that leads to [P-F] here leads to the problem to

[P-H_{d}]

minimize Φ(ρ, ĥ, d̂) := φ(ρ, Ψ(ρ, ĥ, d̂), Υ(ĥ, d̂)),  (38a)
subject to ρ ∈ P,  (38b)
ĥ ∈ ℜ^{|R|},  (38c)
d̂∈ ℜ^{|C|},  (38d)

where

Ψ(ρ, ĥ, d̂) := Proj_{H_{d}}^{h}(ĥ, d̂) − ĥ − c (ρ, Proj_{H_{d}}^{h}(ĥ, d̂)) ,  (38e)
Υ(ĥ, d̂)) := d̂− g^{−1} (Proj_{H_{d}}^{d}(ĥ, d̂)) ,  (38f)

and (Proj_{H_{d}}^{h}, Proj_{H_{d}}^{d}) = Proj_{H_{d}} is the representation of the projection operator in the two components h and d. We remark that this problem has properties similar to [P-H], and the algorithm given extends readily to [P-H_{d}].

7.2 Queueing models

The presence of signal controls in the network are sometimes modelled by means of capacity constraints. In such a circumstance, we would introduce in the equilibrium model a set of side constraints of the form

s_{κ}(h) ≤ 0,  κ ∈ K,  (39)

where K is a finite index set (for example formed by subsets of N, A, C, and R), and s_{κ} : ℜ_{+}^{|R|} ↦ ℜ, κ ∈ K, is continuously differentiable on ℜ_{+}^{|R|}. The flows that satisfy (39) form a closed set in ℜ^{|R|}, which we denote by G.

Note that the constraints are given in terms of route flows without any loss of generality, because a constraint on the total link flows, for example, can be written as s_{κ}(Λh) ≤ 0.

Example 9 (capacity constraints and signal control). The most immediate example of a set of flow restrictions is that of upper bounds on some links’ flows. In the framework of (39), such constraints are described by letting K := \overline{A}, and

s_{a}(f_{a}) := f_{a} − u_{a},  a ∈ \overline{A},  (40)

where \overline{A} ⊆ A and u_{a} ≥ 0 is the upper bound on the flow on link a. In the context of traffic signals, the constant u_{a} may be regarded as the upper bound on the traffic that can pass link a during the green-time period. See Miller et al. [MPT75], Smith and Van Vuren [SmV93], Ferrari [Fer97], and Larsson and Patriksson [LaP94, LaP95, LaP99].

When viewing the traffic management problem as a hierarchical problem, in the example discussed above, the side constraints are part of the equilibrium problem and are therefore lower-level constraints. The equilibrium problem [VIP-H], for example, is then extended to include the additional side constraints (39), creating the inclusion

−c̄(h) ∈ N_{H∩G}(h).  [SCVIP-H]

The corresponding changes in [P-H] and in the algorithm lie only in the additional constraints’ appearance in the projection formulae, where H is everywhere to be replaced by H ∩ G. (A similar effect is obtained if pure link flow side constraints are added to the model [VIP-F].) A main additional complication that this extension causes is a more complex construction of descent directions, as the set G influences the form that the projection Proj_{δ(F ∩G)}(δf̂) [respectively, Proj_{δ(H∩G)}(δĥ)] takes. Given that the form of G allows descent directions still to be calculated (for example, the formula (15) also applies to the set F ∩ G as long as G is polyhedral), the algorithm would work as it now stands, and the only issue remaining to be made on its convergence would be on the differentiability of the operator Proj_{F ∩G} (respectively, Proj_{H∩G}) at the limit point, which again would rely on the form of G.

Side constraints of the form (39) can however also be imposed upon the travellers by means of some decentralized control measure, such as a tax. In such a case, the side constraints would not be part of the equilibrium problem but instead be a set of constraints on the equilibrium flows (perhaps also as joint constraints with the control variables), and as such would be placed as upper-level constraints. The presence of lower-level variables in upper-level constraints could however in general complicate the problem immensely, since the feasible set becomes much more complex (see, e.g., [LPR96]). Therefore, in the MPEC models [MPEC-F] and [MPEC-H], such side constraints would be assumed to be represented as smooth penalties in the upper-level objective function φ.

7.3 Further research

Interesting further research topics fall into several categories, some of which go far beyond the present application. Most urgent is perhaps the (already mentioned) reduction of the assumption of differentiability of the projection operator at the limit point of the sequence of iterates produced by the algorithm. The problem [P-F] constructed by the use of the Minty parameterization can of course be solved by other algorithms, some of which may very well produce stationary points to the problem [MPEC-F] under milder conditions. For example, bundle algorithms can be devised along the lines described in [ScZ92, Kiw96, OKZ98, Mäk+99] for the minimization of locally Lipschitzian and upper semidifferentiable functions—the latter condition of which, for a locally Lipschitzian function ω : ℜ^{p} ↦ ℜ, requires in addition that for any x, d ∈ ℜ^{p} and sequences {g^{t}} and {ℓ_{t}} with g^{t} ∈ ∂ω(x + ℓ_{t}d) and {ℓ_{t}} ↓ 0, that lim sup_{t→∞} (g^{t})^{T}d ≥ lim inf_{t→∞} [ω(x + ℓ_{t}d) − ω(x)]/ℓ_{t}, cf. [Bih84]—based on the generation of arbitrary subgradients of the function Φ (see [OuZ95, DeV97, OKZ98] for their computation). Bundle algorithms can certainly be expected to be viable for the present problem, although upper semidifferentiability does not hold everywhere; in any case, global upper semidifferentiability is, perhaps arguably, milder than differentiability at the limit point. We note that the subgradient formula given in [Pat01] amounts to solving a sequence of affine traffic equilibrium models, thus avoiding at least partly the combinatorial nature of the present algorithm.

From a wider perspective, the Minty parameterization is likely to be beneficial also for the solution of other MPEC problems, where the type of parameterization utilized in the problem [MPEC-F] makes sense, as well as for special cases of MPEC, such as mathematical programs with complementarity constraints (MPCC, see, e.g., [ScS00]). Another interesting technical question surrounding the utilization of the Minty parameterization concerns the associated optimality conditions of first and second order, which may have interesting properties and consequences in their own right for the equivalent MPEC problem.

References

[Aka97] T. Akamatsu, “Decomposition of path choice entropy in general transport networks,” Transportation Science 31 (1997), pp. 349–362.

[Bar98] J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

[BaF82] J. F. Bard and J. E. Falk, “An explicit solution to the multi-level programming problem,” Computers & Operations Research, 9 (1982), pp. 77–100.

[BHR97] P. Bergendorff, D.W. Hearn and M.V. Ramana, “Congestion toll pricing of traffic networks,” In: P. Pardalos, D.W. Hearn, and W.W. Hager (eds.), Network Optimization, Proceedings of the Network Optimization Conference, University of Florida, Gainesville, FL, February 12–14, 1996, Lecture Notes in Economics and Mathematical Systems, vol. 450, Springer-Verlag, Berlin, pp. 51–71.

[Ber99] D. P. Bertsekas, Nonlinear Programming, 2nd edition, Athena Scientific, Bellmont, MA, 1999.

[Bih84] A. Bihain, “Optimization of upper semidifferentiable functions,” Journal of Optimization Theory and Applications, 44 (1984), pp. 545–568.

[BoS00] J.F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, NY, 2000.

[CaS87] G.E. Cantarella and A. Sforza, “Methods for equilibrium network traffic signal setting,” In: A.R. Odoni, L. Bianco and G. Szegö (eds.), Flow Control of Congested Networks, Proceedings of the NATO Advanced Research Workshop on Flow Control of Congested Networks, Capri, Italy, October 12–18, 1986, NATO ASI Series F: Computer and Systems Sciences, vol. 38, Springer-Verlag, Berlin, pp. 69–89.

[CSF00] H.-J. Cho, T. E. Smith and T. L. Friesz, “A reduction method for local sensitivity analyses of network equilibrium arc flows,” Transportation Research, 34B (2000), pp. 31–51.

[DaS71] S. Dafermos and F.T. Sparrow, “Optimal resource allocation and toll patterns in user-optimised transport networks,” Journal of Transportation Economy and Policy, 5 (1971), pp. 184–200.

[Dav94] G.A. Davis, “Exact local solution of the continuous network design problem via stochastic user equilibrium assignment,” Transportation Research, 28B (1994), pp. 61–75.

[Dem97] S. Dempe, “On the leader’s dilemma and a new idea for attacking bilevel programming problems,” Technical report, Fachbereich Mathematik, Technische Universität Chemnitz, Chemnitz, Germany, 1997.

[Dem00] S. Dempe, “A bundle algorithm applied to bilevel programming problems with non-unique lower level solutions,” Computational Optimization and Applications, 15 (2000), pp. 145–166.

[DeS96] S. Dempe and H. Schmidt, “On an algorithm solving two-level programming problems with nonunique lower level solutions,” Computational Optimization and Applications, 6 (1996), pp. 227– 249.

[DeV97] S. Dempe and S. Vogel, “The subdifferential of the optimal solution in parametric optimization,” Technical report, Fachbereich Mathematik, Technische Universität Chemnitz, Chemnitz, Germany, 1997.

[DoR00] A.L. Dontchev and R.T. Rockafellar, “Ample parameterization of variational inclusions,” Preprint, Department of mathematics, University of Washington, Seattle, WA, 2000.

[Fer97] P. Ferrari, “Capacity constraints in urban transport networks,” Transportation Research, 31B (1997), pp. 291–301.

[FeR95] M.C. Ferris and D. Ralph, “Projected gradient methods for nonlinear complementarity problems via normal maps,” In: D. Du, L. Qi, and R. Womersley (eds.), Recent Advances in Nonsmooth Optimization, World Scientific Publishers, 1995, pp. 57–87.

[Fis80] C. Fisk, “Some developments in equilibrium traffic assignment,” Transportation Research, 14B (1980), pp. 243–255.

[Fri+90] T.L. Friesz, R.L. Tobin, H.J. Cho and N.J. Mehta, “Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints,” Mathematical Programming, 48 (1990), pp. 265–284.

[GLL91] L. Grippo, F. Lampariello, and S. Lucidi, “A class of nonmonotone stabilization methods in unconstrained optimization,” Numerische Mathematik, 59 (1991), pp. 779–805.

[Hey83] B. G. Heydecker, “Some consequences of detailed junction modeling in road traffic assignment,” Transportation Science, 17 (1983), pp. 263–281.

[Kiw96] K.C. Kiwiel, “Restricted step and Levenberg–Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization,” SIAM Journal on Optimization, 6 (1996), pp. 227–249.

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

[LaP94] T. Larsson and M. Patriksson, “Equilibrium characterizations of solutions to side constrained asymmetric traffic assignment models,” Le Matematiche, 49 (1994), pp. 249–280.

[LaP95] T. Larsson and M. Patriksson, “An augmented Lagrangean dual algorithm for link capacity side constrained traffic assignment problems,” Transportation Research, 29B (1995), pp. 433–455.

[LaP98] T. Larsson and M. Patriksson, “Side constrained traffic equilibrium models—traffic management through link tolls,” In: P. Marcotte and S. Nguyen, eds., Equilibrium and Advanced Transportation Modelling, Kluwer Academic Publishers, New York, NY, 1998, pp. 125–151.

[LaP99] T. Larsson and M. Patriksson, “Side constrained traffic equilibrium models: Analysis, computation and applications,” Transportation Research, 33B (1999), pp. 233–264.

[LeA79] L.J. LeBlanc and M. Abdulaal, “Continuous equilibrium network design models,” Transportation Research, 13B (1979), pp. 19–32.

[LoM92] P. Loridan and J. Morgan, “Least-norm regularization for weak two-level optimization problems,” In: V. Barbu, J. F. Bonnans and D. Tiba (eds.), Optimization, Optimal Control and Partial Differential Equations, Papers from the First Franco-Romanian Conference held in Iaşi, September 7–11, 1992, International Series of Numerical Mathematics, vol. 107, Birkhäuser, Basel, 1992, pp. 307–318.

[LoM96] P. Loridan and J. Morgan, “Weak via strong Stackelberg problems: New results,” Journal of Global Optimization, 8 (1996), pp. 263–287.

[LPR96] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.

[Mar86] P. Marcotte, “Network design problem with congestion effects: A case of bilevel programming,” Mathematical Programming, 34 (1986), pp. 142–162.

[Mig95] A. Migdalas, “Bilevel programming in traffic planning: Models, methods and challenge,” Journal of Global Optimization, 7 (1995), pp. 381–405.

[MPT75] 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.

[Min67] G.J. Minty, “A theorem on monotone sets in Hilbert spaces,” Journal of Mathematical Analysis and Applications, 16 (1967), pp. 434–439.

[Mäk+99] M.M. Mäkelä, M. Miettinen, L. Lukšan, and J. Vlček, “Comparing nonsmooth nonconvex bundle methods in solving hemivariational inequalities,” Journal of Global Optimization, 14 (1999), pp. 117–135.

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

[Out97] J.V. Outrata, “On a special class of mathematical programs with equilibrium constraints,” In: P. Gritzmann, R. Horst, E. Sachs, and R. Tichatschke (eds.), Recent Advances in Optimization, Proceedings of the 8th French-German Conference on Optimization, Trier, July 21–26, 1996, Lecture Notes in Economics and Mathematical Systems, vol. 452, Springer-Verlag, Berlin, 1997, pp. 246–260.

[OKZ98] J. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

[OuZ95] J. Outrata and J. Zowe, “A numerical approach to optimization problems with variational inequality constraints,” Mathematical Programming, 68 (1995), pp. 105–130.

[PHR91] J.-S. Pang, S.-P. Han and N. Rangaraj, “Minimization of locally Lipschitz functions,“ SIAM Journal on Optimization, 1 (1991), pp. 57–82.

[PaQ93] J.-S. Pang and L. Qi, “Nonsmooth equations: Motivations and algorithms,” SIAM Journal on Optimization, 3 (1993), pp. 443–465.

[PaR96] J.-S. Pang and D. Ralph, “Piecewise smoothness, local invertibility, and parametric analysis of normal maps,” Mathematics of Operations Research, 21 (1996), pp. 401–426.

[Pat94] M. Patriksson, The Traffic Assignment Problem—Models and Methods, Topics in Transportation, VSP BV, Utrecht, The Netherlands, 1994.

[Pat98] M. Patriksson, Nonlinear Programming and Variational Inequalities: A Unified Approach, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.

[Pat01] M. Patriksson, “Sensitivity analysis of fixed demand traffic equilibria,” Transportation Science (submitted).

[PaR01] M. Patriksson and R.T. Rockafellar, “Sensitivity analysis of variational inequalities over aggregated polyhedra, with application to traffic equilibria,” Transportation Science (submitted).

[Qi93] L. Qi, “Convergence analysis of some algorithms for solving nonsmooth equations,” Mathematics of Operations Research, 18 (1993), pp. 227–244.

[QiS93] L. Qi and J. Sun, “A nonsmooth version of Newton’s method,” Mathematical Programming, 58 (1993), pp. 353–368.

[QiM89] Y. Qiu and T.L. Magnanti, “Sensitivity analysis for variational inequalities defined on polyhedral sets,” Mathematics of Operations Research, 14 (1989), pp. 410–432.

[Rob80] S.M. Robinson, “Strongly regular generalized equations,” Mathematics of Operations Research, 5 (1980), pp. 43–62.

[Rob85] S. M. Robinson, “Implicit B-differentiability in generalized equations,” Technical Summary Report No. 2854, Mathematics Research Center, University of Wisconsin at Madison, Madison, WI, 1985.

[Rob92] S.M. Robinson, “Normal maps induced by linear transformations,” Mathematics of Operations Research, 17 (1992), pp. 691–714.

[RoW98] R.T. Rockafellar and R.J-B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften, Vol. 317, Springer-Verlag, Berlin, 1998.

[ScS00] H. Scheel and S. Scholtes, “Mathematical programs with complementarity constraints: Stationarity, optimality and sensitivity,” Mathematics of Operations Research, 25 (2000), pp. 1–22.

[ScZ92] H. Schramm and J. Zowe, “A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,” SIAM Journal on Optimization, 2 (1992), pp. 121–152.

[SmV93] M.J. Smith and T. Van Vuren, “Traffic equilibrium with responsive traffic control,” Transportation Science, 27 (1993), pp. 118–132.

[ToF88] R. L. Tobin and T. L. Friesz, “Sensitivity analysis for equilibrium network flow,” Transportation Science, 22 (1988), pp. 242–250.

[ToW96] Ph. Toint and L. Wynter, “Asymmetric multiclass traffic assignment: A coherent formulation,” In: J.-B. Lesort (ed.), Transportation and Traffic Theory, Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, 24–26 July, 1996, Pergamon Press, Oxford, UK, 1996, pp. 237–260.

[YaL96] H. Yang and W.H.K. Lam, “Optimal road tolls under conditions of queueing and congestion,” Transportation Research, 30A (1996), pp. 319–332.

[Yen95] N. D. Yen, “Lipschitz continuity of solutions of variational inequalities with a parametric polyhedral constraint,” Mathematics of Operations Research, 20 (1995), pp. 695–708.

[Zha94] R. Zhang, “Problems of hierarchical optimization in finite dimension,” SIAM Journal on Optimization, 4 (1994), pp. 521–536.