Introduction

In recent years multi-product multi-criteria supply demand networks have become a subject of intensive study. This is because such networks find abounding applications in several areas of applied sciences such as transport, internet communications, economics, management etc.

The idea of traffic equilibrium dates back to at least 1920 in the work of Pigou. He considered a model where there is only one origin and destination pair connected by two roads: the first one is short and narrow, the second one is wide and long. In the narrow and short road, travel time depends on the flow of vehicles on it. Meanwhile, in the wide and long road, travel time does not depend on the flow. Pigou argued that if the amount of vehicles is equal to the upper bound of capacity on the narrow road, the travel time for each driver on both roads is the same. If one of drivers diverts from the narrow road to the wide one to feel more comfortable in spite of spending the same travel time, then the drivers who remain using the narrow road will perceive a travel time reduction. The more drivers divert to the wide road, the less travel time the drivers remaining on the narrow road spend. However, in practice no driver will, altruistically, travel on a road that reduces his benefit in order to give a spontaneous situation for the network. According to Pigou's point of view, this calls for a State intervention in the form of a tax. Then we impose a tax on the narrow road, some vehicles will be turned away from it towards the wide road. However, all traffic participants will be indifferent with respect to the original situation, that means, the ones that still use the narrow road, despite experiencing a shorter travel time, will pay a tax that equivalent to such travel time reduction. This happens because, otherwise if the toll is greater than the time reduction the drivers would choose the wide road and, in the contrary, if the toll is smaller than the time reduction, some drivers will divert back to the narrow road. Hence, applying a toll policy on the narrow road leads to a situation in which the average cost of all participants in this network is equal; the only welfare difference between two situations with and without the tax is the amount of money collected by the tolls, which corresponds to the net gain to society.

The above mentioned model under conditions of congestions was studied by Knight in 1924 (Some fallacies in the Interpretation of Social cost-Quarterly Journal of Economics). We quote his simple and intuitively clear description of interaction between different users in the network: "Suppose that between two points there are two highways, one of which is broad enough to accommodate without crowding all the traffic which may care to use it, but is poorly graded and surfaced, while the other is a much better road but narrow and quite limited in capacity. If a large number of trucks operate between the two termini and are free to choose either of the two routes, they will tend to distribute themselves between the roads in such proportions that the cost per unit of transportation, or effective return per unit of investment, will be the same for every truck on both routes. As more trucks use the narrower and better road, congestion develops, until a certain point it becomes equally profitable to use the broader but poorer highway." This demonstrates the following principles of traffic distribution among alternative routes in equilibrium: [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF] If between an origin and a destination there are at least two routes actually traveled, the average travel cost to each user must be equal on all these routes.

(2) Since each driver attempts to choose the most convenient route, average cost on all other possible routes cannot be less than that on the route or routes traveled.

(3) The amount of traffic on the network must equal the demand for transportation which prevails.

Some twenty-eight years later, Wardrop stated two principles: the first principle is identical to the notion of equilibrium described by Knight and the second one introduces the alternative behavior postulate of the minimization of total costs in the network. However, no mathematical model was proposed by Wardrop to describe the above ideas. In 1956 Beckmann, McGuire and Winsten [START_REF] Beckmann | Studies in the Economics of Transportation[END_REF] provided optimization reformulations of the governing equilibrium conditions, under a symmetry assumption on the underlying user link cost functions. Subsequently, in a lecture of Micheal Florian in 1984, he presented the elements of the network models used in transportation planning, reviewed their structural properties and most commonly used solution methods and outlined potential applications (see [START_REF] Florian | An introduction to network models used in transportation plannings[END_REF] for details). We notice that all these equilibrium models are based on scalar cost, which are not appropriate to describe real-world situations. Indeed, in practice the choice of paths by road users depends on several factors including for instance travel time, travel cost, comfort, safety and many others.

Multicriteria traffic network models, as a class of traffic network equilibrium problems, were first introduced by Quandt [START_REF] Quandt | A probabilistic abstract mode model[END_REF] and Schneider [START_REF] Schneider | Access and land developement, Urban Developement Models[END_REF] in which both travel time and travel cost were explicitly considered. Further contributions are due to [START_REF] Dafermos | A multicrieria route-mode choice traffic equilibrium model[END_REF][START_REF] Dial | A model and algorithms for multicriteria route-mode choice[END_REF][START_REF] Leurent | Multicriteria assigment modeling: Making explicit the determinants of mode or path choice[END_REF][START_REF]Equilibrium and advanced transportation modelling[END_REF][START_REF] Nagurney | Network Economics, A Variational Inequality Approach[END_REF][START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] and [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model with elastic demand[END_REF]. In these works Wardrop's traffic principle was defined for a weighted sum of the travel time and the travel cost, and therefore the analysis was presented under the angle of singlecriterion models. Therefore, a model that takes into account different criteria is necessary to solve traffic network problems.

A vector version of Wardrop's principle was first given by Chen et Yen [START_REF] Chen | On the variational inequality model for network equilibrium[END_REF] and subsequently developed by [START_REF] Chen | Vector network equilibrium problems and nonlinear scalarization methods[END_REF][START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF][START_REF] Yang | On vector variational inequalities: application to vector equilibria[END_REF] (see also [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF][START_REF] Konnov | Vector network equilibrium problems with elastic demands[END_REF][START_REF] Li | Multiclass, two-criteria traffic network equilibrium models and vector variational inequalities[END_REF][START_REF] Oettli | Necessary and sufficient conditions of Wardrop type for vectorial traffic equilibria[END_REF][START_REF] Tan | Pareto efficiency of reliability-based traffic equilibria and risktaking behavior of travelers[END_REF][START_REF] Wang | Modelling route choice behaviour in a tolled road network with a time surplus maximisation bi-objective user equilibrium model[END_REF]) for supply-demand networks without capacity constraints. Multi-criteria networks with capacity constraints have recently been studied by [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF][START_REF] Li | A remark on a standard and linear vector network equilibrium problems with capacity constraints[END_REF][START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF][START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] and [START_REF] Raciti | Equilibrium Conditions and Vector Variational Inequalities: A Complex Relation[END_REF]. Because of the multi-dimensionality of the cost space several generalizations of Wardrop's principle have been introduced and their characterizations are given in terms of variational inequalities. There are two approaches to construct variational inequalities whose solutions may provide equilibrium flows of a multicriteria network. The first approach is based on scalarization of the vector cost functions and leads to usual (scalar) variational inequality problems. Unfortunately, except for Luc and al. [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF], all variational inequality problems in the above cited papers provide weak vector equilibrium flows only. The second approach constructs directly vector variational inclusions without converting the vector cost function to a scalar function. A major drawback of this approach as pointed out in Li and al. [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF], is the fact that not every equilibrium can be obtained by solving the associated variational inequality problem. To overcome this defect the authors of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] introduced the concept of elementary flows and derived a vector variational inequality problem over elementary flows which is equivalent to the network equilibrium problem. We notice that the concept of vector equilibrium treated in Li and al. [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF] and Luc and al. [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] engages the products individually once a pattern flow is given. Other definitions of equilibrium, which take multi-product aspects into account, have been introduced in Luc [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF]. Namely, this author considered three kinds of equilibrium: weak vector equilibrium, strong vector equilibrium and ideal vector equilibrium, and constructed equivalent vector variational inequalities over elementary flows. In the above cited works on multi-criteria models we find a number of interesting theoretical results about weak and strong vector equilibria. However, as far as we know, a difficult question of how to compute vector equilibria or solutions of the associated vector variational inequality problems was not addressed.

The purpose of this thesis is to study equilibria in multi-criteria traffic networks and develop numerical methods to find them. The thesis is structured as follows. In the first chapter we present an introduction of the thesis. Chapter 2 is of preliminary character. We recall the concept of Pareto minimal points and some notions related to set-valued maps and variational inequality problem. We introduce some scalarizing functions, in particular the so-called augmented biggest/smallest monotone functions and augmented signed distance functions, and establish some properties we shall use later. Chapter 3 describes the traffic network models to be studied in this thesis. We define equilibrium for each model and determine a relationship between them. We also give some counter examples for some existing results in the recent literature on this topic. In Chapter 4 we develop a new solution method for multi-criteria network equilibrium problems without capacity constraints. To this end we shall construct two optimization problems the solutions of which are exactly the set of equilibria of the model, and establish some important generic continuity and differentiability properties of the objective functions. Then we give the formula to calculate the gradient of the objective functions which enables us to modify Frank-Wolfe's reduced gradient method to get descent direction toward an optimal solution. We prove the convergence of the method which generates a nice representative set of equilibria. Since the objective functions of our optimization problems are not continuous, a method of smoothing them is also considered in order to see how global optimization algorithms may help. We shall also introduce the concept of robust equilibrium, establish criteria for robustness and a formula to compute the radius of robustness. In Chapter 5 we consider vector equilibrium in the multi-criteria single-product traffic network with capacity constraints. We apply the approach of Chapter 4 to obtain an algorithm for generating equilibria of this network. In the last chapter we consider strong vector equilibrium in the multi-criteria multi-product traffic network with capacity constraints. We establish conditions for existence of strong vector equilibrium. We also establish relations between equilibrium and efficient points of the value set of the cost function and with equilibrium with respect to a family of functions. Moreover we exploit particular increasing functions discussed in Chapter 2 to construct variational inequality problems, solutions of which are equilibrium flows. The final part of this chapter is devoted to an algorithm for finding equilibrium flows of a multi-criteria network with capacity constraints. Some numerical examples are given to illustrate our method and its applicability. A list of references and appendices containing the code Matlab of our algorithms follow. We close up the thesis with a summary of main results in French.

In this chapter we recall the concept of Pareto minimal points, the notions of continuity of set-valued maps and the variational inequality problem that we shall use throughout this thesis. We also propose some scalarizing functions including the augmented biggest/smallest monotone functions and the augmented signed distance functions, and establish some of their properties, which will be used to prove equivalence between vector equilibrium and scalarized equilibrium and to construct an equivalent scalar variational inequality problem for vector equilibrium. These functions will be amply employed in Chapter 6.

Pareto minimal points

In the space R n with n > 1 we distinguish the following order relations: strict inequality '<' is understood as 'componentwise strictly smaller than', and '≤' means 'componentwise smaller than or equal to' and not equal to. The binary relations '<' and '≤' are actually partial orders generated by the positive orthant R n + of the space R n . Namely, for two vectors x and y from R n , one has x ≤ y (respectively x < y) if and only if yx ∈ R n + \{0} (respectively yx ∈ intR n + ), where intR n + is the interior of R n + . The relation '≦' means either '≤' or '='.

We notice that the partial orders in R n are not complete in the sense that not every couple of vectors is comparable, and hence the usual notion of minimum or maximum does not apply. Here we recall the notation of Pareto minimal points. Definition 2.0.1 Let Q be a nonempty set in R n . A point y ∈ Q is said to be a (Pareto) minimal point of the set Q if there is no point y ′ ∈ Q such that y ′ ≦ y and y ′ = y. And it is said to be a Pareto weakly minimal point if there is no y ′ ∈ Q such that y ′ < y.

The sets of minimal points and weakly minimal points of Q are respectively denoted Min(Q) and WMin(Q). They are traditionally called the efficient and weakly efficient sets or the nondominated and weakly non-dominated sets of Q. The set of maximal points Max(Q) and weakly maximal points WMax(Q) are called the efficient and weakly efficient sets of Q too. A set Q ⊂ R n is called self-minimal if it coincides with the set of its Pareto-minimal points. If a set is self-minimal, it is self-maximal and vice versa. The terminology efficiency is advantageous in certain circumstances in which we deal simultaneously with minimal points of a set as introduced and minimal elements of a family of subsets which are defined to be minimal with respect to inclusion. In some situations one is interested in an ideal minimal point or utopia point which is defined as follows: If the infimum of Q, denoted by Inf(Q), which is the vector whose ith component is the infimum of the projection of Q on the ith axis, is finite and belongs to the set Q, it is called the ideal minimal element of Q. In the other words, a point y ∈ Q is called ideal minimal point if it satisfies y ≦ y ′ for all y ′ ∈ Q. Such a point is generally not attainable, and if exists it is unique and denoted IMin(Q).

Geometrically, a point y of Q is an efficient (minimal) point if the intersection of the set Q with the negative orthant shifted at y consists of y only, that is

Q ∩ (y -R n + ) = {y}
and it is weakly minimal if the intersection of Q with the interior of the negative orthant shifted at y is empty, that is Q ∩ (y -intR n + ) = ∅. Of course, minimal points are weakly minimal, and the converse is not true in general. We refer to [START_REF] Ehrgott | Multicriteria Optimization[END_REF][START_REF] Luc | Theory of Vector Optimisation[END_REF] for more details of the theory of Pareto optimality.

Set-valued maps

Let X and Y be metric spaces and F : X ⇒ Y be a set-valued map. The domain of F is the set dom(F ) := {x ∈ X|F (x) = ∅}, and the graph of F is the subset of the product space X × Y defined by

Graph(F ) := {(x, y) ∈ X × Y |y ∈ F (x)}.
We recall some definitions of continuity of set-valued maps.

Definition 2.0.2 The map F is called upper semi-continuous at x ∈ dom(F ) if for any neighborhood U of F (x), there exists η > 0 such that

F (x ′ ) ⊂ U ∀x ′ ∈ B X (x, η),
where B X (x, η) is the ball of radius η, centered at x. It is said to be upper semi-continuous if it is upper semi-continuous at any point of dom(F ).

The map F is called lower semi-continuous at x ∈ dom(F ) if for any y ∈ F (x) and for any sequence of elements x n ∈ dom(F ) converging to x, there exists a sequence of elements y n ∈ F (x n ) converging to y. It is said to be lower semi-continuous if it is lower semi-continuous at every point x of dom(F ).

When F is both upper semi-continuous and lower semi-continuous at x, we say that it is continuous at x, and it is continuous if it is so at every point of dom(F ).

We note that when F is single valued, upper semi-continuity and lower semi-continuity signify continuity. Moreover, the following equivalent definition of lower semi-continuity is also in use: for any open subset U ⊂ Y such that U ∩ F (x) = ∅, there exists η > 0 such that F (x ′ ) ∩ U = ∅ for every x ′ ∈ B X (x, η). We shall use the following results in [START_REF] Aubin | Set-valued Analysis[END_REF] (Proposition 1.4.8, Theorem 1.4.13 and Theorem 1.4.16 respectively).

Proposition 2.0.3 Let X, Y be metric spaces. The graph of an upper semi-continuous setvalued map F : X ⇒ Y with closed domain and closed values is closed. The converse is true if we assume that Y is compact. Theorem 2.0.4 (Generic Continuity) Let F be a set valued-map from a complete metric space X to a complete separable metric space Y . i) If F is upper semi-continuous, it is continuous on a countable intersection of dense open subsets A n ⊂ X. ii) If F is lower semi-continuous with compact values, it is continuous on a countable intersection of dense open subsets A n ⊂ X. iii) If F is upper semi-continuous with closed values, then there exists a countable intersection R of dense open subsets A n ⊂ X such that ∀x ∈ R, limsup

x ′ →x F (x ′ ) = F (x).
Theorem 2.0.5 (Maximum Theorem) Let metric spaces X, Y , a set valued-map F : X ⇒ Y and a function f : Graph(F ) → R be given. If f and F are lower semi-continuous (respectively upper semi-continuous), the function g : X → R ∪ {+∞} defined by

g(x) := sup y∈F (x) f (x, y)
is also lower semi-continuous (respectively upper semi-continuous).

Variational inequality problem

Let K be a closed convex set in R m and F a continuous function from K to R n . The finitedimensional variational inequality problem, denoted VI(F, K), is to determine a vector

x * ∈ K ⊆ R n , such that F (x * ) T , x -x * ≧ 0, ∀x ∈ K
where ., . denotes the inner product in the n-dimensional Euclidean space R n . The following existence result is known.

Theorem 2.0.6 (Existence under compactness and continuity) If K is a compact convex set and F is continuous from K to R n , then the variational inequality problem admits at least one solution x * .

Proof. Let P K be a projection onto the set K. Since P K and (I -γF ) are each continuous, P K (I -γF ) is also continuous. According to Brouwer's Fixed Point Theorem there is at least one x * ∈ K such that x * = P K (I -γF )(x * ). Then

x * T , x -x * ≧ (x * -γF (x * )) T , x -x * ∀x ∈ K,
and therefore,

F (x * ) T , y -x * ≧ 0 ∀y ∈ K.
For the convergence of numerical algorithms a monotonicity property of F is needed.

Definition 2.0.7 F is monotone on K if (F (x 1 ) -F (x 2 )) T , x 1 -x 2 ≧ 0, ∀x 1 , x 2 ∈ K
and it is strictly monotone on K if

(F (x 1 ) -F (x 2 )) T , x 1 -x 2 > 0, ∀x 1 , x 2 ∈ K, x 1 = x 2 .
Under the strict monotonicity the problem VI(F,K) admits at most one solution.

Theorem 2.0.8 (Uniqueness) Suppose that F is strictly monotone on K, then the solution is unique, if one exists.

Proof. Suppose that x 1 and x * are both solutions and x 1 = x * . Then since both x 1 and x * are solutions, they must satisfy

F (x 1 ) T , x ′ -x 1 ≧ 0, ∀x ′ ∈ K, (2.1)
F (x * ) T , x ′ -x * ≧ 0, ∀x ′ ∈ K. (2.2)
After substituting x * for x ′ in (2.1) and x 1 for x ′ in (2.2), and adding the resulting inequalities, one obtains:

F (x 1 ) -F (x * )) T , x * -x 1 ≧ 0. (2.3) But inequality (2.
3) is in contradiction to the definition of strict monotonicity. Hence,

x 1 = x * .
Details on this subject are found in [START_REF] Nagurney | Network Economics, A Variational Inequality Approach[END_REF].

Increasing functions

Functions that are increasing with respect to the partial orders in R n play an important role in the study of vector optimization problems.

Definition 2.0.9 Let P be a nonempty subset of R n . A real function f : P → R is said to be increasing (respectively weakly increasing) if for every a, b ∈ P ,

a ≥ b (respectively a > b) ⇒ f (a) > f (b). (2.4)
Notice that an increasing function is weakly increasing, but the converse is not true. It is clear that the set of increasing (respectively weakly increasing) functions is a convex cone without apex. In particular, the sum of two increasing functions is increasing and the sum of two weakly increasing functions is weakly increasing. Notice further that the sum of a weakly increasing function and an increasing function is weakly increasing, but not necessarily increasing (see Example 2.0.10 below).

Example 2.0.10 Consider the function g : R 2 + → R defined by

g(x) =            x 1 + x 2 + 2 , (x 1 , x 2 ) > (0, 0); 1 x 1 + 1 , x 1 > 0, x 2 = 0; 1 x 2 + 1 , x 1 = 0, x 2 > 0.
Then the function g is weakly increasing, but not continuous on R 2 + . It is not difficult to see that f + g is not necessarily increasing for any increasing function f on R 2 + . Here is an exception in which the sum of an increasing function and a weakly increasing function is increasing.

Lemma 2.0.11 If g is a continuous, weakly increasing function and f is an increasing function on P , then the sum function f + g is increasing on P . Consequently, every continuous, weakly increasing function is a pointwise limit of a sequence of increasing functions.

Proof. Let a, b ∈ P and a ≥ b. Let e be a strictly positive vector. We have a + te > b for every real number t > 0. Since g is weakly increasing, g(a + te) > g(b) for every t > 0. Due to the continuity of g, we deduce g(a) ≧ g(b). This together with the monotonicity of f implies, consequently, (f + g)(a) = f (a) + g(a) > f (b) + g(b) = (f + g)(b) proving that f + g is increasing. Now given a continuous, weakly increasing function g, we choose any increasing function f (for instance f (x) = x 1 + ... + x n for x = (x 1 , ..., x n ) ∈ R n ) and put f k = g + f /k. Then for every x ∈ R n , we have g(x) = lim k→∞ f k (x) with f k increasing. Thus, g is the pointwise limit of the sequence of f k , k ≧ 1. Now we present some weakly increasing and increasing functions frequently used in vector optimization (see [START_REF] Gert | Nonconvex separation theorems and some applications in vector optimization[END_REF][START_REF] Hiriart-Urruty | New concepts in non-differentiable programming[END_REF][START_REF] Luc | Theory of Vector Optimisation[END_REF][START_REF] Pascoletti | Scalarizing vector optimisation problems[END_REF]) which we shall use in our thesis.

Biggest and smallest weakly increasing functions. Let e the vector of ones in R n + and a = (a 1 , ..., a n ) ∈ R n . For every x ∈ R n define

g a (x) = max{t : x ∈ a + te + R n + } = min i=1, ..., n (x i -a i ).
We are also interested in a counter part of this function when using -R n

+ instead of R n + : G a (x) = min{t : x ∈ a + te -R n + } = max i=1, ..., n (x i -a i ).
These two functions are both continuous weakly increasing, but not increasing. They are called respectively biggest and smallest continuous weakly increasing functions because of the following property: For every continuous weakly increasing function g on R n with g(a) = 0, one has

{x ∈ R n : G a (x) < 0} ⊆ {x ∈ R n : g(x) < 0} ⊆ {x ∈ R n : g a (x) < 0},
that is the strict level set at 0 of G a is the smallest and the strict level set of g a is the biggest among the strict level sets at 0 of continuous weakly increasing functions taking the zero value at a.

Signed distance functions.

Let A be a nonempty set in R n . The signed distance function (see [START_REF] Hiriart-Urruty | New concepts in non-differentiable programming[END_REF]) ∆ A is defined by

∆ A (x) = ρ(x, A) -ρ(x, A c ),
where ρ(x, A) is the distance from x to A, and A c is the complement of A. In other words,

∆ A (x) = -ρ(x, A c ) if x ∈ A; ρ(x, A) if x ∈ A c .
The particular case of this function when A is either the negative or the positive orthant of the space, is frequently used in vector optimization. Namely, let a ∈ R n be given. Define

d a (x) = ∆ (R n + ) C (x -a) and D a (x) = ∆ -R n + (x -a). Then d a (x) ≦ g a (x) ≦ G a (x) ≦ D a (x).
We notice that d a (.) and D a (.) are continuous weakly increasing functions on R n with d a (a) = 0 and D a (a) = 0. The following inclusions are clear

{x ∈ R n : G a (x) < 0} = {x ∈ R n : D a (x) < 0} ⊆ {x ∈ R n : g a (x) < 0}, and {x ∈ R n : G a (x) < 0} ⊆ {x ∈ R n : d a (x) < 0} = {x ∈ R n : g a (x) < 0}.
Let us characterize the partial order '>' by weakly increasing functions.

Lemma 2.0.12 Let a and b be two vectors in R n . The following assertions are equivalent.

(i) a > b; (ii)D u (a) > D u (b) for every u ∈ R n ; (iii) d u (a) > d u (b) for every u ∈ R n ; (iv) 0 > D a (b); (v) 0 < d b (a).
The above assertions are also true if we replace D by G and d by g.

Proof. We prove equivalence between (i) and (iv). The others equivalences are proven similarly. If a > b, then 0 > D a (b) since because the function D a is weakly increasing and D a (a) = 0. For the converse,

D a (b) < 0 implies that b -a ∈ -R n + and ρ(b -a, (-R n + ) C ) = 0, which means that a > b.
For the functions G and g, the proof is similar.

Let us characterize the partial order '≥' by weakly increasing functions, but in a more complicated way.

Lemma 2.0.13 Let a and b be two vectors in R n . The following assertions are equivalent.

(i) a ≥ b; (ii)D u (a) ≥ D u (b) for every u ∈ R n and a = b; (iii) d u (a) ≥ d u (b) for every u ∈ R n and a = b; (iv) D b (a) > 0 ≥ D a (b); (v) d b (a) ≥ 0 > d a (b).
The above assertions are also true if we replace D by G and d by g.

Proof.

As in Lemma 2.0.12 we establish equivalence between (i) and (iv

). If a ≥ b, then b -a ∈ -R n + , which implies that D a (b) = -ρ(b -a, (-R n + ) C ) ≤ 0 and D b (a) = ρ(a -b, -R n + ) > 0.
For the converse, we observe that D a (b) ≤ 0 implies that either b ≤ a or a = b, while D b (a) > 0 implies a = b. By this a ≥ b. For the functions G and g, the proof is similar. Now we will make use of the following "small" affine increasing function in which ǫ is a strictly positive number:

f ǫ a (x) = ε n i=1 (x i -a i )
and apply Lemma 2.0.11 to obtain the following increasing functions which are called respectively augmented biggest/smallest functions and augmented signed distance functions:

g ǫ a (x) = g a (x) + f ǫ a (x) G ǫ a (x) = G a (x) + f ǫ a (x) d ǫ a (x) = d a (x) + f ǫ a (x) D ǫ a (x) = D a (x) + f ǫ a (x)
which pointwisely converge respectively to g a (x), G a (x), d a (x) and D a (x) as ǫ tends to 0. The function G a was used in [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF][START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF] and some others to find weak vector equilibrium. Like g a , d a and D a , it is weakly increasing but not increasing, hence is not suitable for finding strong vector equilibrium. The function g ǫ a was already known, see for instance [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF][START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF]. To our knowledge the functions d ǫ a , G ǫ a and D ǫ a are given here for the first time. As we will see, they have very nice properties that make them crucial in finding strong vector equilibrium. They may also be very useful in the study of multi-criteria decision making and vector optimization, particularly in generating the efficient solution set of a vector problem and in establishing its structure by scalarization. Below are some properties of these functions for our use.

(a i -b i ) ≦ 0 or n i=1 (a i -b i ) > 0.
In the first case,

d ǫ b (a) := -ρ a -b, R n + + ε n i=1 (a i -b i ) ≦ 0 for every ǫ > 0 because a -b ∈ R n + . In the last case, set ǫ(a, b) = ρ a -b, R n + n i=1 (a i -b i ) > 0. Then, for 0 < ǫ < ǫ(a, b), we have d ǫ a (b) = -ρ a -b, R n + + ε n i=1 (a i -b i ) < 0.
The second assertion is obtained from the first assertion by using the proof above. For g ǫ b (.), the proof is similar.

We note that the assertion (ii) of Lemma 2.0.14 is a modified version of the negation of (i). The first assertion applied to g ǫ b (.) is a correction of Lemma 4.8 of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] (the proof given there is correct) and consequently Corollary 4.9 of that paper must be reformulated in a similar manner.

b. If a ≦ b, then D ǫ a (b) ≧ 0 for every ǫ > 0 because D ǫ a is increasing. If a ≦ b, then either n i=1 (b i -a i ) ≧ 0 or n i=1 (b i -a i ) < 0.
In the first case,

D ǫ a (b) := ρ b -a, -R n + + ε n i=1 (b i -a i ) > 0 for every ǫ > 0 because b -a ∈ -R n + . In the last case, set ǫ(a, b) = -ρ b -a, -R n + n i=1 (b i -a i ) > 0. Then, for 0 < ǫ < ǫ(a, b), we have D ǫ a (b) = ρ b -a, -R n + + ε n i=1 (b i -a i ) > 0.
The second assertion is obtained from the first assertion and from the proof above. Now we prove the last assertion. By definition,

D ǫ a (b) = ρ(b -a, -R n + ) -ρ(b -a, (-R n + ) C ) + ε n i=1 (b i -a i ),
and

D ǫ b (a) = ρ(a -b, -R n + ) -ρ(a -b, (-R n + ) C ) + ε n i=1 (a i -b i ).
Then

D ǫ a (b) + D ǫ b (a) = ρ(b -a, -R n + ) + ρ(a -b, -R n + ) -ρ(b -a, (-R n + ) C ) + ρ(a -b, (-R n + ) C ) . If a = b, then D ǫ a (b)+D ǫ b (a) = 0. If b-a ≤ 0, then a-b ∈ (-R n + ) C , and hence D ǫ a (b)+D ǫ b (a) = ρ(a -b, -R n + ) -ρ(b -a, (-R n + ) C ) = a -b -ρ(b -a, (-R n + ) C ) ≧ a -b -b -a ≧ 0. If b -a 0, then D ǫ a (b) + D ǫ b (a) = ρ(b -a, -R n + ) + ρ(a -b, -R n + ) -ρ(a -b, (-R n + ) C ) ≧ 0. For G ǫ a (.
), the proof is similar.

Note that some other interesting properties of the augmented signed functions such as Lipschitz continuity, quasi-convexity etc. can also be established, but we do not give them in details here because they will not directly be used in the present work.

In this chapter we focus on scalar equilibrium and concepts of vector equilibrium in the existing literature and establish some relationships between them. We point out some misunderstandings and inadequacies of certain results in recent works on vector equilibrium.

Single-criterion Traffic Network

Wardrop's model

Consider a traffic network where there is an origin-destination (O/D for short) pair w connected by m alternative routes named p 1 , p 2 , ..., p m . We denote the set of these paths by P . Let Y = (y pi ) pi∈P denote a flow of traffic where y pi is the quantity of drivers following the route p i . Suppose that there are d w drivers transporting on the O/D pair w. Then we say that a flow Y is feasible if it satisfies the following conditions:

y pi ≥ 0, p i ∈ P and pi∈P y pi = d w .
In this model, drivers only pay attention to travel time. The distribution in the network is based on the following two principles:

1) The travel time on all routes actually used is equal, and less than those which would be experienced by a single vehicle on any unused route. 2) The average travel time is minimum.

The first principle is quite a likely one in practice, since it might be assumed that traffic will tend to settle down into an equilibrium situation in which no driver will want to choose an alternate route. In this case, we will say the system is at a user equilibrium state. This principle has been considered as a sound and simple behavioral principle to describe the spreading of traffics over alternate routes due to congested conditions. On the other hand, the second principle is the most efficient in the sense that it minimizes the vehicle-hours spent on the network, when this goal is achieved we will say that the system is at a social optimum state.

Beckmann, McGuire and Winsten's model

Although Wardrop discussed the equilibrium conditions for a general network, he did not propose any method to compute the corresponding flows. Soon after, the first mathematical model of traffic equilibrium on a network was formulated and analyzed by Beckmann, [START_REF] Beckmann | Studies in the Economics of Transportation[END_REF], which was the starting point for the contributions to follow this area. Their model was described as follows: Let xx ′ be a road on the network and y xx ′ be the number of vehicles entering road xx ′ from either end per unit of time, briefly called the flow on that road. However, the elementary variable will be the flow on a road in a given direction to a particular destination, written y xx ′ ,k , where the order pair of subscripts xx ′ denotes the direction from x to x ′ on road xx ′ , and k denotes the destination. This flow is distinct from that in the opposite direction and it does not admit of negative values:

McGuire and Winsten

y xx ′ ,k ≧ 0, for all xx ′ , k.
The total flow on a road equals

y xx ′ = y x ′ x = k (y xx ′ ,k + y x ′ x,k ), (3.1)
and of course

y xx ′ ≧ 0.
The number of vehicles originating at location x with destination k per unit of time is denoted by y x,k . Since this rate of origination is indicated at x by the excess of the flow to k on outgoing roads over that on incoming roads we have

y x,k = x ′ (y xx ′ ,k -y x ′ x,k ). (3.2)
The transportation cost c on road xx ′ is denoted c xx ′ . Since we do not distinguish between costs in the two directions, we have c xx ′ = c x ′ x . For points x and x ′ that are not contiguous, c xx ′ is left undefined. Travel costs from origin x to destination k are denoted by c x,k (notice that the subscripts are separated by a comma). Now

c x,k = min(c xx1 + c x1x2 + c x2x3 + ... + c xnk ),
that is, the minimum of all chain sums of c xixj starting at x and terminating at k in which consecutive elements have one subscript in common. In particular c x,x = 0. Consider c r,k for two locations r = x and r = x ′ connected by a road xx ′ . Extending the minimum chain that leads from x ′ to k by adding c xx ′ , we have a chain from x to k, but not necessarily a minimum chain. Thus

c x,k ≦ c xx ′ + c x ′ ,k .
Then equilibrium flow is determined by

c x,k -c x ′ ,k ≦ c xx ′ if y xx ′ ,k = 0; = c xx ′ if y xx ′ ,k > 0 (3.3)
that is, the quantity of drivers using the road xx ′ to a location k not in a shorted one is zero.

Michael Florian's model

Basing on the idea of Beckmann, McGuire and Winstern, in 1984, Michael Florian considered a single-product single-criterion model where the cost function on each path depends on the traffic flows of the entire network. Consider a transportation network G = [N, A, W ] in which N is a set of nodes, A = {a 1 , ..., a n } is a set of n directed arcs which represent the transportation infrastructure and W is a set of all origin-destination pairs of nodes x, x ′ ∈ N such that there is a path from x to x ′ . For a pair of nodes w = (x, x ′ ), the set of available paths from the origin x to the destination x ′ is denoted by P w , the index set I w consists of all i such that p i ∈ P w and the set of all available paths of the network is denoted by P = {p 1 , ..., p m } = w∈W P w .

Let v a denote the flow of trips on arc a ∈ A and y p denote the flow of trips on path p ∈ P , then v = (v a ) a∈A is the vector of arc flows and Y = (y p ) p∈P is the vector of path flows over the entire network. A relationship between arc flows and path flows is given by

v a = w∈W p∈Pw δ ap y p (3.4)
where

δ ap = 1 if a ∈ p 0 otherwise.
The demand on each w ∈ W is denoted by d w . The flow Y = (y p ) p∈P on the network is said to be feasible if it satisfies conservation of flow and nonnegativity p∈Pw y p = d w , w ∈ W and y p ≧ 0, p ∈ P w , w ∈ W.

(3.5)

The set of all feasible path flows is denoted by K.

One assumes that this network permits the flow of one type of traffic (vehicles or passengers) on its arcs. The cost of travelling in the arc v a is denoted by a user cost function c a (v). This cost function may model the time delay for travel on that arc, in which case it is commonly referred to as a volume/delay function, it may however model other costs, such as fuel consumption.

The cost of each path c p = c p (v) is the sum of the user costs of the arcs in the path

c p = a δ ap c a (v), p ∈ P w , w ∈ W. (3.6)
Let u w = u w (v) be the cost of the least cost path for any O/D pair w, that means

u w = min p∈Pw c p , w ∈ W. (3.7)
In this model, the demands d w depends on the vector of least cost travel times for all the O/D pairs of the network u = (u w ) w∈W and are given by function D w (u)

(0 <)d w = D w (u), w ∈ W. (3.8)
Then the flow Y ∈ K is in equilibrium if for every O/D pair w ∈ W , and every path p ∈ P w , the following condition holds

c p (Y ) = u w (Y ) if y p > 0 ≧ u w (Y ) if y p = 0, (3.9)
that is all the used directed paths are of equal cost. It is relatively straightforward to show that (3.9) may be restated in the "complementarity" form

u w (Y ) ≦ c p (Y ) and (c p (Y ) -u w (Y ))y p = 0, p ∈ P w , w ∈ W (3.10)
and that (3.9) and (3.10) are equivalent to the following statement: For every O/D pair w ∈ W , and paths p, p ′ ∈ P w , one has

c p (Y ) ≦ c p ′ (Y ) if y p > 0.
Thus, Wardrop's first principle for single-class single-criterion model was stated mathematically in several forms.

Multi-criteria Traffic Network

As introduced at the beginning, the pattern of the traffic flows through a network is the result of a subtle and complex interaction between drivers, and in practice their decision in selecting one route of travel depends on many criteria simultaneously. Therefore, it is important to extend the basic model to multi-criteria one in which vector-valued cost function is considered.

Description of multi-product multi-criteria traffic network

Let us consider a supply-demand network G = [N, A, W ] in which N is a set of nodes, A = {a 1 , ..., a n } is a set of n directed arcs and W is a set of all origin-destination pairs of nodes x, x ′ ∈ N such that there is a path from x to x ′ . For a pair of nodes w = (x, x ′ ), the set of available paths from the origin x to the destination x ′ is denoted by P w , the index set I w consists of all i such that p i ∈ P w and the set of all available paths of the network is denoted by P = {p 1 , ..., p m } = w∈W P w .

We assume that there are q different classes of products to traverse in the network. Given a path p i ∈ P , let y j pi ∈ R denote the amount of the jth class of product to transport on the path p i . The matrix Y = (y j pi ) m×q is called a path flow in the network. Thus, each row vector Y pi = (y 1 pi , ..., y q pi ) of the matrix Y represents the vector of q classes of products to traverse the path p i , while the column vector Y j = (y j p1 , ..., y j pm ) T (here (.) T denotes the transpose) represents the vector of the jth class of product to traverse m paths of the network.

To evaluate the transportation of products in the network, a cost function for the path flow Y is given in form of a matrix C(Y ) = (c j pi (Y )) with vector entries

c j pi (Y ) = (c j pi,k (Y )) ∈ R l , with l > 1. The ith row of entries C pi (Y ) = (c 1
pi (Y ), ..., c q pi (Y )) of the matrix C(Y ) represents the cost for the path p i , and the jth column C j (Y ) = (c j p1 (Y ), ..., c j pm (Y )) T represents the cost concerning the jth class of product on m paths of the network. For every origin-destination pair w ∈ W , the set C(w) consists of all vectors C pi (Y ) with p i ∈ P w .

Sometimes arc flows are also considered in association with path flows. If z j a denotes the amount of the jth product to be transported on the arc a, then the matrix Z whose entries are z j a , a ∈ A and j = 1, ..., q represents an arc flow in the network. A vector-valued cost function for the arc flow Z is given by a matrix Ĉ(Z) with entries ĉj a (Z), a ∈ A and j = 1, ..., q. It is known that given a path flow Y , an associated arc flow Z can be determined by the formula

Z = ∆Y,
where ∆ is the so-called incident matrix whose entries δ ap are given by δ ap = 1 if a belongs to path p 0 otherwise.

The cost functions of the arc flow Z and the path flow Y are then linked by the following matrix equality:

C(Y ) = ∆ T Ĉ(Z).
From now on, for a path flow Y , write C and c j pi instead of C(Y ) and c j pi (Y ) if no misunderstanding occurs. We further assume that the demand function depends on the costs for all O/D pairs, that means we can suppose directly that the demand is a function of the path flow Y . A positive demand function d j w (Y ) is given which expresses the quantity of the jth class of product to be transported from the origin x to the destination x ′ of the pair w = (x, x ′ ) ∈ W , and that the demand vector d w = (d 1 w (Y ), ..., d q w (Y )) is non null. The lower and upper capacity constraints on each class of product j and on each path p i are respectively l j pi ∈ R and u j pi ∈ R with l j pi < u j pi . For a path p i , the upper and lower capacity bound vectors (u 1 pi , ..., u q pi ) and (l 1 pi , ..., l q pi ) are respectively denoted by U pi and L pi . It is common to impose the following restrictions on the demand

pi∈Pw L pi ≦ d w ≦ pi∈Pw U pi , ∀ w ∈ W. (3.11)
Otherwise, the network would have no feasible flows. Moreover, if either of equalities holds in the above restrictions, then the network has a unique feasible path flow. Moreover if there exists j ∈ {1, ..., q} such that

d j w = pi∈Pw l j pi or d j w = pi∈Pw u j pi , ∀ w ∈ W, (3.12)
then the feasible flow of the j-th product is unique. These cases are not interesting from the mathematical point of view. Therefore, from now on we assume

pi∈Pw L pi < d w < pi∈Pw U pi , ∀ w ∈ W. (3.13)
We say that a path flow Y is feasible if it satisfies the capacity constraints and the conservation of flows equations:

l j pi ≦ y j pi ≦ u j pi ∀ i = 1, ..., m; ∀j = 1, ..., q; (3.14) pi∈Pw y j pi = d j w ∀ j = 1, ..., q; ∀w ∈ W. (3.15)
The set of all feasible flows for the flow Y is denoted by K and G = [N, A, W ] is called the network with capacity constraints. We say that a path flow Y is feasible for the flow Y if it satisfies the capacity constraints and the conservation of flows equations: l j pi ≦ y j pi ≦ u j pi ∀ p i ∈ P ; ∀j = 1, ..., q;

(3.16) pi∈Pw y j pi = d j w (Y ) ∀ j = 1, ..., q; ∀w ∈ W.

(3.17)

The set of all feasible flows for the flow Y is denoted by K(Y ) and G = [N, A, W ] is called the network with capacity constraints and elastic demand with respect to the feasible flow Y . It is clear that K(Y ) is a closed convex set for every fixed Y . We notice that for a given path flow Y , it may not satisfy demands for oneself, i.e., there exists j 0 and w 0 such that pi∈Pw y j0 pi = d j0 w0 (Y ). (3.18) When in the network, the value of d changes, the feasible set of flows/demands K(d) can be defined as follows

K(d) = {(Y, d)| pi∈Pw y j pi = d j w , l j pi ≦ y j pi ≦ u j pi , p i ∈ P w , w ∈ W, j = 1, ..., q},
then we call G = [N, A, W ] the network with capacity constraints and elastic demand. When l j pi = 0 and u j pi = ∞ for all p i and j the network is called without capacity constraints.

In the subsections 3.2.2 and 3.2.3, we wish to compare different concepts of vector equilibrium. We restrict ourselves to the case of network without capacity constraints for the sake of simplicity and compatibility with existing definitions we meet in the literature.

Single-product multi-criteria supply demand network

In this model, there is only one product to traverse in the network. Let z a denote the traffic load on arc a ∈ A and let y p denote the traffic flow on path p ∈ P . As before we have z a = p∈P y p δ ap and z = ∆y whose entries are δ ap for a ∈ A and p ∈ P .

We shall assume throughout this subsection that the demand d w of the traffic flow for each O/D pair w ∈ W is fixed. A path flow y is said to be feasible if y ≧ 0 and it satisfies the conservation flow equation p∈Pw y p = d w for all w ∈ W.

The set of all feasible path flows is denoted K. Assume further that a vector cost function ĉa is given on each arc a ∈ A, depending on the traffic arc flow z and taking values in a finite dimensional space R l with l ≧ 2. In many classical models l = 2, which corresponds to two criteria: travel time and travel cost. Then the vector cost function c p on path p depends on the path flow y and is computed by

c p (y) = a∈A ĉa (z)δ ap . (3.19)
Let C(y) denote the l × m-matrix, the columns of which are c p , p ∈ P and Ĉ(z) the l × nmatrix, the columns of which are ĉa , a ∈ A. These matrices are linked by the formula

C(y) = Ĉ(z)∆.
We recall below definitions of vector equilibrium and weak vector equilibrium corresponding with this kind of network, which have been originally proposed by Chen and Yen [START_REF] Chen | On the variational inequality model for network equilibrium[END_REF] in 1993. Definition 3.2.1 Let Ȳ be a feasible flow. We say that Ȳ is a vector equilibrium if for every w ∈ W and p α , p β ∈ P w one has implication

c pα ≥ c p β ⇒ y pα = 0.
And Ȳ is a weak vector equilibrium if for every w ∈ W and p α , p p β ∈ P w one has implication

c pα > c p β ⇒ y pα = 0.
It is clear that every vector equilibrium is weak vector equilibrium, but the converse is not true in general. These two kinds of equilibrium are natural generalizations of the Wardrop equilibrium for a scalar valued cost in which inequality c pα ≥ c p β means c pα > c p β , and therefore there is no distinction between weak vector equilibrium and vector equilibrium.

In 1999 Chen, Goh and Yang in [START_REF] Chen | Vector network equilibrium problems and nonlinear scalarization methods[END_REF] introduced G a -equilibrium, where the function G a is given in Chapter 1.

Definition 3.2.2 A feasible flow Ȳ is said to be G a -equilibrium if there exists a ∈ R l + such that for every w ∈ W, p α , p β ∈ P w , G a (c pα ) > G a (c p β ) ⇒ y pα = 0.
The authors of the above mentioned work proved the following result (Theorem 4.5).

Theorem 3.2.3 A feasible flow is weak vector equilibrium if and only if it is G a -equilibrium.

Unfortunately this theorem is not always true. Actually the "if" part is true. In fact, by assuming that the feasible flow y is G a -equilibrium. If for some p α , p β ∈ P w we have c pα > c p β , then for a ∈ R l + , G a (c pα ) > G a (c p β ) by weakly increasing property of the function G a . By hypothesis, we obtain y pα = 0. It deduces that Y is weak vector equilibrium. The "only if" part is not always true which is seen in the next counterexample. Example 3.2.4 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ) and three available paths: P w = {p 1 , p 2 , p 3 }. Assume that the travel demand for w is d w = 15, and c p1 (y) = (3y p1 + 2y p2 , y p1 + y p2 ) T c p2 (y) = (y p1 + 5y p2 , 2y p2 ) T c p3 (y) = (y p1 + y p3 , 2y p1 + y p3 ) T .

With the feasible flow y p1 = 3, y p2 = 7, y p3 = 5, we have

c p1 = (23, 10) T c p2 = (38, 6) T c p3 = (12, 11) T .
Clearly, Y is weak vector equilibrium. Nevertheless, Y is not G a -equilibrium. In fact, take any a ∈ R 2 , we obtain either

G a (c p1 ) < G a (c p2 ) or G a (c p1 ) < G a (c p3 )
and y p2 = 7 > 0, y p3 = 5 > 0.

Consequently neither Corollary 4.7 [START_REF] Chen | Vector network equilibrium problems and nonlinear scalarization methods[END_REF] which gives necessary and sufficient conditions for weak vector equilibrium, nor Theorem 3.2 and Corollary 3.1 in Chen [START_REF] Chen | On vector network equilbrium problems[END_REF] are correct. In 2006 Li, Yang and Chen [START_REF] Li | A note on vector network equilibrium principles[END_REF] proposed another kind of G a -equilibrium flow, which is called weak G a -equilibrium and established a necessary and sufficient condition of a weak vector equilibrium. Definition 3.2.5 A feasible flow Ȳ is said to be weak G a -equilibrium if for every w ∈ W, p α , p β ∈ P w one has

G cp α (c p β ) < 0 ⇒ y pα = 0.
It is clear that every G a -equilibrium is weak G a -equilibrium, but the converse is not true in general. Here is an example.

Example 3.2.6 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ) and three available paths: P w = {p 1 , p 2 , p 3 }. Assume that the travel demand for w is d w = 20, and c p1 (y) = (2y p1 , 5y p1 + 3y p2 ) T c p2 (y) = (3y p2 , y p1 + y p3 ) T c p3 (y) = (2y p2 + y p3 , 3y p3 ) T .

With the feasible flow y p1 = 3, y p2 = 10, y p3 = 7, we have

c p1 = (6, 45) T c p2 = (30, 17) T c p3 = (27, 21) T . Then G C1 (C 2 ) = max {30 -6, 17 -45} = 24, G C1 (C 3 ) = max {27 -6, 21 -45} = 21, G C2 (C 1 ) = max {6 -30, 45 -17} = 28, G C2 (C 3 ) = max {27 -30, 21 -17} = 4, G C3 (C 1 ) = max {6 -27, 45 -21} = 24, G C3 (C 2 ) = max {30 -27, 17 -21} = 3.
Therefore y is weak G a -equilibrium. Nevertheless, y is not G a -equilibrium. In fact, for any a = (a 1 , a 2 ) ∈ R 2 , we have

G a (C 1 ) = max {6 -a 1 , 45 -a 2 } , G a (C 2 ) = max {30 -a 1 , 17 -a 2 } , G a (C 3 ) = max {27 -a 1 , 21 -a 2 } . If G a (C 3 ) = 27 -a 1 , then we have G a (C 3 ) < G a (C 2 ) and y p2 = 10 = 0. If G a (C 3 ) = 21 -a 2 , then we have G a (C 3 ) < G a (C 1
) and y p1 = 3 = 0.

It turns out that weak vector equilibrium and weak G a -equilibrium are equivalent, which was proved in [START_REF] Li | A note on vector network equilibrium principles[END_REF]. Proposition 3.2.7 [START_REF] Li | A note on vector network equilibrium principles[END_REF] A flow y ∈ K is a weak vector equilibrium if and only if y ∈ K is a weak G a -equilibrium.

To go further we recall some notations.

Λ = λ = (λ 1 , ..., λ l ) T ∈ R l |λ i ≧ 0, l i=1 λ = 1 , ri(Λ) = λ = (λ 1 , ..., λ l ) T ∈ R l |λ i > 0, l i=1 λ = 1 , C w (y) = {c p (y) : p ∈ P w }, V -min(C w (y)) = c p (y) | ∄c p ′ (y) ∈ C w (y) such that c p (y) -c p ′ (y) ∈ R l + \{0} .
Goh and Yang [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF] introduced parametric equilibrium (λ-equilibrium).

Definition 3.2.8 A feasible flow Ȳ is said to be a parametric equilibrium if for every w ∈ W, p α ∈ P w and for a parametric λ ∈ Λ given, there exists c w ∈ Min(C w ) such that λ T c pα > λ T c w ⇒ y pα = 0.

They proved the following sufficient and necessary condition for a vector equilibrium.

Proposition 3.2.9 [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF] Let the following assumption hold

Min(C w ) ⊂ Min(co(C w )), where co(C w ) is the convex hull of C w , (3.20)
Then the following assertions hold: i) If a feasible flow y is a vector equilibrium and assumption 3.20 holds, then there exists λ ∈ Λ such that it is a parametric equilibrium. ii) If a feasible flow y is a parametric equilibrium for some λ ∈ ri(Λ), then it is a vector equilibrium.

Again the assertion i) does not always hold. This is seen in the next example. We notice also that Example 2.1 in [START_REF] Li | A note on vector network equilibrium principles[END_REF] fails because the assumption 3.20 in that example does not hold.

Example 3.2.10 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ) and three available paths: P w = {p 1 , p 2 , p 3 }. Assume that the travel demand for w is d w = 10, and

c 1 (Y ) = (2y 1 + 2y 2 , y 1 + 2y 2 ) T c 2 (Y ) = (y 1 + 2y 2 + y 3 , 3y 2 ) T c 3 (Y ) = (y 1 + y 2 + 2y 3 , y 3 ) T .
With the feasible flow y 1 = 3, y 2 = 2, y 3 = 5, we have

c 1 = (10, 7) T c 2 = (12, 6) T c 3 = (15, 5) T .
Clearly, Y is a vector equilibrium. Nevertheless, Y is not a parametric equlibrium. In fact, although C(w) = Min(C(w)) = {c 1 , c 2 , c 3 } and assumption 3.20 holds, for any λ ∈ Λ, we have λ T c 3 > λ T c 1 and y 3 = 5 > 0.

To obtain a complete characterization for a vector equilibrium, Li, Yang and Chen [31] introduced another parametric equilibrium, which is called "weakened parametric equilibrium". Definition 3.2.11 A feasible flow Ȳ is said to be a weakened parametric equilibrium if for every w ∈ W, p α ∈ P w and for any λ ∈ Λ, there exists c w ∈ Min(C w ) such that

λ T c pα > λ T c w ⇒ y pα = 0.
Under the assumption 3.20 they obtained a necessary condition for vector equilibrium. Proposition 3.2.12 [START_REF] Li | A note on vector network equilibrium principles[END_REF] Let y be a feasible pattern flow on the network G and assumption 3.20 holds. Then if y is a vector equilibrium, it is a weakened parametric equilibrium.

We summarize a relationship between the aforementioned concepts of equilibrium in the following diagram.

Parametric equilibrium

G a -equilibrium

Vector equilibrium Weak vector equilibrium

Weakened parametric equilibrium Weak G a -equilibrium

Multi-product single-criterion supply demand network

The multi-product single-criterion supply demand network can be explained as a network in which certain goods are produced by suppliers and need to be shipped to destination points according to given demand. The cost of transporting different products along an arc may differ.

Consider a supply demand model without capacity constraint. Let Ȳ be a feasible flow. We are interested in the following conditions which can also be considered as different types of equilibrium.

• (B1) For every w ∈ W and p α ∈ P w , Y pα ≥ 0 ⇒ C pα = Inf(C(w)), Y pα = 0 ⇒ C pα ≧ Inf(C(w)).
• (B2) For every w ∈ W and p α , p β ∈ P w ,

[(C(w) -C p β ) ∩ (-R q + ) = {0}, C pα -C p β = 0] ⇒ Y pα = 0. • (B3) For every w ∈ W and p α , p β ∈ P w , [clcone(C(w) + R q + -C p β ) ∩ (-R q + ) = {0}, C pα -C p β = 0] ⇒ Y pα = 0. • (B4) For every w ∈ W and p α , p β ∈ P w , C pα -C p β ≥ 0 ⇒ Y pα = 0. • (B5) For every w ∈ W and p α ∈ P w , C pα / ∈ Min(C(w)) ⇒ Y pα = 0.
• (B6) For every w ∈ W, p α , p β ∈ P w , and j = 1, ..., q, c j pαc j p β > 0 ⇒ y j pα = 0.

Remark 3.2.13 1) Condition (B1) has been introduced by Cheng and Wu [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF] and the pattern flow Y satisfying it is called a Wardrop equilibrium.

Notice that the second implication of (B1) is superfluous because for any path p α ∈ P w inequality C α ≧ Inf(C(w)) is always true and if there exists an equilibrium satisfying the condition (B1), that is the unique solution of the network.

2) Condition (B3) has been introduced by Wu and Cheng [START_REF] Wu | Benson efficiency of a multi-criterion network equilibrium model[END_REF]. They used it to define the so-called Benson equilibrium which is a kind of Benson proper efficient solutions of vector optimization problems.

3) Condition (B4) has been studied in [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF] for multi-criteria networks. In [START_REF] Raciti | Equilibrium Conditions and Vector Variational Inequalities: A Complex Relation[END_REF] Raciti called it a strong vector Wardrop equilibrium. 4) Cheng and Wu [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF] proved that the conditions (B1) and (B4) are equivalent. However, if the set C(w) has no ideal minimal element, the implication (B4) ⇒ (B1) may fail as it is shown in the next example. Proposition 2.1 of [START_REF] Cheng | A multiclass, multicriteria supply-demand network equilibrium model[END_REF] and Proposition 3.2 of [START_REF] Wu | Benson efficiency of a multi-criterion network equilibrium model[END_REF] are then not always available.

Example 3.2.14 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ), two products traverse the network with two available paths: P w = {p 1 , p 2 }. The other data are given as below d 1 w = 5, d 2 w = 2, and

c 1 1 (Y ) = 10y 1 1 c 1 2 (Y ) = 2y 1 2 + y 2 2 c 2 1 (Y ) = 3y 1 1 + y 2 1 c 2 2 (Y ) = y 1 2 + 10y 2 2
With the feasible flow y

1 1 = 3, y 2 1 = 1, y 1 2 = 2, y 2 2 = 1, we have C 1 (Y ) = (30, 10) C 2 (Y ) = (5, 12) Inf(C(w)) = (5, 10).
Clearly, Y is an equilibrium according to (B4) as both

C 1 ≥ C 2 and C 2 ≥ C 1 . Nevertheless, Y does not satisfy (B1) since Y 1 ≥ 0 but C 1 = Inf(C(w)).
As a matter of fact conditions (B1) and (B4) lead to different concepts of equilibrium whenever the multiplicity of products for transport in the network is present. Moreover the operation of taking closed cone in (B3) by Wu and Cheng [START_REF] Wu | Benson efficiency of a multi-criterion network equilibrium model[END_REF] is unnecessary. To see this let us recall the following result from [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] with its proof. Lemma 3.2.15 [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] Let D be a finite subset of R q and d ∈ D. Then the following relations are equivalent

(i) clcone(D + R q + -d) ∩ (-R q + ) = {0} (ii)(D -d) ∩ (-R q + ) = {0}.
Proof. The implication (i)⇒(ii) is clear because the set D-d is a subset of clcone(D+R q + -d) and the origin of the space belongs to both of them. For the converse suppose the contrary that (ii) is true, but (i) is not. There is a nonzero vector a belonging to the intersection on the left hand side of (i), say a = lim

α→∞ t α (d α -d + u α ) (3.21)
for some positive numbers t α , some vectors d α from D and u α ∈ R q + . Since D is a finite set, we may assume without loss of generality that d α = d 0 for some d 0 ∈ D. If d 0d = 0, we arrive at a contradiction that a ∈ R q + ∩ (-R q + ) and a = 0. It remains to consider the case d 0d = 0. We may also assume that the sequence {t α } α converges to some limit t among three possible values: 1) t = 0, 2) t = ∞, and 3) t ∈ (0, ∞). In the first case, a = lim α→∞ t α u α ∈ R q + , which contradicts the hypothesis. In the second case, it follows from

(3.21) that a = t α (d α -d + u α ) + o(t α ) with lim α→∞ o(t α )/t α = 0.
By dividing the latter equality by t α and passing to the limit as α tends to ∞, we obtain d 0d = lim α→∞ u α ∈ -R q + \{0} which contradicts (ii). In the case 3), a similar argument yields

d 0 -d = a t -lim α→∞ u α ∈ -R q + \{0} (3.22)
which is a contradiction too.

We remark that the conclusion of Lemma 3.2.15 remains true under a milder condition on D. For instance, when D is not finite, but the set cone(Dd) has a compact base, which means that there is a compact set B not containing the origin of the space such that cone(D-d) = cone (B), then the argument of the proof above goes through. In particular, the conclusion of Lemma 3.2.15 is true when D is a polyhedral set. Here are some relationships between (B1)-(B6). Proposition 3.2.16 [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] Given a feasible pattern flow Y on the network G. The following assertions hold:

(i) (B1) ⇔ (B2) ⇔ (B3).
Each of these conditions implies that for every w ∈ W , the set C(w) has ideal minimal elements. Moreover, under the latter condition on C(w), all conditions (B1) through (B5) are equivalent.

(ii)(B4) ⇔ (B5) (iii)(B1) ⇒ (B6).
The converse (B6) ⇒ (B1) is true provided q = 1.

Proof. We note that for every w ∈ W , the set C(w) is finite, hence in view of Lemma 3.2.15, conditions (B2) and (B3) are equivalent. To prove the first part of (i), it suffices to establish equivalence between (B1) and (B2). We assume (B1). Since for each w ∈ W the demand vector d w is non null, there must be some path p β0 on which the flow y

p β 0 is non null. Hence the cost C p β 0 is an ideal minimal element of C(w). Let p β ∈ P w satisfy (C(w) -C p β ) ∩ -R q + = {0}. Then C p β = C p β 0 = Inf(C(w))
, and C pα ≥ Inf(C(w)) for every p α ∈ P w with C pα -C p β = 0. By (B1), y pα = 0, which shows that (B2) holds. Now assume (B2). Since the set C(w) is finite, it has minimal elements. Let C p β be one of them. Then (C(w) -C p β ) ∩ -R q + = {0}. For any p α ∈ P w , if C pα is not minimal, then C pα -C p β = 0 and by (B2), the corresponding flow y pα is null. If C pα is minimal, but C pα -C p β = 0, then we also have y pα = 0 by (B2). With C pα minimal, switching the roles of C pα and C p β we obtain y p β = 0 too. Thus, if the set Min(C(w)) consists of more than two elements, the flow y is null on every path joining w, which is impossible because the demand is not null. Consequently, the set Min(C(w)) has only one value, say C * . We deduce C pα = C * for all p α ∈ P w , which shows that C * is the ideal minimal element of C(w) and (B1) follows. For the second part of (i), assume that for every w ∈ W , the set C(w) has ideal minimal elements. It suffices to prove equivalence between (B1) and (B4), because the equivalence between (B4) and (B5) will be given in (ii). Let p α , p β ∈ P w satisfy C pα -C p β ≥ 0. Then C pα is not ideal minimal. Under (B1), one has y pα = 0 and obtains (B4). Conversely, if (B4) holds and if y pα ≥ 0, then C pα must be ideal minimal, which shows that (B1) is true. Indeed, if C pα were not ideal minimal, there would exist some ideal element C p β such that C pα -C p β ≥ 0 which yields y pα = 0, a contradiction. By this, (B4) is equivalent to (B1). We proceed to (ii) by assuming (B4). Let C pα / ∈ Min(C(w)). By definition, there is some

C p β ∈ C(w) such that C pα ≥ C p β .
In view of (B4) one has y pα = 0 and (B5) follows. Conversely, if (B5) holds and if C pα -C p β ≥ 0 for some p α , p β ∈ P w , then C pα is not a minimal element of C(w) and in view of (B5) the flow y pα is null. Thus, (B4) is true and we obtain the equivalence between (B4) and (B5). Finally, suppose (B1). Strict inequality c i pα > c i ′ pα for some i, i ′ ∈ {1, ..., q} and p α ∈ P w in (B6) implies that C pα is not an ideal minimal element of c(w). By (B1), one has y pα = 0. In particular, y i pα = 0 and (B6) follows. When q = 1 inequality y pα ≥ 0 means y 1 pα > 0, and so under (B6) one has c 1 pα ≦ c 1 p β for all p β ∈ P w , that is c 1 pα = Inf(C(w)). Thus, for q = 1, conditions (B1) and (B6) are equivalent.

In multi-product networks, equilibra defined via (B4) and (B6) do not follow from each other. We can see that in the following examples: Example 3.2.17 Consider a network consisting of four nodes {N i : i = 1, ..., 4}, one origin destination pair w = (N 1 , N 4 ) and two paths p 1 and p 2 connecting w via N 2 and N 3 respectively. We assume there are two products in the network. Let a feasible pattern flow Y be given by its rows Y 1 = (20, 320) and Y 2 = (10, 500) representing the quantities of the two products to traverse the paths p 1 and p 2 respectively. Assume further that the cost matrix associated to the path flow Y has its rows

C 1 = (2, 16) and C 2 = (1, 25). Then (B4) holds, but not (B6) because C 1 1 = 2 > 1 = C 1 2 with y 1 p1 = 20 = 0.

Multi-product multi-criteria supply demand network

In this subsection we study a multi-product multi-criteria supply demand network which is one of the topics of our attention. In the definition below inequality of matrices is understood as vector inequality in the space R l×q , and the negation of strict inequality Y pα > L pα means there is at least one component of Y pα less than or equal to the corresponding component of L pα .

Let Ȳ be a feasible solution. We consider the following conditions:

• (H1) For every w ∈ W and p α ∈ P w ,

C pα ≥ InfC(w) =⇒ Y pα = L pα ;
• (H2) For every w ∈ W and p α ∈ P w ,

C pα ≥ InfC(w) =⇒ either Y pα = L pα or Y p β = U p β
for all p β ∈ P w with C p β = InfC(w);

• (H3) For every w ∈ W and p α ∈ P w ,

C pα ≥ InfC(w) =⇒ either Y pα = L pα or Y p β = U p β for some p β ∈ P w with C p β = InfC(w).
The following implications are clear:

(H1) =⇒ (H2) =⇒ (H3).

Note that the converse implications are not true in general. Actually these conditions are closely related to the existence of ideal minimal costs.

Proposition 3.2.19 If the feasible pattern flow Y satisfies either of (H1), (H2) and (H3), then for every origin destination pair w ∈ W the set of vector costs C(w) has ideal minimal elements.

Proof. Due to the implications of (H1), (H2) and (H3) we have mentioned, it suffices to prove the proposition when the flow Y satisfies (H3). Suppose to the contrary that for some origin destination pair w ∈ W the set C(w) has no ideal elements. This means that C pα ≥ InfC(w) for all p α ∈ P w . In view of (H3), we have Y pα = L pα . Summing up Y pα over all paths p α joining w, we obtain

d w = pα∈Pw Y pα = pα∈Pw L pα which contradicts (3.13).
Since in most situations, ideal elements of a set of vectors do not exist, conditions (H1), (H2) and (H3) are very difficult to be fulfilled. Instead, we offer a better choice for equilibrium in multi-product multi-criteria models with capacity constraints. We consider also the following conditions:

• (H4) For every w ∈ W and p α , p β ∈ P w ,

C pα ≥ C p β =⇒ either Y pα = L pα or Y p β = U p β • (H5) For every w ∈ W and p α , p β ∈ P w , C pα ≥ C p β =⇒ either Y pα ≯ L pα or Y p β ≮ U p β • (H6) For every w ∈ W and p α , p β ∈ P w , C pα > C p β ⇒ either Y pα = L pα or Y p β = U p β . Remark 3.2.20 1)
In a model without capacity constraints, condition (H4) collapses to (B4) of the previous subsection.

2) Again in a model without constraints condition (H5) is named in [START_REF] Raciti | Equilibrium Conditions and Vector Variational Inequalities: A Complex Relation[END_REF] as a weak vector Wardrop principle. It was introduced by Oettli in [START_REF] Oettli | Necessary and sufficient conditions of Wardrop type for vectorial traffic equilibria[END_REF] to express a necessary condition for a vector variational equilibrium.

3) Conditions (H1)-(H6) given above were developed for networks with capacity constraints by Luc [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF].

For networks with capacity constraints, the following notion of equilibrium introduced by Li, Teo and Yang has received a lot of attention (see [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF][START_REF] Li | A remark on a standard and linear vector network equilibrium problems with capacity constraints[END_REF][START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] for instance): a feasible pattern flow y is said to be a vector equilibrium if for every j = 1, ..., q, w ∈ W and p α , p β ∈ P w one has implication c j pα ≥ c j p β =⇒ either y j pα = l j pα or y j p β = u j p β . Observe that this concept of equilibrium and the ones given in (H4) and (H5) are equivalent when q = 1, but they are not comparable when q > 1 as it is shown by Examples 3.2.21 and 3.2.22. Because the implication in the definition of vector equilibrium involves individually q products, its analysis is much similar to single product multi-criteria models (see [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF]). In contrast to this, equilibrium in conditions (H4) and (H5) consider collectively different kinds of products and seem to be more suitable in the models in which a certain proportion between the products to transport is to be kept (for instance, we cannot transport cows without dried grass on a long distance even if on a route the cost for cows is cheaper and the cost for dried grass is more expensive than on another route).

Example 3.2.21 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with two available paths:

P w = {p 1 , p 2 }. Assume that d 1 w = 6, d 2 w = 13, l j pi = 2, u j pi = 10 for p i ∈ P w , j = 1, 2,
and

y 1 p1 = 2 y 2 p1 = 3 c 1 p1 = (20, 10) T c 12 = (15, 8) T y 1 p2 = 4 y 2 p2 = 10 c 1 p2 = (15, 9) T c 2 p2 = (10, 7) T Since c 1 p1 ≥ c 1 p2 and y 1 p1 = l 1 p1 = 2; c 2 p1 ≥ c 2 p2 and y 2 p2 = u 2 p2 = 10, Y is a vector equilibrium. However, Y is not a strong vector equilibrium. In fact, Y p2 = U p2 and Y p1 = L p1 , although C p1 ≥ C p2 .
Example 3.2.22 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with three available paths: P w = {p 1 , p 2 , p 3 }. Assume that d 1 w = 15, d 2 w = 20, l j pi = 2, u j pi = 10 for p i ∈ P w and j = 1, 2, and

y 1 p1 = 3 y 2 p1 = 6 c 1 p1 = (12, 20) T c 2 p1 = (19, 10) T y 1 p2 = 3 y 2 p2 = 9 c 1 p2 = (20, 18) T c 2 p2 = (15, 12) T y 1 p3 = 9 y 2 p3 = 5 c 1 p3 = (18, 12) T c 2 p3 = (10, 19) T Since C pα ≦ C p β and C pα ≧ C p β , ∀p α , p β ∈ P w and L i < Y pi < U pi , ∀p i ∈ P w , Y is a strong vector equilibrium. However, Y is not a vector equilibrium. In fact, c 1 p2 > c 1 p3 but y 1 p2 = l 1 p2 and y 1 p3 = u 1 p3 .
In a similar vein, Raciti [START_REF] Raciti | Equilibrium Conditions and Vector Variational Inequalities: A Complex Relation[END_REF] studies equilibrium for a model without capacity constraints by requiring that for every k ∈ {1, ..., l}, w ∈ W and p α , p β ∈ P w one has implication c j pα,k ≥ c j p β ,k =⇒ y j pα = 0 for all j = 1, ..., q. In this definition not only products are considered individually, but the criteria too. So its study belongs to the category of single-product single-criterion network equilibria. Here are some relationships between the conditions of equilibrium. L pα .

Proof. The implication (H4) ⇒ (H5) is obvious. For the implication (H1) ⇒ (H4), let C pα ≥ C p β for some p α , p β ∈ P w . Then C pα is not ideal minimal, and Y pα = L pα by (H1). This shows that (H4) is satisfied. To prove (ii), we assume (H4). Let C pα ≥ InfC(w) for some p α ∈ P w . Picking any C p β = InfC(w), we obtain C pα ≥ C p β which implies that either

Y pα = L pα or Y p β = U p β . If Y pα = L pα ,
, we obtain (H1). If not, Y pγ = U pγ for all p γ ∈ P w with C pγ = InfC(w). Consequently,

d w = pα∈Pw Y pα = p β ∈Pw:Cp β =InfC(w) U p β + pα∈Pw:Cα =InfC(w) Y pα ≥ p β ∈Pw:Cp β =InfC(w) U p β + pα∈Pw:Cp α =InfC(w)
L pα which contradicts the hypothesis.

Remark 3.2.24

1) The implication (H5) ⇒ (H4) is not true except for the case q = 1, in which the two conditions (H4) and (H5) coincide. Of course, both of them generalize Wardrop's equilibrium [START_REF] Wardrop | Correspondence. Some theoretical aspects of road traffic research[END_REF] when q = 1 and l = 1.

2) The results obtained in Proposition 3.2.19 and Proposition 3.2.23 of Luc [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] suggest to call a feasible flow satisfying (H1), (H4) and (H5) as an ideal equilibrium, a strong equilibrium and a weak equilibrium respectively.

3) Condition (H6) is a general version of weak vector equilibrium defined in Li, Teo, Yang [START_REF] Li | A remark on a standard and linear vector network equilibrium problems with capacity constraints[END_REF] with respect to the number of considered products.

Note that a multi-product network hardly possesses ideal equilibrium flows, the concept of strong equilibrium seems to be most appropriate for multi-product networks. Weak equilibrium is particularly interesting in networks in which products are transported by bundles. For instance, machines sending from a factory to a destination are accompanied by a number of accessories. It is possible that on a path lower limits for certain accessories are reached while lower limits for other accessories are not. In such a model, strong equilibria infrequently exist and weak equilibria turn to be good substitutes.

Equilibrium in a multi-criteria traffic network without capacity constraints

In this chapter, we develop a new method to generate the set of equilibrium flows of a multi-criteria traffic network. To this end we introduce two optimization problems by using a vector version of the Heaviside Step function and the distance function to Pareto minimal elements and show that the optimal solutions of these problems are exactly the equilibria of the network. We study the objective functions by establishing their generic differentiability and local calmness at equilibrium solutions. Then we present an algorithm to generate a representative set of equilibrium solutions by using a modified Frank-Wolfe reduced gradient method and prove its convergence. We give some numerical examples to illustrate our algorithm and show its advantage over a popular method by using linear scalarization. A method of smoothing the objective functions by analytic approximations of the Heaviside Step function is also considered. Finally, we introduce the concept of robust equilibrium and obtain a formula to compute the radius of robustness together with an algorithm to find robust equilibrium flows.

The following concept of equilibrium is known as a vector version of Wardrop's famous user principle (see [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF]). Definition 4.0.25 A feasible path flow y is said to be a vector equilibrium (respectively a weak vector equilibrium) of G if for every O/D pair w ∈ W and for every couple of paths p, p ′ ∈ P w one has implication

c p (y) -c p ′ (y) ≥ 0 (respectively c p (y) -c p ′ (y) > 0) =⇒ y p = 0.
It is clear that every vector equilibrium is weak vector equilibrium, and the converse is not true in general. Note that the set of weak vector equilibria is closed if the vector cost functions are continuous, while it is not always the case for the set of vector equilibria (see Example 4.3.2). Further, if we denote by C w (y) the set of all vectors c p (y), p ∈ P w for an O/D pair w ∈ W , then the above definition is equivalent to the implication

c p (y) ∈ Min(C w (y)) (respectively c p (y) ∈ WMin(C w (y)) ) =⇒ y p = 0,
for every p ∈ P w and every w ∈ W .

Equivalent problems

A common technique to find equilibrium of a multi-criteria traffic network is to transform it to an equivalent problem the solution methods of which are already known. In this section we discuss two well-known approaches of such transformations: an approach by scalarization and an approach by variational inequalities. Then we introduce a new approach by constructing two optimization problems the solutions of which are exactly the vector equilibria of the network.

Scalarization

The first method for solving a multi-criteria traffic network equilibrium problem is to convert it to a single-criterion problem by scalarizing the vector cost function. Namely, let h be a realvalued function on the set {c p (y) : y ∈ K, p ∈ P } which satisfies a monotonicity (respectively weak monotonicity) condition: for every w ∈ W, p and p ′ ∈ P w ,

h(c p (y)) > h(c p ′ (y)) if c p (y) ≥ c p ′ (y) (respectively c p (y) > c p ′ (y)).
By considering the network G equipped with the scalar cost function

π p (y) = h(c p (y))
one says that a feasible path flow ȳ is a π-equilibrium if for every w ∈ W and for every p, p ′ ∈ P w , one has implication

π p (y) -π p ′ (y) > 0 =⇒ y p = 0.
It is clear that if h is monotone, then a π-equilibrium is a vector equilibrium and if h is weakly monotone, then a π-equilibrium is a weak vector equilibrium. The converse is not true in general. Here are some typical instances of scalarization.

1) Linear scalarization. In the classical bi-criteria models of [START_REF] Dafermos | A multicrieria route-mode choice traffic equilibrium model[END_REF][START_REF] Dial | A model and algorithms for multicriteria route-mode choice[END_REF][START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF][START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model with elastic demand[END_REF] the authors consider a vector cost function on arcs

c a (z) = t a (z) u a (z)
where t a (z) is the travel time function and u a (z) is the travel cost function on arc a ∈ A.

They choose nonnegative weights λ 1 a and λ 2 a associated with t a and u a respectively on each arc a ∈ A and define the scalarized cost function on paths as follows Assume there is some weight vector (α, β) ≥ 0 such that (λ 1 a , λ 2 a ) = (α, β) for all a ∈ A, that is, the weights (λ 1 a , λ 2 a ) are common on all arcs and equal to (α, β). Then the scalarized cost function π p can be written as π p (y) = (α, β)c p (y).

π p (y) = a∈A λ 1 a , λ
The (linear) scalarizing function h defined by

h(c p (y)) = (α, β)c p (y)
is monotone if (α, β) > 0 and weakly monotone if (α, β) ≥ 0. Consequently, a π-equilibrium is a vector equilibrium or a weak vector equilibrium depending on whether (α, β) > 0 or (α, β) ≥ 0. It is worthwhile noting here that when the weights (λ 1 a , λ 2 a ) are distinct on arcs, a πequilibrium is not necessarily a vector equilibrium or a weak vector equilibrium.

2) Nonlinear scalarization. As it was already said a weak vector equilibrium is not necessary a π-equilibrium when h takes a linear form. In other words, without any specific properties of the cost functions, not all weak vector equilibria of G may be obtained by solving network equilibrium problems in which the cost functions are of type h(c p (y)) = (α, β)c p (y) with (α, β) ≥ 0. To fulfill this gap nonlinear scalarizing functions are widely used in recent models ( [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF][START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF][START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF][START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF]). Namely, for every path flow y and path p ∈ P w , w ∈ W we define a scalarized relative cost function r p (y) to be

r p (y) = max p ′ ∈Pw min j=1, ••• , l (c p,j (y) -c p ′ ,j (y))
where c p,j (y) denotes the jth component of c p (y). The function h defined by

h(c p (y)) = r p (y) is weakly monotone. Indeed, let p, p ′ ∈ P w , w ∈ W with c p (y) > c p ′ (y). Let p ′′ ∈ P w such that h(c p ′ (y)) = min j=1, ••• , l (c p ′ ,j (y) -c p ′′ ,j (y)).
We have

min j=1, ••• , l (c p,j (y) -c p ′′ ,j (y)) = min j=1, ••• , l [(c p,j (y) -c p ′ ,j (y)) + (c p ′ ,j (y) -c p ′′ ,j (y))] ≧ min j=1, ••• , l (c p,j (y) -c p ′ ,j (y)) + min j=1, ••• , l (c p ′ ,j (y) -c p ′′ ,j (y)) > min j=1, ••• , l (c p ′ ,j (y) -c p ′′ ,j (y)),
and deduce

h(c p (y)) ≧ min j=1, ••• , l (c p,j (y) -c p ′′ ,j (y)) > h(c p ′ (y)).
As before, we say that a feasible path flow y is r-equilibrium if for every w ∈ W and p, p ′ ∈ P w , one has implication

r p (y) > r p ′ (y) =⇒ y p = 0. (4.2)
We observe that (4.2) is equivalent to (4.3) below

r p (y) > 0 =⇒ y p = 0. (4.3)
Indeed, since r p (y) ≧ 0 for all p ∈ P , implication (4.3) =⇒ (4.2) is clear. For the converse implication, suppose r p (ȳ) > 0 for some p ∈ P w . There exists some p ′ ∈ P w such that

r p (ȳ) = min j=1, ••• , l (c p,j (y) -c p ′ ,j (y)) > 0.
This shows that c p (ȳ) > c p ′ (ȳ) and implies r p (ȳ) > r p ′ (ȳ) because h is weakly monotone. In view of (4.2), we deduce ȳp = 0.

The following property demonstrates an important role of nonlinear scalarization: a feasible path flow is a weak vector equilibrium if and only if it is an r-equilibrium. Indeed, the function h being weakly monotone, the "if" part is clear. For the "only if" part, suppose ȳ is not r-equilibrium. By (4.3) there exist some w ∈ W and p ′ ∈ P w such that r p (ȳ) > 0 and ȳp = 0. Let p ′ ∈ P w be such that

r p (ȳ) = min j=1, ••• , l (c p,j (ȳ) -c p ′ ,j (ȳ)) > 0.
Then c p (ȳ) > c p ′ (ȳ), and hence ȳ is not a weak vector equilibrium.

3) Augmented nonlinear scalarization. We notice that an r-equilibrium is not necessarily a vector equilibrium. In order to obtain vector equilibria we consider a new scalarized relative cost function R ǫ p (y) defined by

R ǫ p (y) = max p ′ ∈Pw min j=1, ••• , l [c p,j (y) -c p ′ ,j (y) + ǫ l j=1 (c p,j (y) -c p ′ ,j (y))]
for every y ∈ K and p ∈ P w for some w ∈ W , where ǫ > 0 is a small constant. Using an argument similar to the case of r p , we may prove that the function h defined by

h(c p (y)) = R ǫ p (y)
is a monotone function. A feasible path flow y is said to be R ǫ -equilibrium if for every path p ∈ P, one has implication R ǫ p (y) > 0 =⇒ y p = 0. It can also be proven that a feasible path flow is a vector equilibrium if and only if there is some ǫ > 0 such that it is an R ǫ -equilibrium. Notice that the constant ǫ depends on each equilibrium flow. Therefore, in order to generate the set of vector equilibria by this approach one has to find the set of R ǫ -equilibria for all ǫ > 0.

Vector variational inequalities

Another approach in solving a multi-criteria traffic network equilibrium problem is to construct a suitable vector variational inequality the solutions of which are vector equilibria of the model, see [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF]. We consider two vector variational inequality problems, denoted respectively (VI) and (WVI): Find ȳ ∈ K such that C(ȳ)(yȳ) ≤ 0 for all y ∈ K and C(ȳ)(yȳ) < 0 for all y ∈ K.

The first variational inequality can be written as C(ȳ)(yȳ) ∈ -R l + \ {0} and the second one is written as C(ȳ)(yȳ) ∈ intR l + . The following claim is also clear (see [START_REF] Li | Vector equilibrium problems with elastic demands and capacity constraints[END_REF]): If ȳ solves (VI) (respectively (WVI)), then it is a vector equilibrium (respectively a weak vector equilibrium). The converse is not true, that is, a vector equilibrium (respectively weak vector equilibrium) is not necessarily a solution of (VI) (respectively (WVI)). By considering the set of the so-called elementary flows one is able to construct an equivalent vector variational inequality for the multi-criteria network equilibrium problem. Namely, let us denote by K(ȳ) the set of flows y ∈ K such that yȳ is elementary in the sense that there are w ∈ W and p, p

′ ∈ P w such that [y -ȳ] p ′′ = 0 for p ′′ ∈ P \ {p, p ′ } and [y -ȳ] p = -[y -ȳ] p ′ , where [y -ȳ] p ′
is the traffic load on path p ′ . It was proven in [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] that ȳ is a vector equilibrium if and only if it is a solution of the following vector quasi-variational inequality problem

C(ȳ)(y -ȳ) ≤ 0 for all y ∈ K(ȳ).
A similar result is true for weak vector equilibria. Notice that finding a feasible flow satisfying the above mentioned vector variational inequality is hard and as far as we know, up to now there is no efficient method to solve it.

Two optimization problems

In this part we develop a new approach to solve a multi-criteria traffic equilibrium problem. Specifically we shall construct two optimization problems the solutions of which are exactly the vector equilibria of the network. The following notations will be used:

• d[x, B] is the Euclidean distance from a point x to a set B in R l .
• e ∈ R l is the vector of ones and H + : R l → R l is defined by

H + (x) = e if x ≧ 0 0 else.
The function H + is vector version of the Heaviside Step function, which can also be expressed by

H + (x) = l i=1 h + (x i ) e for all x ∈ R l ,
where h + is the scalar Heaviside Step function, that is h + (t) = 1 for t ∈ R + and h + (t) = 0 for t < 0. Let us define two functions on the set of feasible flows:

φ(y) := p∈Pw,w∈W y p d[c p (y), Min(C w (y))] ψ(y) := p∈Pw,w∈W y p p ′ ∈Pw [c p (y) -c p ′ (y)] T H + [c p (y) -c p ′ (y)].
In general these functions are not continuous, but still have nice properties that we shall develop in the next section. We now show that the problems of minimizing them on the feasible set K are equivalent to the multi-criteria network equilibrium problem. (i) ȳ is a vector equilibrium.

(ii) ȳ is an optimal solution of the following problem, denoted (P1):

minimize φ(y) subject to y ∈ K and the optimal value of this problem is zero. (iii)ȳ is an optimal solution of the following problem, denoted (P2): minimize ψ(y) subject to y ∈ K and the optimal value of this problem is zero.

Proof. We first prove that (i) and (ii) are equivalent. Let ȳ be a vector equilibrium. Since φ(y) ≧ 0 for every y ∈ K, it suffices to prove φ(ȳ) = 0 in order to deduce (ii). In fact, for every p ∈ P w , w ∈ W one has either c p (ȳ) ∈ Min(C w (ȳ)) or there is some p ′ ∈ P w such that c p (ȳ)c p ′ (ȳ) ≥ 0. In the first case, d[c p (ȳ), Min(C w (ȳ))] = 0, and in the second case, ȳp = 0 by definition. Thus, the terms ȳp d[c p (ȳ), Min(C w (ȳ))], p ∈ P are all equal to zero, which implies φ(ȳ) = 0. Conversely, assume ȳ is an optimal solution of (P1) with φ(ȳ) = 0. Since all terms in the sum defining φ are nonnegative, we have y p d[c p (ȳ), Min(C w (ȳ))] = 0 for all p ∈ P w , w ∈ W . If for some p and p ′ from P w , w ∈ W one has c p (ȳ)c p ′ (ȳ) ≥ 0, then c p (ȳ) ∈ Min(C w (ȳ)). Hence d[c p (ȳ), Min(C w (ȳ))] = 0 and ȳp = 0. This proves that ȳ is a vector equilibrium.

Next we show equivalence between (i) and (iii). Let ȳ be a vector equilibrium. Since ψ(y) ≧ 0 for every y ∈ K, as before, it suffices to prove ψ(ȳ) = 0 in order to deduce (iii). Let p ∈ P w , w ∈ W . Consider the term

p ′ ∈Pw ȳp [c p (ȳ) -c p ′ (ȳ)] T H + [c p (ȳ) -c p ′ (ȳ)], denoted b p . If c p (ȳ) -c p ′ (
ȳ) ≥ 0 for some p ′ ∈ P w , then by definition, ȳp = 0. If c p (ȳ)c p ′ (ȳ) = 0 for some p ′ ∈ P w , it is clear that the corresponding term of the above sum is zero. If c p (ȳ)c p ′ (ȳ) ≧ 0 for some p ′ ∈ P w , then H + [c p (ȳ)c p ′ (ȳ)] = 0. Therefore b p = 0. Consequently, ψ(ȳ) = 0 as requested. Conversely, assume ȳ solves (P2) and ψ(ȳ) = 0. It follows that b p = 0 for every p ∈ P . If for some p and p ′ from P w , w ∈ W one has c p (ȳ) -

c p ′ (ȳ) ≥ 0, then [c p (ȳ) -c p ′ (ȳ)] T H + [c p (ȳ) -c p ′ (ȳ)] > 0.
Consequently, ȳp = 0. We deduce that ȳ is a vector equilibrium.

We note that problems (P1) and (P2) belong to the class of nonconvex problems under linear constraints. Their significance resides in the fact that the set of optimal solutions is exactly the set of vector equilibrium flows. Therefore these problems will be used to develop algorithms to generate vector equilibrium flows of the network. Furthermore, by using the same method of proof we may establish a similar result for weak vector equilibria. Namely, a feasible ȳ is a weak vector equilibrium if and only if it solves each of the following problems minimize φ w (y) :=

y p p ′ ∈Pw [c p (y) -c p ′ (y)] T H w + [c p (y) -c p ′ (y)] subject to y ∈ K
and the optimal values are equal to zero, where H w + is defined by

H w + (x) = e if x > 0 0 else.
And finally, we observe that the conclusion of Theorem 5.2.1 remains true when the function H + defining the objective function of (P2) is substituted by the function

H+ (x) = l i=1 h+ (x i ) e for all x ∈ R l ,
where h+ (t) = h + (t) for all t ∈ R \ {0} and h+ (0) = 1/2.

Generic differentiability and local calmness of the objective functions

The objective functions φ and ψ of problems (P1) and (P2) are not only nonconvex, but also not continuous as we have already noticed. This defect causes major difficulties in applying global optimization tools to solve (P1) and (P2). However, as we shall see in this section, these functions enjoy certain generic properties on continuity and differentiability. Specifically, we shall show that they are discontinuous or nondifferentiable only on a negligible subset. We first need some preliminary lemmas in order to establish generic properties of the functions φ and ψ. Let b 1 , • • • , b k be vector-valued functions from R m to R l . For every y ∈ R m and j ∈ {1, • • • , k} denote

I(y) = i ∈ {1, • • • , k} : b i (y) ∈ Min{b 1 (y), • • • , b k (y)} J j (y) = i ∈ {1, • • • , k} : b j (y) ≧ b i (y) .
Thus, y → I(y) and y → J j (y), j ∈ {1, • • • , k} are set-valued maps from R m to the topological space {1, • • • , k} equipped with the discret topology. In this case the map I is lower semi-continuous at y if there is a neighborhood U of y in R m such that I(y ′ ) ⊇ I(y) for every y ′ ∈ U , and it is upper semi-continuous if there is a neighborhood U of y in R m such that I(y ′ ) ⊆ I(y) for every y ′ ∈ U .

j (y ′ ) ∈ b i (y ′ ) -R l + for j = i, y ′ ∈ U. Hence b i (y ′ ) ∈ Min{b 1 (y ′ ), • • • , b k (y ′
)} for all y ′ ∈ U , which means i ∈ I(y ′ ). We conclude I(y) ⊆ I(y ′ ) for all y ′ ∈ U.

To prove (ii) we show that for any fixed index j, the map y → J j (y) is closed. Indeed, let {y ν } ν≧0 be a sequence in R m converging to y and i ν ∈ J j (y ν ) converging to i. Then i ν = i for ν sufficiently large, which means that b j (y ν ) ≧ b i (y ν ) for ν large. By continuity, when ν tends to ∞, we obtain b j (y) ≧ b i (y), which proves that i ∈ J j (y). Since the image space of J j is finite, in view of Proposition 1.4.8 of [START_REF] Aubin | Set-valued Analysis[END_REF], the map J j is upper semi-continuous.

We note that in general the map y → I(y) is not upper semi-continuous and it is not lower semi-continuous without the condition that the vectors b 1 (y), • • • , b k (y) are distinct from each other. Similarly the maps y → J j (y), j ∈ {1, • • • , k} are not lower semi-continuous. This observation is seen in the following example. We claim that the map y → I(y) is not upper semi-continuous at y. Indeed, for ν > 1, set y ν = (3-1/ν, 3+1/ν, 3) T . Then y ν converges to y as ν tends to ∞, while I(y ν ) = {1, 2, 3} for every ν > 1.

For the family {b 2 (y), b 3 (y), b 4 (y)}, the hypothesis of (i) of Lemma 4.2.1 does not hold at y = (3, 3, 3) T . We have I(y) = {2, 3, 4} and J 3 (y) = {3, 4}. However, for y ν = (3, 3 + 1/ν, 3 -1/ν) T with ν > 1, we have I(y ν ) = {2, 3} and J 3 (y ν ) = {3} for all ν > 1. Since y ν converges to y as ν tends to ∞ we conclude that the maps y → I(y) and y → J 4 (y) are not lower semi-continuous at y.

According to a generic theorem (Theorem 1.4.13 of [START_REF] Aubin | Set-valued Analysis[END_REF]) the set-valued maps y → J j (y), j ∈ {1, • • • , k} and y → I(y) are continuous on a dense subset of R n . Below we establish a stronger result which says that the set of discontinuity of these maps is nowhere dense.

I(y ′ ) ⊆ {1, • • • , k}, y ′ ∈ U 3 .
We find an index set I(y ′ ) for some y ′ ∈ U 3 which is maximal with respect to inclusion. Apply again Lemma 4.2.1 to this y ′ we may find a smaller neighborhood U ′ ⊆ U 3 such that I(y ′ ) ⊆ I(y ′′ ) for all y ′′ ∈ U ′ . But I(y ′ ) was chosen to be maximal, we have I(y ′ ) = I(y ′′ ) for all y ′′ ∈ U ′ as requested.

To prove (ii), let us consider a point y ∈ U . In view of Lemma 4.2.1 (ii) for each j ∈ {1, • • • , k} there exists an open set U 1 of y in U such that J j (y ′ ) ⊆ J j (y) for all y ′ ∈ U 1 .

For j = 1, consider the family of index set J 1 (y ′ ), y ′ ∈ U 1 and let y 1 ∈ U 1 be a point at which J 1 (y 1 ) is minimal with respect to inclusion. Then there is an open set

U 2 of y 1 in U 1 such that J 1 (y ′ ) ⊆ J 1 (y 1 ) for all y ′ ∈ U 2 .
Because of the choice of y 1 , the above inclusion is equality. The same argument is applied to J 2 (.) on U 2 . We obtain an open set U 3 ⊆ U 2 such that

J 1 (y ′ ) = J 1 (y ′′ ) J 2 (y ′ ) = J 2 (y ′′ ) for all y ′ , y ′′ ∈ U 3 .
Continuing this process we arrive at an open set U ′ ⊆ U in which

J j (y ′ ) = J j (y ′′ ) for all y ′ , y ′′ ∈ U ′ and j = 1, • • • , k as requested.
We recall that the Hausdorff distance between two bounded closed sets B and B ′ in R l is defined by

H(B, B ′ ) = min{t ≧ 0 : B ⊆ B ′ + tB, B ′ ⊆ B + tB} = max{max x∈B d(x, B ′ ), max x ′ ∈B ′ d(x ′ , B)},
where B denotes the unit ball centered at 0 in R l . Now we are in position to present and prove the main result of this section. the set of indices i ′ ∈ I such that the above distance is attained. We claim that the set-valued map y → I ′ (y) is upper semi-continuous. Indeed, let y ∈ U w and let {y ν } ν≧0 be a sequence of elements in U w converging to y. Let i ′ ν ∈ I ′ (y ν ). Since I ′ (y ν ) ⊆ I and I is finite, we may assume without loss of generality that i ′ ν = i 0 for some i 0 ∈ I and for all ν ≧ 0. We have

d[c pi (y ν ), c pi 0 (y ν )] ≦ d[c pi (y ν ), c p i ′ (y ν )
] for all i ′ ∈ I.

By passing to the limit as ν tends to ∞, we obtain For a path p i in P let us denote w(i) the O/D pair for which the set P w(i) contains this path. Thus, w(i) = w(i ′ ) if the paths p i and p i ′ connect the same O/D pair. We will also adopt a convention that for two vectors b, b

′ ∈ R l , (b -b ′ )/ b -b ′ = 0 if b = b ′ .
Theorem 4.2.5 Assume that the vector cost functions c pi , i = 1, • • • , m are differentiable. Then for every point y outside of some nowhere dense subset and for every path p i , there exists a path p ν(i) from P w(i) such that

(i) c p ν(i) (y) ∈ MinC w(i) (y) (ii)d[c pi (y), MinC w(i) (y)] = c pi (y) -c p ν(i) (y) (iii)
φ is differentiable at y and its gradient is computed by

∇φ(y) =   c p1 (y) -c p ν(1) (y) • • • c pm (y) -c p ν(m) (y)   + m i=1 y pi     cp i (y)-c ν(i) (y) cp i (y)-cp ν(i) (y) ∂cp i ∂yp 1 (y) - ∂cp ν(i) ∂yp 1 (y) • • • cp i (y)-cp ν(i) (y) cp i (y)-cp ν(i) (y) ∂cp i ∂yp m (y) - ∂cp ν(i)
(i) , i = 1, • • • , m such that d[c pi (y), MinC w(i) (y)] = c pi (y) -c p i ′ (y) for all y ∈ U ′ , i ′ ∈ I w(i) , i ∈ {1, • • • , m}. Choose ν(i) to be any i ′ from I w(i) for i = 1, • • • , m, we have φ(y) = m i=1 y pi c pi (y) -c p ν(i) (y)
for all y ∈ U ′ . If i ∈ I w(i) , then c pi (y)c p ν(i) (y) = 0 for all y ∈ U ′ . If i ∈ I w(i) , then c pi (y)c p ν(i) (y) > 0 for all y ∈ U ′ . In any case every term in the sum of the function φ is differentiable on U ′ . A direct calculation produces the formula for the gradient of φ given in (iii).

In the next theorem we set j∈J c pi (y)c pj (y) = 0 if the index set J is empty and keep the notation I w(i) for the set of all indices j such that p j ∈ P w(i) satisfying d[c pi (y), MinC w(i) (y)] = c pi (y)c pj (y) . Theorem 4.2.6 Assume that the vector cost functions c pi , i = 1, • • • , m are differentiable. Then for every point y outside of some nowhere dense subset and for every path p i , there exists a subset J i (y) ⊆ I w(i) such that

(i) c pi (y) ≥ c pj (y) for every j ∈ J i (y) (ii) ψ(y) = m i=1 y pi j∈Ji(y) c pi (y) -c pj (y) , e (
iii)ψ is differentiable at y and its gradient is computed by

∇ψ(y) =   j∈J1(y) c p1 (y) -c pj (y), e • • • j∈Jm(y) c pm (y) -c pj (y), e   + m i=1 y pi    j∈Ji(y) ∂cp i ∂yp 1 (y) - ∂cp j ∂yp 1 (y), e • • • j∈Ji(y) ∂cp i ∂yp m (y) - ∂cp j ∂yp m (y), e   
Proof. We apply an argument similar to the proof of Theorem 4.2.5. Given any open set U , there are an open set U ′ ⊆ U and index sets J 1 , • • • , J m such that for y ∈ U ′ , i ∈ {1, • • • , m} and p j ∈ P w(i) one has c pi (y)c pj (y) ≥ 0 if and only if j ∈ J i . We deduce that

ψ(y) = m i=1 y pi j∈Ji c pi (y) -c pj (y), e
for all y ∈ U ′ . Consequently, ψ is differentiable on U ′ . A direct calculation gives us the formula (iii) for the gradient of ψ.

To establish some more continuity properties of the objective functions we recall that a function f on K is said to be locally calm at y ∈ K if there are some constants δ > 0 and κ > 0 such that |f (y)f (y)| ≦ κ yy for all y ∈ K with yy ≦ δ (see [START_REF] Dontchev | Implicit Functions and Solution Mappings: A View From Variational Analysis[END_REF]). Proposition 4.2.7 Assume that the vector cost functions c p1 , • • • , c pm are continuous. Then the functions φ and ψ are continuous at every vector equilibrium. If in addition c p1 , • • • , c pm are locally calm at a vector equilibrium, then φ and ψ are also locally calm there.

Proof. Let y ∈ K be a vector equilibrium of G. Assume that c p1 , • • • , c pm are continuous on K and locally calm at y. The case where these functions are merely continuous is proven by a similar argument. We wish to show that there exist some δ > 0 and κ > 0 such that |φ(y)φ(y)| ≦ κ yy and |ψ(y)ψ(y)| ≦ κ yy for every y ∈ K with yy ≦ δ. Because φ and ψ take nonnegative values and as y is equilibrium, by Theorem ??, φ(y) = ψ(y) = 0, the above inequalities are equivalent to

φ(y) ≦ κ y -y (4.4)
and ψ(y) ≦ κ yy .

We establish (4.4) first. Recall that for i ∈ {1, ..., m}, w(i) denotes the O/D pair connected by the path p i and P w(i) denotes the set of all paths connecting this O/D pair. We make also use of the following notations

I 0 = {i ∈ {1, • • • , m} : ȳpi = 0} I + = {i ∈ {1, • • • , m} : ȳpi > 0} D = max{d w : w ∈ W } T = max{ c pi (y) : y ∈ K, i = 1, • • • , m}.
The following inequalities are clear

y pi ≦ y ≦ D (4.6) d[c pi (y), Min(C w(i) (y))] ≦ 2T (4.7)
for every y ∈ K and p i ∈ P. Consider the terms

f i (y) := y pi d[c pi (y), Min(C w(i) (y))], i = 1, ..., m.
If i ∈ I 0 , then (4.6) and (4.7) yield

|f i (y) -f i (ȳ)| = f i (y) ≦ 2T y pi ≦ 2T y -y . ( 4
Q := {c pj ∈ C w(i) : c pj (ȳ) = c pi (ȳ)}.
We have

(C w(i) (ȳ)\Q(ȳ)) ∩ (Q(ȳ) -R l + ) = ∅. Because the set C w(i) (y)\Q(ȳ) is finite and the set Q(ȳ) -R l + is closed, there exists some γ > 0 such that [(C w(i) (ȳ) + γB)\(Q(ȳ) + γB)] ∩ (Q(ȳ) + γB -R l + ) = ∅.
By continuity there exists δ i > 0 such that

C w(i) (y) ⊆ C w(i) (ȳ) + γB Q(y) ⊆ Q(ȳ) + γB
for every y ∈ K with yy ≦ δ i . We deduce for such y and for every

c pj ∈ Q that [C w(i) (y)\Q(y)] ∩ (c pj (y) -R l + ) = ∅. (4.9)
Consider the set Min(Q(y)). It is nonempty because Q(y) is finite. We claim that

Min(Q(y)) ⊆ Min(C w(i) (y)). (4.10)
Indeed, let a ∈ Min(Q(y)). For each p j ∈ P w(i) , if c pj (y) / ∈ Q(y), then by (4.9), one has

c pj (y) / ∈ a -R l + . (4.11)
If c pj (y) ∈ Q(y)\{a}, then (4.11) is true because a is an efficient element of Q(y). By this, a ∈ Min(C w(i) (y)) and (4.10) follows. Furthermore, by the calmness hypothesis there are some constants δ ′ > 0 and κ ′ > 0 such that c pj (y)c pj (y) ≦ κ ′ yy (4.12)

for every y ∈ K with yy ≦ δ ′ and j = 1, • • • , m. By using (4.10) we obtain the following estimation

d[c pi (y), Min(C w(i) (y))] ≦ d[c pi (y), Min(Q(y))] ≦ max cp j ∈Q c pi (y) -c pj (y) ≦ max cp j ∈Q c pi (y) -c pi (y) + c pj (y) -c pj (y) ≦ 2κ ′ y -y .
This and (4.6) imply

|f i (y) -f i (y)| = f i (y) ≦ 2Dκ ′ y -y (4.13)
for all y ∈ K with yy ≦ min(δ i , δ ′ ). By setting δ = min{min(δ i , δ ′ ) : i ∈ I + } and κ = 2T |I 0 | + 2Dκ ′ |I + | we obtain (4.4) from (4.8) and (4.13). To prove (4.5), we proceed in a similar manner. Consider the terms

g i (y) := y pi pj ∈P w(i) [c pi (y) -c pj (y)] T H + [c pi (y) -c pj (y)], i = 1, ..., m. Observe first that 0 ≦ [c pi (y) -c pj (y)] T H + [c pi (y) -c pj (y)] ≦ 2lT,
for all p i , p j ∈ P and y ∈ K. Therefore, if i ∈ I 0 , then |g i (y)g i (y)| = g i (y) ≦ 2mlT y pi ≦ 2mlT yy .

(4.14)

If i ∈ I + , we have pj ∈P w(i)
[c pi (y)c pj (y)] T H + [c pi (y)c pj (y)] = 0, which implies that for p j ∈ P w(i) \{p i }, either c pi (y) c pj (y) or c pi (y) = c pj (y). In the first case, due to the continuity hypothesis, there exists some δ ′′ i > 0 such that c pi (y) c pj (y) for all y ∈ K with yy ≦ δ ′′ i . In the second case, by the calmness hypothesis (4.12), we have

c pi (y) -c pj (y) = c pi (y) -c pi (y) + c pj (y) -c pj (y) ≦ 2κ ′ y -y for all y ∈ K with y -y ≦ δ ′ . Set γ i = min{δ ′ , δ ′′ i }. We deduce |g i (y) -g i (y)| = g i (y) ≦ lD pj ∈P w(i) c pi (y) -c pj (y) ≦ 2lmDκ ′ y -y (

Generating vector equilibrium flows

In this section we propose an algorithm based on Theorem 4.1.1 to generate a subset of vector equilibrium flows of the network we described in Section 2. This algorithm, denoted (A), consists of two procedures. The first procedure is to create a net of feasible flows with which the second procedure will start. The second procedure is aimed at solving problem (P2) which is equivalent to the network equilibrium problem as stated in Theorem 4.1.1 by starting from an initial point from the net obtained by the first procedure. Even if the vector cost functions are linear or differentiable, problem (P2) belongs to the class of nonconvex global optimization problems and is hard to solve. The main difficulty in solving this problem is caused by the fact that the index sets J i in the definition of the function ψ (Theorem 4.2.6) change from point to point. To overcome this we modify Frank-Wolfe's reduced gradient method to find descent direction at each iteration in order to construct a decreasing sequence of feasible values.

Description of the algorithm (A)

Assume that W consists of r elements w 1 , • • • , w r in the network and for each pair w i there are |P wi | paths connecting its origin to its destination. We denote also

I j = {i ∈ {1, • • • , m} : p i ∈ P wj }.
Step 0 (initialization). Choose a positive integer q and a tolerance level ǫ ≧ 0.

Procedure A1.

Step 1. Set

δ j = d wj /(q|P wj |), j = 1, • • • , r. Step 2. Choose (k 1 , • • • , k m ) T ∈ N m satisfying i∈Ij k i = q|P wj |, j = 1, • • • , r.
Step 3. Store y = (y 1 , • • • , y m ) T in Y 0 where

y i = k i δ j for i ∈ I j , j = 1, • • • , r
and return to Step 2 for other vectors (k 1 , • • • , k m ) unless no one left.

Procedure A2.

Step 4. Choose a feasible flow y 0 from Y 0 to start. Set k = 0,

u k-1 = y k , α k-1 = ∞, Y 0 = Y 0 \ {y 0 } and E ǫ q = ∅.
Step 5.

Compute J i (y k ) = {i ′ ∈ {1, • • • , m} : p i ′ ∈ P w(i) , c pi (y k ) -c p i ′ (y k ) ≧ 0} for every i ∈ {1, • • • , m}. Set ψ k (y) := m i=1 y pi i ′ ∈Ji(y k ) c pi (y) -c p i ′ (y), e .
Compute ψ k (y k ). If ψ k (y k ) ≦ ǫ, store y k in E ǫ q and return to Step 4 until no element of Y 0 left. Otherwise go to the next step.

Step 6. If |ψ k (y k ) -α k-1 | ≦ ǫ, go to Step 4 to choose another feasible solution from Y 0 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 ) Some comments on the implementation of the algorithm are in order. 1) By using the notation J i (y) defined in Lemma 4.2.1 for the system of vector-valued functions c p1 , • • • , c pm we have equality

minimize u T ∇ψ k (y k ) subject to u ∈ K |u i -y 0 i | ≦ δ w(i) , i = 1, • • • , m. Let u k be an optimal solution. If |ψ k (y k ) -ψ k (u k )| ≦ ǫ,
ψ(y k ) = m i=1 y k pi i ′ ∈Ji(y k ) c pi (y k ) -c p i ′ (y k ), e = ψ k (y k ).
Note, however, that the functions ψ and ψ k may differ from each other around y k .

2) If the vector cost functions c pi , i ∈ {1, • • • , m} are differentiable, then the function ψ k is differentiable and its gradient is given in Theorem 4.2.6.

3) If ψ k (y k ) = 0, then y k is a vector equilibrium. If ǫ > 0 and |ψ k (y k )| ≦ ǫ, we call y k a vector ǫ-equilibrium. 4) Problem (P k ) is considered as a linearized problem of (P2) at y k . Therefore, when ψ k (u k ) = ψ k (y k ) or ψ(u k ) = ψ(y k ), the current solution y k is called a stationary point of (P2), which includes also the case ∇ψ k (y k ) = 0. It is a local optimal solution of (P2) if in addition ψ is locally convex, but not a global optimal solution whenever the network has equilibrium because ψ(y k ) = ψ k (y k ) = 0. When |ψ k (u k )ψ k (y k )| ≦ ǫ with ǫ > 0, we call y k an ǫ-stationary point of (P2). We notice that ψ(y k ) = ψ k (y k ), but ψ(u k ) may differ from ψ k (u k ).

Convergence of the algorithm

We have already noticed that the objective function ψ is not continuous, and in general the limit of a sequence of vector ǫ-equilibrium flows is not necessarily a vector ǫ-equilibrium. However, the continuity of ψ at vector equilibria (Proposition 4.2.7) allows us to cover all vector equilibrium flows by the output E ǫ q . We recall that the outer limit of a sequence {A q } q≧1 of sets in R l , denoted lim sup q→∞ A q , consists of all cluster points of sequences {a q } q≧1 with a q ∈ A q for all q ≧ 1. The sets of vector equilibrium flows and weak vector equilibrium flows are denoted respectively E and W E. Theorem 4.3.1 Assume the vector cost functions c pi , i = 1, • • • , m are differentiable. For a fixed ǫ > 0, the algorithm terminates after a finite number of iterations and the output E ǫ q contains vector ǫ-equilibrium flows. Moreover, the following inclusions hold true

E ⊆ ǫ>0 lim sup q→∞ E ǫ q ⊆ W E.
Proof. By definition the output E ǫ q collects vector ǫ-equilibrium flows obtained at Step 5 of Procedure A2. Moreover, because the set Y 0 generated by Procedure A1 is finite, to prove the first part of the theorem it suffices to show that for a given y 0 ∈ Y 0 Procedure A2 terminates after a finite number of iterations. Assume this procedure does not terminate at iteration k ≧ 1. We claim that

ψ i+1 (y i+1 ) ≦ ψ i (y i ) -ǫ for i = 0, • • • , k -1. (4.16)
Indeed, let us consider the case of y 0 and y 1 in details when k ≧ 1. Because the procedure does not terminate, we have ǫ < ψ 0 (y 0 ) < ∞ǫ and go to Step 7. By the same reason we have ψ 0 (y 0 )ψ 0 (y 1 ) > ǫ (4.17)

and either of the following conditions is true

ψ 1 (y 1 ) < ψ 0 (y 0 ) -ǫ (4.18) ψ 1 (y 1 ) > ψ 0 (y 0 ) + ǫ. (4.19)
If (4.19) holds, then according to our algorithm y 1 is replaced by y 0 + (y 1y 0 )/2 until (4.18) is satisfied. Indeed, if (4.18) does not hold, then after some cycles y 1 is so close to y 0 that by Lemma 4.2.1 we may assume that J i (y 0 ) ⊇ J i (y 1 ) for every

i = 1, • • • , m. It follows that ψ 0 (y) -ψ 1 (y) = m i=1 y pi i ′ ∈Ji(y 0 )\Ji(y 1 )
c pi (y)c p i ′ (y), e ≧ 0 for all y ∈ K.

Combining this with (4.17) we deduce ψ 0 (y 0 ) > ψ 0 (y 1 ) + ǫ ≧ ψ 1 (y

i ) = ψ i (y i ) for i = 0, • • • , k we deduce the following inequalities ψ(y k ) < ψ(y k-1 ) -ǫ < • • • < ψ(y 0 ) -kǫ.
It is clear that for k sufficiently large, the procedure must be over because ψ takes nonnegative values only.

We now turn to the second part of the theorem. Let ȳ be a vector equilibrium. We know ψ(ȳ) = 0. By Proposition 4.2.7 there is some δ > 0 sufficiently small such that ψ(y) < ǫ for every y with yȳ ∞ < δ (we are in a finite dimensional space, therefore the norm . ∞ is equivalent to the Euclidean norm . ). Choose q sufficiently large so that δ w(i) < δ/2 for all i = 1, • • • , m. By the construction of Y 0 , there is y 0 ∈ Y 0 such that y 0ȳ ∞ < δ.

It follows that ψ(y 0 ) < ǫ which implies that y 0 is an ǫ-equilibrium and collected in E ǫ q . By this ȳ belongs to the outer limit of E ǫ q when q tends to infinity and for very fixed ǫ > 0. This proves the first inclusion. To prove the second inclusion let ȳ be any element of the intersection of the outer limits of E ǫ q and suppose to the contrary that it is not a weak vector equilibrium. There exist some paths p i and p j ∈ P w(i) such that c pi (ȳ)c pj (ȳ) > 0 and ȳpi > 0. By continuity, there exists δ > 0 and t > 0 such that c pi (y)c pj (y) > t and y pi > t for all y ∈ K satisfying yȳ < δ. We have then ψ(y) > t 2 for all such y, and so y cannot belong to E ǫ q once ǫ < t 2 . This completes the proof. We note that the inclusions in the above theorem are generally strict as it is shown by the two examples below. Actually in the first example we prove that the set of vector equilibrium flows is not closed, hence the first inclusion is strict, for the outer limit is a closed set. In the second example we present a network in which there is a weak vector equilibrium that is not a vector equilibrium. At this equilibrium the value of the function ψ is strictly positive, hence whenever ψ is continuous at it, there is no ǫ-equilibrium nearby with ǫ sufficiently small.

c p1 (y ν ) -c p2 (y ν ) = 34 -2/ν 18 + 1/ν - 35 + 2/ν 18 -1/ν = -1 -4/ν 2/ν / ∈ R 2 + .
When ν tends to ∞, y ν converges to the feasible flow y = (2, 8) T . However, y is not a vector equilibrium because c p2 (y) = (35, 18) T ≥ c p1 (y) = (34, 18) T while y p2 = 8 = 0. We observe that in this model every feasible flow is a weak vector equilibrium because c p1,1 (y) > c p2,1 (y) and c p1,2 (y) = c p2,2 (y) for every y ≥ 0. Moreover, the function ψ is given by ψ(y) = y p1 (c p1,1 (y)c p2,1 (y)) = y p1 (5y p1 + 5y p2 ) = 50y p1 .

Consider the flow y = (1, 9) T and choose ǫ ∈ (0, 1). Then every feasible flow y = (y p1 , y p2 ) T satisfying |y p1y p1 | ≤ 1/2 has ψ(y) ≥ 25. Consequently, y cannot be an ǫ-equilibrium.

Numerical examples

In this section we present some numerical examples to illustrate the algorithm described in the preceding section. We use the MATLAB Optimization Toolbox to compute a representative set of vector equilibria and vector ǫ-equilibria for networks in which the cost functions are linear or nonlinear and the number of criteria is at least two. We also compare our method with the method by scalarization in each example. For the readers' convenience, let us briefly recall the scalarization method of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] to find a vector equilibrium. It is to underline that [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] gave a method to find one vector equilibrium, but not the entire set of equilibria or a representative part of it. Without loss of generality we assume l = 2 and choose some α ∈ (0, 1). As we already discussed in Section 4.1, the scalarizing function h(c p (y)) = (α, 1α)c p (y) is monotone, which ensures that every equilibrium of the network equipped with the scalarized cost functions π p (y) = h(c p (y)) is a vector equilibrium. In order to find an equilibrium of the scalarized network the author of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] solves the following variational inequality problem: Find y ∈ K such that F (y, yy ≧ 0 for all y ∈ K,

where

F (y) = ((α, 1 -α)c p1 (y), • • • , (α, 1 -α)c pm (y))
T . This later problem is solved by a modified projection method which is known to be convergent when F is Lipschitz continuous and monotone on K in the sense that F (y ′ ) -F (y), y ′y ≧ 0, for all y, y ′ ∈ K.

In general, for a weight vector (α, 1α) the modified projection method yields one solution of the variational inequality problem which is also a vector equilibrium of the network. Therefore, in order to generate a set of vector equilibria by this method we use a finite family of equally distributed weight vectors in our examples. The number of weight vectors is chosen to be equal to the number of initial points of our method so that the comparison of computing time has sense. Apparently the scalarization method has an advantage over our method that the function F has nice structure when the vector cost functions are linear or differentiable and one may hope to utilize a lot of existing optimization algorithms to obtain a solution of the variational inequality problem, while the function ψ used in our method is even not continuous. However, there are at least three drawbacks of the scalarization method. First, there exist vector equilibria that are not solutions of the variational inequality problem whatever weight vector (α, 1α) be chosen. This is seen in Example 4.3.7. Hence there may be a large portion of vector equilibria that cannot be generated by the scalarization method. Second, even when the weight vectors are chosen to be equally spaced, there is no guarantee that the set of solutions of the variational inequality problems associated with these weight vectors is well distributed among the set of vector equilibria. Third, the modified projection method and some recent improvements [START_REF] Bigi | A successive linear programming algorithm for nonsmooth monotone variational inequalities[END_REF][START_REF] Han | A new modified Gold Stein-Levitin-Dolyak projection method for variational inequality problems[END_REF][START_REF] Mastroeni | Gap functions and descent methods for Minty variational inequality[END_REF][START_REF] Solodov | A new projection method for variational inequality problems[END_REF][START_REF] Wand | Incremental Constraint Projection Methods for Variational Inequalities[END_REF] converge only under a certain monotonicity or generalized monotonicity property, which generally is not satisfied by network cost functions. This is illustrated in Example 4.3.6.

Example 4.3.4 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ), two criteria: travel time and travel cost, two available paths: P w = {p 1 , p 2 } with the travel demand d w = 30. Assume that travel time and travel cost functions on the paths are linear and are given as follows c p1,1 (y) = y p1 + 2y p2 c p2,1 (y) = y p1 + 6y p2 c p1,2 (y) = 6y p1 + 2y p2 c p2,2 (y) = 6y p1 + 8y p2 .

We tested our program for the zero tolerance ǫ = 0 and q = 2 which yields 5 initial points.

The results are displayed in the table below. We remark that starting from the first four initial points our algorithm finds no vector equilibrium because after some iterations either the value ψ k (y k ) is almost the same as α k-1 at

Step 6 or the value ψ k (y k ) is almost the same as ψ k (u k ) at Step 7, which enforces us to go to Step 4 to choose another initial point to restart. Moreover, when the tolerance is strictly positive, the program runs much faster. For instance with ǫ = 10 -4 , the algorithm finds two vector ǫ-equilibria in 0.069872 seconds, one of which is (30, 0) T and the other is very near to it.

To apply the scalarization method of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] we solve the following scalarized variational inequality problem: Find y ∈ K such that

F (y) T , y -y ≧ 0, ∀y ∈ K,
where

F (y) = (α(y 1 + 2y 2 ) + (1 -α)(6y 1 + 2y 2 ), α(3y 1 + 6y 2 ) + (1 -α)(9y 1 + 8y 2 )
) and α ∈ (0, 1). Since F is monotone and Lipschitz continuous on K, the modified projection method is convergent. For any weight vector (α, 1α), it yields exactly the unique solution (30, 0) T of the problem. The CPU time to obtain the vector equilibrium by this method and the one by our method are almost the same.

In the following example, we shall see that the method by scalarization is slower in comparison with our method and it produces a not very well distributed set of equilibria. With q = 10 we have 21 initial points. Using the algorithm (A) we obtain 9 vector equilibria in 0.293389 seconds.

The scalarization method of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] consists of solving the following variational inequality problem: Find y ∈ K such that F (y) T , yy ≧ 0, ∀y ∈ K, where

F (y) T = α (3y p1 + y p2 ) + (1 -α) (5y p1 + 3y p2 ) α (y p1 + y p2 ) + (1 -α) (3y p1 + 5y p2 ) with α ∈ (0, 1) .
Since the function F is monotone and Lipschitz continuous, the modified projection method to solve this variational inequality problem is applied and produces a vector equilibrium for each weight vector (α, 1α) with α ∈ (0, 1). We performed this method for the initial point (3, 7) T and 21 weight vectors from the family It can be seen that the set of all vector equilibria is the segment between (0, 10) T and (5, 5). The vector equilibrium sets obtained by the two approaches are graphically presented below. The set obtained by our method is uniformly distributed, while the set obtained by the scalarization method is getting more condensed as we are approaching the point (5, 5) T .

In the next example the travel time and travel cost functions are nonlinear. The scalarization method of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] fails in finding even one equilibrium because the function defining the corresponding variational inequality is not monotone, while our algorithm works quite well and gives a satisfactory result. The variational inequality problem of the scalarization method of [START_REF] Nagurney | A multiclass, multicriteria traffic network equilibrium model[END_REF] is the following: Find y ∈ K such that F (y) T , yy ≧ 0, ∀y ∈ K, where

F (y) T =   α y 2 p1 + y 2 p2 + y 3 3 + (1 -α) (2y p1 + 5y p2 + 3y p3 ) α 8y p1 y p2 + y 2 p2 + (1 -α) (y p2 + 10y p3 ) α y p1 + y 2 p2 + y 3 p3 + (1 -α)10y 3 p3   with α ∈ (0, 1).
It is clear that this function is Lipschitz, but not monotone on K. We run a program to solve it by starting from the point (5, 5, 8) T and taking weight vectors from the family .

However, after 549.238187 seconds no solution is found. In this example the modified projection algorithm does not converge.

We have also tested our program for a number of networks with more than three paths connecting an O/D pair. Our experience is that when the cost functions are linear both the scalarization method and our method work well with advantage in computing time of our method, and when the cost functions are not linear, in most cases the scalarization method is not convergent. For instance in one test with 6 paths we used 456 initial points and found 2 equilibrium flows in about two minutes, and in another test with 7 paths we used 6182 initial points and found 33 equilibrium flows in about 25 minutes. In both tests the scalarization method is not convergent and yields no equilibrium.

As we already mentioned at the beginning of this section, not every vector equilibrium of a multi-criteria network can be obtained by linear scalarization. Here is an example. Let us consider the feasible flow y * = (3, 2, 2) T . It is clear that it is a vector equilibrium. We claim that whatever a vector weight (α, 1α) be chosen, this flow cannot be an equilibrium of the network equipped with the scalarized cost functions (α, 1α)c i , where c p1 (y) = (c p1,1 (y), c p1,2 (y)) T , c p2 (y) = (c p2,1 (y), c p2,2 (y)) T and c p3 (y) = (c p3,1 (y), c p3,2 (y)) T . In fact, let α ∈ (0, 1). We know that a feasible flow is an equilibrium of the network with the scalar cost functions (α, 1α)c pi , p i ∈ P w if and only if it solves the following variational inequality problem

(α, 1 -α)C(y)(y -y) T ≧ 0, ∀y ∈ K, (4.20)
where C(y) = 4y p1 + 3 3y p1 + 1 4y p1 + 5 3y p1 + y p2 + y p3 + 2 3y p1 + 2y p2 + y p3 + 5 3y p1 + y p2 + y p3 + 1 .

By setting y = y * = (3, 2, 2) T ∈ K, inequality (4.20) is equivalent to

15 (y p1 -3) + (20 -10α) (y p2 -2) + (14 + 3α) (y p3 -2) ≧ 0, ∀y ∈ K.
It is easy to see that this latter inequality cannot hold for α ∈ (0, 1), for instance with y = (4, 2, 1) T one has α ≦ 1/3 in contradiction with α ≧ 5/7 when y = (0, 0, 7) T . Thus, for any α ∈ (0, 1), y * cannot be a solution of (4.20).

Smoothing the objective function

The function H+ we defined in Section 4 admits the following analytic approximations

Hν (x) = l i=1 1 + tanh(νx i ) 2 e for ν ≧ 1,
which produce also smooth approximations of the objective function ψ when the cost functions are smooth:

ψ ν (y) := p∈Pw,w∈W y p p ′ ∈Pw [c p (y) -c p ′ (y)] T Hν [c p (y) -c p ′ (y)].
The corresponding optimization problems, denoted (P 2 ν ), are given below minimize ψ ν (y) subject to y ∈ K.

Note that unlike ψ, the function ψ ν may take negative values on K and an optimal solution of (P 2 ν ) is not necessarily a weak vector equilibrium. Then for every flow y = (y p1 , y p2 ) T with y p1 + y p2 = 10 we have

ψ 1 (y) = 2α(y)y p1 1 + tanh(α(y)) 2 2 -2α(y)y p2 1 + tanh(-α(y)) 2 2 = 2α(y)y p1 1 + tanh(α(y)) 2 2 + 1 + tanh(-α(y)) 2 2 -20α(y) 1 + tanh(-α(y)) 2 2 .
It is clear that ψ 1 (0.3, 9.7) < ψ 1 (0, 10) < 0, which proves that the optimal value of (P2 1 ) is strictly negative and at every optimal solution y = (y p1 , y p2 ) T one has y p1 > 0, while c p1 (y) > c p2 (y). Hence optimal solutions of (P2 1 ) cannot be weak vector equilibria.

Theorem 4.3.9 Assume that the cost functions c p1 , ..., c pm are continuous. If for every ν ≧ 1, y ν ∈ K is an optimal solution of (P 2 ν ), then every cluster point y of the sequence {y ν } ν≧1 is a weak vector equilibrium.

Proof. We keep the notations D and T defined in the proof of Proposition 4.2.7 and conduct the proof by contradiction. Suppose that y is not a weak vector equilibrium. There exist some w ∈ W and p i , p j ∈ P w such that y pi > 0 and c pi (y)c pj (y) > 0.

(4.21)

Claim 1. There exists some δ > 0 and ν 0 ≧ 1 such that

ψ ν (y ν ) ≧ δ for all ν ≧ ν 0 . (4.22)
To prove this claim let us fix a small ǫ > 0 and consider any two paths p, p ′ ∈ P w for w ∈ W . Denote

γ ν (t) := 1 + tanh(νt) 2
β p,p ′ (y ν ) := y ν p l r=1 γ ν (c p,r (y ν ) -c p ′ ,r (y ν )) c p (y ν ) -c p ′ (y ν ), e .
We distinguish three possible cases concerning the components c p,r (y)c p ′ ,r (y), r = 1, ..., l of the vector c p (y)c p ′ (y).

Case 1: c p,r (y)c p ′ ,r (y) > 0. By continuity there exists some ν 1 ≧ 1 such that

c p,r (y ν ) -c p ′ ,r (y ν ) ≧ 1 2 (c p,r (y) -c p ′ ,r (y)) , γ ν (c p,r (y ν ) -c p ′ ,r (y ν )) ≧ 1 4 (4.23)
for all ν ≧ ν 1 . If in addition y p > 0 and c p (y)c p ′ (y) > 0, then there is ν ′ 1 ≧ ν 1 such that

y ν p ≧ 1 2 y p , β p,p ′ (y ν ) ≧ 1 4 l+1 y p c p (y) -c p ′ (y), e (4.24)
for every ν ≧ ν ′ 1 . Case 2: c p,r (y)c p ′ ,r (y) = 0. Again, by continuity there exists some ν 2 ≧ 1 such that

|c p,r (y ν ) -c p ′ ,r (y ν )| ≦ ǫ for ν ≧ ν 2 . (4.25)
In particular, if c p (y)c p ′ (y) ≧ 0 and c p (y)c p ′ (y) ≯ 0, then there exists ν ′ 2 ≧ ν 2 such that

β p,p ′ (y ν ) ≧ -Dlǫ for ν ≧ ν ′ 2 . (4.26)
Case 3: c p,r (y)c p ′ ,r (y) < 0. As in the first case, one may find some ν 3 ≧ 1 such that

c p (y ν ) -c p ′ (y ν ) ≦ 1 2 (c p,r (y) -c p ′ ,r (y)) , γ ν (c p,r (y ν ) -c p ′ ,r (y ν )) ≦ ǫ for ν ≧ ν 3 .
We deduce that if c p (y)c p ′ (y) 0, then there exists some ν ′ 3 ≧ ν 3 such that

β p,p ′ (y ν ) ≧ -2lDT ǫ for ν ≧ ν ′ 3 . (4.27)
Let us now evaluate ψ ν (y ν ) by using (4.24-4.27). We have

ψ ν (y ν ) = p∈Pw,w∈W p ′ ∈Pw β p,p ′ (y ν ).
We decompose this sum into three sums 1 , 2 and 3 . The first sum 1 collects all terms β p,p ′ (y ν ) with p, p ′ ∈ P w for some w ∈ W such that c p (y)c p ′ (y) > 0. The second sum 2 collects all terms β p,p ′ (y ν ) with p, p ′ ∈ P w for some w ∈ W such that c p (y)c p ′ (y) ≧ 0, but c p (y)c p ′ (y) ≯ 0, and the last sum 3 contains all terms β p,p ′ (y ν ) with p, p ′ ∈ P w for some w ∈ W such that c p (y)c p ′ (y) 0. We may choose ν ′ 1 , ν ′ 2 and ν ′ 3 depending on ǫ so that the relations (4.24-4.27) hold true for all components of the vectors c p (y)c p ′ (y), p, p ′ ∈ P w and w ∈ W . It follows from the hypothesis (4.21) that the sum 1 contains β pi,pj (y ν ) and the other terms of this sum are positive for ν large. Moreover, in view of (4.24), there exists ν 4 ≧ ν ′ 1 such that to obtain q 0 and then set δ = 1 4 l+2 y pi c pi (y)c pj (y), e to satisfy Claim 1. Claim 2. Let y * ∈ K be a vector equilibrium. Then lim ψ→∞ ψ(y * ) = 0. Indeed, since y * is a vector equilibrium, we have y * p > 0, p ∈ P w , w ∈ W only when either c p (y)c p ′ (y) = 0 or c p (y)c p ′ (y) 0 for every p ′ ∈ P w . In the first case,

y * p [c p (y * ) -c p ′ (y * )] T Hν [c p (y * ) -c p ′ (y * )] = 0. (4.31)
In the second case, there is some r ∈ {1, ..., l} such that c p,r (y * )c p ′ ,r (y * ) < 0. Because and, in view of Claims 1 and 2, we arrive at a contradiction that δ ≦ 0. The proof is complete.

We have used the Matlab Global Optimization ToolBox to find optimal solutions of (P2 ν ), ν = 1, • • • , 10 for Examples 4.3.5 and 4.3.6. The numerical results are encountered below. For Example 4.3.5 we chose three initial points (0, 10) T , (5, 5) T and (10, 0) T and obtained corresponding optimal solutions, which are all vector equilibrium. Initial point (0, 10) T (5, 5) T (10, 0) [START_REF] Dafermos | A multicrieria route-mode choice traffic equilibrium model[END_REF][START_REF] Bigi | A successive linear programming algorithm for nonsmooth monotone variational inequalities[END_REF], 0) T , (0, 12, 6) T and (6, 6, 6) T . By using the first initial point, for ν = 1, the optimal solution is (7.0158, 2.9657, 8.0185) T and for every ν = 2, • • • , 10 we arrive at the same optimal solution (7.0178, 2.9657, 8.0165) T . With the second and the third initial points the toolbox produced the same optimal solutions for every ν = 1, • • • , 10 :

(0.9675, 13.9921, 3.0404) T and (4.5458, 4.5046, 8.9496) T .

Fortunately, they are all vector equilibria. This, however, is not true in general as the next example shows. With q = 1 we have 462 initial points to start with in finding optimal solutions of (P 2 ν ). For ν = 10 the Global Optimization Toolbox produced 403 local optimal solutions and 59 global optimal solutions. Direct checking proves that there are 206 solutions which are vector equilibria. Meanwhile using the algorithm (A) for the problem (P2) with the same initial points we obtained one vector equilibrium (37.5, 4.1667, 4.1667, 8.3333, 16.6667, 29.1667) T .

Robust equilibrium

In this section we are interested in vector equilibrium flows that are not affected by small perturbation of the cost functions. We shall write (G, C) to indicate the network G equipped with the vector cost functions c p (y), p ∈ P . Let y be a feasible path flow. We say that it is a robust vector equilibrium if there is some ǫ > 0 such that it is a vector equilibrium of the network (G, C) for any perturbed cost functions cp satisfying c p (y)cp (y) ≦ ǫ, p ∈ P . In other words, y is a robust vector equilibrium if there is ǫ > 0 such that for every O/D pair w ∈ W , for every couple of paths p, p ′ ∈ P w and functions cp , cp ′ with cp (y)c p (y) ≦ ǫ and cp ′ (y)c p ′ (y) ≦ ǫ one has implication cp (y)cp ′ (y) ≥ 0 =⇒ y p = 0.

The biggest value of ǫ for which the above implication holds is called radius of robustness at y. In robust optimization one considers a parametric maximization problem and defines a robust feasible solution as a solution that is feasible for all instances of parameter. A robust feasible solution is optimal if it maximizes the worst value of the objective function over the robust feasible set (see [START_REF] Ben-Tal | Robust Optimization[END_REF]). The concept of robust equilibrium we defined above can be considered as a particular version of robust solutions in optimization when the constraint set does not depend on the parameter and all instances of the objective function realize its maximum at the solution under consideration. It is clear from the definition that a robust vector equilibrium is a vector equilibrium, but not all vector equilibria are robust. Moreover, as we know a multi-criteria network with continuous cost functions always has a vector equilibrium, but this is not true for robust equilibrium. For instance, the unique vector equilibrium y = (30, 0) T of the network described in Example 4.3.4 is not robust. Indeed, a small perturbation of c p1 by

c ǫ 1 (y) = y p1 + 2y p2 + ǫ 6y p1 + 2y p2 with ǫ > 0 makes y non-equilibrium.
We shall make use of the following notation: for w ∈ W and y ∈ K, I w (y) denotes the set of indices i such that p i ∈ P where χ {0} is the characteristic function of {0}, that is χ {0} (t) = 0 if t = 0 and χ {0} (t) = 1 if t = 0.

Theorem 4.4.1 Let y ∈ K be a vector equilibrium of G. The following statement are equivalent.

(i) y is robust.

(ii)y is an optimal solution of the following optimization problem, denoted (P

′ 1 )
minimize ρ(y)

subject to y ∈ K,
and the optimal value of this problem is equal to zero. (iii)There exists an ǫ > 0 such that for every w ∈ W, p ∈ P w with y p > 0, one has

(c p (y) -R l + ) ∩ ( Cw (y)\{c p (y)}) = ∅ for all cpi , p i ∈ P w satisfying cpi (y) -c pi (y) ≦ ǫ.
Proof. To prove implication (i) ⇒ (ii), let y ∈ K be a robust vector equilibrium. We know by Theorem 4.1.1 that φ(y) = 0. Suppose to the contrary that ρ(y) > 0. There are some w ∈ W and p ∈ P w such that

y p   d[c p (y), Min(C w (y))] + i∈Iw(y),pi =p χ {0} ( c p (y) -c pi (y) )   > 0.
In particular, y p > 0 and because d[c p (y), Min(C w (y))] = 0, there is some i ∈ I w (y) such that p i = p and c p (y) = c pi (y). For every ǫ > 0 define

cpj = c pj if p j = p c p + (ǫ/l)e if p j = p.
It is clear that cpjc pj ≦ ǫ, p j ∈ P and y is not a vector equilibrium of (G, C) because cp (y) > cpi (y) while y p > 0. For implication (ii) ⇒ (iii) assume ρ(y) = 0 and y p > 0 for some p ∈ P w , w ∈ W . We deduce that c p (y) ∈ Min(C w (y)) and

i∈Iw(y),pi =p χ {0} ( c p (y)-c pi (y) ) = 0. In particular, c pi (y) / ∈ c p (y) -R l + for all p i ∈ P w , p i = p. (4.33)
Then we can find

ǫ p > 0 such that cpi (y) / ∈ cp (y) -R l + (4.34)
for all p i ∈ P w , p i = p, and cpi (y)c pi (y) ≦ ǫ p and cp (y)c p (y) ≦ ǫ p . It remains to choose ǫ = min{ǫ p : p ∈ P, y p > 0} to obtain (iii).

In order to prove the implication (iii) ⇒ (i), we observe that for the perturbed cost functions satisfying (iii), cp (y) ∈ Min Cw (y) for every p ∈ P w with y p > 0. By this, y is a vector equilibrium of the network (G, C). Consequently, y is a robust vector equilibrium.

Corollary 4.4.2 Assume that y is a vector equilibrium and for every w ∈ W the elements c pi (y), i ∈ I w (y) are all distinct from each other. Then y is a robust vector equilibrium.

Proof. Under the hypothesis of the corollary, one has i∈Iw(y),pi =p χ {0} ( c p (y)c pi (y) ) = 0 for every p ∈ P . Therefore, ρ(y) = 0 and by Theorem 4.4.1, y is robust.

Let y be a given feasible flow of G. We denote by C(y) the set of l × m-matrices of continuous cost functions on K such that y is a vector equilibrium of (G, C), C ∈ C(y). It is clear that C(y) is nonempty, for it contains all constant functions. We consider the subset C R (y) consisting of all C ∈ C(y) such that y is a robust vector equilibrium of (G, C). It is clear that C R (y) is a proper subset of C R (y), for y is not robust of (G, C) when C is a constant cost function and G has at least two paths joining an O/D pair. We shall see that

C R (y) is dense in C(y). Lemma 4.4.3 Let q 1 , • • • , q m ∈ R l with q 1 = • • • = q k ∈ Min{q 1 , • • • , q m }
for some k ≦ m and q k = q j for j > k. Then for every ǫ > 0 there exists q1 ,

• • • , qk such that (i) qi -q i ≦ ǫ for i = 1, • • • , k (ii) qi -qj / ∈ R l + ∪ (-R l + ), i, j ∈ {1, • • • , k}, i = j (iii)Min{q 1 , • • • , qk , q k+1 , • • • , q m } = {q 1 , • • • , qk } ∪ (Min{q 1 , • • • , q m })\{q 1 , • • • , q k } .
Proof. Let ǫ > 0 be given. As before e i ∈ R l denotes the unit ith vector and e the vector of ones. Since q 1 = • • • = q k = q j for j > k, there exists a positive ǫ ′ ≦ ǫ/(3l) such that

q i -ǫ ′ e / ∈ q j -R l + for all q j ∈ Min{q 1 , • • • , q m }, j > k, i = 1, • • • , k. (4.35) Define qi = q i -ǫ ′ e + ǫ ′ i k e 1 + (1 - i k )e l , i = 1, • • • , k. Then qi -q i = ǫ ′ -e + i k e 1 + (1 - i k )e l ≦ 3lǫ ′ ≦ ǫ, which prove (i). Moreover for i, j ∈ {1, • • • , k}, i = j one has qi -qj = ǫ ′ i -j k e 1 + j -i k e l / ∈ R l + ∪ (-R l + )
which is (ii). Finally, since q i ∈ Min{q 1 , • • • , q m } we have q j / ∈ q i -R l + and hence q j / ∈ qi -R l + for all j > k. This and (ii) prove that qi Proof. The fact that C R (y) is open is immediate from the definition of robust vector equilibrium. To prove the density let ǫ > 0 and assume y is a vector equilibrium of (G, C) for some C ∈ C(y), but it is not robust. In view of Theorem 4.4.1 there exist some w ∈ W and p i ∈ P w such that y pi > 0 and the set {j ∈ I w (y) : c pi (y) = c pj (y) ∈ MinC w (y)} consists of at least two elements. Applying Lemma 4.4.3 to the set C w (y) we find cost functions cp , p ∈ P such that cp (y)c p (y) ≦ ǫ for all p ∈ P , all elements of MinC w (y) are distinct from each other and I w (y) is unchanged for C(y). We deduce that d[c p (y), Min C(y)] = 0 and χ {0} ( cpi (y)cpj (y) ) = 0 for j = i and j ∈ I w (y). This argument applied to all path on which the flow y has a nonzero component, we deduce

∈ Min{q 1 , • • • , qk , q k+1 , • • • , q m }, i = 1, • • • , k. For j > k such that q j ∈ Min{q 1 , • • • , q m } one observes that q j -R l + ⊆ q j + ǫ ′ i k e 1 + (1 - i k )e l -R l + and deduces from (4.35) that qi / ∈ q j -R l + , for i ∈ {1, • • • , l}. By this q j belongs to the set Min{q 1 , • • • , qk , q k+1 , • • • , q m }. For j > k such that q j ∈ Min{q 1 , • • • , q m } we find some q i ∈ Min{q 1 , • • • , q m } such that q i ≤ q j . If i > k, then it is clear that q j ∈ Min{q 1 , • • • , qk , q k+1 , • • • , q m }. If i ≦ k, then we have qi ≤ q i ≤ q j , which again implies that q j ∈ Min{q 1 , • • • , qk , q k+1 , • • • , q m }. By this (iii) follows.
ρ(y) = p∈Pw,w∈W y p   d[c p (y), Min Cw (y)] + i∈Iw(y),pi =p χ {0} ( cp (y) -cpi (y) )   = 0.
which, in view of Theorem 4.4.1, implies that y is robust for (G, C).

When a robust vector equilibrium y ∈ K is given, we wish to know how far we can perturb the cost function C so that y remains equilibrium for the perturbed costs. In other words we wish to find the radius of robustness at this equilibrium. For a feasible flow y ∈ K we denote I + w (y) = {i ∈ I w (y) : y pi > 0}.

Corollary 4.4.5 Let y ∈ K be a robust vector equilibrium. Then the radius of robustness at y is computed by

r(y) = √ l 2 min w∈W,i∈I + w (y) min p ′ ∈Pw\{pi} (c p ′ (y) -c pi (y)) +
where (c p ′ (y)c pi (y)) + denotes the positive part of the vector c p ′ (y)c pi (y).

Proof. It follows from the proof of Theorem 4.4.1 that y is a vector equilibrium of (G, C) as soon as (4.34) is true which is equivalent to

(c pi (y) -cp (y)) + = 0,
where p ∈ P w with y p > 0 and p i ∈ P w . Let ǫ < r(y) and cpi (y

) -c pi (y) ≤ ǫ, cp (y) - c p (y) ≤ ǫ, one has (c pi (y) -cp (y)) + ≧ [(c pi (y) -ǫe) -(c p (y) + ǫe)] + ≥ 0,
proving that y is a vector equilibrium of (G, C). Let ǫ > r(y) and let

r(y) = √ l 2 (c p ′ (y) -c pi (y)) + for some i ∈ I + w (y), p ′ ∈ P w \{p i }. Define a perturbed cost C by cp (y) =    c p (y) if p = p ′ , p = p i c pi (y) + (ǫ/ √ l)e if p = p i c pi (y) -(ǫ/ √ l)e if p = p ′ .
Then cp (y)c p (y) ≦ ǫ for all p ∈ P and cp ′ (y)cpi (y) = c p ′ (y)c pi (y) -2ǫ ≤ 0. Consequently cpi (y) / ∈ Min Cw (y). This and the fact that y pi > 0 implies that φ(y) > 0. By Theorem 4.1.1, y is not a vector equilibrium of (G, C).

We complete this section by presenting an algorithm to find robust vector equilibria among the vector equilibria obtained by the algorithm (A) of Section 5 and to compute the radius of robustness at it.

Description of the algorithm

We denote E q the set of vector equilibria, S×R = {(y, r(y)) : y is robust equilibrium and r(y) is radius of robustness corresponding with robust equilibrium}.

Step 1. Choose a vector equilibrium y 1 from E q to start. Set k = 1, S = ∅ and R = ∅.

Step 2. Determine I w (y k ). Calculate ρ(y k ) = p∈Pw,w∈W

y k p i∈Iw(y k ),pi =p χ {0} ( c p (y k ) -c pi (y k ) ).
If ρ(y k ) = 0, then return to Step 1 and choose another vector equilibrium from E q to restart the algorithm until no element of E q left. If ρ(y k ) = 0, then determine I + w (y k ) and calculate

r(y k ) = √ l 2 min w∈W,i∈I + w (y k ) min p ′ ∈Pw\{pi} (c p ′ (y k ) -c pi (y k )) + .

Equilibrium in a multi-criteria traffic network with capacity constraints

The purpose of this chapter is to study a single-product multi-criteria traffic network with capacity constraints. We construct an optimization problem the solutions of which are exactly the set of equilibria of the model. We establish some important generic continuity and differentiability properties of the objective function and give the formula to calculate the gradient of the objective function. Then we apply the algorithm proposed in Chapter 4 with some modifications in order to obtain a subset of optimal solutions which are equilibria of our model. Numerical examples are also presented to illustrate our approach.

Single-product multi-criteria traffic network with capacity constraints

We consider a traffic network G = [N, A, W ] that consists of a set of nodes N , a set of n directed arcs or links A = {a 1 , • • • , a n } and a set W of r origin/destination (O/D for short) pairs of nodes w = (x, x ′ ) with x, x ′ ∈ N such that there is a path from x to x ′ . For a pair of nodes w = (x, x ′ ), the set of available paths from the origin x to the destination x ′ is denoted by P w , and the set of all available paths of the network is denoted by

P = {p 1 , • • • , p m } = ∪ w∈W P w .
As in the preceding chapter, y p denotes the traffic flow on path p ∈ P . We assume throughout this chapter that the demand d w of the traffic flow for each O/D pair w ∈ W is fixed and there are capacity constraints on each path of the network. Namely, for every p ∈ P we have two nonnegative numbers l p ∈ R and u p ∈ R with l p < u p that represent the lower and the upper capacity constraint on thepath p. A path flow y is said to be feasible if it satisfies the capacity constraints and the conservation of flows equations:

l p ≦ y p ≦ u p ∀ p ∈ P ; (5.1) p∈Pw y p = d w ∀w ∈ W. (5.2)
The set of all feasible path flows is denoted K. Assume further that a vector cost function ĉa is given on each arc a ∈ A, depending on the traffic arc flow z and taking values in a finite dimensional space R l with l ≧ 2. Then the vector cost function c p on path p depends on the path flow y and is computed by

c p (y) = a∈A ĉa (z)δ ap , (5.3)
as we already knew in the model without capacity constraints in Chapter 4. We recall that C(y) denotes the l × m-matrix, the columns of which are c p , p ∈ P and Ĉ(z) denotes the l × n-matrix, the columns of which are ĉa , a ∈ A. Then these matrices are linked by the formula C(y) = Ĉ(z)∆, with ∆ the incident matrix. In this chapter we study the concept of equilibrium introduced in [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF] which is a vector version of Wardrop's famous user principle.

Definition 5.1.1 A feasible path flow y is said to be a vector equilibrium (respectively a weak vector equilibrium) of G if for every O/D pair w ∈ W and for every couple of paths p, p ′ ∈ P w one has implication

c p (y) -c p ′ (y) ≥ 0 (respectively c p (y) -c p ′ (y) > 0) =⇒ either y p = l p or y p ′ = u p ′ .
It is clear that every vector equilibrium is weak vector equilibrium, and the converse is not true in general. When l p = 0 and u p = +∞, that is, there are no capacity constraints, the aforementioned definition coincides with the one given in Definition 4.0.25.

Equivalent optimization problem

In this section we construct an optimization problem the optimal solutions of which are equilibria of the traffic network with capacity constraints we described above. For every feasible flow y define

ψ(y) := p,p ′ ∈Pw,w∈W (y p -l p )(u p ′ -y p ′ )[c p (y) -c p ′ (y)] T H + [c p (y) -c p ′ (y)].
where the function H + is a vector version of the Heaviside Step function, which was given in Chapter 4. Since in the case of network without capacity constraints the upper capacity constraint is set equal to +∞, the function ψ introduced in Chapter 4 cannot be obtained from this function. However, most of properties of that function we established in Chapter 4 remain true. The following theorem is important for the further developments.

Theorem 5.2.1 Let ȳ be a feasible flow. The following statements are equivalent:

(i) ȳ is a vector equilibrium.

(ii) ȳ is an optimal solution of the following problem, denoted (P):

minimize ψ(y)
subject to y ∈ K and the optimal value of this problem is zero.

Proof. Let ȳ be a vector equilibrium. Since ψ(y) ≧ 0 for every y ∈ K, as before, it suffices to prove ψ(ȳ) = 0 in order to deduce (ii). Let p ∈ P w , w ∈ W . Consider the term

(ȳ p -l p )(u p ′ -ȳp ′ )[c p (ȳ) -c p ′ (ȳ)] T H + [c p (ȳ) -c p ′ (ȳ)], denoted b p,p ′ . If c p (ȳ) -c p ′ (ȳ)
≥ 0 for some p ′ ∈ P w , then by definition, either ȳp = l p or ȳp ′ = u p ′ . If c p (ȳ)c p ′ (ȳ) = 0 for some p ′ ∈ P w , it is clear that the corresponding term of the above sum is zero. If c p (ȳ)c p ′ (ȳ) ≧ 0 for some p ′ ∈ P w , then H + [c p (ȳ)c p ′ (ȳ)] = 0. Therefore b p,p ′ = 0. Consequently, ψ(ȳ) = 0 as requested. Conversely, assume ȳ solves (P) and ψ(ȳ) = 0. It follows that b p,p ′ = 0 for every p ∈ P . If for some p and p ′ from P w , w ∈ W one has c p (ȳ) -

c p ′ (ȳ) ≥ 0, then [c p (ȳ) -c p ′ (ȳ)] T H + [c p (ȳ) -c p ′ (ȳ)] > 0.
Consequently, either ȳp = l p or ȳp ′ = u p ′ . We deduce that ȳ is a vector equilibrium.

By using the same method of proof we may establish a similar result for weak vector equilibria. For this purpose let us define

ψ w (y) := p,p ′ ∈Pw,w∈W (y p -l p )(u p ′ -y p ′ )[c p (y) -c p ′ (y)] T H w + [c p (y) -c p ′ (y)]
for every y ∈ K, and consider the optimization problem (P w ):

minimize ψ w (y) subject to y ∈ K,
where H w + is defined by

H w + (x) = e if x > 0 0 else.
Theorem 5.2.2 Let ȳ be a feasible flow. Then ȳ is a weak vector equilibrium if and only if it solves the problem (P w ) with the optimal value equal to zero.

Proof. Apply the method of proof of Theorem 5.2.1.

Finally we observe that the conclusion of Theorem 5.2.1 remains true when the function H + defining the objective function of (P) is substituted by the function

H+ (x) = ( l i=1 h+ (x i ))e for all x ∈ R l ,
where h+ (t) = h + (t) for all t ∈ R \ {0} and h+ (0) = 1/2.

Generic differentiability and local calmness of the objective function

We apply the methods of proof of Chapter 4 to establish some properties of the function ψ. Proof. The general term of this ψ is obtained from the general term of the function ψ of Chapter 4 by substituting y p by (y pl p )(u py p ) which is continuous (or locally Lipschitz/differentiable). Therefore the proof of Theorem 4.2.4 applies. Theorem 5.3.2 Assume that the vector cost functions c pi , i = 1, • • • , m are differentiable. Then for every point y outside of some nowhere dense subset and for every path p i , there exists a subset J i (y) ⊆ I w(i) such that Proof. The same proof of Theorem 4.2.6 goes through for (i) and (ii). The formula given in (iii) is obtained by a direct calculation.

(i) c pi (y) ≥ c pj (y) for every j ∈ J i (y) (ii)ψ(y) = m i=1 (y pi -l pi ) j∈Ji(y) u pj -y pj c pi (y) -c pj (y) , e (iii)
We notice that in general the objective function of the problem (P) is not continuous. Again we are able to prove its calmness at a point that is a vector equilibrium.

Proposition 5.3.3 Assume that the vector cost functions c p1 , • • • , c pm are continuous. Then the function ψ is continuous at every vector equilibrium. If in addition c p1 , • • • , c pm are locally calm at a vector equilibrium, then ψ is also locally calm there.

Proof. Let y ∈ K be a vector equilibrium of G. Assume that c p1 , • • • , c pm are continuous on K and locally calm at y. The case where the function ψ is merely continuous is proven by a similar argument. We wish to show that there exist some δ > 0 and κ > 0 such that |ψ(y)ψ(y)| ≦ κ yy for every y ∈ K with yy ≦ δ. Because ψ takes nonnegative values and as y is equilibrium, by Theorem 5.2.1, ψ(y) = 0, the above inequality is equivalent to ψ(y) ≦ κ yy .

(

Recall that for i ∈ {1, ..., m}, w(i) denotes the O/D pair connected by the path p i and P w(i) denotes the set of all paths connecting this O/D pair. We make also use of the following notations

I 0 = {i ∈ {1, • • • , m} : ȳpi = l pi } I + = {i ∈ {1, • • • , m} : l pi < ȳpi ≦ u pi } D = max{d w : w ∈ W } T = max{ c pi (y) : y ∈ K, i = 1, • • • , m} U = max{ u pi (y) : y ∈ K, i = 1, • • • , m}.
The following inequality is clear y pi ≦ y ≦ D (5.5)

for every y ∈ K and p i ∈ P. Consider the terms

g i (y) := (y pi -l pi ) pj ∈P w(i) (u pj -y pj )[c pi (y) -c pj (y)] T H + [c pi (y) -c pj (y)] for i = 1, ..., m. Observe first that 0 ≦ (u pj -y pj )[c pi (y) -c pj (y)] T H + [c pi (y) -c pj (y)] ≦ 2lT U,
for all p i , p j ∈ P and y ∈ K. Therefore, if i ∈ I 0 , then In the first case, there exists some p i ∈ P w(i) such that c pi (y) ≥ c pj (y). Due to the continuity hypothesis, there exists some δ ′ i > 0 such that c pi (y) ≥ c pj (y) for all y ∈ K with y -y ≦ δ ′ i . In the second case, also due to the continuity hypothesis, there exists some δ ′′ i > 0 such that c pi (y) c pj (y) for all y ∈ K with y-y ≦ δ ′′ i . In the third case, by the calmness hypothesis, there are some constants δ ′ > 0 and κ ′ > 0 such that

|g i (y) -g i (y)| = g i (y) ≦ 2mlT U (y pi -l pi ) ≦ 2mlT U y -y . ( 5

Generating vector equilibrium flows

In this section we present an algorithm based on the one in Chapter 4 with some modifications to obtain a subset of vector equilibria of the network. We also present some numerical examples to illustrate the algorithm.

Description of the algorithm

Assume that W consists of r elements w 1 , • • • , w r in the network and for each pair w i there are |P wi | paths connecting its origin to its destination. We denote also

I j = {i ∈ {1, • • • , m} : p i ∈ P wj }.
Step 0 (initialization). Choose a positive integer q and a tolerance level ǫ ≧ 0.

Procedure A1.

Step 1. Enter L = (l p ) p∈P and U = (u p ) p∈P . Set

δ j = d wj /(q|P wj |), j = 1, • • • , r. Step 2. Choose (k 1 , • • • , k m ) T ∈ N m satisfying i∈Ij k i = q|P wj |, and l pi ≦ k i .δ j ≦ u pi for i ∈ I j ; j = 1, • • • , r.
Step 3. Store y = (y 1 , • • • , y m ) T in Y 0 where

y i = k i δ j for i ∈ I j , j = 1, • • • , r
and return to Step 2 for other vectors (k 1 , • • • , k m ) unless no one left.

Procedure A2.

Step 4. Choose a feasible flow y 0 from Y 0 to start. Set k = 0,

u k-1 = y k , α k-1 = ∞, Y 0 = Y 0 \ {y 0 } and E ǫ q = ∅.
Step 5.

Compute J i (y k ) = {i ′ ∈ {1, • • • , m} : p i ′ ∈ P w(i) , c pi (y k ) -c p i ′ (y k ) ≧ 0} for every i ∈ {1, • • • , m}. Set ψ k (y) := m i=1 (y pi -l pi ) i ′ ∈Ji(y k ) (u p i ′ -y p i ′ ) c pi (y) -c p i ′ (y), e .
Compute ψ k (y k ). If ψ k (y k ) ≦ ǫ, store y k in E ǫ q and return to Step 4 until no element of Y 0 left. Otherwise go to the next step. We tested our program for the zero tolerance ǫ = 0 and q = 3 which yields 4 feasible initial points. The results are displayed in the table below. We remark that starting from the first two initial points our algorithm finds no vector equilibrium because after some iterations either the value ψ k (y k ) is almost the same as α k-1 at

Step 6 or the value ψ k (y k ) is almost the same as ψ k (u k ) at Step 7, which enforces us to go to Step 4 to choose another initial point to restart. Moreover, when the tolerance is strictly positive, the program runs much faster. For instance with ǫ = 10 -4 , the algorithm finds two vector ǫ-equilibria in 0.053571 seconds, one of which is (20, 10) T and the other is very near to it. With q = 10 we have 11 feasible initial points, we obtain 5 vector equilibria in 0.814601 seconds. It can be seen that the set of all vector equilibria is the segment between (3, 7) T and (5, 5). The vector equilibrium set is graphically presented below.

In the next example the travel time and travel cost functions are nonlinear.

Equilibrium in a multi-product multi-criteria traffic network with capacity constraints

The purpose of this chapter is to study a multi-product, multi-criteria network with capacity constraints in which all products and all criteria are simultaneously considered. We establish existence conditions for strong vector equilibrium and a relationship between strong vector equilibrium and Pareto efficient elements of the value set of the vector cost function. The main attention is paid to constructing equivalent variational inequality problems with the help of particular classes of increasing functions. An algorithm is proposed to solve multicriteria network equilibrium problems and numerical examples are presented to illustrate our approach.

Let us now recall some principal concepts of equilibrium in a multi-product multi-criteria network. Definition 6.0.4 [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] A feasible flow Y is said to be a strong vector equilibrium of the network G if for every w ∈ W and p α , p β ∈ P w one has implication

C pα (Y ) ≥ C p β (Y ) ⇒ either Y pα = L pα or Y p β = U p β .
It is said to be a weak vector equilibrium if for every w ∈ W and p α , p β ∈ P w one has implication

C pα (Y ) ≥ C p β (Y ) ⇒ either Y pα > L pα or Y p β < U p β .
The aforementioned implications were already given in Chapter 3 in which we gave a number of comments on their relations with other concepts of equilibrium.

Existence conditions

It is known that in a single-criterion traffic model, Wardrop's equilibrium exists under rather mild conditions (the continuity of the cost function and the compactness of the feasible set for instance). This, however, is not true in the case of multi-criteria networks. A simple example below gives a network without strong vector equilibrium flows in which the cost function is linear.

Example 6.1.1 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with two available paths: To establish existence conditions for strong vector equilibrium flows we need the concept of elementary flows [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF], which we suggest to call elementary flow variations in reference to the well known concept of elementary variations in the theory of optimal control. A path flow Y of the network G is said to be an elementary flow variation if there are some origin-destination pair w ∈ W and paths p α , p β ∈ P w such that

P w = {p 1 , p 2 }. Assume that d 1 w = y 1 p1 + y 1 p2 = 10, d 2 w = y 2 p1 + y 2 p2 = 10 and l 1 p1 = l 2 p1 = 1 l 1 p2 = 3.5 l 2 p2 = 2 u 1 p1 = u 2 p1 = 10 u 1 p2 = u 2 p2 = 12 c 1 p1 (Y ) = (y 1 p1 , y 1 p1 ) T c 2 p1 (Y ) = (y 2 p1 , y 2 p1 ) T c 1 p2 (Y ) = (3y 1 p2 , 2y 1 p2 ) T c 2 p2 (Y ) = (3y 2 p2 , 2y 2
Y pα = -Y p β Y pi = 0 for p i ∈ P w \{p α , p β }.
From now on, let us fix a path flow Ȳ , write C and cj pi instead of C( Ȳ ) and c j pi ( Ȳ ) if no misunderstanding occurs. We use also upper index r to indicate the rth component of each vector c j pi and set

K + (Y ) = {Y ∈ K : Y -Y is elementary with (Y -Y ) pα ≥ 0 for some p α } ∪ {Y }.
We shall need also the following result (Theorem 5.4 [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF]): If a feasible flow Y is a strong vector equilibrium flow, then it satisfies the following vector variational inequality

       m i=1 c 1 pi,1 (Y pi -Y pi ) . . . m i=1 c q pi,1 (Y pi -Y pi ) . . . . . . . . . m i=1 c 1 pi,l (Y pi -Y pi ) • • • m i=1 c q pi,l (Y pi -Y pi )        / ∈ -R q + l×q \{0} (6.1)
for all Y ∈ K + (Y ). Conversely, if Y is a solution of the above variational inequality and satisfies the following condition: For every origin-destination pair w ∈ W and for every couple of paths p α , p β ∈ P w one has implication

L pα ≤ Y pα and Y p β ≤ U p β ⇒ l k pα < y k pα and y k p β < u k p β for some k ∈ {1, ..., q}, (6.2)
then Y is a strong vector equilibrium flow. We notice that condition (6.2) holds trivially when the network is without capacity constraints, or more generally when the upper bound on each path is sufficiently large with regard to the demand. For instance, it is the case when d j w < u j pi for every p i ∈ P w , j ∈ {1, ..., q}.

Theorem 6.1.2 Assume that the feasible set K is nonempty. The network G admits a weak vector equilibrium flow if the cost function C(.) is continuous with respect to the variables y j p1 , ..., y j pm for some j ∈ {1, ..., q}. Moreover, if C(.) is continuous, then the vector variational inequality (6.1) has a solution, which is also a strong vector equilibrium when it satisfies condition (6.2).

Proof. Without loss of generality we may assume j = 1. We fix a feasible flow y and consider the network G with a single product j = 1 and a single-criterion cost function on path i: f i (z) = l r=1 q s=1 c s pi,r (z, y 2 , ..., y q ). The feasible set K 1 for this model consists of flows z = (z 1 p1 , ..., z 1 pm ) T satisfying the constraints: l 1 pi ≦ z 1 pi ≦ u 1 pi for p i ∈ P = {p 1 , ..., p m } and pi∈Pw z 1 pi = d 1 w for every w ∈ W . By hypothesis the cost function f = (f 1 , ..., f m ) is continuous, and therefore the network admits an equilibrium z in the classical sense:

f α (z) > f β (z) ⇒ either z 1 pα = l 1 pα or z 1 p β = u 1 pα .
We claim that the flow Z = (z, y 2 , ..., y q ) is a weak vector equilibrium flow of the original network. Indeed, it is clear that Z belongs to K. If for some w ∈ W , p α , p β ∈ P w one has C pα (Z) ≥ C p β (Z), then all components of C pα (Z) are bigger than or equal to the corresponding components of C p β (Z), and at least one inequality is strict, which yields f α (z) = l r=1 q s=1 c s pα,r (z, y 2 , ..., y q ) > l r=1 q s=1 c s p β ,r (z, y 2 , ..., y q ) = f β (z). It follows that either z 1 pα = l 1 pα or z 1 p β = u 1 p β , which implies either Z pα > L pα or Z < U p β . This shows that Z is a weak vector equilibrium. To prove the second part of the theorem we consider the following variational inequality problem: Find z ∈ R mq such that φ(z), zz ≧ 0 for every z ∈ Q, where z ∈ Q if and only if z = (y 1 p1 , ..., y q p1 , ..., y 1 pm , ..., y q pm ) for some Y ∈ K, and φ(z) = (φ 1 (z), ..., φ 1 (z), ..., φ m (z), ..., φ m (z)) ∈ R mq for z ∈ Q, in which φ i (z) = q j=1 l r=1 c j pi,r (Y ) with Y generating z as above. Since K is a compact set and φ is continuous by hypothesis, this variational inequality admits a solution. Let y be a feasible flow corresponding to this solution. Then one can check that it is a solution to a vector variational inequality (6.1). Due to the condition (6.2) we may apply Theorem 5.4 of [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] to conclude that y is a strong vector equilibrium flow of the original network.

We notice also that if the condition (6.2) is not satisfied, then a solution of (6.1) is not necessarily a strong vector equilibrium. This is seen by the following example. Then, Y does not satisfy the condition [START_REF] Chen | On vector network equilbrium problems[END_REF]. In fact Y p1 ≥ L p1 , Y p2 ≤ U p2 , and there is not any j ∈ {1, 2} such that y j p1 > l j p1 and y j p2 < u j p2 . And for all Y ∈ K + (Y ) one has

  c 1 p1,1 (Y p1 -Y p1 ) + c 1 p2,1 (Y p2 -Y p2 ) c 2 p1,1 (Y p1 -Y p1 ) + c 2 p2,1 (Y p2 -Y p2 ) c 1 p1,2 (Y p1 -Y p1 ) + c 1 p2,2 (Y p2 -Y p2 ) c 2 p1,2 (Y p1 -Y p1 ) + c 2 p2,2 (Y p2 -Y p2 )   =     5(y 1 p1 -2) 10(y 1 p1 -2) 5(y 2 p1 -10) 10(y 2 p1 -10) 15(y 1 p1 -2) 8(y 1 p1 -2) 15(y 2 p1 -10) 8(y 2 p1 -10)     / ∈ -R 2 + 2×2 \{0}
which shows that Y is a solution of the problem (6.1). However, Y is not a strong vector equilibrium as

C p1 = (c 1 p1 c 2 p1 ) ≥ C p2 = (c 1 p2 c 2 p2 ) but Y p1 = L p1 and Y p2 = U p2 .

Equivalent problems

Equilibrium with respect to a family of increasing functions

Let F be a family of real functions on R l×q . We say that a feasible flow Y is F-equilibrium if for every w ∈ W and p α , p β ∈ P w , one has

Variational inequality problems

Scalarization is a method widely used in the theory of multiple criteria decision making and in vector optimization. It has already been developed in the existing literature [START_REF] Goh | Vector equilibrium problem and vector optimization[END_REF][START_REF] Li | A remark on a standard and linear vector network equilibrium problems with capacity constraints[END_REF][START_REF] Li | A note on vector network equilibrium principles[END_REF] and [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF]. However, all variational inequality problems obtained in these works produce only solutions which are weak equilibrium flows. In this section we employ augmented increasing functions to construct variational inequality problems which are equivalent to the problem of finding strong vector equilibrium flows. For a given feasible flow Y ∈ K, we shall make use of the following notations: We wish to prove that this problem is equivalent to the network equilibrium problem under our consideration in the sense that a feasible flow Y is a strong vector equilibrium if and only if it is a solution to (6.5) under a suitable hypothesis. Lemma 6.2.6 If the function h is increasing with respect to the second variable and if the condition (6.2) is satisfied, then every solution of the variational problem (6.5) is a strong vector equilibrium. Conversely, if the function h satisfies the condition: a b ⇔ h(a, b) ≧ 0, then every strong vector equilibrium is a solution of the variational problem (6.5).

Γ := {(p i , w, j) : j ∈ {1, ..., q}, w ∈ W, p i ∈ P w } A w := p α ∈ P w such that Y pα ≥ L pα B w := p β ∈ P w such that Y p β ≤ U p β
Proof. Suppose that Y is not a strong vector equilibrium. Then there exists w 0 ∈ W and p α0 , p β0 ∈ P w0 such that

C pα 0 ≥ C p β 0 , y pα 0 ≥ L pα 0 , y p β 0 ≤ U p β 0 .
By (6.2), there exists j 0 ∈ {1, ..., q} such that l j0 pα 0 < y j0 pα 0 and y j0 p β 0 < u j0 p β 0

. Construct a flow Y as follows

y j pi =    y j pi if p i ∈ {p α0 , p β0 }, j ∈ {1, ..., q}, or p i ∈ {p α0 , p β0 }, j ∈ {1, ..., q}\{j 0 } y j pi -δ if p i = p α0 , j = j 0 y j pi + δ if p i = p β0 , j = j 0 where 0 < δ ≦ min{y j0 pα 0 -l j0 pα 0 , u j0 p β 0 -y j0 p β 0 }. It is clear that Y is a feasible flow. Moreover, (pi,w,j)∈Γ min pα∈Aw h(C pα , C pi ) y j pi -y j pi = pi min pα∈Aw 0 h(C pα , C pi ) y j0 pi -y j0 pi = min pα∈Aw 0 h(C pα , C pα 0 ) y j0 pα 0 -y j0 pα 0 + min pα∈Aw 0 h(C pα , C p β 0 ) y j0 p β 0 -y j0 p β 0 = δ min pα∈Aw 0 h(C pα , C β0 ) -min pα∈Aw 0 h(C pα , C pα 0 ) ≦ δ min pα∈Aw 0 [h(C pα , C β0 ) -h(C pα , C α0 )] < 0,
in which the last inequality follows from the fact that h(C pα , .) is increasing with respect to the second variable for every fixed C pα . This shows that y is not a solution of (6.5).

For the converse, suppose that Y is a strong vector equilibrium. and hence y j pi -y j pi = y j pi -l j pi ≧ 0. This implies that ( min

pα∈Aw h(C pα , C pi )-t w )(y j pi -y j pi ) ≧ 0. Case 3: min pα∈Aw h(C pα , C pi ) -t w = 0. It is clear that ( min pα∈Aw h(C pα , C pi ) -t w )(y j
piy j pi ) = 0. By taking the constraint (3.15) into account we deduce that

(pi,w,j)∈Γ min pα∈Aw h(C pα , C i ) y j pi -y j pi ≧ (pi,w,j)∈Γ t w y j pi -y j pi ≧ (pi,w,j)∈Γ t w (d j w -d j w ) = 0,
which proves that y is a solution of (6.5).

We are now able to construct specific variational inequality problems to obtain strong vector equilibrium flows by using augmented signed distance functions. for some ǫ > 0, then it is a strong vector equilibrium. Conversely, if Y is a strong vector equilibrium, then there is ǫ 0 > 0 such that it satisfies (6.6) for all ǫ ∈ (0, ǫ 0 ).

Proof. For the first part of the theorem, we set h(a, b) = D ǫ a (b). By the definition this function is increasing with respect to b. In view of Lemma 6.2.6 every solution of (6.6) is a strong vector equilibrium. To prove the second part of the theorem we apply Lemma 2.0.15 to find some ǫ 0 > 0 such that for every ǫ ∈ (0, ǫ 0 ), a, b ∈ {C pi : p i ∈ P } one has that a ≥ b if and only if D ǫ a (b) ≧ 0. The proof now follows from Lemma 6.2.6.

The same argument of proof shows that the above theorem is true when the augmented signed distance functions D ǫ a (b) are replaced by the augmented smallest increasing functions G ǫ a (b). In the next result we have a variational inequality problem obtained by augmented biggest functions. Theorem 6.2.8 Let Y be a feasible flow. If it satisfies the condition (6.2) and

(pi,w,j)∈Γ max p β ∈Bw g ǫ Cp β (C pi ) y j pi -y j pi ≧ 0 f or every Y ∈ K, (6.7)
for some ǫ > 0, then it is a strong vector equilibrium. Conversely, if Y is a strong vector equilibrium, then there is ǫ 0 > 0 such that it satisfies (6.7) for all ǫ ∈ (0, ǫ 0 ).

Proof. Apply the same argument as in the proof of the preceding theorem with a suitable arrangement of Lemma 2.0.14.

This result is a correction to Theorem 5.1 of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF], in which "min" was mistakenly employed instead of "max". Again, it remains true when the functions g ǫ a (b) are substituted by the functions d ǫ a (b). In the above theorems, if the condition (6.2) is not satisfied, then a solution of the variational inequality problem (6.6) (or (6.7)), is not necessarily a strong vector equilibrium. This is seen by the following example. Example 6.2.9 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with two available paths:

P w = {p 1 , p 2 }. Assume that d 1 w = 7, d 2 w = 19
, l j pi = 2, u j pi = 10 for p i , p j ∈ P w and

y 1 p1 = 2 y 2 p1 = 9 c 1 p1 = (15, 35) T c 2 p1 = (25, 20) T y 1 p2 = 5 y 2 p2 = 10 c 1 p2 = (10, 20) T c 2 p2 = (15, 12) T
Then, Y does not satisfy the condition (6.2). In fact, Y p1 ≥ L p1 and Y p2 ≤ U p2 , and there is not any j ∈ {1, 2} such that y j p1 > l j p1 and y j p2 < u j p2 . Moreover,

D ǫ Cp 1 (C p2 ) < 0 since C p1 ≥ C p2 . Then, for all Y ∈ K one has (pi,w,j)∈Γ min α∈Aw D ǫ Cp α (C pi ) y j pi -y j pi = D ǫ Cp 1 (C p2 ) y 1 p2 -y 1 p2 + D ǫ Cp 1 (C 2 ) y 2 p2 -y 2 p2 = D ǫ Cp 1 (C p2 ) y 1 p2 -5 + D ǫ Cp 1 (C p2 ) y 2 p2 -10 .
We have y 1 p2 ≦ 5 since y 1 p1 ≧ 2. Hence, (pi,w,j)∈Γ min α∈Aw D ǫ Cα (C pi ) y j piy j pi ≧ 0 for all Y ∈ K, which shows that the path flow Y solves the variational inequality problem (6.6). However, Y is not a strong vector equilibrium as C p1 ≥ C p2 but Y p1 = L p1 and Y p2 = U p2 .

Algorithms

As we saw in Section 6.1 finding a weak vector equilibrium of a multi-product and multicriteria network is quite clear. It suffices to fix one product and to consider a model with this single product while keeping the other products unchanged and with a single cost function being the sum of all components of the vector cost function. This amounts to saying that the problem of finding a weak vector equilibrium is computationally equivalent to a classical network equilibrium problem, or a variational inequality problem. The situation is more complicated with strong vector equilibrium. In fact, firstly, strong vector equilibrium does not always exist even when the cost function is linear and the set of feasible flows is compact (see Example 6.1.1). Secondly, almost all equivalent variational inequality problems in our disposal do not satisfy sufficient conditions needed for convergence of existing algorithms, namely the functions determining the associated variational inequalities are not monotone. Thirdly, a solution to a variational inequality problem is not necessarily a strong vector equilibrium, which requests an additional computational effort to check certain sufficient conditions for strong vector equilibrium. Because of these reasons, solving a multi-product and multi-criteria network equilibrium problem is a challenging task. In this section we develop an algorithm for finding a strong vector equilibrium by using the variational inequality generated by the augmented signed distance function and discuss its implementability through a number of numerical examples. As in multi-objective programming, by solving a multi-criteria network equilibrium problem we mean generating the entire set of equilibrium flows or at least a representative part of it. In this sense our algorithm can be seen as a first step towards a complete resolution of the problem. We begin with expressing the variational inequality problem (6.6) in the standard form:

F (Y ), Y -Y ≧ 0 ∀Y ∈ K. (6.8)
To obtain an explicit form of F , we assume that W = {w 1 , ..., w s }, that is there are s origin-destination pairs in the network. For each w t , t = 1, ..., s we define

K wt = {Y wt ∈ R |Pw t |×q : l j pi ≦ y j pi ≦ u j pi , j =
F wt (Y ) = (F 1 wt (Y ), ..., F |Pw t | wt (Y )) (6.10)
where for each p i ∈ {p 1 , ..., p |Pw t | }, the vector F i wt (Y ) has q components, which are all equal to min

pα∈Aw t D ε Cp α (Y ) (C i (Y )
). Below we propose an algorithm to find a strong vector equilibrium of our model in which the modified projection method (see [START_REF] Bigi | Existence and solution methods for equilibria[END_REF][START_REF] Michael | Modified projection-type methods for monotone variational inequalities[END_REF][START_REF] Nagurney | Network Economics, A Variational Inequality Approach[END_REF][START_REF] Noor | A modified projection method for monotone variational inequalities[END_REF]) is applied to solve the associated variational inequality problem (6.8):

Step 0: Initialization Start with a feasible flow Y 0 ∈ K. Select a coefficient ρ ∈ (0, 1) for the modified projection method, a positive coefficient ǫ and a small error tolerence δ > 0. Set k := 1.

Step 1: Solving (6.8) a) Find A wt and compute

D ǫ Cα(Y k-1 ) (C pi (Y k-1 )) for all α ∈ A wt , p i ∈ P wt , w t ∈ W. b) Compute the functions F wt (Y k-1 ) for all w t ∈ W F wt (Y k-1 ) = min α∈Aw t D ǫ Cα(Y k-1 ) (C p1 (Y k-1 )), ..., min α∈Aw t D ǫ Cα(Y k-1 ) (C p1 (Y k-1 )), ..., min pα∈Aw t D ǫ Cp α (Y k-1 ) (C |Pw t | (Y k-1 )), ..., min pα∈Aw t D ǫ Cp α (Y k-1 ) (C |Pw t | (Y k-1 )) .
c) Solve s linearized variational inequality subproblems:

F wt (Y k-1 ) + U -Y k-1 wt T , U ′ -U ≧ 0, ∀U ′ ∈ K wt (6.11)
by using the modified projection method. Let Step 3: Final verification For Y k obtained in Step 2, compute C(Y k ) and check three conditions (i) -(iii) of Theorem 6.2.5. If three conditions are satisfied, then Y k is a strong vector equilibrium. Otherwise, set ǫ = ǫ/2 and return to Step 1. If ǫ < δ and no strong vector equilibrium is found, then stop. It is considered that the network has no strong vector equilibrium.

U = Y k-1 wt -ρ[Y k-1 wt -P Kw t (Y k-1 wt -ρF wt (Y k-1 ))] (6.12) be a solution. Set Y k wt = U and Y k = (Y k wt ) wt∈W . Step 2: Convergence verification If Y k -Y k-1 ≦ δ,
Before presenting numerical examples we discuss some convergence aspects of the algorithm. We assume throughout that the cost function C(.) is continuous, which is a sufficient condition for existence of solutions to the variational inequality problem (6.8).

Convergence under condition (6.2)

It follows from the definition of the functions F that with q > 1 it is never strictly monotone. Therefore the uniqueness of solution to the variational inequality problem (6.8) is not guaranteed [START_REF] Nagurney | Network Economics, A Variational Inequality Approach[END_REF]. However, if the condition (6.2) is satisfied, then any solution of (6.8) is a strong vector equilibrium (Theorem 6.2.7). Under this hypothesis the last step of the algorithm is unnecessary. Moreover, for every δ > 0 the algorithm will terminate after a finite number of iterations and yields an approximate solution of (6.8) which is considered as an approximate strong vector equilibrium of the network. When δ tends to zero, that approximate solution converges to an exact solution of (6.8), which is also a strong vector equilibrium of the network.

Convergence without condition (6.2)

The network may have a strong vector equilibrium without condition (6.2). According to Theorem 6.2.7 at least one of the solutions of the variational inequality problem (6.8) is a strong vector equilibrium when ǫ is sufficiently small. Of course, if a solution of the variational inequality problem (6.8) with ǫ small is unique, it must be a unique strong vector equilibrium and as before no verification at Step 3 is requested. When a solution to (6.8) is not unique, the last step that verifies the necessary and sufficient conditions for strong vector equilibrium, is needed.

Nonexistence of strong vector equilibrium

Except for the models without capacity constraints (or when u ij are large), verification of condition (6.2) is not easy, and therefore it is not known a priori whether a strong vector equilibrium exists or not. We observe that if the model has no strong vector equilibrium, then at each iteration we decrease ǫ by half because the conditions of Theorem 6.2.7 are not satisfied, and so, after a finite number of iterations we have ǫ < δ, by which the algorithm terminates. When the algorithm stops without producing strong vector equilibrium, there are two possible situations: either the solution obtained by the projection method is a wrong solution of (6.8) and cannot be a strong vector equilibrium, or that solution is a solution of (6.8), but it is not a strong vector equilibrium. Therefore, in the implementation of the algorithm, when no strong vector equilibrium is detected in Step 3 with ǫ < δ, we restart it with a new initial flow. If after a number of trials no equilibrium is found, we may consider that the network has no strong vector equilibrium.

Conclusion

In this thesis we studied several concepts of equilibrium in multi-criteria traffic networks. For us solving a multi-criteria network equilibrium problem means finding the set of all equilibria of the network or a representative part of it. This problem is very hard, and by our knowledge, there exists no numerical method to solve it because multi-criteria models generally do not have necessary properties for convergence of existing numerical methods.

In the thesis, we applied two approaches to this problem. The first approach constructs an optimization problem the solutions of which are equilibria of the network and the second approach proposes an equivalence between the vector variational inequality problem and the vector equilibrium problem under some appropriate assumptions.

The main results of this thesis are presented in the three Chapters 4, 5 and 6.

In the fourth and fifth chapters, we concentrated our attention on studying the optimization problems based on a vector version of the Heaviside Step function and the distance function to Pareto minimal elements. We proved that the optimal solutions of these problems are exactly the equilibria of the single-product multi-criteria traffic network with and without capacity constraints. Due to the generic differentiability of the objective functions of these optimization problems, we developed an algorithm based on modified Frank-Wolfe gradient method and obtained a representative set of equilibria. A method of smoothing the objective functions by analytic approximations of the Heaviside Step function was also considered in order to see how global optimization may help. We also investigated the robustness of equilibrium and gave a formula to calculate the radius of robustness. Many numerical examples were given to illustrate the above algorithms.

In the sixth chapter we analyzed a complex model of multi-product, multi-criteria networks with capacity constraints, constructed an equivalent variational inequality problem and presented an algorithm to find strong vector equilibria of the model. We also gave sufficient and necessary conditions for strong vector equilibrium in terms of efficient elements of the value set of the criteria function. Major difficulty we face when solving a multi-criteria network equilibrium problem are due to the fact that the conditions for convergence of variational inequality methods are not satisfied, the function determining the associated variational inequality problem is generally not monotone. Nevertheless, the use of a particular class of scalarizing functions in the algorithm, which are proposed in Chapter 2 seems to be quite successful.

In future research we wish to develop an algorithm for multi-product, multi-criteria networks with capacity constraints where convergence conditions can be found. Stability and robustness of equilibrium in the above models will be of our attention. Applications to real models of urban transportation in big cities such as Hanoi and Ho Chi Minh City will be also of interest. Subprogram function K= Matrix K2(q) k1= 0:1:2*q; k2= 0:1:2*q; S=zeros(0); for i1=1:2*q+1 for i2=1:2*q+1 if (k1(1,i1)+ k2(1,i2)==2*q) S=[S;k1(1,i1) k2(1,i2)]; end end end K = S. ′ ; end 2. Subprogram function K= Matrix K3(q) k1= 0:1:3*q; k2= 0:1:3*q; k3= 0:1:3*q; S=zeros(0); for i1=1:3*q+1 for i2=1:3*q+1 for i3=1:3*q+1 if (k1(1,i1)+ k2(1,i2) + k3(1,i3)==3*q) end end A2. For the model in which the cost functions are not linear. Main program epsilon = input ('A tolerance level epsilon= '); m = input ('Number of paths m = '); q = input ('q = '); Dans un troisième temps, nous donnons une formule permettant de calculer le gradient des fonctions objectifs, qui nous permet de modifier la méthode de gradient réduit de Frank-Wolfe pour obtenir une direction de descente vers une solution optimale. Ces résultats sont présentés dans le Théorème 4. La dernière partie de ce chapitre est consacrée à un algorithme permettant de trouver des points d'équilibre d'un réseau multi-critère sous constraintes de capacité. Certains exemples numériques sont donnés pour illustrer notre méthode.

Nous fermons la thèse avec une liste de références et appendix contenant le code matlab de nos algorithmes.

Lemma 2 .

 2 0.14 Let a and b be two vectors in R n . The following assertions hold. (i) a ≥ b if and only if d ǫ b (a) > 0 for every ǫ > 0. (ii)a b if and only if there is ǫ(a, b) > 0 such that d ǫ b (a) ≦ 0 for all 0 < ǫ < ǫ(a, b). The above assertions are also true for g ǫ b (a). Proof. If a ≥ b, then d ǫ b (a) > 0 for all ǫ > 0 because the function d ǫ b is increasing and d ǫ b (b) = 0. For the converse let a b. If a ≦ b, then d ǫ b (a) ≦ 0 for every ǫ > 0 because d ǫ b is increasing. If a ≦ b, then either n i=1

Lemma 2 .

 2 0.15 Let a and b be two vectors in R n . The following assertions hold. (i) a ≥ b if and only if D ǫ a (b) < 0 for every ǫ > 0. (ii)a b if and only if there is ǫ(a, b) > 0 such that D ǫ a (b) ≧ 0 for all 0 < ǫ < ǫ(a, b). (iii) For every ǫ > 0, one has D ǫ a (b)+D ǫ b (a) ≧ 0. In particular, if D ǫ a (b) ≦ 0, then D ǫ b (a) ≧ 0. The above assertions are also true for G ǫ a (.). Proof. For (i) let a ≥ b. Then D ǫ a (b) < 0 because the function D ǫ a is increasing and D ǫ a (a) = 0. For the converse, suppose a

Example 3 . 2 . 18

 3218 Consider the network of the previous example. Let a feasible pattern flow Y be given by its rows Y 1 = (0, 830 and Y 2 = (30, 0) representing the quantities of the two products to traverse the paths p 1 and p 2 respectively. Assume further that the cost matrix associated to the path flow Y has its rows C 1 = (2, 16) and C 2 = (2, 25). Then (B6) holds, but not (B4) because C 2 ≥ C 1 with Y 2 = 0.

Proposition 3 . 2 .

 32 [START_REF] Gert | Nonconvex separation theorems and some applications in vector optimization[END_REF] Let Y be a feasible pattern flow. The following assertions hold. i) (H1) ⇒(H4)⇒ (H5). ii) (H4) ⇒ (H1) provided that for every w ∈ W , the set C(w) has ideal minimal elements and that d w p β ∈Pw:Cp β =InfC(w)U p β + pα∈Pw:Cp α =InfC(w)

  2 a c a (∆y)δ ap = a∈A λ 1 a t a (∆y) + λ 2 a u a (∆y) δ ap for every flow y ∈ K and every path p ∈ P . Since c p (y) = a∈A ĉa (z)δ ap , the vector cost function c p on path p can be written as c p (y) = a∈A t a (∆y) u a (∆y) δ ap . (4.1)

Theorem 4 . 1 . 1

 411 Let ȳ be a feasible flow. The following statements are equivalent:

  p∈Pw,w∈W y p d[c p (y), WMin(C w (y))] subject to y ∈ K and minimize ψ w (y) := p∈Pw,w∈W

Lemma 4 . 2 . 1

 421 Assume that the functions b 1 , • • • , b k are continuous. The following statements hold. (i) The set-valued map y → I(y) is lower semi-continuous at every point y ∈ R m at which the vectors b 1 (y), • • • , b k (y) are distinct from each other. (ii)The set-valued maps y → J j (y), j = 1, • • • , k are upper semi-continuous. Proof. To prove (i), let i ∈ I(y). Since all vectors b j (y), j ∈ {1, • • • , k} are distinct, by definition one has b j (y) ∈ b i (y) -R l + for j = i. Moreover, because b 1 , • • • , b k are continuous, there exists an open neighborhood U of y such that b

Example 4 . 2 . 2

 422 Let vector-valued functions b 1 , b 2 , b 3 , b 4 from R 3 to R 2 be defined as follows b 1 (y) = (y 1 + y 2 , y 1 + y 3 ) T , b 2 (y) = (y 2 , y 2 + y 3 ) T , b 3 (y) = (y 1 + y 2 + 2y 3 , y 3 ) T , b 4 (y) = (y 1 + 2y 2 + y 3 , y 2 ) T . Consider the family {b 1 (y), b 2 (y), b 3 (y)} at the point y = (3, 3, 3) T . We have b 1 (y) = (6, 6) T , b 2 (y) = (3, 6) T , b 3 (y) = (12, 3) T . By definition, I(y) = {2, 3}.

Lemma 4 . 2 . 3

 423 Assume that the functions b 1 , • • • , b k are continuous. For every open set U ⊆ R m there is an open subset U ′ such that(i) I(y) = I(y ′ ) for every y, y ′ ∈ U ′ (ii)J j (y) = J j (y ′ ) for every y, y ′ ∈ U ′ and j ∈ {1, • • • , k}.Proof. For each couple b i and b j , i = j, either b i (y) = b j (y) for all y ∈ U , or there is some y ∈ U such that b i (y) = b j (y), in which case, due to continuity, there is a small neighborhood U 1 of y in U such that b i (y ′ ) = b j (y ′ ) for all y ′ ∈ U 1 . Applying this argument to all possible couples from the family {b 1 , • • • , b k } we may assume the existence of an open subset U 2 in U and an index set I ⊆ {1, • • • , k} such that the vectors b i (y ′ ), i ∈ I are all distinct from each other and for every i ∈ {1, • • • , k} there is some j ∈ I such that b i (y ′ ) = b j (y ′ ), y ′ ∈ U 2 . Let y ∈ U 2 . In view of Lemma 4.2.1 one find some neighborhood U 3 of y in U 2 such that I(y) ⊆ I(y ′ ) for all y ′ ∈ U 3 with I(y) and I(y ′ ) being subsets of I. It follows from the definition of I that the latter statement is true for the family b 1 , • • • , b k . Let us now consider the set of all index sets

Theorem 4 . 2 . 4

 424 Assume that the vector cost functions c pi , i = 1, • • • , m are continuous (respectively locally Lipschitz or differentiable). Then every open set in R m contains an open subset where the objective functions φ and ψ of problems (P1) and (P2) are continuous (respectively locally Lipschitz or differentiable). Proof. Let U be an open set in R m . Let w ∈ W . In view of Lemma 4.2.3 there is an open subset U w ⊆ U and an index set I ⊆ i ∈ {1, • • • , m} : p i ∈ P w such that Min(C w (y)) = {c pi (y) : i ∈ I} for all y ∈ U w .Then for y, y ′ ∈ U w we haveH[Min(C w (y)), Min(C w (y ′ ))] ≦ max{max i∈I d(c pi (y), Min(C w (y ′ )), max i∈I d(c pi (y ′ ), MinC w (y))} ≦ max i∈I c pi (y)c pi (y ′ ) .If the functions c pi , p i ∈ P are continuous, then the set-valued map y → Min(C w (y)) is also continuous on U w with respect to the Hausdorff distance. In view of Theorem 1.4.16[START_REF] Aubin | Set-valued Analysis[END_REF] we deduce that the functions d[c pi (y), Min(C w (y))], p i ∈ P w are continuous on U w . By choosing another O/D pair w ′ from W and applying the same argument as above on the open set U w ′ we obtain an open set U ′ ⊆ U such that all functions d[c pi (y), Min(C w (y))], p i ∈ P w , w ∈ W are continuous, which implies the same property for φ on U ′ . If the functions c pi , p i ∈ P are locally Lipschitz, then the set-valued map y → Min(C w (y)) is also locally Lipschitz on U w . The method of proof of Theorem 1.4.16[START_REF] Aubin | Set-valued Analysis[END_REF] can be applied to show that the functions d[c pi (y), Min(C w (y))], p i ∈ P w , w ∈ W are locally Lipschitz on U w , and then one obtains an open set U ′ ⊆ U on which φ is locally Lipschitz. Assume now the functions c pi , p i ∈ P are differentiable. We consider the family C w on the open set U w . Then for every p i ∈ P w and y ∈ U w one hasd[c pi (y), Min(C w (y))] = min{d[c pi (y), c p i ′ (y)] : i ′ ∈ I}.If c pi (y) ∈ Min(C w (y)) for all y ∈ U w , then d[c pi (y), Min(C w (y))] = 0 on U w , and so this function is differentiable on U w . If c pi (y) ∈ Min(C w (y)) for all y ∈ U w , we denote by I ′ (y)

  d[c pi (y), c pi 0 (y)] ≦ d[c pi (y), c p i ′ (y)] for all i ′ ∈ I which proves that i 0 ∈ I ′ (y), and hence the map I ′ (y) is upper semi-continuous. Let y 0 ∈ U w be a point such that I ′ (y 0 ) is minimal with respect to inclusion among the index sets I ′ (y), y ∈ U w . Then, there is an open neighborhood U 1 of y 0 in U w such thatI ′ (y ′ ) = I ′ (y 0 ) for all y ′ ∈ U 1 . By choosing any i ′ ∈ I ′ (y 0 ) we obtain d[c pi (y), Min(C w (y))] = d[c pi (y), c p i ′ (y)] > 0 for all y ∈ U 1 . Hence d[c pi (y), Min(C w (y))] is differentiable on U 1 .Apply this argument to other paths and other O/D pairs to obtain an open set U ′ ⊆ U where φ is differentiable. Now we consider ψ. First we prove that for p, p ′ ∈ P w there is an open set U ′ ⊆ U such that the function H + [c p (y)c p ′ (y)] is constant on U ′ . Indeed, If c p (y)c p ′ (y) ≧ 0 for every y ∈ U , then by definition H + [c p (y ′ )c p ′ (y ′ )] = e on U . If c p (y)c ′p (y) ≧ 0 for some y, then it is clear that there is some neighborhoodU ′ of y in U such that c p (y ′ )c p ′ (y ′ ) ≧ 0 for all y ′ ∈ U ′ .By definition H + [c p (y ′ )c p ′ (y ′ )] = 0 on U ′ . Applying the above argument to all p, p ′ ∈ P w and w ∈ W , we find an open set U ′ ⊆ U on which the functions H + [c p (y)c p ′ (y)] are constant. Hence the function ψ is continuous (respectively Lipschitz continuous or differentiable) on U ′ whenever the functions c pi , i = 1, • • • , m are continuous (respectively Lipschitz continuous or differentiable).

  Let U be any open set in K. According to the proof of Theorem 4.2.4 there are an open set U ′ ⊆ U and index sets I w

. 8 )

 8 If i ∈ I + , then we have d[c pi (ȳ), Min(C w(i) (ȳ))] = 0. Consider the family of functions

  4.15) for y ∈ K with yy ≦ γ i . It remains to choose δ = min{γ i : i ∈ I + } and κ = 2mlT |I 0 | + 2mlDκ ′ |I + | to obtain (4.5) from (4.14) and (4.15). The proof is complete.

  go to Step 4 to choose another feasible solution from Y 0 to restart the procedure until no element of Y 0 left. Otherwise, set y k+1 = u k . Update k = k + 1 and return to Step 5.

Example 4 . 3 . 2

 432 Consider a network equilibrium problem with one pair of origin-destination nodes w = (x, x ′ ), two criteria: travel time and travel cost, two available paths: P w = {p 1 , p 2 } with the travel demand d w = 10. Assume that travel time and travel cost functions on the paths are given as follows c p1,1 (y) = 5y p1 + 3y p2 c p2,1 (y) = y p1 + 3y p2 + 9 c p1,2 (y) = y p1 + 2y p2 c p2,2 (y) = 2y p1 + y p2 + 6 Let ν ∈ N \ {0}. Define y ν = (2 -1/ν, 8 + 1/ν) T . It is a vector equilibrium because

Example 4 . 3 . 3

 433 We consider the network with one pair of origin-destination nodes as described in Example 4.3.2. The travel demand is d w = 10. The travel time and travel cost are given as below c p1,1 (y) = 8y p1 + 6y p2 c p2,1 (y) = 3y p1 + y p2 c p1,2 (y) = 7y p1 + y p2 c p2,2 (y) = 7y p1 + y p2

Example 4 . 3 . 5

 435 Consider the network described in Example 4.3.4 with one pair of origindestination nodes, two paths and two criteria. We assume d w = 10 and the travel time and travel cost functions on the paths p 1 and p 2 are given as follows c p1,1 (y) = 3y p1 + y p2 c p2,1 (y) = y p1 + y p2 c p1,2 (y) = 5y p1 + 3y p2 c p2,2 (y) = 3y p1 + 5y p2 .

Example 4 . 3 . 6

 436 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria: travel time and travel cost, three available paths: P w = {p 1 , p 2 , p 3 } with the travel demand d w = 18. Assume that travel time and travel cost functions on the paths are given as follows c p1,1 (y) = y 2 p1 + y 2 p2 + y 3 p3 c p2,1 (y) = 8y p1 y p2 + y 2 p2 c p1,2 (y) = 2y p1 + 5y p2 + 3y p3 c p2,2 (y) = y p2 + 10y p3 c p3,1 (y) = y p1 + y 2 p2 + y 3 p3 c p3,2 (y) = 10y 3 p3 . With ǫ = 0 and q = 20 we have 1888 initial points. Using the algorithm (A) we obtained 1017 vector equilibria in 67.938183 seconds which are presented in the next figure.

Example 4 . 3 . 7

 437 In this example we consider a network problem with one pair of origindestination nodes, two criteria, three available paths: P w = {p 1 , p 2 , p 3 } and the travel demand d w = 7. The travel time and travel cost functions on the paths are given as follows c p1,1 (y) = 4y p1 + 3 c p2,1 (y) = 3y p1 + 1 c p1,2 (y) = 3y p1 + y p2 + y p3 + 2 c p2,2 (y) = 3y p1 + 2y p2 + y p3 + 5 c p3,1 (y) = 4y p1 + 5 c p3,2 (y) = 3y p1 + y p2 + y p3 + 1.

Example 4 . 3 . 8

 438 We consider the case ν = 1. Examples for ν > 1 are constructed in a similar manner. Suppose we have one pair w of origin-destination nodes, two paths p 1 and p 2 joining them, two criteria and the demand d w = 10. Let c p2 (y) = (c p2,1 (y), c p2,2 (y)) T be a continuous vector cost function on p 2 . We define a vector cost function on p 1 to be c p1 (y) = c p2 (y) + α(y)(p 1 , 1) T , where α(y) is the function given by α(y) = 0.4 if 0.3 ≦ y p1 ≦ 10 -0.4y p1 + 1.6 if 0 ≦ y p1 < 0.3.

1 ≧ 1 4′ 2 such that 2 ≧′ 3 such that 3 ≧

 112233 l+1 y pi c pi (y)c pj (y), e for ν ≧ ν 4 . (4.[START_REF] Konnov | Vector network equilibrium problems with elastic demands[END_REF] Furthermore, because the sum 2 contains at most m terms β p,p ′ (y ν ) in which at most l components of c p (y)c p ′ (y) are equal to zero and the others are strictly positive, in view of (4.26), there exists ν 5 ≧ ν -mDlǫ for ν ≧ ν 5 .(4.29)As to the sum 3 we apply (4.27) to find ν 6 ≧ ν -mlDT ǫ for ν ≧ ν 6 . (4.30)We set ν 0 = max{ν 4 , ν 5 , ν 6 } and deduce from (4.28), (4.29) and (4.30)that ψ ν (y ν ) ≧ 1 4 l+1 y pi c pi (y)c pj (y), e -3mlD(T + 1)ǫ for ν ≧ ν 0 . It remains to choose ǫ = y pi c pi (y)c pj (y), e 4 l+2 3mlD(T + 1)

  lim ν→∞ γ ν (c p,r (y * )c p ′ ,r (y * )) = 0, we deduce lim ν→∞ y * p (c p (y * )c p ′ (y * )) T Hν [c p (y * )c p ′ (y * )] = 0. (4.32) It follows from (4.31) and (4.32) that lim ν→∞ ψ ν (y * ) = 0 as requested. To complete the proof we choose a vector equilibrium y * ∈ K, which evidently exists. By hypothesis ψ ν (y ν ) ≦ ψ ν (y * ) for every ν ≧ 1. This implies lim inf ν→∞ ψ ν (y ν ) ≦ lim ν→∞ ψ ν (y * ).

Example 4 . 3 . 10

 4310 Consider a network problem with one pair of origin-destination nodes, two criteria, six available paths and the travel demand d w = 100. The travel time and travel cost functions on the paths are given as follows c p1,1 (y) = 2y 2 p1 + 7y 2 p2 c p2,1 (y) = 8y p1 y p2 + y 2 p2 c p3,1 (y) = y p1 + y 2 p2 + y 2 p3 c p1,2 (y) = 2y p1 + 5y p2 + 3y 3 c p2,2 (y) = 3y p2 + 10y 2 p3 c p3,2 (y) = y p3 + 10y 3 p3 c p4,1 (y) = y 3 p1 + y p4 y 5 c p5,1 (y) = y p2 + y p5 + y p6 c p6,1 (y) = y p3 + y p6 c p4,2 (y) = 2y p2 + y 2 p4 c p5,2 (y) = y p1 y p5 + y p3 y p6 + 10 c p6,2 (y) = y p1 + y 2 p6

  w and c pi (y) ∈ Min(C w (y)) and define a function ρ on K to be ρ(y) := p∈Pw,w∈W y p d[c p (y), Min(C w (y))] + i∈Iw(y),pi =p χ {0} ( c p (y)c pi (y) )

Corollary 4 . 4 . 4

 444 Let y be a feasible flow of G. Then the set C R (y) is open and dense in C(y).

Theorem 5 . 3 . 1

 531 Assume that the vector cost functions c pi , i = 1, • • • , m are continuous (respectively locally Lipschitz or differentiable). Then every open set in R m contains an open subset where the objective function ψ of problem (P) is continuous (respectively locally Lipschitz or differentiable).

-

  ψ is differentiable at y and its gradient's components are computed by ∂ψ(y)∂y k = m i=1 (y pil pi ) j∈Ji(y) (u pjy pj ) ∂cp i (y) ∂y k y pi ) c pi (y)c p k (y), e + j∈J k (y)(u pjy pj ) c p k (y)c pj (y), e for k = 1, ..., m.

. 6 )

 6 If i ∈ I + , we have pj ∈P w(i) (u pjy pj )[c pi (y)c pj (y)] T H + [c pi (y)c pj (y)] = 0,which implies that for p j ∈ P w(i) \{p i }, either y pj = u pj or c pi (y) c pj (y) or c pi (y) = c pj (y).

c

  pj (y)c pj (y) ≦ κ ′ yy (5.7) for every y ∈ K with yy ≦ δ ′ and j = 1, • • • , m. We havec pi (y)c pj (y) = c pi (y)c pi (y) + c pj (y)c pj (y) ≦ 2κ ′ yy for all y ∈ K with yy ≦ δ ′ . Set γ i = min{δ ′ , δ ′ i , δ ′′ i }. We deduce |g i (y)g i (y)| = g i (y) ≦ lDU pj ∈Pw i c pi (y)c pj (y) ≦ 2lmDU κ ′ yy(5.8) for y ∈ K with yy ≦ γ i . It remains to choose δ = min{γ i : i ∈ I + } and κ = 2mlT U |I 0 | + 2mlDU κ ′ |I + | to obtain (5.4) from (5.6) and (5.8). The proof is complete.

Step 6 .Step 7 .Example 5 . 4 . 1

 67541 If |ψ k (y k )α k-1 | ≦ ǫ, go to Step 4 to choose another feasible solution from Y 0 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 ky k-1 )/2 and return to Step 5. Compute ∇ψ k (y k ). Solve (P k ) minimize u T ∇ψ k (y k ) subject to u ∈ K |u iy 0 i | ≦ δ w(i) , i = 1, • • • , m.Let u k be an optimal solution.If|ψ k (y k )ψ k (u k )| ≦ ǫ,go to Step 4 to choose another feasible solution from Y 0 to restart the procedure until no element of Y 0 left. Otherwise, set y k+1 = u k . Update k = k + 1 and return to Step 5. 5.4.2 Numerical examples The examples below are modified versions of Examples 4.3.4-4.3.6 of Chapter 4 to which we add lower and upper capacity constraints. They are coded and computed on Matlab Version 2014a. Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ), two criteria: travel time and travel cost, two available paths: P w = {p 1 , p 2 } with the travel demand d w = 30. Assume that l p1 = 1 l p2 = 1 u p1 = 20 u p2 = 25 c p1,1 (y) = y p1 + 2y p2 c p2,1 (y) = y p1 + 6y p2 c p1,2 (y) = 6y p1 + 2y p2 c p2,2 (y) = 6y p1 + 8y p2 .

  Initial point Numbers of iterations Vector equilibrium CPU Time (seconds)

Example 5 . 4 . 2

 542 Consider the network described in Example 5.4.1 with one pair of origindestination nodes, two paths and two criteria with the travel demand d w = 1. Assume that l p1 = 1 l p2 = 2 u p1 = 8 u p2 = 7 c p1,1 (y) = 3y p1 + y p2 c p2,1 (y) = y p1 + y p2 c p1,2 (y) = 5y p1 + 3y p2 c p2,2 (y) = 3y p1 + 5y p2 .

Example 5 . 4 . 3 2 p1 + y 2 p2 + y 3 p3c

 543223 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria: travel time and travel cost, three available paths: P w = {p 1 , p 2 , p 3 } with the travel demand d w = 18. Assume that l p1 = 1 l p2 = 0 l p3 = 3 u p1 = 10 u p2 = 15 u p3 = 12 c p1,1 (y) = y p2,1 (y) = 8y p1 y p2 + y 2 p2 c p1,2 (y) = 2y p1 + 5y p2 + 3y p3 c p2,2 (y) = y p2 + 10y p3 c p3,1 (y) = y p1 + y 2 p2 + y 3 p3 c p3,2 (y) = 10y 3 p3 . With ǫ = 0 and q = 20 we have 839 feasible initial points. Using the algorithm we obtained 659 vector equilibria in 18.809593 seconds which are presented in the next figure.

  p2 ) T There does not exist any feasible flow Y satisfying the following condition: C pα (Y ) ≥ C p β (Y ) implies either Y pα = L pα or Y p β = U p β for p α , p β ∈ P w . That means this problem does not have any strong vector equilibrium.

Example 6 . 1 . 3

 613 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse in the network with two available paths: P w = {p 1 , p 2 }. Assume that d w1 = 4, d 2 w = 20, l j pi = 2, u j pi = 10 for p i , p j ∈ P w and

  Let h be a real function of the variables (a, b) for a, b ∈ {C pi (Y ) : p i ∈ P, Y ∈ K}. Consider the following variational inequality problem: Find Y such that (pi,w,j)∈Γ min pα∈Aw h(C pα , C pi ) y j piy j pi ≧ 0 for every Y ∈ K. (6.5)

Theorem 6 . 2 . 7

 627 Let Y be a feasible flow. If it satisfies the condition (6.2) and (pi,w,j)∈Γ min pα∈Aw D ǫ Cp α (C pi ) y j piy j pi ≧ 0 f or every Y ∈ K, (6.6)

1 , 9 )

 19 ..., q; p i ∈ P wt and pi∈Pw t y j pi = d j wt , j = 1, ..., q}, where s t=1 |P wt | = m with |.| denoting the cardinality of a set. Then the feasible set K is decomposed by We may assume that the components of Y are grouped according to origin-destination pairs: Y = (Y w1 , Y w2 , ..., Y ws ) and define F (Y ) = (F w1 (Y ), ..., F wt (Y ), ..., F ws (Y )) with

  then stop and go to Step 3; otherwise, set k := k + 1 and go to Step 1.

  wtime =toc; fprintf(1, 'Elapsed CPU time = f\n', wtime)The following code lines are to simulate the set of vector equilibrium in the two-dimension space. for i=1:size(SO,2) plot(SO(1,i),SO(2,i),'b.') hold on end grid on xlabel('Number of products on the first path') ylabel('Number of products on the second path') title('Optimization Method ') hold on The following code lines are to simulate the set of vector equilibrium in the three-dimension space. for i=1:size(SO,2) plot3(SO(1,i),SO(2,i),SO(3,i),'b.') hold on end grid on xlabel('Number of products on the first path') ylabel('Number of products on the second path') zlabel('Number of products on the third path') title('Optimization Method ') hold on T riangle3D(d w ); hold on 1.

  d w = input ('Demand value d w = '); delta = d w /(q*m); Y 0 = Matrix K2(q) * delta (If we consider two paths in the model) Y 0 = Matrix K3(q) * delta (If we consider three paths in the model) Y 0 = Matrix K6(q) * delta (If we consider six paths in the model) Y 0 = Matrix K7(q) * delta (If we consider seven paths in the model) s=size(Y0,2) n = input ('Number of loops n= '); l = input ('Number of criteria l = '); Solution = zeros(0); tic; for j=1:s y 0 = Y 0 (1:m,j); T = F indSolution.nl(m, d w , delta, y 0 , l, epsilon, n); if size(T)==[0,0] P=ones(m,1); Solution=[Solution P]; else Solution=[Solution T] end end Final.Solution = zeros(0); for i=1:s B= Solution(1:m,i)-ones(m,1); if Matrix.O(B) == 0 Final.Solution =[Final.Solution Solution(1:m,i)]; end end SO = Final.Solution wtime =toc; fprintf(1, 'Elapsed CPU time = f\ n', wtime) 1. Subprogram function Solution =F indSolution.nl(m, d w , delta, y 0 , l, epsilon, n) Aeq = ones(1,m); beq= d w ; lb=Comparetwovectors(y 0 , delta, m); ub= Samecoef f icient(m, delta) + y 0 ; alpha = inf; Matrix.si = zeros (0); A= zeros (0); Solution=zeros(0); for i=1:n A = [A y 0 ] L'objectif de cette thèse est d'étudier des propriétés des points d'équilibre dans des réseaux de transport multicrière et de développer des méthodes numériques permettant de trouver l'ensemble de tous les points d'équilibre ou une partie représentative de cet ensemble. Le travail comporte cinq chapitres.Le chapitre 2 est un rappel de certaines notions que nous utilisons dans les autres. Nous y rappelons le concept de point optimal de Pareto, les fonctions multivoques et les problèmes d'inégalité variationnelle. Nous introduisons certaines fonctions de scalarisation, en particulier les fonctions monotones augmentées et les fonctions distance signées augmentées, puis éstablissons quelques propriétés que nous allons utiliser plus tard. Voici ces fonctions.Les fonctions monotones augmentées:g ǫ a (x) = min i=1, ..., n (x ia i ) + ε n i=1 (x ia i ) G ǫ a (x) = max i=1, ..., n (x ia i ) + ε n i=1 (x ia i )Les fonctions distance signées augmentées:d ǫ a (x) = ∆ (R n + ) C (xa) + ε n i=1 (x ia i ) D ǫ a (x) = ∆ -R n + (xa) + ε n i=1 (x ia i )où pour A un sous-ensemble non vide de R n , ∆ A est la fonction distance signée qui est définie par∆ A (x) = d(x, A)d(x, A c ), où d(x, A) est la distance euclidienne de x à A, et A c est le complémentaire de A de R n .Dans le chapitre 3, nous décrivons les réseaux de transport qui sont étudiés dans cette thèse. Dans chaque modèle, nous rappelons les définitions des points d'équilibre et donnons une relation entre ces définitions. Nous présentons également certains contre-exemples pour certains résultats existant dans la littérature récente sur ce sujet.Dans le chapitre 4 nous traitons les réseaux de transport multi-criteriès mono-produit sans constraintes de capacité. Notons que K dans ce chapitre est l'ensemble de tous les flots faisables Y satisfaisant les conditions suivantes:y p ≧ 0 ∀ p ∈ P ; (9.1) p∈Pw y p = d w ∀w ∈ W. (9.2) Dans un premier temps, nous construisons deux problèmes d'optimisation dont les solutions sont exactement l'ensemble des points d'équilibre du modèle initiale. Ce résultat est présenté dans le Théorème 4.1.1. comme suit. Théorème 4.1.1 Si ȳ est un flot faisable, alors les assertions suivantes sont équivalentes: (i) ȳ est un équilibre vectoriel. (ii) ȳ est une solution optimale du problème suivant, noté (P1): minimiser p∈Pw,w∈W y p d[c p (y), Min(C w (y))] sous la constrainte y ∈ K et la valeur optimale de ce problème est nulle. (iii) ȳ est une solution optimale du problème suivant, noté (P2): minimiser p∈Pw,w∈W y p p ′ ∈Pw [c p (y)c p ′ (y)] T H + [c p (y)c p ′ (y)]. sous la constrainte y ∈ K et la valeur optimale de ce problème est nulle, et où la fonction H + : R l → R l est la version vectorielle de la fonction de Heaviside Step qui est définie par H + (c p (y)c p ′ (y)) = (1, ..., 1) T si c p (y)c p ′ (y) ≧ 0 0 sinon. Dans un second temps, nous établissons certaines propriétés importantes de continuité et dérivabilité génériques des fonctions objectifs, qui sont introduites dans le Théorème 4.2.4 et la Proposition 4.2.7: Théorème 4.2.4 Supposons que les fonctions de coût vectorielles c pi , i = 1, • • • , m sont continues (respectivement Lipschitz ou localement differentiables). Alors chaque ensemble ouvert dans R m contient un sous-ensemble ouvert où les fonctions objectifs φ et ψ des problèmes (P1) et (P2) sont continues (respectivement Lipschitz ou differentiable localement). Proposition 4.2.7 Supposons que les fonctions de coût vectorielles c p1 , • • • , c pm sont continues. Alors la fonction φ et ψ sont continues en chaque équilibre vectoriel. Si en outre c p1 , • • • , c pm sont localement calmes en un équilibre vectoriel, alors φ et ψ sont également localement calmes en cet équilibre.

6 : 4 . 2 . 5

 6425 2.5 et le Théorème 4.2.Théorème Supposons que les fonctions de coût vectorielles c pi , i = 1, • • • , m sont differentiables. Alors pour chaque point y en dehors de certain sous-ensemble négligable et pour chaque chemin p i , il existe un chemin p ν(i) de P w(i) tel que(i) c p ν(i) (y) ∈ MinC w(i) (y) (ii)d[c pi (y), MinC w(i) (y)] = c pi (y)c p ν(i) (y) (iii) φ est differentiableen y et son gradient est donné par ∇φ(y) =    c p1 (y)c p ν(1) (y) . . . c pm (y)c p ν(m) (y) i (y)-c ν(i) (y) cp i (y)-cp ν(i) (y)

Théorème 4 . 2 . 6

 426 cp i (y)-cp ν(i) (y) cp i (y)-cp ν(i) (y) Supposons que les fonctions de coût vectorielles c pi , i = 1, • • • , m sont differentiables. Alors pour chaque point y en dehors de certain sous-ensemble négligable et pour chaque chemin p i , il existe un sous-ensemble J i (y) ⊆ I w(i) tel que(i) c pi (y) ≥ c pj (y) pour chaque j ∈ J i (y) (ii) ψ(y) = m i=1 y pi j∈Ji(y) c pi (y)c pj (y) , e(iii) ψ est differentiable en y et son gradient est donné par ∇ψ(y) =    j∈J1(y) c p1 (y)c pj (y), e . . . j∈Jm(y) c pm (y)c pj (y), e

Corollaire 4 . 4 . 5 -

 445 Dans un quatrième temps, nous proposons un algorithme et prouvons sa convergence pour générer une représentation de l'ensemble des points d'équilibre. Puisque les fonctions objectifs de nos problèmes d'optimisation ne sont pas continues, une méthode de lissage est également considérée afin d'utiliser quelques techniques d'optimisation globale. En particulier, nous utilisons les approximations analytiques suivantesHν (x) = l i=1 1 + tanh(νx i ) 2 e f or ν ≧ 1,qui produisent ainsi des approximations lisses de la fonction objectif ψ quand les fonctions de coût sont continues:ψ ν (y) := p∈Pw,w∈W y p p ′ ∈Pw [c p (y)c p ′ (y)] T Hν [c p (y)c p ′ (y)].Le problème d'optimisation notée (P 2 ν ), est obtenu à partir de (P 2) en remplacant ψ par ψ ν .Enfin, nous introduisons le concept de point d'équilibre robuste, puis nous établissons des critères de robustesse et une formule permettant de calculer le rayon de robustesse. Ces résultats sont présentés dans le Théorème 4.4.1 et le Corollaire 4.4.5 comme suivants. Théorème 4.4.1 Soit y ∈ K un équilibre vectoriel de G. Les assertions suivantes sont équivalentes. (i) y est robuste. (ii)y est une solution optimale du problème d'optimization suivant, noté (P ′ 1 ) minimiser p∈Pw,w∈W y p d[c p (y), Min(C w (y))]+ i∈Iw(y),pi =p χ {0} ( c p (y)c pi (y) ) sous la constrainte y ∈ K, et la valeur optimale de ce problème est égale à zéro, où pour w ∈ W et y ∈ K, I w (y) désigne l'ensemble des indices i telle que p i ∈ P w et c pi (y) ∈ Min(C w (y)), et χ {0} est la fonction charactéristique de {0}. (iii) Il existe ǫ > 0 tel que pour chaque w ∈ W, p ∈ P w avec y p > 0, on a :(c p (y) -R l + ) ∩ ( Cw (y)\{c p (y)}) = ∅ pour tous cpi , p i ∈ P w satisfaisant cpi (y)c pi (y) ≦ ǫ. Soit y ∈ K équilibre vectoriel robuste.Alors le rayon de robustesse en y est donné parr(y) = √ l 2 min w∈W,i∈I + w (y) min p ′ ∈Pw\{pi} (c p ′ (y)c pi (y)) + où (c p ′ (y)c pi (y)) + désigne la partie positive du vecteur c p ′ (y)c pi (y) et I + w (y) = {i ∈ I w (y) : y pi > 0}.Dans le chapitre 5 nous étudions des points d'équilibre vectoriel dans le réseau de transport multi-critère mono-produit sous constraintes de capacité. Tout d'abord, nous proposons un problème d'optimisation équivalent et nous établissons également certaines propriétés importantes de continuité et dérivabilité génériques de la fonction objectif. En suite, nous donnons une formule permettant de calculer le gradient de la fonction objectif qui est présenté dans le Théorème 5.3.2 ci-dessous. Puis nous appliquons l'algorithme proposé dans le chapitre 4 avec quelques modifications permettant d'obtenir un sous-ensemble des solutions optimales qui sont des points d'équilibre de notre modèle. Des exemples numériques sont également présentés afin d'illustrer notre approche.Théorème 5.3.2 Supposons que les fonctions de coût vectorielles c pi , i = 1, • • • , m sont differentiables. Alors pour chaque point y en dehors de certain sous-ensemble négligable et pour chaque chemin p i , il existe un sous-ensemble J i (y) ⊆ I w(i) tel que(i) c pi (y) ≥ c pj (y) pour chaque j ∈ J i (y) (ii) ψ(y) = m i=1 (y pil pi )j∈Ji(y) u pjy pj c pi (y)c pj (y) , e (iii)ψ est differentiable en y et son gradient est donné par ∂ψ(y)∂y k = m i=1 (y pil pi ) j∈Ji(y) (u pjy pj ) ∂cp i (y) ∂y k y pi ) c pi (y)c p k (y), e + j∈J k (y) (u pjy pj ) c p k (y)c pj (y), e pour k = 1, ..., m.Dans le dernier chapitre nous considérons des points d'équilibre fort dans le réseau de transport multi-critère multi-produit sous constraintes de capacité. Alors K dans ce chapitre est l'ensemble de tous les flots faisables Y satisfaisant les conditions suivantes:l p ≦ y p ≦u p ∀ p ∈ P ; (9.3) p∈Pw y p = d w ∀w ∈ W. (9.4) Nous établissons des conditions d'existence des points d'équilibre fort. Nous produissons des relations entre des points d'équilibre fort et des points d'équilibre par rapport à une famille de fonctions. Ces résultats sont présentés dans les Lemmes 6.2.1 et 6.2.3 et le Corollaire 6.2.4 comme suit: Lemme 6.2.1 Soit un flot faisable Y donné. Si la famille F contient des fonctions croissantes en {C pi , p i ∈ P }, alors chaque F-équilibre est un équilibre vectoriel fort. Inversement, si F satisfait la condition suivante: Pour chaque w∈ W et p i , p i ′ ∈ P w on a l'implication f (C pi ) > f (C p i ′ ) ∀ f ∈ F ⇒ C pi ≥ C p i ′ ,(9.5)alors chaque équilibre vectoriel fort est un F-équilibre. Lemme 6.2.3 Soit un flot faisable Y donné. Il existe ǫ 0 > 0 tel que pour tous ǫ ∈ (0, ǫ 0 ), chacune des familles de fonctions croissantes ci-dessous satisfait à la condition (9.5):F 1 = {D ǫ Cp i : p i ∈ P }, F 2 = {G ǫ Cp i : p i ∈ P }, F 3 = {d ǫ Ci : p i ∈ P } et F 4 = {g ǫ Cp i : p i ∈ P }.Corollaire 6.2.4 Soit un flot faisable Y donné. Alors il est équilibre vectoriel si et seulement s'il est un F i -équilibre pour certain i ∈ {1, ..., 4}.Nous éstablissons également une relation entre des points d'équilibre fort et les points efficaces de l'ensemble des valeurs de la fonction de coût, qui est présentée dans le Théorème 6.2.5 comme suit: Théorème 6.2.5 Soit Y un flot faisable. Il est un équilibre vectoriel fort si et seulement si pour tout w ∈ W les conditions sont satisfaites(i) (C Lw + R l×q + \{0}) ∩ (C Uw ∪ C Ew ) = ∅, (ii) (C Uw -R l×q + \{0}) ∩ (C Lw ∪ C Ew ) = ∅,(iii) C Ew est auto-maximal, où pour w ∈ W , L w := p i ∈ P w tel que Y pi = L pi U w := p i ∈ P w tel que Y pi = U pi E w := p i ∈ P w tel que L i ≤ Y pi ≤ U pi et pour un ensemble I, C I = {C pi , p i ∈ I}. En plus nous utilisons les fonctions croissantes déjà discutées au chapitre 2 pour construire des problèmes d'inéqualité variationnellle, dont les solutions sont les points d'équilibre fort. Ces résultats sont présentés dans le Théorème 6.2.7 et le Théorème 6.2.8: Théorème 6.2.7 Soit Y un flot faisable. S'il satisfait la condition: C pα(Y ) ≥ C p β (Y ) implique soit Y pα = L pα ou Y p β = U p β pour p α , p β ∈ P w et (i,w,j)∈Γ min α∈Aw D ǫ Cα (C i ) y ijy ij ≧ 0 pour tout Y ∈ K,(9.6) pour certain ǫ > 0, alors il est un équilibre vectoriel fort. Inversement, si Y est un équilibre vectoriel fort, alors il existe ǫ 0 > 0 tel que Y satisfait (9.6) pour tout ǫ ∈ (0, ǫ 0 ). Théorème 6.2.8 Soit Y un flot faisable. S'il satisfait la condition: C pα (Y ) ≥ C p β (Y ) implique soit Y pα = L pα soit Y p β = U p β pour p α , p β ∈ P w et (i,w,j)∈Γ max β∈Bw g ǫ C β (C i ) y ijy ij ≧ 0 pour tout Y ∈ K, (9.7) pour certain ǫ > 0, alors il est un équilibre vectoriel fort. Inversement, si Y est un équilibre vectoriel fort, alors il existe ǫ 0 > 0 tel que Y satisfait (9.7) pour tout ǫ ∈ (0, ǫ 0 ).

  1 ) + ǫ which contradicts(4.19). Thus, (4.18) is true. By applying the same argument to y 2 , • • • , y k we obtain (4.16), and by observing ψ(y

  T (2.5133, 7.4867) T (4.3057, 5.6943) T ν = 10 (0.6347, 9.3653) T (2.5132, 7.4868) T (4.2789, 5.7211) T For Example 4.3.6 we chose three initial points

		T
	ν = 1	(3.3621, 6.6379) T (3.3624, 6.6376) T (3.3617, 6.6383) T
	ν = 2	(2.4865, 7.5135) T (2.5128, 7.4872) T (3.6852, 6.3148) T
	ν = 3	(1.7666, 8.2334) T (2.5127, 7.4873) T (3.9860, 6.0140) T
	ν = 4	(1.4403, 8.5597) T (2.5127, 7.4873) T (4.1482, 5.8518) T
	ν = 5	(1.1060, 8.8940) T (2.5126, 7.4874) T (4.2404, 5.7596) T
	ν = 6	(1.0053, 8.9947) T (2.5137, 7.4863) T (4.2915, 5.7085) T
	ν = 7	(1.1353, 8.8647) T (2.5135, 7.4865) T (4.3150, 5.6850) T
	ν = 8	(0.7096, 9.2904) T (2.5134, 7.4866) T (4.3184, 5.6816) T
	ν = 9	(0.6348, 9.3652)

  It follows that C pα C p β for all p α ∈ A w , p β ∈ B w . According to our assumption, we have h(C pα , C p β ) ≧ 0 for every p α ∈ A w and p β ∈ B w . Let Y be a feasible flow. Set t w := min pα∈Aw, p β ∈Bw h(C pα , C p β ) ≧ 0, and for each path p i ∈ P w consider three possible values of the difference min pα , C ps ) ≦ 0, ∀p s ∈ A w , we deduce p i / ∈ A w

				pα∈Aw	h(C pα , C pi )-
	t w . Case 1: min pα∈Aw	h(C pα , C pi ) -t w < 0. Then p i / ∈ B w and y j pi -y j pi = y j pi -u j pi ≦ 0. Hence,
	one has ( min pα∈Aw	h(C pα , C pi ) -t w )(y j pi -y j pi ) ≧ 0. Case 2: min pα∈Aw	h(C pα , C pi ) -t w > 0. Then
	min pα∈Aw	h(C pα , C pi ) > 0. Moreover, as min

pα∈Aw h(C

Equilibrium in a multi-criteria traffic network without capacity constraints

Equilibrium in a multi-criteria traffic network with capacity constraints

Equilibrium in a multi-product multi-criteria traffic network with capacity constraints

The next result is a version of Theorem 4.2 of [START_REF] Luc | Multi-product supply demand networks with elementary flows[END_REF] for strong vector equilibrium. Lemma 6.2.1 Let a feasible flow Y be given. If the family F consists of increasing functions on {C pi , p i ∈ P }, then every F-equilibrium is a strong vector equilibrium. Conversely, if F satisfies the following condition: For every w ∈ W and p i , p i ′ ∈ P w one has implication

then every strong vector equilibrium is an F-equilibrium.

Proof. Assume that the feasible flow Y is an F-equilibrium. If for some w ∈ W and p α , p β ∈ P w , we have C pα ≥ C p β , then for every increasing function f ∈ F, we obtain f (C pα ) > f (C β ). By definition, we have either Y pα = L pα or Y p β = U β . Hence, Y is a strong vector equilibrium.

Conversely, let Y be a strong vector equilibrium. If for some w ∈ W and p α , p β ∈ P w , we have f (C pα ) > f (C p β ) for all f ∈ F, then by the assumption, it implies that C pα ≥ C β . We deduce that either Y pα = L pα or Y p β = U p β which shows that Y is an F-equilibrium.

We notice that if the family F does not satisfy (6.4), then a strong vector equilibrium is not necessarily an F-equilibrium as it is shown by the example below.

Example 6.2.2 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with three available paths: P w = {p 1 , p 2 , p 3 }. Assume that d 1 w = 10, d 2 w = 18, l j pi = 2, u j pi = 10 for p i ∈ P w and j = 1, 2, and Then the condition (6.4) does not hold, that is G ǫ Cp 1

and C p3 ≥ C p2 . Obviously, Y is a strong vector equilibrium, but not a G-equilibrium.

We now show that families of increasing functions satisfying the condition (6.4) do exist.

Lemma 6.2.3 Let a feasible flow Y be given. There exists ǫ 0 > 0 such that for every ǫ ∈ (0, ǫ 0 ), each of the families below of increasing functions satisfies the condition (6.4):

Proof. Consider the pairs (p i , p j ) with p i , p j ∈ P and define ǫ ij = +∞ if C pi ≥ C pj and ǫ ij = ǫ(C pi , C pj ) if C pi C pj , where ǫ(C pi , C pj ) is obtained by Lemma 2.0.15. Then set ǫ 0 = min {ǫ ij : p i , p j ∈ P }. We show that for all ǫ ∈ (0, ǫ 0 ), F 1 satisfies the condition (6.4). Indeed, let p j , p j ′ ∈ P be such that D ǫ . The same argument is applied to the families F 3 and F 4 with the help of Lemma 2.0.14 instead of Lemma 2.0.15. Corollary 6.2.4 Let a feasible flow Y be given. Then it is a strong vector equilibrium if and only if it is an F i -equilibrium for some i ∈ {1, ..., 4}.

Proof. It follows from Lemmas 6.2.1 and 6.2.3.

Efficiency

We wish to express strong vector equilibrium flows in terms of efficient points of the value set of the criteria function. This result is an improvement of Theorem 6.1 of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] and will be used in the algorithm of Section 6.3. For w ∈ W , let us denote

and for an index set I, C I = {C i , i ∈ I}. Theorem 6.2.5 Let Y be a feasible flow. It is a strong vector equilibrium if and only if for every w ∈ W the following conditions hold

Proof. We prove first the "if" part. Assume that Y satisfies the three conditions of the theorem. Let w ∈ W and p α , p β ∈ P w such that C pα ≥ C p β . If p α ∈ L w or p β ∈ U w , we are done. If not, we consider four possible cases: a) p α ∈ U w and p β ∈ E w . This implies C p β belongs to the intersection of

For the converse, let Y be a strong vector equilibrium of the network. If (i) does not hold, then one can find p α ∈ L w and p β ∈ E w ∪ U w such that C pα ≤ C p β . The latter inequality implies either p α ∈ U w or p β ∈ L w which is not the case. Similarly, if (ii) does not hold, then one can find p α ∈ U w and p β ∈ E w ∪ L w such that C pα ≥ C p β , which leads to the same contradiction. Finally, if (iii) does not hold, then one has C pα ≥ C p β for some p α , p β ∈ E w . This is in contradiction with the definition of strong vector equilibrium.

It is worthwhile noticing that conditions (i) and (ii) can be substituted respectively by

We also observe that applying Theorem 6.2.5 with (i ′ ) and (ii ′ ) above to each product j, we deduce Theorem 6.1 of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF] (Remark that in Theorem 6.1 of [START_REF] Luc | Equilibrium in a vector supply demand network with capacity constraints[END_REF], R l + \{0} should be instead of R l + ).

Numerical examples

In this subsection we give some examples to illustrate the algorithm. In Example 6.4.1, with ǫ > 0 relatively large, a solution of the variational inequality problem (6.8) obtained in Step 2 is not a strong vector equilibrium, but with ǫ > 0 small, we do obtain a strong vector equilibrium after some iterations.

Example 6.4.1 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with three available paths:

p3 ) T Set the initial path flow (y 1 p1 ) 0 = 3, (y 1 p2 ) 0 = 7, (y 1 p3 ) 0 = 10, (y 2 p1 ) 0 = 5, (y 2 p2 ) 0 = 10, (y 2 p3 ) 0 = 10, ρ = 0.6 and δ = 0.0001. For ǫ = 2.5, after 42 iterations, we obtain the following solution of the variational inequality (6.8): y 1 p1 = 1, y 1 p2 = 9.5968, y 1 p3 = 9.4032, y 2 p1 = 2, y 2 p2 = 8.3058, y 2 p3 = 14.6942 which is not a strong vector equilibrium. Nevertheless, when we reduce the value of ǫ until it is sufficiently small, for example ǫ = 0.1, after 13 iterations, we obtain the following solution of the variational inequality (6.8):

which is a strong vector equilibrium.

Note that without condition (6.2) a solution of (6.8) is not necessarily a strong vector equilibrium, but another initial flow may lead to a good solution (which is a strong vector equilibrium). In Example 6.4.2, we show that the time for finding strong vector equilibrium depends largely on the choice of the initial path flow Y 0 . Example 6.4.2 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), three criteria and three products to traverse in the network with three available paths: P w = {p 1 , p 2 , p 3 }. Assume that d w1 = 25, d 2 w = 30, d 3 w = 20 and

1, tolerance δ = 0.0001, we obtain a solution of the variational inequality ( 14): y 1 p1 = 5.6863, y 1 p2 = 0.0002, y 1 p3 = 19.3135, y 2 p1 = 10.3780, y 2 p2 = 1.0006, y 2 p3 = 18.6214, y 3 p1 = 9.8743, y 3 p2 = 1.0001, y 3 p3 = 9.1256 after 98 iterations and it is a strong vector equilibrium.

However the number of loops decreases a lot when we use another initial path flow. Particularly, with the initial path flow (y

1, tolerance δ = 0.0001, after 55 iterations, we obtain a solution of the variational inequality ( 14):

.4917 and it is also a strong vector equilibrium.

In the proof of Theorem 6.1.2 we used a variational inequality problem in which the function is given by the sum of all components of the cost function of q products, which corresponds to the weighted method with equal weight for every criterion and every product. This problem seems to be much simpler than the ones developed in Subsection 6.2.3 and in our algorithm. However, in general it is not sufficiently subtle to solve multi-criteria network equilibrium problems because of lack of convexity. The example below shows that the weighted sum method does not find strong vector equilibrium, while the method by augmented increasing functions does. Example 6.4.3 Consider a network problem with only one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with three available paths:

p3 ) 0 = 5, ρ = 0.5 and δ = 0.0001. When using the method of taking the sum of all components of the cost function, after 200 iterations, we obtain the following solution of the associated variational inequality: y 1 p1 = 5.0000, y 1 p2 = 6.8571, y 1 p3 = 3.1429, y 2 p1 = 5.8571, y 2 p2 = 10.1429, y 2 p3 = 4.0000 which is not a strong vector equilibrium. Nevertheless, using our algorithm with ǫ sufficiently small, for example ǫ = 0.0001, after 42 iterations, we obtain the following solution of the variational inequality (6.8): y 1 p1 = 4.9946, y 1 p2 = 4.4553, y 1 p3 = 5.5501, y 2 p1 = 7.0112, y 2 p2 = 5.6238, y 2 p3 = 7.3650 which is a strong vector equilibrium.

In the last example we randomly generate the cost functions to see what is the percentage of problems that have strong vector equilibrium flows according to our algorithm. Example 6.4.4 Consider a network problem with one pair of origin-destination nodes w = (x, x ′ ), two criteria and two products to traverse the network with three available paths: P w = {p 1 , p 2 , p 3 }. The other data are given as below d 1 w = 15, d 2 w = 20, l j pi = 2, u j pi = 15 for p i ∈ P w and j = 1, 2, and

) T in which the positive coefficients a k ij , i = 1, 2, 3; j, k = 1, 2 are randomly generated. With ǫ = 0.01, ρ = 0.5 and δ = 0.0001, we carried out about 100 tests and obtained a strong vector equilibrium only in less than half of them.

Subprogram

function K= Matrix K6(q) k1= 0:1:6*q; k2= 0:1:6*q; k3= 0:1:6*q; k4= 0:1:6*q; k5= 0:1:6*q; k6= 0:1:6*q; S=zeros(0); for i1=1:6*q+1 for i2=1:6*q+1 for i3=1:6*q+1 for i4=1:6*q+1 for i5=1:6*q+1 for i6=1:

Subprogram function K= Matrix K7(q) k1 = 0 : 1 : 7 * q; k2 = 0 : 1 : 7 * q; k3 = 0 : 1 : 7 * q; k4 = 0 : 1 : 7 * q; k5 = 0 : 1 : 7 * q; k6 = 0 : 1 : 7 * q; k7 = 0 : 1 : 7 * q; S=zeros(0); for i1=1:7*q+1 for i2=1:7*q+1 for i3=1:7*q+1 for i4=1:7*q+1 for i5=1:7*q+1 for i6=1:7*q+1 for i7=1:7*q+1 1. Subproblem function K= Matrix K2(q,lb,ub,d w ,m) delta = d w /(q*m) k1= 0:1:2*q; k2= 0:1:2*q; S=zeros(0); for i1=1:2*q+1 for i2=1: for i=1 : summ(M,s) for j = 1:q if UL(i,j) ¡ 0 error('Verify the coefficients of the matrix L and U') end end end d = zeros(0); for i=1:s dwi = input ('Enter dwi = '); d = [d ; dwi]; end for i=1 : s for j = 1:q if d(i,j) ¡ min(L(summ(M,i-1)+1:summ(M,i),j))*M(1,i) -d(i,j) ¿ max(U(summ(M,i-1)+1:summ(M,i),j))*M(1,i) error('Verify the coefficients of the demand matrix d') end end end epsilon = input ('Epsilon = '); delta = input ('Delta = '); gamma = input ('Gamma = '); tol = input ('Tol = '); nn=input('nn = '); t = input('t = '); Lc = ArrangeLM Ctotal(L, M, q, s); Uc = ArrangeU M Ctotal(U, M, q, s); beq = zeros(0); for i=1:s beqi = d(i,1:q)'; beq = [beq ; beqi]; end beq=beq; Y01=linprog(zeros(M(1,1)*q,1),[],[],F indAeq(M (1, 1), q), Collumdw(M (1, 1),q, beq(1:q,1)),Lc(1:M(1,1)*q,1),Uc(1:M(1,1)*q,1)); Y0i = zeros(0); for i=2:s Yi = linprog(zeros(M(1,i)*q,1),[],[],F indAeq(M (1, i), q), Collumdw(M (1, i),q, beq((i-1)*q+1:i*q,1)),Lc(summ(M,i-1)*q+1:summ(M,i)*q,1),Uc(summ(M,i-1)*q+1: summ(M,i)*q,1)); Y0i = [Y0i ; Yi]; end Y0=[Y01;Y0i]; Y00 = ArrangeY 0total(Y 0, M, q, s) C = zeros(0); for i=1:s Cwi = input ('Cwi = '); C = [C ; Cwi]; end Y = Soluptionoptgeneralf distance(C, nn, delta, rho, s, l, q, L, U, M, epsilon, beq, Y 00) Time = cputime-t CC=MatrixCYNewtotal(M,q,l,Y,C,s); for i=1:s Ci=CC((summ(M, i -1))*l+1:(summ(M, i))*l,1:q); Yi=Y(summ(M, i -1)+1:summ(M, i), 1 : q); Li=L(summ(M, i -1)+1:summ(M, i), 1 : q); Ui=U(summ(M, i -1)+1:summ(M, i), 1 : q); CLw=zeros(0); for ii = 1: M(1,i) if Yi(ii,1:q)==Li(ii,1:q) CLw=[CLw;Ci((ii-1)*l+1:ii*l,1:q)]; end end CLw; CUw=zeros(0); for i1 = 1: M(1,i) if Yi(i1,1:q)==Ui(i1,1:q) CUw=[CUw;Ci((i1-1)*l+1:i1*l,1:q)]; end end CUw; CEw=zeros(0);

CEw=[CEw;Ci((i2-1)*l+1:i2*l,1:q)]; end end CEw; y1=size(CUw,1); y2=size(CEw,1); y3=size(CLw,1); z1=y1/l; z2=y2/l; z3=y3/l; b1=0; for i3=1:z1 for j=1:z3 if Count(CU w((i3 -1) * l + 1 : i3 * l, 1 : q), CLw((j -1) * l + 1 : j * l, 1 : q))¿=1 b1=b1+1; end end end if b1¿=1 disp('The first and second conditions are not satisfied') end b2=0; for i4=1:z2 for j=1:z3 if Count(CEw((i4 -1) * l + 1 : i4 * l, 1 : q), CLw((j -1) * l + 1 : j * l, 1 : q))¿=1 b2=b2+1; end end end if b2¿=1 disp('The first condition is not satisfied') else disp('The first condition is satisfied') end b3=0; for i5=1:z1 for j=1:z2 ifCount(CU w((i5 -1) * l + 1 : i5 * l, 1 : q), CEw((j -1) * l + 1 : j * l, 1 : q))¿=1 b3=b3+1; end end end if b3¿=1 disp('The second condition is not satisfied') else disp('The second condition is satisfied') end if size(CEw,1) = 0 A2=M axM atrixA(CEw, l, q); A1=M inM atrixA(CEw, l, q); if (size(CEw)==size(A1))-(size(CEw)==size(A2)) disp('The third condition is satisfied') else disp('The third condition is not satisfied') end disp('The next O/D pair') else disp('The third condition is satisfied') disp('The next O/D pair') end end 1. Subproblem function LchangeMCtotal = ArrangeLMCtotal(L,M,q,s) L1=ArrangeM CL(L(1 : M (1, 1), 1 : q), M (1, 1), q); LL=zeros(0); for i=2:s Larrange=[LL;ArrangeMCL(L(summ(M,i-1)+1:summ(M,i),1:q),M(1,i),q)]; LL=Larrange; end LchangeMCtotal=[L1;LL]; end 2. Subproblem function LchangeMC = ArrangeMCL(L,m,q) LchangeMC=zeros(0); for i=1:q LchangeMC=[LchangeMC;L(1:m,i)]; end end 3. Subproblem function UchangeMCtotal = ArrangeUMCtotal(U,M,q,s) U1=ArrangeM CU (U (1 : M (1, 1), 1 : q), M (1, 1), q); UU=zeros(0); for i=2:s Uarrange=[UU;ArrangeM CU (U (summ(M, i -1) + 1 : summ(M, i), 1 : q), M (1, i), q)]; UU=Uarrange; end UchangeMCtotal=[U1;UU]; end 4. Subproblem function UchangeMC = ArrangeMCU(U,m,q) UchangeMC=zeros(0); for i=1:q UchangeMC=[UchangeMC;U(1:m,i)]; end end 5. Subproblem function Aeq=FindAeq(m,q) Aeq0 = zeros(1); for i=1:m Aeq0 = [Aeq0 1]; end Aeq0(:,1)=[]; Aeq=zeros(m*q); for j=1:q Aeq(j,(j-1)*m+1:j*m)=Aeq0; end end 6. Subproblem function dwi = Collumdw(m,q,beq) dwi=[beq;zeros(m*q-q,1)]; end 7. Subproblem function Yn = FindSolutionoptfdistance(m,s,nn,delta,rho,q,l,L,U,epsilon,C, Aeq,beq,Y,M,Ytotal) Loop=0; B=Solutionoptf distance(m, s, rho, q, l, L, U, epsilon, C, Aeq, beq, Y, M, Y total); for i=1:nn diff=norm(B(m*q+1:2*m*q,1)-B(1:m*q,1),2); if (diff ¿= delta) B=Solutionoptf distance(m, s, rho, q, l, L, U, epsilon, C, Aeq, beq, ArrangeB(B(m * q + 1 : 2 * m * q, 1), m, q), M, ArrangeB(B(m * q + 1 : 2 * m * q, 1), m, q)); Y1=B(m*q+1:2*m*q,1); Loop=Loop+1; a=Loop else Y1=B(m*q+1:2*m*q,1); a=Loop; break end end Y2=Y1; Z1=zeros(0); for k=1:q Z1=[Z1 Y2((k-1)*m+1:k*m,1)]; end Tolerance=diff Yn=Z1; The numbers of loops=a end 8. Subproblem function B = Solutionoptfdistance(m,s,rho,q,l,L,U,epsilon,C,Aeq,beq,Y,M,Ytotal) C1=M atrixCY (m, q, l, Y total, C, M, s); B=ArrangeM CL(Y, m, q); Calpha = zeros(0); for i = 1:m if Count(Y (i, 1 : q), L(i, 1 : q))¿=1 Calpha = [Calpha ; C1(i*l-(l-1):i*l,1:q)]; end end n=size(Calpha,1)/l; F=zeros(0); for j=1:m fd=zeros(0); for ii = 1:n D=C1((j-1)*l+1:j*l,1:q)-Calpha((ii-1)*l+1:ii*l,1:q); if (D ¿=0)==zeros(l,q) fCalphaCj = -distancene(D)+ epsilon*SumM atrix(D); else fCalphaCj = distancepo(D)+ epsilon* SumM atrix(D); end fd=[fd;fCalphaCj]; end fd1=min(fd); fd2=zeros(0); for i = 1:q fd2=[fd2;fd1]; end F=[F;fd2]; end Fchange=[]; for i=1:m Fchange=[Fchange;F((i-1)*q+1:i*q,1)']; end Frechange=ArrangeM CL(F change, m, q); Y1=ArrangeM CL(Y, m, q); S1= Y1 -rho*Frechange; lb=ArrangeM CL(L, m, q); ub=ArrangeM CL(U, m, q); S2=lsqlin(eye(m*q),S1,[],[],Aeq,beq,lb,ub); Yn=(1-rho)*Y1+rho*S2; B= [B;Yn]; end 9. Subproblem function CY=MatrixCY(m,q,l,Y,C,M,s) CY=zeros(m*l,q); for i=1:m*l for j=1:q CY(i,j)=sum(sum( C((i-1)*summ(M,s)+1 : i*summ(M,s),(j-1)*q+1:j*q).*Y )); end end end 12. Subproblem function dis = distancepo(x) a=zeros(0); for i=1:size(x,1) for k=1:size(x,2) if x(i,k)¿0 a=[a;x(i,k)]; end end end b=a; sum=0; for j=1:size(b,1) for l=1:size(b,2) sum=sum+b(j,l). 2 ; end end dis=sqrt(sum); 13. Subproblem function Bchange = ArrangeB(B,m,q) Bchange=zeros(0); for i=1:q Bchange=[Bchange B((i-1)*m+1:i*m,1)]; end end 14. Subproblem function sum = summ(M,s) sum=0; for i=1:s sum=sum+M(1,i); end end 15. Subproblem function summatrix = SumMatrix( A ) summatrix = 0; for i = 1:size(A,1) for j = 1:size(A,2) summatrix = summatrix + A(i,j); end end end 16. Subproblem function Y0total = ArrangeY0total(Y0,M,q,s ) Y1=ArrangeY0(Y0(1:M(1,1)*q,1),M(1,1),q); YY=zeros(1,q); for i=2:s Yarrange=[YY;ArrangeY 0(Y 0(summ(M, i -1) * q + 1 : summ(M, i) * q, 1), M (1, i), q)]; YY=Yarrange; end YY(1,:)=[]; Y0total=[Y1;YY]; end 17. Subproblem function Ychange = ArrangeY0(Y0,m,q) Ychange=zeros(m,1); for i=0:(q-1) Ychange=[Ychange Y0(m*i+1:m*(i+1),1)]; end end end 21. Subproblem function MinA= MinMatrixA(A,l,q) [r1, r2]=size(A); s1=r1/l; MinA=zeros(0); B1=zeros(0); for i=1:s1 for j=1:s1 B=A((j-1)*l+1:j*l,1:q)-A((i-1)*l+1:i*l,1:q); B1=[B1;B]; end end B1; s2=size(B1,1)/r1; for i=1:s2 B2=B1((i-1)*r1+1:i*r1,1:q); s4=size(B2,1)/l; t=T extDM in(B2, q, l); if t==s4 MinA=[MinA;A((i-1)*l+1:i*l,1:q)]; else MinA=[MinA;zeros(0)]; end end end 22. Subproblem function a = TextDMax(D,q,l) r1=size(D,1); a=0; s1=r1/l; for i=1:s1 D1=D((i-1)*l+1:i*l,1:q); if DauM T T M ax(D1)==1-D1==zeros(l,q) a=a+1; end end end