Robust Equilibrium in Transportation Networks

Abstract

We introduce the concept of robust equilibrium in a multi-criteria transportation network and obtain a formula to compute the radius of robustness together with an algorithm to find robust equilibrium flows.

1 Preliminaries

We consider a transportation network G = [N, A, W] that consists of a set of nodes N, a set of n directed arcs or links $A=\{a_{1},\dots ,a_{n}\}$ and a set W of r origin-destination (OD for short) pairs of nodes $w=(x,x^{\prime })$ with $x,x^{\prime }\in N$ such that there is a path from x to $x^{\prime }$. We shall make use of some notations from [14]. Namely, for w ∈ W, P_w is the set of available paths from the origin x to the destination $x^{\prime }$; $P=\{p_{1},\dots ,p_{m}\} =\cup _{w\in W} P_{w}$ is the set of all available paths of the network; d_w > 0 is the demand of the traffic flow from x to $x^{\prime }$. The traffic load in the network is often presented either by arc flows z_a, a ∈ A, or by path flows y_p, p ∈ P. Given a path flow, the arc flow can be obtained by the formula $z_{a}= {\sum }_{p\in P} y_{p} \delta _{ap},$ where δ_ap has value 1 if path p contains arc a and 0 otherwise. In this paper we shall deal with traffic load presented by path flows only. A path flow $y:=(y_{1}, {\dots } , y_{m})^{T}$ (notation “^T” is for transposition) is said to be feasible if its components are all nonnegative, that is, $y\geqq 0$, and satisfy the conservation flow equation

$$\sum\limits_{p\in P_{w}} y_{p} = d_{w} \text{ for all } w\in W. $$

The set of all feasible path flows is denoted K. We assume that on each path p, a cost function c_p is given and depends on the flow y = (y_p)_p∈P on the entire network. The cost functions c_p take values in a finite dimensional space ℝ^ℓ with $\ell \geqq 1$ and are utilized by travelers to evaluate the routes and make their choice. The case ℓ = 1 is classic and well studied. Multi-criteria models deal with $\ell \geqq 2$. In many practical situations, ℓ = 2, which corresponds to two criteria: travel time and travel cost. We assume also that travelers have a complete information on the network and make their choice according to the vector version of Wardrop’s principle: no traveler chooses a path p if he finds another path $p^{\prime }$ connecting the same origin destination such that $c_{p}(y)-c_{p^{\prime }}(y) \geq 0$, which means $c_{p}(y)-c_{p^{\prime }}(y) \geqq 0$ and $c_{p}(y)\not = c_{p^{\prime }}(y)$. This assignment of the network is known as a vector user equilibrium. Thus, at a vector user equilibrium no traveler having chosen route p can reduce at least one of his cost components without increasing other cost components by individually switching to another route $p^{\prime }\not =p$. Mathematically, the problem of multi-criteria traffic assignment is formulated as follows:

Find a feasible path flow $\bar {y}\in K$, called a vector user equilibrium (or equilibrium for short), such that for every OD pair w ∈ W and for every couple of paths $p, p^{\prime }\in P_{w}$ one has implication

$$c_{p}(\bar{y})-c_{p^{\prime}}(\bar{y}) \geq 0 \Longrightarrow \bar{y}_{p}= 0. $$

The traffic assignment problem with multiple cost functions has been a subject of intensive study for almost 50 years (see Quandt [21] and Schneider [26], Dafermos [5], and Dial [6] for pioneer works and Chen et al. [3], Chen and Yen [4], Goh and Yang [9], Li and Chen [10], Lin [11], Luc [12], Luc, Rocca and Papalia [13], Nagurney [15], Nagurney and Dong [16], Tan, Yang and Guo [27], Tian and Xu [28], Wang and Ehrgott [29] and some others (see [15,16,17,18,19,20,21,22,23,24,25]) for recent developments). The interested readers are referred to [23] for a detailed discussion on studies of vector equilibria.

In a parametric model it is assumed that the vector cost functions h_a depend not only on the arc flow z := (z_a)_a∈A but also on a parameter ξ from some parameter set U and the demands d_w are also functions of a parameter. The vector cost function along a path p is then a function of the path flow y and the parameter ξ accordingly: $c_{p}(y, \xi )= {\sum }_{a\in A} {h}_{a}(z, \xi ) \delta _{ap}$. The vector user equilibrium flows, it they exist, are functions of the parameter too. One of the most important issues of the traffic assignment problem is to know how the vector equilibrium flows change when parameters in the cost functions and in the demands change. This issue has been thoroughly treated in the case of single criterion models ([18] and many references given therein), but as far as we know, there are very few works devoted to the multi-criteria case (see [8] for multi-criteria stochastic models).

In stochastic traffic assignment models, the parametric costs c_p(y, ξ) are often given in the form c_p(y, ξ) = c_p(y) + ξ_p, where c_p(y) is the measured cost and ξ_p is an additive random error term with a probabilistic description. In the present paper, we consider a family $\mathcal {C}$ as an uncertainty set of cost functions. Sometimes, it is parametrically given in the form {c(., ξ) := (c_p(., ξ))_p∈P : ξ ∈ U}. It may represent a set of perturbed costs or a set of approximations of the real costs. We shall focus on a particular question of whether it is possible to construct a flow that is equilibrium for any realization of uncertainty in the set $\mathcal {C}$. This question is important in traffic network management when the costs are approximately given, or when the decision makers wish to modify, within a given tolerance, the travel costs (for instance, to increase toll rate, to raise or to lower speed limits) without affecting the traffic load on the whole system. As we shall see later, it is closely related to the concept of robust solutions of optimization problems under uncertainty. Here, we give a simple example to show that both positive and negative answers to our question are possible.

Example 1

Consider a network problem with one pair of origin-destination nodes $w = (x, x^{\prime })$, two criteria: travel time and travel cost, two available paths: P_w = {p₁, p₂} with the travel demand d_w = 30. Assume that the uncertainty sets of travel time and travel cost functions on the paths p₁ and p₂ are respectively given as follows

$${c}_{1}(y,\xi_{1}) = \left( \begin{array}{c} y_{1}+ 2y_{2}-\xi_{1}\\ 6y_{1}+ 2y_{2} \end{array}\right) ,\quad\quad {c}_{2}(y,\xi_{2}) = \left( \begin{array}{c} y_{1}+ 6y_{2}\\ 10 + 6y_{1}+ 8(y_{2}-\xi_{2}) \end{array}\right) $$

with ξ₁ ∈ [0,1] and ξ₂ ∈ [− 1,1]. Direct computation shows that $\overline {y}=(30, 0)^{T}$ is a vector equilibrium for any realization of ξ ∈ [0,1] × [− 1,1].

If we are given another uncertainty sets, for instance,

$${c}_{1}(y,\xi_{1}) = \left( \begin{array}{c} y_{1}+ 2y_{2}-\xi_{1}\\ 6y_{1}+ 2y_{2} \end{array}\right), \quad\quad {c}_{2}(y,\xi_{2}) = \left( \begin{array}{c} y_{1}+ 6y_{2}\\ 6y_{1}+ 8(y_{2}-\xi_{2}) \end{array}\right) $$

with ξ₁ ∈ [0,1] and ξ₂ ∈ [− 1,1], then no flow exists which is equilibrium for all realizations of ξ ∈ [0,1] × [− 1,1].

Throughout this paper, we assume that the demands d_w, w ∈ W are fixed and $\mathcal {C}$ is a given uncertainty set in which components c_p of $c\in \mathcal {C}$ are continuous vector functions from K to $\mathbb R^{\ell }$ with $\ell \geqq 1$. We equip $\mathcal {C}$ with the max-norm: $\Vert c\Vert = \max _{p\in P, y\in K} \Vert c_{p}(y)\Vert$ where ∥c_p(y)∥ is the usual norm in $\mathbb R^{\ell }$ and make use of the following notations:

∙ Given $Q\subseteq \mathbb R^{\ell } ,$ the set Min(Q), called the set of minimal elements of Q, consists of vectors q ∈ Q such that there is no $q^{\prime }\in Q$ satisfying $q\leq q^{\prime }$.

∙ d[a, Q] is the Euclidean distance from a point $a\in \mathbb R^{\ell }$ to Q.

∙ T(Q, a) is the contingent cone of Q at a ∈ Q: v ∈ T(Q, a) if and only if there are a sequence of elements a^ν in Q and a sequence of positive numbers t_ν convergent to $\infty$ such that t_νa^ν converges to v.

∙ T⁰(Q, a) is the cone of admissible directions of Q at a: v ∈ T⁰(Q, a) if and only if there is some δ > 0 such that a + tv ∈ Q for all t ∈ [0, δ].

∙ C_w is the set of all functions $c_{p^{\prime }}\in \mathcal {C}, p^{\prime }\in P_{w}$ for an OD pair w ∈ W.

∙ B(a, r) is the ball of radius r centered at a in a normed space that contains a.

We shall introduce the concept of robust equilibrium and establish a relationship with the concept of robustness of uncertainty optimization. Properties of robust equilibria will be proven and an algorithm to compute robust equilibria will be presented with its convergence. Some numerical examples are given to illustrate our algorithm. By our knowledge, this topic is new and there exist no study on it even for single criterion models.

2 Robust Equilibrium

For every element $c\in \mathcal {C}$ we denote (G, c) the network G equipped with the cost function c.

Definition 1

Let $\overline {y}$ be a feasible path flow. We say that $\overline {y}$ is a robust vector equilibrium if it is a vector equilibrium of the network (G, c) for every realization c in $\mathcal {C}$. Given an instance $\bar {c}\in \mathcal {C}$ we say that $\bar {y}$ is a local robust vector equilibrium of $(G, \bar {c})$ if there is some δ > 0 such that it is an equilibrium of (G, c) for every realization c in $\mathcal {C}$ with $\Vert c-\bar {c}\Vert \leqq \delta$.

We have already known from the example given in the preceding section that an uncertainty model of traffic networks may have a robust equilibrium and may have no robust equilibrium, depending on the nature of the uncertainty set. When a robust equilibrium exists, it is also local robust for any realization of uncertainty in the set $\mathcal {C}$. For a local robust vector equilibrium $\bar y$ of $(G, \bar {c})$, the radius of robustness at $\bar y$, denoted $R_{\mathcal C}(\bar y)$, is the supremum of δ > 0 such that $\bar y$ is equilibrium of (G, c) for every $c\in \mathcal {C}$ with $\Vert c-\bar {c}\Vert \leqq \delta$. It is clear that a local robust vector equilibrium $\bar {y}$ of $(G, \bar {c})$ is robust if and only if the uncertainty set $\mathcal {C}$ is contained in the ball of radius $R_{\mathcal C}(\bar {y})$ centered at $\bar {c}$. To link the concept of robust equilibrium of networks under uncertainty and the concept of optimal solution in robust optimization we define a real-valued function ϕ on K by

$$\phi(y, c):= \sum\limits_{p\in P_{w}, w\in W} y_{p} d[c_{p}(y),\text{Min} (C_{w}(y))]. $$

When $\mathcal {C}$ is parametrically given, that is $\mathcal {C}=\{c(.,\xi ): \xi \in U\}$, we shall write ϕ(y, ξ) instead of ϕ(y, c). For instance, under the first uncertainty set in Example 1, we have

$$ \phi(y, \xi) = y_{2} \sqrt{(120-4y_{1}+\xi_{1})^{2} + (190-6y_{1}-8\xi_{2})^{2}}, $$

(1)

for every y = (y₁, y₂) ∈ K and (ξ₁, ξ₂) ∈ [0,1] × [− 1,1], and under the second uncertainty set the function ϕ(y, ξ) takes the form

$$ \phi(y, \xi) = \left\{\begin{array}{lll} y_{2} \sqrt{(4y_{2}+\xi_{1})^{2} + (6y_{2} -8\xi_{2})^{2}}&\text{ if either } \xi_{1}>0, y_{2}\geqq 4\xi_{2}/3,\\ &\text{ or } 0<y_{2}\leqq 4\xi_{2}/3,\\ 240 \xi_{2}& \text{ if } y_{2}= 0, \xi_{1}= 0, \xi_{2} >0,\\ 0 & \text{ othewise}. \end{array}\right. $$

(2)

Here is a characterization of robust equilibrium via the function ϕ.

Proposition 1

Let $\bar {y}$be a feasible flow. The following statements are equivalent.

• (i) $\bar {y}$isa robust equilibrium;

• (ii) For every $c\in \mathcal {C}, p\in P$andw ∈ W one hasimplication

  $$c_{p}(\overline{y})\not\in \text{Min}(C_{w}(\overline{y})) \Longrightarrow \overline{y}_{p}= 0; $$

• (iii) $\bar {y}$is an optimal solution of the problem

  $$\begin{array}{@{}rcl@{}} \text{minimize } && \!\!\underset{c\in \mathcal{C}}{\max} \phi(y,c)\\ \text{subject to } && \!\!\!y\in K \end{array} $$

  (3)

and the optimal value is equal to zero.

Proof

The equivalence between (i) and (ii) is immediate from the definition of robust equilibrium. We prove implication (ii) ⇒ (iii). By definition, $\phi (y,c)\geqq 0$ for all y ∈ K and $c\in \mathcal {C}$. If $\bar y$ satisfies (ii), then $\phi (\bar y, c)= 0$ for all $c\in \mathcal {C}$. Consequently, $\bar y$ solves (3) and the optimal value is equal to zero. Conversely, if (iii) is satisfied, then $\max _{c\in \mathcal {C}} \phi (\bar y,c) = 0$. Again, because $\phi (\bar y,c)\geqq 0$, we deduce $\phi (\bar y,c)= 0$ for all $c\in \mathcal {C}$. Notice that all the terms in the expression of $\phi (\bar y,c)$ are nonnegative. Therefore, $\bar y_{p} d[c_{p}(\bar y),\text {Min} (C_{w}(\bar y))]= 0$ which implies $\bar y_{p}= 0$ when $c_{p}(\bar y)\not \in \text {Min} (C_{w}(\bar y))$ for every $c\in \mathcal {C}, p\in P$ and w ∈ W as requested. □

A local version of Proposition 1 is given below.

Proposition 2

Let $\bar {y}$be a feasible flow and let $\bar c\in \mathcal {C}$. The following statements are equivalent.

• (i) $\bar {y}$isa local robust equilibrium of $(G,\bar c)$;

• (ii) There is δ > 0 suchthat for every $c\in \mathcal {C}\cap B(\bar c, \delta ) , p\in P$andw ∈ W one hasimplication

  $$c_{p}(\overline{y})\not\in \text{Min}((C_{w}\cap B(\bar c, \delta)) (\overline{y})) \Longrightarrow \overline{y}_{p}= 0; $$

• (iii) There is δ > 0 such that $\bar {y}$is an optimal solution of the problem

  $$\begin{array}{@{}rcl@{}} \text{minimize } && \!\!\underset{c\in \mathcal{C}\cap B(\bar c, \delta)}{\max} \phi(y,c)\\ \text{subject to } && \!\!y\in K \end{array} $$

  (4)

and the optimal value is equal to zero.

Proof

Apply the argument of the proof of Proposition 1. □

The objective function $\mathop {\max _{c\in \mathcal {C}}} \phi (y, c)$ of (3) represents the worst case scenario among all possible realizations $\phi (y, c), c\in \mathcal {C}$. The optimization problem (3) is recognized as the robust counterpart of parametric problems of minimizing ϕ(y, c) over K for $c\in \mathcal {C}$ (see [2]). We deduce that every robust equilibrium is a robust optimal solution of (3). The converse, however, is not always true, that is, a robust optimal solution of (3) is not necessarily a robust equilibrium if the optimal value is not equal to zero. In Example 1, when ϕ given by (1), the feasible flow $\bar y=(30,0)^{T}$ is a robust optimal solution of (3) and the optimal value is equal to zero. It is a robust equilibrium of the network under the first uncertainty set. When ϕ is given by (2), direct calculation shows that (3) admits an optimal solution, but its optimal value is strictly positive; hence, the network under the second uncertainty set has no robust equilibrium as we have already observed.

When $\mathcal {C}$ is parametrically given, problem (3) becomes a minimax problem. Although the objective function ϕ(y, ξ) is neither convex nor concave, it enjoys some useful properties. In fact, given ξ, the function ϕ(., ξ) is continuous (or locally Lipschitz/differentiable) on an open and dense subset of K as soon as the function c(y, ξ) is continuous (or locally Lipschitz/differentiable) on K (see [14, Theorem 4.1]). Many existing methods for minimax problems then can be applied to solve (3) (see, for instance, [1, 7, 20, 25]), in particular when the set U is finite. When U is not finite, say U is a compact set in a finite dimensional Euclidean space, because of difficulties related to the implementation of global optimization algorithms in finding global optimal solutions of badly structured problems, it is more reasonable to work with local robust equilibria. We shall now concentrate on local robust equilibria only.

Theorem 1

Let $\mathcal {C}=(\mathcal C_{p})_{p\in P}$be the uncertainty set of G. Let $\bar c\in \mathcal {C}$be given and let $\overline {y} \in K$be an equilibrium of $(G, \bar c)$. If $\overline {y}$is a local robust equilibrium of $(G,\bar c),$then for every $w \in W, p,p^{\prime } \in P_{w}$with $\bar c_{p}(\bar y) =\bar c_{p^{\prime }}(\bar y)$and $\overline {y}_{p} > 0,$one has

$$ \left( T^{0}(\mathcal{C}_{p}, \bar c_{p})(\bar y)- \mathbb R^{\ell}_{+}\right) \cap \left( T^{0}(\mathcal{C}_{p^{\prime}}, \bar c_{p^{\prime}})(\bar y) +\mathbb R^{\ell}_{+}\setminus \{0\} \right)= \emptyset. $$

(5)

Conversely, if for every w ∈ W, p ∈ P_w with $\bar c_{p}(\bar y) =\bar c_{p^{\prime }}(\bar y)$and $\overline {y}_{p} > 0,$one has

$$ \left( T(\mathcal{C}_{p}(\bar y), \bar c_{p}(\bar y)) - \mathbb R^{\ell}_{+}\right)\cap \left( T(\mathcal{C}_{p^{\prime}}(\bar y), \bar c_{p^{\prime}}(\bar y)) +\mathbb R^{\ell}_{+} \right) = \{0\}, $$

(6)

then $\bar y$is a local robust equilibrium of $(G,\bar c)$.

Proof

We prove the first part of the theorem by contradiction. Suppose there are nonzero vectors $r_{1},r_{2}\in \mathbb R^{\ell }_{+}$ with r₂≠ 0 and some functions $u\in T^{0}(\mathcal {C}_{p}, \bar c_{p})$, $v\in T^{0}(\mathcal {C}_{p^{\prime }}, \bar c_{p^{\prime }})$ such that $u(\bar y)-r_{1}=v(\bar y)+r_{2}$. By definition, there is some t₀ > 0 such that for every t ∈ [0, t₀] one has $\bar c_{p} + t u \in \mathcal {C}_{p}$ and $\bar c_{p^{\prime }}+ tv\in \mathcal {C}_{p^{\prime }}$. Choose t ∈ (0, t₀) such that $t< R(\bar y)/(\Vert u\Vert + \Vert v\Vert )$ and define a vector cost function c := (c_s)_s∈P on K by

$$c_{s} =\left\{\begin{array}{lll} \bar c_{s} & \text{if } s\not\in \{ p, p^{\prime}\}\\ \bar c_{p}+tu & \text{if } s= p\\ \bar c_{p^{\prime}}+tv & \text{if } s=p^{\prime}. \end{array}\right. $$

We have $c \in \mathcal C$ and $\Vert c-\bar c\Vert \leq \Vert t u\Vert + \Vert tv\Vert < R(\bar y)$. On the other hand, $c_{p}(\bar y) - c_{p^{\prime }}(\bar y) = t(u(\bar y) -v(\bar y)) = t(r_{1}+r_{2}) \geq 0$. This contradicts the hypothesis that $\bar y_{p} >0$ and $\bar y$ is an equilibrium of (G, c).

Conversely, suppose that $\bar y$ is not a local robust equilibrium of $(G, \bar c)$. There exists a sequence of functions c^ν of $\mathcal C$ converging to $\bar c$, OD pairs w^ν ∈ W and paths $p_{\nu }, p^{\prime }_{\nu }\in P_{w^{\nu }}$ such that

$$ c^{\nu}_{p_{\nu}}(\bar y) \geq c^{\nu}_{p^{\prime}_{\nu}}(\bar y) \quad\text{and}\quad \bar y_{p_{\nu}} >0. $$

(7)

Since the number of OD pairs and the number of paths are finite, without loss of generality, we may assume that w^ν = w for some w ∈ W, p_ν = p and $p^{\prime }_{\nu }=p^{\prime }$ for some $p,p^{\prime }\in P_{w}$ and for all $\nu \geqq 1$. In particular, $\bar y_{p} >0$. Observe further that the sequence $\{ c^{\nu }_{p}(\bar y)\}$ converges to $\bar c_{p} (\bar y)$ and the sequence $\{ c^{\nu }_{p^{\prime }}(\bar y)\}$ converges to $\bar c_{p^{\prime }} (\bar y))$ as ν tends to infinity. Therefore, $\bar c_{p} (\bar y)\geqq \bar c_{p^{\prime }} (\bar y)$. Because $\bar y$ is equilibrium for $(G, \bar c)$ and $\bar y_{p}>0,$ we obtain equality $\bar c_{p} (\bar y))= \bar c_{p^{\prime }} (\bar y)$. Then, inequality (7) gives

$$ c^{\nu}_{p}(\bar y) - \bar c_{p}(\bar y) \geq c^{\nu}_{p^{\prime}}(\bar y) - \bar c_{p^{\prime}}(\bar y)\text{ for all }\nu \geqq 1. $$

(8)

Set $t_{\nu }:= \Vert c^{\nu }_{p}(\bar y) - \bar c_{p} (\bar y)\Vert$ and $s_{\nu }:= \Vert c^{\nu }_{p^{\prime }}(\bar y) - \bar c_{p^{\prime }} (\bar y)\Vert$. By working with subsequences if necessary, we may assume either (a) t_ν > 0, s_ν = 0 for all $\nu \geqq 1$ and the sequence $\{ (c^{\nu }_{p}(\bar y) - \bar c_{p} (\bar y))/ t_{\nu }\}$ converges to some unit norm vector u; or (b) s_ν > 0, t_ν = 0 for all $\nu \geqq 1$ and the sequence $\{ (c^{\nu }_{p^{\prime }}(\bar y) - \bar c_{p^{\prime }} (\bar y))/s_{\nu }\}$ converges to some unit norm vector v; or (c) both s_ν and t_ν are strictly positive for all $\nu \geqq 1$, the sequence {s_ν/t_ν} (or {t_ν/s_ν}) converges to some $\alpha \geqq 0$ and both sequences $\{ (c^{\nu }_{p}(\bar y) - \bar c_{p} (\bar y))/ t_{\nu }\}$ and $\{ (c^{\nu }_{p^{\prime }}(\bar y) - \bar c_{p^{\prime }} (\bar y))/s_{\nu }\}$ converge to unit norm vectors u and v, respectively. Note that in all cases $u \in T(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y))$ and $v\in T(\mathcal {C}_{p^{\prime }}(\bar y), \bar c_{p^{\prime }}(\bar y))$. In the case (a), we have $c^{\nu }_{p}(\bar y) - \bar c_{p} (\bar y) \geq 0$. Therefore, u ≥ 0 and belongs to $T(\mathcal {C}_{p^{\prime }}(\bar y), \bar c_{p^{\prime }}(\bar y)) +\mathbb R^{\ell }_{+}$ as well. This contradicts (6). In the case (b), we have $c^{\nu }_{p^{\prime }}(\bar y) - \bar c_{p^{\prime }} (\bar y)\leq 0$, which implies v ≤ 0. Clearly, $v\in T(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y)) - \mathbb R^{\ell }_{+}$, which again contradicts (6). In the case (c), if {t_ν/s_ν} converges to $\alpha \geqq 0$, then we deduce from (8) that

$$ \alpha u= \lim_{\nu\to\infty} \frac{t_{\nu}}{s_{\nu}}\frac{ c^{\nu}_{p}(\bar y) - \bar c_{p}(\bar y)} {t_{\nu}} \geqq \lim_{\nu\to\infty} \frac{ c^{\nu}_{p^{\prime}}(\bar y) - \bar c_{p^{\prime}}(\bar y)}{s_{\nu}}= v. $$

(9)

Similarly, if {s_ν/t_ν} converges to $\alpha \geqq 0$, then

$$ u= \lim_{\nu\to\infty} \frac{ c^{\nu}_{p}(\bar y) - \bar c_{p}(\bar y)} {t_{\nu}} \geqq \lim_{\nu\to\infty} \frac{s_{\nu}}{t_{\nu}} \frac{ c^{\nu}_{p^{\prime}}(\bar y) - \bar c_{p^{\prime}}(\bar y)}{s_{\nu}}= \alpha v. $$

(10)

By expressing v = αu + (v − αu) with $v-\alpha u \leqq 0$ from (9) and u = αv + (u − αv) with $u-\alpha v \geqq 0$ from (10) we have either $v\in T(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y)) - \mathbb R^{\ell }_{+}$ or $u\in T(\mathcal {C}_{p^{\prime }}(\bar y), \bar c_{p^{\prime }}(\bar y))+\mathbb R^{\ell }_{+}$, respectively. By remembering $u \in T(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y))$ and $v\in T(\mathcal {C}_{p^{\prime }}(\bar y), \bar c_{p^{\prime }}(\bar y))$, we obtain a contradiction with (6). The proof is complete. □

The gap between the necessary condition and the sufficient condition for local robustness in the preceding theorem is expressed in the cones involved in (5) and (6). The cones in (5) consist of the values of admissible direction functions computed in the space of functions, while the cones in (6) are contingent cones computed in the space $\mathbb R^{\ell }$. It is clear that $T^{0}(\mathcal {C}_{p}, \bar c_{p})(\bar y) \subseteq T^{0}(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y))$ and equality is not true in general. This observation is also valid for the contingent cone. Moreover, (5) can clearly be simplified to

$$ T^{0}(\mathcal{C}_{p}, \bar c_{p})(\bar y) \cap \left( T^{0}(\mathcal{C}_{p^{\prime}}, \bar c_{p^{\prime}})(\bar y) +\mathbb R^{\ell}_{+}\setminus \{0\} \right)= \emptyset. $$

(11)

Let us now consider some closely related conditions:

$$\begin{array}{@{}rcl@{}} \left( T^{0}(\mathcal{C}_{p}(\bar y), \bar c_{p}(\bar y)) - \mathbb R^{\ell}_{+}\right) \cap \left( T^{0}(\mathcal{C}_{p^{\prime}}(\bar y), \bar c_{p^{\prime}}(\bar y)) +\mathbb R^{\ell}_{+} \setminus \{0\}\right) &=& \emptyset, \end{array} $$

(12)

$$\begin{array}{@{}rcl@{}} \left( T(\mathcal{C}_{p}, \bar c_{p})(\bar y)) - \mathbb R^{\ell}_{+}\right) \cap \left( T(\mathcal{C}_{p^{\prime}}, \bar c_{p^{\prime}})(\bar y) +\mathbb R^{\ell}_{+}\setminus \{0\}\right) &=& \emptyset, \end{array} $$

(13)

$$\begin{array}{@{}rcl@{}} \left( T^{0}(\mathcal{C}_{p}, \bar c_{p})(\bar y)) - \mathbb R^{\ell}_{+}\right) \cap \left( T^{0}(\mathcal{C}_{p^{\prime}}, \bar c_{p^{\prime}})(\bar y) +\mathbb R^{\ell}_{+}\right) &=& \{0\}, \end{array} $$

(14)

$$\begin{array}{@{}rcl@{}} T(\mathcal{C}_{p}(\bar y), \bar c_{p}(\bar y)) \cap \left( T(\mathcal{C}_{p^{\prime}}(\bar y), \bar c_{p^{\prime}}(\bar y) +\mathbb R^{\ell}_{+} \right) &=& \{0\}. \end{array} $$

(15)

As we have already said (5) is equivalent with (11). It is also clear that each of (12) and (13) implies (5), while (6) implies (13), (14), and (15). Next, we give two examples to show that (5) cannot be substituted by (12) (Example 2) and (6) cannot be substituted by (15) (Example 3).

Example 2

Let G be a network consisting of a single OD pair and two routes p and $p^{\prime }$ connecting this pair and the demand d = 20. Let the uncertainty set $\mathcal {C}$ be a set of vector functions with values in $\mathbb R^{2}$ and composed of the functions $\bar c$ and c^t, t ∈ [0,1] given below:

$$\bar c=\left( \left( \begin{array}{c} 10\\ 10 \end{array}\right)\!, \left( \begin{array}{c} 10\\ 10 \end{array} \right) \right)\!,\enskip c^{t} =\left( \left( \begin{array}{c} 30 + (2t-1)y_{1} \\ 10 + 20 t + (1-t)y_{2} \end{array}\right) \!, \left( \begin{array}{c} 30 + (t/2 - 1)y_{1} \\ 10 + 10 t + (1-t/2)y_{2} \end{array}\right) \right)\!, $$

where y₁ is a flow on p and y₂ is a flow on $p^{\prime }$. The first and the second vector components of $\bar c$ and c^t indicate the costs on p and $p^{\prime }$, respectively. Clearly, the flow $\bar y= (20, 0)^{T}$ is a robust equilibrium. However,

$$T^{0}(\mathcal{C}_{p}(\bar y), \bar c_{p}(\bar y))= \left\{ t \left( \begin{array}{c} 40\\ 20 \end{array} \right): t\geqq 0 \right\}, \hspace{0.5cm} T^{0}(\mathcal{C}_{p^{\prime}}(\bar y), \bar c_{p^{\prime}}(\bar y))= \left\{ t \left( \begin{array}{c} 10\\ 10 \end{array}\right): t\geqq 0\right\}. $$

Hence, $T^{0}(\mathcal {C}_{p}(\bar y), \bar c_{p}(\bar y))\cap \left (T^{0}(\mathcal {C}_{p^{\prime }}(\bar y), \bar c_{p^{\prime }}(\bar y)) +\mathbb R^{\ell }_{+}\setminus \{0\} \right )\not = \emptyset .$ In this example, we have $T^{0}(\mathcal {C}_{p}, \bar c_{p})(\bar y) = T^{0}(\mathcal {C}_{p^{\prime }}, \bar c_{p^{\prime }})(\bar y)= \{0\}$ and so (5) holds true.

Example 3

We consider the network described in Example 2 with the uncertainty set $\mathcal {C}$ composed of the functions $\bar c$ and c^t, t ∈ [0,1] given below:

$$\begin{array}{@{}rcl@{}} \bar c&=&\left( \left( \begin{array}{c} 10\\ 10 \end{array}\right), \left( \begin{array}{c} 10\\ 10 \end{array} \right) \right),\\ c^{t} &=&\left( \left( \begin{array}{c} 10 +\sqrt{t} + (t- \sqrt{t})y_{1}/20 \\ 10+ t + (\sqrt{t}-t)y_{2}/20 \end{array}\right) , \left( \begin{array}{c} 10+ t+ (t^{2} - t)y_{1} /20\\ 10+ t^{2} + (t-t^{2})y_{2} /20 \end{array}\right) \right), \end{array} $$

where, as before, y₁ is a flow on p, y₂ is a flow on $p^{\prime }$, and the first and the second vector components of $\bar c$ and c^t indicate the costs on p and $p^{\prime }$, respectively. We choose the flow $\bar y= (20, 0)^{T}$. Clearly, it is an equilibrium of $(G,\bar {c})$. It is not a local robust equilibrium because for any t ∈ (0,1), we have

$${c_{p}^{t}} (\bar y) = \left( \begin{array}{c} 10+t\\ 10+t \end{array} \right) >\left( \begin{array}{c} 10+t^{2}\\ 10+t^{2} \end{array} \right) = c_{p^{\prime}}(\bar y). $$

Despite this,

$$T(\mathcal{C}_{p}, \bar c_{p})(y)= T(\mathcal{C}_{p^{\prime}}, \bar c_{p^{\prime}})(y)= \left\{ s \left( \begin{array}{c} 1- y_{1}/20\\ y_{2}/20 \end{array}\right): s\geqq 0 \right\}, $$

which implies $T(\mathcal {C}_{p}, \bar c_{p})(\bar y) = T(\mathcal {C}_{p^{\prime }}, \bar c_{p^{\prime }})(\bar y)=\{0\}$ and shows that (15) holds.

3 Strict Equilibrium

Among local robust equilibria, there may exist some that remain local robust even when the uncertainty set moves around a given element. We wish to give some details on them. First, we derive a necessary and sufficient condition for such equilibria from Theorem 1.

Lemma 1

Let $\bar c=(\bar c_{p})_{p\in P}$be a given function where $\bar c_{p}: K\to \mathbb R^{\ell }$are continuous, and let $\bar y\in K$be an equilibrium of $(G, \bar c)$. Then, $\bar y$is a local robust equilibrium for any uncertainty set $\mathcal C$containing $\bar c$if and only if for every w ∈ W, p ∈ P_w with $\bar y_{p}>0$one has $\bar c_{p}(\bar y) \not = \bar c_{p^{\prime }}(\bar y)$for all $p^{\prime }\in P_{w}, p^{\prime }\not =p$.

Proof

The “if” part is immediate from Theorem 1. For the “only if” part, it suffices to choose an uncertainty set that contains $\bar c$ in its interior. Then, the intersection in the left-hand side of (5) is nonempty, by which there is no $p^{\prime }\in P_{w}, p^{\prime }\not =p$ such that $\bar c_{p}(\bar y) = \bar c_{p^{\prime }}(\bar y)$. □

Definition 2

A feasible flow $\bar y$ is said to be a strict equilibrium of $(G, \bar c)$ if there is some 𝜖 > 0 such that it is an equilibrium of (G, c) for every continuous vector cost function c such that $\Vert c-\bar c\Vert \leqq \epsilon$.

When a strict equilibrium $\overline {y}\in K$ of $(G, \bar c)$ is given, we denote by $r(\bar y)$ the supremum of 𝜖 such that $\bar y$ is equilibrium of (G, c) with $\Vert c-\bar c\Vert \leqq \epsilon$. This $r(\bar y)$ gives us a lower bound for the radius of robustness at $\bar y$, that is, $r(\bar y) \leqq R_{\mathcal C}(\bar y)$ for any uncertainty set $\mathcal C$ containing $\bar c$. Now, we wish to construct an optimization problem that allows us to find a strict equilibrium of the network when a vector cost function $\bar c$ from the uncertainty set is given. To this end, denote

$$I_{w}(y):=\left\{ i\in \{1, {\dots} , m\}: p_{i}\in P_{w}, \bar c_{p_{i}}(y)\in \text{Min}(\bar C_{w}(y))\right\} $$

for every y ∈ K and define a real-valued function ρ on K to be

$$\rho(y) := \sum\limits_{p\in P_{w}, w\in W} y_{p} \left( d[\bar c_{p}(y), \text{Min} (\bar C_{w}(y))] + \sum\limits_{i\in I_{w}(y), p_{i}\not=p} \chi_{\{0\}} (\Vert \bar c_{p}(y) - \bar c_{p_{i}}(y)\Vert )\right), $$

where χ_{0} is the characteristic function of {0}, that is χ_{0}(t) = 0 if t≠ 0 and χ_{0}(t) = 1 if t = 0.

Corollary 1

Let $\overline {y} \in K$ be a feasible flow. Then, $\overline {y}$ is a strict equilibrium of $(G,\bar c)$ if and only if it is an optimal solution of the following optimization problem

and the optimal value of this problem is equal to 0.

Proof

Assume $\overline {y}\in K$ is a strict equilibrium. In particular, it is an equilibrium. Therefore, if $\bar y_{p}>0$ and p ∈ P_w, one has $\bar c_{p}(\bar y) \in \text {Min}(\bar C_{w}(\bar y))$ and so $d[\bar c_{p}(\bar y), \text {Min} (\bar C_{w}(\bar y))] = 0$. Moreover, in view of Lemma 1, $\bar c_{p}(\bar y) \not = \bar c_{p_{i}}(\bar y)$ for p_i ∈ P_w ∖{p}, which implies ${\sum }_{i\in I_{w}(\bar y), p_{i}\not =p} \chi _{\{0\}} (\Vert \bar c_{p}(\bar y)$$- \bar c_{p_{i}}(\bar y)\Vert )= 0$. We deduce that $\rho (\bar y) = 0$. Because ρ takes nonnegative values only, $\bar y$ is an optimal solution of ($P_{1}^{\prime }$).

Conversely, if $\rho (\bar y) = 0$, then for every w ∈ W, p ∈ P, we have

$$\bar y_{p} \left( d[\bar c_{p}(\bar y), \text{Min} (\bar C_{w}(\bar y))] + \sum\limits_{i\in I_{w}(\bar y), p_{i}\not=p} \chi_{\{0\}} (\Vert \bar c_{p}(\bar y) - \bar c_{p_{i}}(\bar y)\Vert )\right)= 0 $$

because all the terms in the expression of $\rho (\bar y)$ are nonnegative. Consequently, when $\bar y_{p}>0$, the terms $d[\bar c_{p}(\bar y), \text {Min} (\bar C_{w}(\bar y))]$ and $\chi _{\{0\}} (\Vert \bar c_{p}(\bar y) - \bar c_{p_{i}}(\bar y)\Vert ), p_{i}\in I_{w}(\bar y)$ are all equal to 0. We deduce that $c_{p}(\bar y)\in \text {Min} (\bar C_{w}(\bar y))$ proving that $\bar y$ is equilibrium, and $\bar c_{p}(\bar y)\not = \bar c_{p_{i}}(\bar y)$ for $p_{i}\in I_{w}(\bar y), p_{i}\not =p$. It is clear that for $p^{\prime }\in P_{w}$ and $p^{\prime }\not \in I_{w}(\bar y)$ one also has $\bar c_{p}(\bar y)\not = \bar c_{p^{\prime }}(\bar y)$. In view of Lemma 1, $\overline {y}$ is a strict equilibrium. □

We know that given a continuous vector cost function $\bar c$, the network $(G, \bar c)$ does have equilibria, but it may have no robust or local robust equilibrium. We shall show that the set of cost functions c for which (G, c) has no local robust equilibrium, is nowhere dense. First we need the following auxiliary result.

Lemma 2

Let $\{q^{1}, \dots , q^{m} \}$be a family of vectors in $\mathbb R^{l}$with $q^{1}={\dots } = q^{k} \in \text {Min} \{q^{1},\dots ,$q^m} for some $k \leqq m$andq^k≠q^j forj > k. Then for every 𝜖 > 0, thereexists $\tilde {q}^{1}, \dots , \tilde {q}^{k}$such that

• (i) $\|\tilde {q}^{i} - q^{i}\| \leqq \epsilon$for $i = 1, \dots , k$.

• (ii) $\tilde {q}^{i} - \tilde {q}^{j} \notin \mathbb R^{l}_{+} \cup (- \mathbb R^{l}_{+}), i, j \in \{1, \dots , k\},~ i \ne j$.

• (iii) $\text {Min} \{\tilde {q}^{1}, \dots , \tilde {q}^{k}, q^{k + 1}, \dots , q^{m}\} = \{\tilde {q}^{1}, \dots , \tilde {q}^{k}\} \cup ((\text {Min} \{q^{1}, \dots , q^{m}\}) \backslash \{q^{1}, \dots ,$q^k}).

Proof

Let 𝜖 > 0 be given. Let $e^{i} \in \mathbb R^{l}$ denote the unit ith vector and e the vector of ones. Since $q^{1}= \dots = q^{k} \ne q^{j}$ for j > k, there exists a positive $\epsilon ^{\prime } \leqq {\epsilon }/{(3l)}$ such that

$$ q^{i} - \epsilon^{\prime} e \notin q^{j} - \mathbb R^{l}_{+}\text{ for all } q^{j} \in \text{Min} \{q^{1}, \dots, q^{m}\}, j > k, i = 1, \dots, k. $$

(16)

Define

$$\tilde{q}^{i} = q^{i} - \epsilon^{\prime} e + \epsilon^{\prime} \left( \frac{i}{k} e^{1} + \left( 1 - \frac{i}{k} \right)e^{l}\right), ~ i = 1, \dots, k. $$

Then,

$$\|\tilde{q}^{i} - q^{i}\| = \epsilon^{\prime} \Vert -e + \frac{i}{k} e^{1} + \left( 1 - \frac{i}{k} \right)e^{l}\Vert \leqq 3 l \epsilon^{\prime} \leqq \epsilon, $$

which proves (i). Moreover for $i, j \in \{1, \dots , k\}, i \ne j$, one has

$$\tilde{q}^{i} - \tilde{q}^{j} = \epsilon^{\prime} \left( \frac{i-j}{k} e^{1} + \frac{j-i}{k} e^{l}\right) \notin \mathbb R^{l}_{+} \cup (- \mathbb R^{l}_{+}) $$

which is (ii). Finally, since $q^{i} \in \text {Min} \{q^{1}, \dots , q^{m}\}$, we have $q^{j} \notin q^{i} - \mathbb R^{l}_{+}$ and hence $q^{j} \notin \tilde {q}^{i} - \mathbb R^{l}_{+}$ for all j > k. This and (ii) prove that $\tilde {q}^{i} \in \text {Min} \{\tilde {q}^{1}, \dots , \tilde {q}^{k}, q^{k + 1}, \dots , q^{m}\}, i = 1, \dots , k$. For j > k such that $q^{j} \in \text {Min} \{q^{1}, \dots , q^{m}\}$, one observes that

$$q^{j} - \mathbb R^{l}_{+} \subseteq q^{j} + \epsilon^{\prime} \left( \frac{i}{k} e^{1} + \left( 1 - \frac{i}{k} \right)e^{l}\right) - \mathbb R^{l}_{+} $$

and deduces from (16) that $\tilde {q}^{i} \notin q^{j} - \mathbb R^{l}_{+},$ for $i \in \{1, \dots , l\}$. Therefore, $q^{j} \in \text {Min} \{\tilde {q}^{1}, \dots , \tilde {q}^{k},$q^k+ 1, $\dots , q^{m}\}$. For j > k such that $q^{j}\not \in \text {Min} \{q^{1}, \dots , q^{m}\}$, we find some $q^ i \in \text {Min} \{q^{1}, \dots , q^{m}\}$ such that qⁱ ≤ q^j. If i > k, then it is clear that $q^{j}\not \in \text {Min} \{\tilde {q}^{1}, \dots , \tilde {q}^{k}, q^{k + 1}, \dots , q^{m}\}$. If $i \leqq k$, then we have $\tilde {q}^ i \leq q^{i} \leq q^{j}$, which again implies that $q^{j}\not \in \text {Min} \{\tilde {q}^{1}, \dots , \tilde {q}^{k}, q^{k + 1}, \dots , q^{m}\}$. From this, (iii) follows. □

For a feasible flow $\bar y\in K$ and w ∈ W, we define

$$I_{w}^{+}(\bar y):= \{i\in I_{w}(\bar y): \bar y_{p_{i}} >0 \}. $$

Because the set $\bar C_{w}(\bar y)$ is finite, the set $I_{w}(\bar y)$ is nonempty. Moreover, if $\bar y$ is an equilibrium, then, in view of the conservation flow equation, the set $I_{w}^{+}(\bar y)$ is nonempty too.

Theorem 2

Let $\overline {y}$be a feasible flow of $(G,\bar c)$. If it is an equilibrium, then for every𝜖 > 0, there exists a continuous vector cost function $\hat c$such that $\Vert \hat c-\bar c\Vert \leqq \epsilon$and $\bar y$is a strict equilibrium of $(G,\hat c)$. Consequently the set of continuous vector cost functions c for which $\bar y$is a strict equilibrium is open and dense in the space of continuous vector cost functions. Moreover, if $\overline {y}$is a strict equilibrium of $(G, \bar c)$, then

$$r (\overline {y}) = \frac {\sqrt{l}}{2} \mathop { \min }\limits_{w \in W, i\in I_{w}^{+}(\overline{y})} \mathop { \min }\limits_{p^{\prime} \in P_{w} \backslash \{p_{i}\}} \|(\bar c_{p^{\prime}}(\overline {y} )- \bar c_{p_{i}}(\overline {y}))^{+}\|, $$

where $(\bar {c}_{p^{\prime }}(\overline {y}) - \bar {c}_{p_{i}}(\overline {y}))^{+}$denotes the positive part of the vector $\bar {c}_{p^{\prime }}(\overline {y}) - \bar {c}_{p_{i}}(\overline {y})$.

Proof

If $\overline {y}$ be a strict equilibrium of $(G,\bar c)$, then we are done. We consider the case where $\bar y$ is not a strict equilibrium of $(G,\bar c)$. Observe first that because $\overline {y}$ is an equilibrium,

$$\sum\limits_{p\in P_{w}, w\in W} y_{p} d[\bar c_{p}(y), \text{Min} (\bar C_{w}(y))]= 0. $$

In view of Corollary 1, there exist some w ∈ W and p_i ∈ P_w such that $\overline {y}_{p_{i}} >0$ and the set $\{ j\in I_{w}(\overline {y}): \bar c_{p_{i}}(\overline {y})=\bar c_{p_{j}} (\overline {y})\in \text {Min} \bar C_{w}(\overline {y})\}$ consists of at least two elements. Applying Lemma 2 to the set $\bar C_{w}(\overline {y})$, we find cost functions $\hat {c}_{p}, p\in P$ such that $\Vert \hat {c}_{p}(\overline {y}) - \bar c_{p}(\overline {y})\Vert \leqq \epsilon$ for all p ∈ P, all elements of $\text {Min}\hat C_{w}(\overline {y})$ are distinct from each other and $I_{w}(\overline {y})$ is unchanged for $\hat {C}(\overline {y})$. We deduce that $d[\tilde {c}_{p}(\overline {y}), \text {Min} \hat {C}(\overline {y})] = 0$ and $\chi _{\{0\}}(\Vert \hat {c}_{p_{i}}(\overline {y})-\hat {c}_{p_{j}}(\overline {y})\Vert ) = 0$ for j≠i and $j\in I_{w}(\overline {y})$. This argument applied to all paths on which the flow $\overline {y}$ has a nonzero component, we deduce

$$\hat{\rho}(y) = \sum\limits_{p\in P_{w}, w \in W} \overline {y}_{p} \left( d[\hat{c}_{p}(\overline {y}), \text{Min} \hat{C}_{w}(\overline {y})] + \sum\limits_{i\in I_{w}(\overline{y}), p_{i} \ne p}\chi_{\{0\}} (\|\hat{c}_{p}(\overline {y}) -\hat{c}_{p_{i}}(\overline {y})\|)\right) = 0, $$

which, in view of Corollary 1, implies that $\overline {y}$ is a strict equilibrium for $(G, \hat {c})$.

Finally, assume that $\bar y$ is a strict equilibrium of $(G,\bar c)$. It follows from the proof of Corollary 1 that $\overline {y}$ is a vector equilibrium of $(G, \tilde {c})$ as soon as $\tilde {c}_{p_{i}}(\overline {y}) \not = \tilde {c}_{p}(\overline {y})$ and $\tilde {c}_{p_{i}}(\overline {y}) \not \leq \tilde {c}_{p}(\overline {y})$ for any w ∈ W, p_i, p ∈ P_w with p_i≠p and $\overline {y}_{p} > 0$, which is equivalent to

$$(\tilde{c}_{p_{i}}(\overline {y}) - \tilde{c}_{p}(\overline {y}))^{+} \ne 0. $$

Let $\epsilon < r(\overline {y})$ and $\|\tilde {c}_{p_{i}}(\overline {y}) - {c}_{p_{i}}(\overline {y})\| \leq \epsilon , \|\tilde {c}_{p}(\overline {y}) - {c}_{p}(\overline {y})\| \leq \epsilon$, one has

$$(\tilde{c}_{p_{i}}(\overline {y}) - \tilde{c}_{p}(\overline {y}))^{+} \geqq [({c}_{p_{i}}(\overline {y}) - \epsilon e) - ({c}_{p}(\overline {y}) + \epsilon e)]^{+} \geq 0, $$

proving that $\overline {y}$ is a vector equilibrium of $(G, \tilde {c})$.

Let $\epsilon > r(\overline {y})$ and let

$$r(\overline {y}) = \frac {\sqrt{l}}{2} \|(c_{p^{\prime}}(\overline {y} ) - c_{p_{i}}(\overline {y} ))^{+}\| $$

for some $i\in I_{w}^{+}(\overline {y}), p^{\prime } \in P_{w} \backslash \{p_{i}\}$. Define a perturbed cost $\tilde {c}$ by

$$\tilde{c}_{p}(\overline {y}) = \left\{\begin{array}{lll} c_{p}(\overline {y}) & \text{if } p \ne p^{\prime}, p \ne p_{i}\\ c_{p_{i}}(\overline {y}) + (\epsilon/\sqrt{l}) e &\text{if } p = p_{i} \\ c_{p_{i}}(\overline {y}) - (\epsilon/\sqrt{l}) e &\text{if } p=p^{\prime}. \end{array}\right. $$

Then, $\|\tilde {c}_{p}(\overline {y}) - {c}_{p}(\overline {y})\| \leqq \epsilon$ for all p ∈ P and $\tilde {c}_{p^{\prime }}(\overline {y}) - \tilde {c}_{p_{i}}(\overline {y}) = c_{p^{\prime }}(\overline {y}) - c_{p_{i}}(\overline {y}) - 2 \epsilon \leq 0$. Consequently, $\tilde {c}_{p_{i}}(\overline {y}) \notin \text {Min} \tilde {C}_{w}(\overline {y})$. This and the fact that $\overline {y}_{p_{i}} > 0$ implies that $\tilde {\varphi } (\overline {y}) > 0$. By Theorem 2, $\overline {y}$ is not a vector equilibrium of $(G, \tilde {c})$. □

We notice that when $\bar y$ is a strict equilibrium, in view of Lemma 1, for $i\in I^{+}_{w}(\bar y)$, one has $\mathop { \min }\limits _{p^{\prime } \in P_{w} \backslash \{p_{i}\}} \|(\bar c_{p^{\prime }}(\overline {y} )- \bar c_{p_{i}}(\overline {y}))^{+}\| >0$, by which $\mathop { \min }\limits _{w \in W, i\in I_{w}^{+}(\overline {y})} \mathop { \min }\limits _{p^{\prime } \in P_{w} \backslash \{p_{i}\}} \|(\bar c_{p^{\prime }}(\overline {y} )- \bar c_{p_{i}}(\overline {y}))^{+}\| >0$ as we expected for $r(\bar y)$. When $\bar y$ is an equilibrium, one may have $\mathop { \min }\limits _{p^{\prime } \in P_{w} \backslash \{p_{i}\}} \|(\bar c_{p^{\prime }}(\overline {y} )- \bar c_{p_{i}}(\overline {y}))^{+}\| = 0$ for some $i\in I^{+}_{w}(\bar y)$, in which case $r(\bar y)= 0$ and $\bar y$ is not a strict equilibrium.

4 Computing Strict Equilibria

In this section, we propose an algorithm to generate a set of strict equilibrium flows together with their radius of robustness. Actually, we first apply the algorithm of [14] to generate a subset of vector equilibrium flows and then identify the elements of this set that are strict and compute their radius of robustness. We shall illustrate our algorithm by some numerical examples.

4.1 Description of the Algorithm

Assume that W consists of r elements $w_{1},{\dots } , w_{r}$ in the network and for each pair w_i there are $\vert P_{w_{i}}\vert$ paths connecting its origin to its destination. We denote $I_{j} =\{ i\in \{1,{\dots } , m\}: p_{i}\in P_{w_{j}} \}$. We denote also ${E}^{\epsilon }_{q}$ the set of 𝜖 −equilibria, E_q the set of vector equilibria when 𝜖 = 0, $S \times R = \{(\overline {y}, r(\overline {y})) : \overline {y} \text { is a strict equilibrium and } r(\overline {y})\text { is radius of robustness corresponding to } \overline {y}\}$.

Part 1

(Algorithm of [14] generating a subset of vector equilibrium flows)

Step 0

(Initialization) Choose a positive integer q and a tolerance level $\epsilon \geqq 0$.

Step 1

Set $\delta _{j}= d_{w_{j}} / (q \vert P_{w_{j}}\vert ), j = 1,{\dots } , r$.

Step 2

Choose $(k_{1},{\dots } , k_{m})^{T}\in \mathbb {N}^{m}$ satisfying

$$\sum\limits_{i\in I_{j}} k_{i} = q\vert P_{w_{j}}\vert, ~ j = 1,{\dots} , r. $$

Step 3

Store $y=(y_{1},{\dots } , y_{m})^{T}$ in S⁰, where

$$y_{i}= k_{i} \delta_{j} \text{ for } i\in I_{j}, j = 1,{\dots} , r $$

and return to Step 2 for other vectors $(k_{1},{\dots } , k_{m})$ unless no one is left.

Step 4

Choose a feasible flow y⁰ from S⁰ to start. Set k = 0, u^k− 1 = y^k, $\alpha _{k-1}= \infty$, S⁰ = S⁰ ∖{y⁰} and $E^{\epsilon }_{q}=\emptyset$.

Step 5

Compute $J_{i}(y^{k})=\{ {i^{\prime }}\in \{1,\dots ,m\}: p_{i^{\prime }}\in P_{w(i)}, ~ c_{p_{i}}(y^{k})-c_{p_{i^{\prime }}}(y^{k}) \geqq 0\}$ for every $i\in \{1,\dots , m\}$. Set

$$\psi_{k}(y):= \sum\limits_{i = 1}^{m} {y_{p_{i}}} \sum\limits_{i^{\prime}\in J_{i}(y^{k})} \langle c_{p_{i}}(y) - c_{p_{i^{\prime}}}(y), e\rangle. $$

Compute ψ_k(y^k).

If $\psi _{k}(y^{k}) \leqq \epsilon$, store y^k in $E^{\epsilon }_{q}$ and return to Step 4 until no element of S⁰ is left.

Otherwise, go to the next step.

Step 6

If $\vert \psi _{k}(y^{k} ) -\alpha _{k-1} \vert \leqq \epsilon$, go to Step 4 to choose another feasible solution from S⁰ to restart the procedure.

If ψ_k(y^k) < α_k− 1 − 𝜖, set α_k = ψ_k(y^k) and go to Step 7.

If ψ_k(y^k) > α_k− 1 + 𝜖, replace y^k = y^k− 1 + (y^k − y^k− 1)/2 and return to Step 5.

Step 7

Compute ∇ψ_k(y^k). Solve (P_k)

$$\begin{array}{@{}rcl@{}} \text{minimize } && u^{T}\nabla \psi_{k}(y^{k})\\ \text{subject to } && u\in K \\ && \vert u_{i} -{y^{0}_{i}}\vert \leqq \delta_{w(i)}, ~i = 1,\dots,m. \end{array} $$

Let u^k be an optimal solution.

If $\vert \psi _{k}(y^{k}) - \psi _{k}(u^{k})\vert \leqq \epsilon$, go to Step 4 to choose another feasible solution from S⁰ to restart the procedure until no element of S⁰ is left.

Otherwise, set y^k+ 1 = u^k. Update k = k + 1 and return to Step 5.

Part 2

(Identifying strict equilibria and computing their radius of robustness)

Step 8

Choose a vector equilibrium $\overline {y}^{1}$ from E_q to start. Set k = 1, S = ∅ and R = ∅.

Step 9

Determine $I_{w}(\overline {y}^{k})$.

Calculate

$$\rho(\overline {y}^{k}) = \sum\limits_{p\in P_{w}, w \in W} \overline {y}^{k}_{p} \sum\limits_{i\in I_{w}(\overline {y}^{k}), p_{i} \ne p}\chi_{\{0\}} (\|c_{p}(\overline {y}^{k}) - c_{p_{i}}(\overline {y}^{k})\|). $$

If $\rho (\overline {y}^{k}) \ne 0$, then return to Step 1 and choose another vector equilibrium from E_q to restart the algorithm until no element of E_q is left. If $\rho (\overline {y}^{k}) = 0$, then determine $I_{w}^{+}(\overline {y}^{k})$ and calculate

$$r (\overline{y}^{k}) = \frac {\sqrt{l}}{2} \mathop {\min}\limits_{w \in W, i\in I_{w}^{+}(\overline{y}^{k})} \mathop {\min}\limits_{p^{\prime} \in P_{w} \backslash \{p_{i}\}} \|(c_{p^{\prime}}(\overline{Y}^{k} )- c_{p_{i}}(\overline{Y}^{k}))^{+}\|. $$

Store $(\overline {y}^{k}, r (\overline {y}^{k}))$ in S × R and go to Step 8 until no element of E_q is left.

Observe that in Step 9, if $\rho (\overline {y}^{k}) = 0$, then, in view of Corollary 1, the current equilibrium flow $\overline {y}^{k}$ is strict and its radius of robustness is given by the formula of Theorem 2. Moreover, according to [14, Theorem 5.1] the upper limit of the sets E_q (the set of all possible accumulation points) when q tends to $+\infty$, contains all equilibria of the network. Therefore, the upper limit of the sets obtained from Part 2 of our algorithm contains all strict equilibria.

4.2 Numerical Examples

In this subsection, we give some numerical examples to illustrate our algorithm. Using the MATLAB optimization toolbox, we compute a representative set of strict vector equilibria for a network with either linear or nonlinear vector cost functions. We know that if the cost functions are continuous, then the network has equilibrium flows, but it may have no strict equilibrium as it was shown in [14]. In Examples 4 and 6 with nonlinear cost functions, every equilibrium obtained by our algorithm is strict. In Example 5, the network has some strict equilibria and some equilibria that are not strict as well.

Example 4

Consider a network problem with one pair of origin-destination nodes $w = (x, x^{\prime })$, two criteria: travel time and travel cost, 5 available paths: $P_{w} =\{p_{1}, p_{2}, \dots , p_{5} \}$ with the travel demand d_w = 500. Assume that

$$\begin{array}{lllllll}\displaystyle &c_{1,1}(y) &= & {y_{1}^{3}} + {y_{2}^{2}} + {y_{5}^{3}}, \quad\quad& c_{4,1}(y) &= & 8{y_{1}^{2}} + y_{2} + {y_{4}^{3}},\\ &c_{1,2}(y) &= & 2 y_{1} + y_{2}y_{3}+ 15y_{5},\quad\quad& c_{4,2}(y) &= & 5y_{1} + 3y_{4} + 3 {y_{5}^{2}},\\ &c_{2,1}(y) &= & {y_{1}^{3}} + {y_{2}^{2}} + {y_{3}^{2}}, \quad\quad & c_{5,1}(y) &= & 8y_{3}y_{4} + {y_{5}^{2}},\\ &c_{2,2}(y) &= & 5y_{2} + 3y_{3}+ 12y_{4}, \quad\quad &c_{5,2}(y) &= & 10{y_{2}^{3}} + y_{5} . \\ &c_{3,1}(y) &= & y_{1} + y_{2} + {y_{3}^{3}}, &&&\\ & c_{3,2}(y) &= & 10y_{2} + y_{3}+ 2 y_{5}, &&& \end{array} $$

With q = 1 we have 126 initial points. After 52.06344 seconds we obtained 9 vector equilibria which are all strict equilibria. The obtained strict vector equilibria and radius of robustness are given in the table below.

Strict vector equilibria	Radius of robustness
(0,100,100,300,0)T	141.4
(50,300,50,150,0)T	282.8
(50,200,150,75,25)T	0
(0,200,100,200,0)T	1060.7
(28.1259,246.8740,53.1259,171.8742,0)T	660.7
(0,300,50,150,0)T	282.8
(0,300,89.812,110.188,0)T	1.3
(100,50,200,150,0)T	176.8
(0,300,50,150,0)T	282.8

Example 5

Consider a network problem with one pair of origin-destination nodes $w = (x, x^{\prime })$, two criteria: travel time and travel cost, four available paths: P_w = {p₁, p₂, p₃, p₄} with the travel demand d_w = 200. Assume that

$$\begin{array}{lllllll} &c_{1,1}(y) &= & 2y_{1} + {y_{4}^{2}}, \quad\quad &c_{3,1}(y) &= & 200-y_{1} -y_{2}+y_{2}y_{3}, \\ &c_{1,2}(y) &= & y_{1} + y_{2} + y_{3} + 5{y_{4}^{2}}, \quad\quad &c_{3,2}(y) &= & 200+ y_{2}(y_{2}-1)+y_{3}({y_{3}^{2}}-1),\\ &c_{2,1}(y) &= & y_{2}y_{3}+ y_{3} + y_{4}, \quad\quad &c_{4,1}(y) &= & {y_{4}^{2}} + 450,\\ &c_{2,2}(y) &= & y_{1} +{y_{2}^{2}}+{y_{3}^{3}}+y(4,1), \quad\quad &c_{4,2}(y) &= &5{y_{4}^{2}}. \end{array} $$

With q = 1, we have 35 initial points. After about 4.5 s, we obtained 2 strict equilibria among 16 vector equilibria. The numerical results are given in the tables below.

Strict vector equilibria	Radius of robustness
(0,0,50,150)T	0.201 × 10− 13
(0,150,0,50)T	0.0502 × 10− 13

Vector equilibria	ρ	Vector equilibria	ρ	Vector equilibria	ρ
(0,0,50,150)T	50	(100,0,100,0)T	100	(50,0,50,100)T	50
(0,0,100,100)T	100	(50,150,0,0)T	150	(150,50,0,0)T	50
(0,0,150,50)T	150	(100,0,50,50)T	50	(0,150,0,50)T	150
(0,50,50,100)T	100	(100,100,0,0)T	100	(50,50,50,50)T	100
(50,0,100,50)T	100	(150,0,50,0)T	50

Example 6

Consider a network problem given in Fig. 1 with two pairs of origin-destination nodes w₁ = (x₂, x₁) and w₂ = (x₂, x₃), two criteria: travel time and travel cost, three available paths: $P_{w_{1}} =\{p_{1}, p_{2}, p_{3} \}$ between x₂ and x₁, five available paths: $P_{w_{2}} =\{p_{4}, p_{5}, \dots , p_{8} \}$ between x₂ and x₃ with the travel demands $d_{w_{1}}= 200; d_{w_{2}} = 300$. Assume that for the first O/D pair the cost functions are as below

$$\begin{array}{lllllll} &c_{1,1}(y) &= & {y_{1}^{2}} + {y_{2}^{2}} + {y_{3}^{3}}, \quad\quad &c_{2,2}(y) &= & y_{2} + 10y_{3} + 2y_{7}+y_{8}, \\ &c_{1,2}(y) &= & 2 y_{1} + 5y_{2} + 3y_{3}+y_{4}, \quad\quad &c_{3,1}(y) &= & y_{1} + {y_{2}^{2}} + {y_{3}^{3}} + y_{5}+y_{6},\\ &c_{2,1}(y) &= & 8y_{1}y_{2} + {y_{2}^{2}} +y_{7}+y_{8},\quad\quad &c_{3,2}(y) &= & 10{y_{3}^{3}} + 2y_{5}, \end{array} $$

and for the second O/D pair the cost functions are given by

$$\begin{array}{lllllll} &c_{4,1}(y) &= & y_{1}+ y_{2}+ {y_{4}^{3}} + {y_{5}^{2}} + {y_{8}^{3}}, \quad\quad & c_{7,1}(y) &= & y_{2}+ 8{y_{4}^{2}} + y_{5} + {y_{7}^{3}}, \\ &c_{4,2}(y) &= & y_{1}+ 2 y_{4} + y_{5}y_{6}+ 15y_{8},\quad\quad & c_{7,2}(y) &= & y_{1}+ y_{2}+ 5y_{4} + 3y_{7} + 3 {y_{8}^{2}},\\ &c_{5,1}(y) &= & y_{1}+ y_{3}+{y_{4}^{3}} + {y_{5}^{2}} + {y_{6}^{2}}, \quad\quad & c_{8,1}(y) &= & y_{1}+ y_{3}+ 8y_{6}y_{7} + {y_{8}^{2}},\\ &c_{5,2}(y) &= & y_{1}+ 5 y_{3}+ 5y_{5} + 3y_{6}+ 12y_{7},\quad\quad &c_{8,2}(y) &= & y_{1}+ y_{3}+ 10{y_{5}^{3}} + y_{8}. \\ &c_{6,1}(y) &= & y_{3}+ y_{4} + y_{5} + {y_{6}^{3}}, &&&\\ &c_{6,2}(y) &= & 3y_{3}+ 10y_{5} + y_{6}+ 2 y_{8}, &&& \end{array} $$

With 1260 initial points, after about 82 s, we obtained only one vector equilibrium (0,200,0,0,180,0,0,120)^T which is also a strict equilibrium the radius of robustness with radius of robustness 1001.9804.

Fig. 1

Network problem