Keywords

1 Introduction

The optimal flow allocation in a network is a central problem with both theoretical and practical aspects in fields as economics [12, 15], transportation [1, 16] and communication [10, 11]. In this respect, it was Wardrop in [16] who first identified the principles that capture two diverging notions of optimal flow inside networks: the user equilibrium and the system optimum.

Wardrop’s first principle, which describes the user equilibrium, states that the journey times on all routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route. A flow satisfying the above condition is also called a Wardrop equilibrium since users cannot reduce their journey time by selecting a different route [2]. The second principle states that the flow in the network minimizes the average journey times for all used routes. A flow satisfying Wardrop’s second principle is clearly optimum from a network operator perspective.

Although for a given network in general, the flows that satisfy Wardrop’s first and second principles don’t coincide, there are networks that have identical user equilibrium and system optimal flows. A flow that satisfies both principles simultaneously is called Wardrop optimal flow and the corresponding networks Wardrop optimal networks.

In the present paper we investigate Wardrop optimal flows on networks of parallel links and the properties of the associated Wardrop optimal networks. The flow from the origin to the destination node is distributed among the alternative links of the network and creates congestion externalities which cause an increase in the time needed for the journey captured by a strictly increasing link-specific latency function. We show that the user equilibrium and system optimum of a given network are connected through the associated Pigovian network and using this important relation we prove existence and uniqueness for convex networks and obtain sufficient and necessary conditions characterizing the system optimum of the network.

The paper is organized as follows: in the next section, we describe the network framework and present the notions of user equilibrium, system optimum and Wardrop optimal flow of a network. In Sect. 3, we present some useful properties concerning the existence and uniqueness of user equilibrium optimum in our networks. The system optimum is investigated in Sect. 4. We introduce the corresponding Pigovian network, prove existence and uniqueness and obtain sufficient and necessary conditions for the system optimum. In Sect. 5 we examine networks that have Wardrop optimal flows. We provide a characterization of Wardrop optimal flows for differentiable convex networks and using this result we show that Wardrop optimal flows are preserved via continuous, strictly increasing, convex functions. Moreover, we prove that they are preserved by uniform increase or decrease of the latency functions. Furthermore, we illustrate a method to construct networks that admit any given point as Wardrop optimal flow and prove that Wardrop optimal flows are preserved by network addition and multiplication.

2 Preliminaries

We consider networks of m parallel links \(\textbf{I}_m=\{1,2,\dots ,m\}\) between the two nodes of origin and destination and denote by \(x_i\ge 0\) the flow passing through the link i of the network, for all \(i\in \textbf{I}_m\). In this setup, a unit total flow has to be distributed among all network links. All traffic of the network is routed in the sense that it holds

$$\begin{aligned} \sum \nolimits _{i=1}^m x_i =1. \end{aligned}$$

We denote by \(\mathbb {S}^{m-1}=\{x\in \mathbb {R}_+^m:\sum _{i=1}^m x_i =1\}\) the standard simplex and using this convention the points of the simplex represent flows of the network. For a given flow x, we define the support of x by \(supp(x):=\{i\in \textbf{I}_m:x_i\ne 0\}\) and denote by \(\textrm{Int}(\mathbb {S}^{m-1})=\{x\in \mathbb {S}^{m-1}:supp(x)=\textbf{I}_m\}\) the set of all internal points of the simplex. The flow in each link causes congestion which increases the delay while traversing the link. This is measured by flow dependent latency functions

$$\begin{aligned} \ell _i(x):[0,1]\rightarrow [0,\infty ), i\in \textbf{I}_m, \end{aligned}$$

which are assumed continuous and strictly increasing.

With this formalism, a network of m parallel links between two nodes can be identified with the latency functions vector \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\). A differentiable network (resp. convex network) is a network \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\) with all the latency functions \(\ell _i(x)\) differentiable (resp. convex).

A user equilibrium or Wardrop equilibrium of a network \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\) is a flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) such that

$$\begin{aligned} \ell _k(x_k)=\underset{i\in \textbf{I}_m}{\min }\{\ell _i(x_i)\},\text { for all }k\in \textbf{I}_m\text { with }x_k>0, \end{aligned}$$

i.e., the delay is the same across all links with nonzero flow and smaller than the zero flow delay of the rest of the links [1]. The average delay of a network \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\) at a flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is given by the sum

$$\begin{aligned} \sum \nolimits _{i=1}^m x_i \ell _i(x_i). \end{aligned}$$

A system optimum of a network \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\) is a flow

$$\begin{aligned} x=(x_1,\dots ,x_m)\in \mathbb {S}^{m-1} \end{aligned}$$

that minimizes the average delay [1].

Given a network \(\mathbf {L_m}=(\ell _1(x),\dots , \ell _m(x))\), a flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is called a Wardrop optimal flow if it is user equilibrium and system optimum of the network \(\mathbf {L_m}\). A network that has a Wardrop optimal flow is called a Wardrop optimal network.

3 User Equilibrium and System Optimum

In this section we present the properties of the user equilibrium and the system optimum of a parallel network that we will need in the rest of the paper. The following lemma states that the user equilibrium is preserved by strictly increasing mappings.

Lemma 1

Given a network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) and a continuous and strictly increasing function \(f(x):[0,\infty ]\rightarrow [0,\infty )\), if a flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a user equilibrium of \(\mathbf {L_m}\) then it is also a user equilibrium of the network \(f(\mathbf {L_m})=(f(\ell _1(x)),\dots ,f(\ell _m(x))).\)

In general, the system optimum is not preserved even under continuous, strictly increasing and convex functions as opposed to user equilibrium. An important question that arises naturally at this point concerns whether Wardrop optimal flows are preserved by such transformations. This will be addressed in Theorem 7 of Sect. 4.

The following property regarding existence and uniqueness of a user equilibrium will be necessary for our construction later on.

Proposition 1

Every network \(\mathbf {L_m}\) has a unique user equilibrium.

Proof (Sketch of Proof)

For any network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), we prove that there is a unique flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) such that

$$\begin{aligned} \ell _k(x_k)=\underset{i\in \textbf{I}_m}{\min }\{\ell _i(x_i)\},\text { for all }k\in \textbf{I}_m\text { with }x_k>0 \end{aligned}$$

by showing that this can be obtained by taking the inverse of a stictly increasing function on an appropriate interval.

Now we proceed by examining internal points of the simplex \(\mathbb {S}^{1}\) and we identify a necessary but not sufficient condition for such a flow to be system optimum. This can be proved by considering \(\epsilon \)-perturbations from one link to the other and show that a better total latency always exists unless if the following condition is satisfied.

Proposition 2

Given two differentiable latency functions \(\ell _1(x),\ell _2(x)\), if the flow \((x_1,x_2)\in \textrm{Int}(\mathbb {S}^{1})\) is a system optimum of \(\textbf{L}_2=(\ell _1(x),\ell _2(x))\) then it holds

$$\begin{aligned} \ell _1(x_1)+x_1\ell _1'(x_1)=\ell _2(x_2)+x_2\ell _2'(x_2). \end{aligned}$$
(1)

The above result can be generalized for m parallel links as follows.

Proposition 3

Given a differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if the flow \(x=(x_1,\dots , x_m)\in \textrm{Int}(\mathbb {S}^{m-1})\) is a system optimum of \(\mathbf {L_m}\) then for all \(i,j\in \textbf{I}_m\) it holds

$$\ell _i(x_i)+x_i\ell _i'(x_i)=\ell _j(x_j)+x_j\ell _j'(x_j).$$

Proof

Using the result of Proposition 2, for any \(i,j\in \textbf{I}_m\), if

$$\ell _i(x_i)+x_i\ell _i'(x_i)>\ell _j(x_j)+x_j\ell _j'(x_j).$$

then we can obtain a lower total delay by \(\epsilon \)-reducing the flow of \(x_i\) and simultaneously \(\epsilon \)-increasing it for \(x_j\) and vice versa if the direction of the above inequality is the opposite. Since we assumed that x is a system optimum this can not be the case so we get the result.

The general case of flow \(x\in \mathbb {S}^{m-1}\) can be proved by taking into account zero flows.

Theorem 1

Given a differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a system optimum of \(\mathbf {L_m}\) then it holds

$$\ell _i(x_i)+x_i\ell _i'(x_i)=\ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

Given any differentiable latency function \(\ell _i(x)\), we introduce the Pigovian function

$$g_i(x)=\ell _i(x)+x\ell _i'(x).$$

In this way, to every differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) we can associate the corresponding Pigovian network \(\textbf{PL}_m=(g_1(x),\dots , g_m(x))\) and Theorem 1 can be reformulated illustrating the relation between a network and it’s corresponding Pigovian network.

Theorem 2

Given a differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if a flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a system optimum of \(\mathbf {L_m}\) then it is a user equilibrium of the corresponding Pigovian network \(\textbf{PL}_m=(g_1(x),\dots , g_m(x))\).

Proof

Direct result of Theorem 1 and the definition of the user equilibrium.

By employing Proposition 1 we obtain the following result regarding the uniqueness of a system optimum.

Proposition 4

There exists a unique system optimum for a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\).

Proof

Since the functions \(\ell _i(x)\) are differentiable in [0, 1] we get that their total delay

$$\sum \nolimits _{i=1}^m x_i \ell _i(x_i)$$

has at least one minimum, thus, by definition, there will be at least one system optimum of \(\mathbf {L_m}\). Moreover since \(\ell _i(x)\) are differentiable and convex we get that the functions \(g_i(x)\) will be continuous and strictly increasing. Hence from Proposition 1 there will be a unique user equilibrium of the network \(\textbf{PL}_m=(g_1(x),\dots , g_m(x))\). From Theorem 2, we get that every system optimum of \(\mathbf {L_m}\) is a unique user equilibrium of \(\textbf{PL}_m\). Therefore there is a unique system optimum of \(\mathbf {L_m}\) and it is the unique user equilibrium of \(\textbf{PL}_m\).

Combining Theorem 1 and Proposition 4 we obtain the following characterization of system optimums.

Theorem 3

The flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is the system optimum of a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) if and only if

$$\ell _i(x_i)+x_i\ell _i'(x_i)=\ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

The system optimum of a network can be characterized as the user equilibrium of the corresponding Pigovian network in the following way.

Theorem 4

The flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is the system optimum of a differential and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) if and only if it is the user equilibrium of \(\textbf{PL}_m=(g_1(x),\dots , g_m(x))\), i.e. if and only if it holds

$$\ell _k(x_k)+x_kl'(x_k)=\min _{i\in \textbf{I}_n}\{\ell _i(x_i)+x_i\ell _i'(x_i)\},\quad \text { for all }x_k>0.$$

4 Wardrop Optimal Networks

In this section we examine Wardrop Optimal networks i.e., networks that have identical user equilibrium and system optimum. First we identify necessary conditions for a user equilibrium to be system optimum.

Proposition 5

Given a differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if a user equilibrium \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) of \(\mathbf {L_m}\) is also a system optimum of \(\mathbf {L_m}\) then it holds

$$x_i\ell _i'(x_i)=x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0$$

Proof

If \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a system optimum of \(\mathbf {L_m}\) then, from Theorem 3 it holds

$$\ell _i(x_i)+x_i\ell _i'(x_i)=\ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0$$

The result is obtained by taking into account that \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a user equilibrium i.e., that it holds

$$\ell _i(x_i) =\ell _j(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0.$$

In the following Proposition we prove that if the network is in addition convex then the conditions of Proposition 5 are sufficient.

Proposition 6

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if for a user equilibrium \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) of \(\mathbf {L_m}\) it holds

$$x_i\ell _i'(x_i)=x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0,$$

then it is a system optimum of \(\mathbf {L_m}\).

Proof

By considering Theorem 3 we only need to show that for \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) it holds

$$\ell _k(x_k)+x_kl'(x_k)=\min _{i\in \mathbb {I}_n}\{\ell _i(x_i)+x_i\ell _i'(x_i)\},\quad \text { for all }x_k>0.$$

or equivalently

$$\ell _i(x_i)+x_i\ell _i'(x_i)=\ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

The result is obtained by taking into account that \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a user equilibrium i.e., it holds

$$\ell _i(x_i) =\ell _j(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

and

$$\ell _i(0)\ge \ell _j(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

Hence we obtain the following theorem describing the necessary and sufficient conditions for a user equilibrium to be system optimum.

Theorem 5

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), a user equilibrium \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) of \(\mathbf {L_m}\) is a system optimum of \(\mathbf {L_m}\) if and only if it holds

$$x_i\ell _i'(x_i)=x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0,$$

and

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

On the other hand if x is a system optimum, the requirements for x to be a user equilibrium are more relaxed as it is illustrated in the following proposition.

Proposition 7

Given a differentiable network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\), if for a system optimum \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) of \(\mathbf {L_m}\) it holds

$$\ell _i(x_i)=\ell _j(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0$$

then it is a user equilibrium of \(\mathbf {L_m}\).

Proof

By the definition of user equilibrium we only have to show that

$$\ell _i(0)\ge \ell _j(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.$$

Since x is system optimum, by Theorem 1, we get that it holds

$$\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0,$$

which concludes the proof.

The Wardrop optimal flows of a network can now be characterized as follows:

Theorem 6

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) a flow \((x_1,\dots , x_m)\in \mathbb {S}^{m-1}\), is Wardrop optimal flow if and only if all the following conditions hold.

  1. i)

    \(\ell _i(x_i) =\ell _j(x_j), \quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0,\)

  2. ii)

    \(x_i\ell _i'(x_i)=x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0,\)

  3. iii)

    \(\ell _i(0)\ge \ell _j(x_j)+x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i=0,\text { and }x_j>0.\)

For internal flows \((x_1,\dots , x_m)\in \textrm{Int}(\mathbb {S}^{m-1})\) we obtain the following corollary of the previous Theorem.

Corollary 1

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) a flow \((x_1,\dots , x_m)\in \textrm{Int}(\mathbb {S}^{m-1})\), is Wardrop optimal flow if and only if all the following conditions hold

  1. i)

    \(\ell _i(x_i) =\ell _j(x_j), \quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0,\)

  2. ii)

    \(x_i\ell _i'(x_i)=x_j\ell _j'(x_j),\quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0.\)

We are now ready to settle the question we posed in Sect. 3 regarding the behavior of Wardrop optimal flows under strictly increasing and convex network transformations.

Theorem 7

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) and a continuous, strictly increasing and convex function \(f(x):[0,\infty ]\rightarrow [0,\infty ]\), if the flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is a Wardrop optimal flow of \(\mathbf {L_m}\) then it is also a Wardrop optimal flow of

$$\begin{aligned} f(\mathbf {L_m})=(f(\ell _1(x)),\dots , f(\ell _m(x))). \end{aligned}$$

Proof (Sketch of Proof)

From Lemma 1 and given that x is the user equilibrium of \(\mathbf {L_m}\) we get that x is the user equilibrium of the network \(f(\mathbf {L_m})\). From x being system optimum of \(\mathbf {L_m}\) we prove the second condition of Theorem 6 for the set \(f(\mathbf {L_m})\). Finally we need the convexity of f(x) to prove the third condition of Theorem 6.

From Theorem 7 we obtain that a Wardrop optimal flow is preserved if the network is transformed by adding a constant toll price to the latency of each link or by increasing (resp. decreasing) the latency on every link by the same percentage. This is illustrated in the following corollaries.

Corollary 2

If a flow \(x\in \mathbb {S}^{m-1}\) is a Wardrop optimal flow of a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) then it is also a Wardrop optimal flow of the network

$$\begin{aligned} \mathbf {L_m+b}=(\ell _1(x)+b,\dots ,\ell _m(x)+b) \end{aligned}$$

for all \(b>0\).

Corollary 3

If a flow \(x\in \mathbb {S}^{m-1}\) is a Wardrop optimal flow of a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) then it is also a Wardrop optimal flow of the network

$$\begin{aligned} \mathbf {aL_m}=(a\ell _1(x), \dots , a\ell _m(x)), \end{aligned}$$

for all \(a>0\).

Moreover, since we only employ the convexity condition to prove the third part of Theorem 6, we obtain the following.

Corollary 4

Given a differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) and a continuous, strictly increasing function \(f(x):[0,\infty ]\rightarrow [0,\infty ]\), if the flow \(x=(x_1,\dots , x_m)\in int\mathbb {S}^{m-1}\) is a Wardrop optimal flow of \(\mathbf {L_m}\) then it is also a Wardrop optimal flow of \(f(\mathbf {L_m})=(f(\ell _1(x)),\dots , f(\ell _m(x)))\).

Wardrop optimal flows are also preserved if a network is transformed by taking powers of the latency functions and this can be alternatively proved without using Theorem 7.

Proposition 8

If the flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is Wardrop optimal flow of the differentiable and convex network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) then it is also Wardrop optimal flow of \(\mathbf {L_m^k}=(\ell _1^k(x),\dots , \ell _m^k(x))\), \(k\in \mathbb {N}^*\).

Proof

Since x is Wardrop optimal flow of \(\mathbf {L_m}\), by the first condition of Theorem 6 we get

$$\begin{aligned} \ell _i^k(x_i) =\ell _j^k(x_j), \quad \text { for all }i,j\in \textbf{I}_m\text { with }x_i,x_j>0 \end{aligned}$$
(2)

Taking into account the first and the second condition of Theorem 6 we have

$$\begin{aligned} x_i(\ell _i^k(x_i))'=x_i\, k\, \ell _i^{k-1}(x_i)\, \ell _i'(x_i)=x_j\, k\, \ell _j^{k-1}(x_j)\, \ell _j'(x_j)=x_j(\ell _j^k(x_j))'. \end{aligned}$$
(3)

At this point we note that all latency functions are defined on the domain [0, 1], hence the functions \(\ell _i^k(x)\) will be convex for all \(k\in \mathbb {N}^*\) and we can used Theorem 6 to prove this proposition. From Eqs. 2 and 3 we get that the first two conditions of Theorem 6 are satisfied by x for the network \(\mathbf {L_m^k}\). It now remains to prove the third condition, i.e., that for all \(i,j\in \textbf{I}_m\) with \(x_i=0\) and \(x_j>0\) we have

$$\ell _i^k(0)\ge \ell _j^k(x_j)+x_j\left( \ell _j^k(x_j)\right) '=\ell _j^k(x_j)+x_j\,k\,\ell _j^{k-1}(x_j)\,\ell _i'(x)$$

Since x is Wardrop optimal flow of \(\mathbf {L_m}\), by taking the power of the third condition of Theorem 6, for all for all \(i,j\in \textbf{I}_m\) with \(x_i=0\) and \(x_j>0\) we have

$$\begin{aligned} \ell _i^k(0)&\ge (\ell _j(x_j)+x_j\ell _j'(x_j))^k=\ell _j^k(x_j)+\left( \begin{matrix}k\\ 1\end{matrix}\right) \ell _j^{k-1}(x_j)x_j\ell _j'(x_j)+C, \end{aligned}$$

where C denotes the sum of the remaining terms of the binomial identity we used above. The result follows by observing that C is positive.

Networks with identical flows admit the center of the simplex as the Wardrop optimal flow as it is shown in the below proposition.

Proposition 9

A network \(\mathbf {L_m}=(l(x),\dots , l(x))\) with identical latency functions across all links has a uniformly distributed Wardrop optimal flow.

Proof

It is easy to check that \(x=(\frac{1}{n},\dots , \frac{1}{n})\). i.e., the center of the simplex \(\mathbb {S}^{n-1}\), is the Wardrop optimal flow of \(\mathbf {L_m}\).

In a similar way we get that for any a priori given internal flow \(\textbf{p}=(p_1,\cdots ,p_n)\in int \mathbb {S}^{m-1}\), there exists always a network for which \(\textbf{p}\) is its Wardrop optimal flow.

Proposition 10

Any internal flow \(\textbf{p}=(p_1,\cdots ,p_n)\in int \mathbb {S}^{m-1}\) is the Wardrop optimal flow of the network \(\mathbf {L_m}=(\frac{x_1}{p_1},\dots ,\frac{x_m}{p_m})\).

By combining the above result with Corollary 4, we can find more networks admitting any given user equilibrium.

Proposition 11

An internal flow \(\textbf{p}=(p_1,\cdots ,p_n)\in int \mathbb {S}^{m-1}\) is the Wardrop optimal flow of the network \(\mathbf {L_m}=(f (\frac{x_1}{p_1}),\dots ,f (\frac{x_m}{p_m}))\), where f(x) is any continuous, strictly increasing function.

The product of two differentiable and convex latency functions is also a differentiable and convex function and thus we can use Theorem 6 to prove the following result.

Proposition 12

If the flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is Wardrop optimal flow of the differentiable and convex networks \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) and \(\mathbf {\overline{L}_m}=(\overline{\ell }_1(x),\dots ,\overline{\ell }_m(x))\) then it is also Wardrop optimal flow of the network \(\mathbf {L_m}\mathbf {\overline{L}_m}=(\ell _1(x)\overline{\ell }_1(x),\dots ,\ell _m(x)\overline{\ell }_m(x))\).

Similarly with the above, we can use again Theorem 6 to prove the following, since differentiable and convex functions are preserved by addition .

Proposition 13

If the flow \(x=(x_1,\dots , x_m)\in \mathbb {S}^{m-1}\) is Wardrop optimal flow of the differentiable and convex networks \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) and \(\mathbf {\overline{L}_m}=(\overline{\ell }_1(x),\dots ,\overline{\ell }_m(x))\) then it is also Wardrop optimal flow of the network \(\mathbf {L_m}+\mathbf {\overline{L}_m}=(\ell _1(x)+\overline{\ell }_1(x),\dots ,\ell _m(x)+\overline{\ell }_m(x))\).

By using Corollary 4 we can construct networks for given internal flows as follows.

Proposition 14

For any polynomial \(P(x)=a_0+a_1x+\cdots +a_nx^n\), strictly increasing and continuous in [0,1] and any internal flow \(\textbf{p}=(p_1,\cdots ,p_n)\in int \mathbb {S}^{m-1}\) we can construct a network \(\mathbf {L_m}=(\ell _1(x),\dots ,\ell _m(x))\) with \(\ell _1(x)=P(x)\) with Wardrop optimal flow \(\textbf{p}\).

Proof

Assume \(P(x)=a_0+a_1x+a_2 x^2+\cdots +a_nx^n\) is a polynomial strictly increasing and continuous in [0,1] and \(\textbf{p}=(p_1,\cdots ,p_n)\) any given flow. Then by taking the image of the network \(\mathbf {L_m}=(\frac{x}{p_1}, \dots , \frac{x}{p_m})\) via the function

$$\begin{aligned} f(x)=a_0+a_1p_1x+a_2p_1^2 x^2+\cdots +a_np_1^nx^n \end{aligned}$$

we obtain a network that has P(x) as latency function on the first link. The function f(x) is also continuous and strictly increasing in [0, 1] since from \(f(x)=P(p_1x)\) and \(0<p_1<1\) we get that f(x) is the composition of two strictly increasing and continuous functions.

5 Conclusion and Future Work

We examined user equilibrium and system optimum in parallel networks with congestion externalities and obtained sufficient and necessary conditions for the system optimum. This leads to a characterization of Wardrop optimal flows for differentiable convex networks from which we obtained important closure properties preserving Wardrop optimal flows.

The importance of Wardrop optimal networks for transportation and communication networks stems from the integration of the interests of both users and system operators. Convergence to the Wardrop optimal flow inside such networks will allow us to simulate dynamic flow distribution in networks in the manner of [13, 14]. Wardrop optimal flows can be investigated in the framework of general directed graphs by identifying a fixed origin and destination node in the graph and considering all possible paths from origin to destination as this has been done using the path hyperoperation on directed graphs [7, 9]. This will allow us to model diffusion inside Wardrop networks as in [3] and moreover, as another future direction, the capacity of graph recognizability to identify graph properties (see [4,5,6, 8]) can be employed towards the recognition of Wardrop optimal networks.