# Traffic Network Equilibrium Problems with Capacity Constraints of Arcs and Linear Scalarization Methods

Authors: X. Q. Tian; Y. D. Xu
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Traffic network equilibrium problems with capacity constraints of arcs are studied. A (weak) vector equilibrium principle with vector-valued cost functions, which are different from the ones in the work of Lin (2010), and three kinds of parametric equilibrium flows are introduced. Some necessary and sufficient conditions for a (weak) vector equilibrium flow to be a parametric equilibrium flow are derived. Relationships between a parametric equilibrium flow and a solution of a scalar variational inequality problem are also discussed. Some examples are given to illustrate our results.


---

## Body

## 1. Introduction

The earliest traffic network equilibrium model was proposed by Wardrop [1] for a transportation network. After getting Wardrop’s equilibrium principle, many scholars have studied variant kinds of network equilibrium models, see, for example, [2–5]. However, most of these equilibrium models are based on a single criterion. The assumption that the network users choose their paths based on a single criterion may not be reasonable. It is more reasonable to assume that no user will choose a path that incurs both a higher cost and a longer delay than some other paths. In other words, a vector equilibrium should be sought based on the principle that the flow of traffic along a path joining an O-D pair is positive only if the vector cost of this path is the minimum possible among all the paths joining the same O-D pair. Recently, equilibrium models based on multiple criteria or on a vector cost function have been proposed. In [6], Chen and Yen first introduced a vector equilibrium principle for vector traffic network without capacity constraints. In [7, 8], Khanh and Luu extended vector equilibrium principle to the case of capacity constraints of paths. For other results of vector equilibrium principle with capacity constraints of paths, we refer to [9–17].Very recently, in [18, 19], Lin extended traffic network equilibrium principle to the case of capacity constraints of arcs and obtained a sufficient condition and stability results of vector traffic network equilibrium flows with capacity constraints of arcs. In [20], Xu et al. also considered that vector network equilibrium problems with capacity constraints of arcs. By virtue of a Δ function, which was introduced by Zaffaroni [21], the authors introduced a Δ-equilibrium flow and a weak Δ-equilibrium flow, respectively, and obtained sufficient and necessary conditions for a weak vector equilibrium flow to be a (weak) Δ-equilibrium flow.In this paper, our aim is to further investigate traffic network equilibrium problems with capacity constraints for arcs. We introduce a (weak) vector equilibrium principle with vector-valued cost functions, which are more reasonable from practical point of view than the ones in [18, 19]. In order to obtain necessary and sufficient conditions for a (weak) vector equilibrium, we introduce three kinds of parametric equilibrium flows. Simultaneously, we also discuss relationships between a parametric equilibrium flow and a solution of a scalar variational inequality problem.The outline of the paper is as follows. In Section2, a (weak) equilibrium principle with capacity constraints of arcs is introduced. In Section 3, three kinds of parametric equilibrium flows are introduced. Some sufficient and necessary conditions for a (weak) vector equilibrium flow are obtained. Relationships between a parametric equilibrium flow and a solution of a scalar variational inequality problem are also discussed.


## 2. Preliminaries

For a traffic network, letN and E denote the set of nodes and directed arcs, respectively, and let C=(ce)e∈E denote the capacity vector, where ce (>0) denotes the capacity of arc e∈E. Let W denote the set of origin-destination (O-D) pairs and let D=(dw)w∈W denote the demand vector, where dw (>0) denotes the demand of traffic flow on O-D pair w. A traffic network with capacity constraints of arcs is usually denoted by G=(N,E,C,W,D). For each arc e∈E, the arc flow needs to satisfy the capacity constraints: ce≥ve≥0, for each e∈E. For each w∈W, let Pw denote the set of available paths joining O-D pair w. Let m=∑w∈W‍|Pw|. For a given path k∈Pw, let hk denote the traffic flow on this path and h=(h1,h2,…,hm)∈Rm is called a path flow. The path flow vector h induces an arc flow ve on each arc e∈E given by
(2.1)ve=∑w∈W‍∑k∈Pw‍δekhk,
where δek=1 if the arc e is contained in path k and 0, otherwise. Suppose that the demand of network flow is fixed for each O-D pair w. We say that a path flow h satisfies demand constraints
(2.2)∑k∈Pw‍hk=dw,∀w∈W.
A path flow h satisfying the demand constraints and capacity constraints is called a feasible path flow. Let H={h∈R+m : for all w∈W,  ∑k∈Pw‍hw=dw and for all e∈E, ce≥ve≥0}={h∈R+m : for all w∈W, ∑k∈Pw‍hw=dw and for all e∈E, ce≥∑w∈W‍∑k∈Pw‍δekhk≥0} and let H≠∅. Clearly, H is convex and compact. Let te(hk):R+→Rr be a vector-valued cost function for the path k on the arc e. Let Tk(h):R+m→Rr be a vector-valued cost function along the path k. Then the vector-valued cost on the path k is equal to the sum of the all costs of the flow hk through arcs, which belong to the path k, that is,
(2.3)Tk(h)=∑e∈E‍δekte(hk).
Let T(h)=(T1(h),T2(h),…,Tm(h))∈Rr×m.Remark 2.1.
In [18, 19], Lin defined the vector cost function along the path k as follows:
(2.4)T-k(h)=∑e∈E‍δekt-e(h),
where t-e(h):Rm→Rr be a vector-valued cost function for arc e. If the paths have common arcs, then the definition is unreasonable. The following example can illustrate the case.Example 2.2.
Consider the network problem depicted in Figure1. V={1,2,3,4}, E={e1,e2,e3,e4,e5}, C=(3,2,2,4,3), W={(1,4),(3,4)}, D=(3,4). The cost functions of arcs from R to R are, respectively, as follows:
(2.5)t-e1(h)=t-e1(ve1)=50ve1+100,t-e2(h)=t-e2(ve2)=20ve2+500,t-e3(h)=t-e3(ve3)=60ve3+100,t-e4(h)=t-e4(ve4)=30ve4+200,t-e5(h)=t-e5(ve5)=70ve5+300.Figure 1
Network topology for an example.ForO-D pair (1, 4): P(1,4) includes path 1=(1,2,4) and path 2=(1,4), for O-D pair (3,4):P(3,4) includes path 3=(3,2,4) and path 4=(3,4). And by (2.4), we have
(2.6)T-1(h)=t-e1(h)+t-e5(h)=50ve1+70ve5+400,T-2(h)=t-e2(h)=20ve2+500,T-3(h)=t-e3(h)+t-e5(h)=60ve3+70ve5+400,T-4(h)=t-e4(h)=30ve4+200.
Then, for flow h=(h1,h2,h3,h4)=(2,1,1,3), we have that arc flows
(2.7)v=(ve1,ve2,ve3,ve4,ve5)=(2,1,1,3,3).
It follows from (2.4) that
(2.8)T-1(h)=t-e1(ve1)+t-e5(ve5)=50×2+100+70×3+300=710,T-3(h)=t-e3(ve3)+t-e5(ve5)=60×1+100+70×3+300=670.
However, from the practical point of view, the cost values of the path 1 and path 3 with respect to h are, respectively, as follows:
(2.9)T1(h)=t-e1(h1)+t-e5(h1)=50×2+100+70×2+300=640,T3(h)=t-e3(h3)+t-e5(h3)=60×1+100+70×1+300=530.
So, in this paper, we define the vector-valued cost function on a path as (2.3).In this paper, the cost space is anr-dimensional Euclidean space Rr, with the ordering cone S=R+r, a pointed, closed, and convex cone with nonempty interior intS. We define the ordering relation as follows:
(2.10)x≤Sy,iffy-x∈S;x<Sy,iffy-x∈intS.
The orderings ≥S and >S are defined similarly. In the sequel, we let the set S+:={φ∈Rr:φ(s)≥0, for all s∈S} be the dual cone of S. Denote the interior of S+ by
(2.11)intS+:={φ∈Rr:φ(s)>0,∀s∈S∖{0}}.Lemma 2.3 (see [22]).
Consider(2.12)S∖{0}:={x∈Rr:φ(x)>0,∀φ∈intS+},intS:={x∈Rr:φ(x)>0,∀φ∈S+∖{0}}.Definition 2.4 (see [18, 19]).
Assume that a flowh∈H, (i)
fore∈E, if ve=ce, then arc e is said to be a saturated arc of flow h, otherwise a nonsaturated arc of flow h.(ii)
fork∈⋃w∈W‍Pw, if there exists a saturated arc e of flow h such that e belongs to path k, then path k is said to be a saturated path of flow h, otherwise a nonsaturated path of flow h.We introduced the following vector equilibrium principle and weak vector equilibrium principle.Definition 2.5 (vector equilibrium principle).
A flowh∈H is said to be a vector equilibrium flow if for all w∈W, for all k,j∈Pw, we have
(2.13)Tk(h)-Tj(h)∈S∖{0}⇒hk=0orpathjisasaturatedpathofflowh.Definition 2.6 (weak vector equilibrium principle).
A flowh∈H is said to be a weak vector equilibrium flow if for all w∈W, for all k,j∈Pw, we have
(2.14)Tk(h)-Tj(h)∈intS⇒hk=0orpathjisasaturatedpathofflowh.
If for all e∈E, ce=c≥∑w∈W‍dw, then the capacity constraints of arcs are invalid, in this case, the traffic equilibrium problem with capacity constraints of arcs reduces to the traffic equilibrium problem without capacity constraints of arcs.


## 3. Sufficient and Necessary Conditions for a (Weak) Vector Equilibrium Flow

In this section, we introduce anintS+-parametric equilibrium flow, a S+∖{0}-parametric equilibrium flow and a φ-parametric equilibrium flow, respectively. By using the three new concepts, we can obtain some sufficient and necessary conditions of a vector equilibrium flow and a weak vector equilibrium flow, respectively.Definition 3.1.
A flowh∈H is said to be in intS+-parametric equilibrium if for all w∈W, for all k,j∈Pw and for all φ∈intS+, we have
(3.1)φ(Tk(h)-Tj(h))>0⇒hk=0orpathjisasaturatedpathofflowh.Definition 3.2.
A flowh∈H is said to be in S+∖{0}-parametric equilibrium if for all w∈W, for all k,j∈Pw and for all φ∈S+∖{0}, we have
(3.2)φ(Tk(h)-Tj(h))>0⇒hk=0orpathjisasaturatedpathofflowh.Definition 3.3.
Let aφ∈S+∖{0} be given. A flow h∈H is said to be in φ-parametric equilibrium flow if for all w∈W and for all k,j∈Pw, we have
(3.3)φ(Tk(h)-Tj(h))>0⇒hk=0orpathjisasaturatedpathofflowh.TheintS+-equilibrium flow and φ-parametric equilibrium flow for some φ∈intS+ are defined in Definitions 3.1 and 3.2, respectively. They can be used to characterize vector equilibrium flow in the following theorems.Theorem 3.4.
A flowh∈H is in vector equilibrium if and only if the flow h is in intS+-parametric equilibrium.Proof.
It can get immediately the above conclusion by Lemma2.3. Thus the proof is omitted here.Theorem 3.5.
If there existsφ∈intS+ such that a flow h∈H is in φ-parametric equilibrium, then the flow h is in vector equilibrium.Proof.
Suppose that for anyO-D pair w∈W, for all k,j∈Pw, we have
(3.4)Tk(h)-Tj(h)∈S∖{0}.
By φ∈intS+ and Lemma 2.3, we get immediately
(3.5)φ[Tk(h)-Tj(h)]>0.
Since h is in φ-parametric equilibrium, we have
(3.6)hk=0orpathjisasaturatedpathofflowh.
Thus, the flow h∈H is in vector equilibrium.Now, we give the following example to illustrate Theorem3.5.Example 3.6.
Consider the network problem depicted in Figure2. N={1,2,3,4}, E={e1,e2,e3,e4,e5,e6}, C=(3,3,3,2,3,4)T, W={(1,4),(3,4)}, D=(6,4). The cost functions of arcs from R to R2 are defined as follows:
(3.7)te1(h1)=(h12+12h1),te2(h2)=(5h23h22),te3(h3)=(h32+75h3),te4(h4)=(2h4+13h4),te5(h5)=(3h526h5),te6(h1)=(h122h1),te6(h4)=(h422h4).
Then, we have(3.8)T1(h)=te1(h1)+te6(h1)=(2h12+14h1),T4(h)=te4(h4)+te6(h4)=(h42+2h4+15h4),T2(h)=te2(h2)=(5h23h22),T3(h)=te3(h3)=(h32+75h3),T5(h)=te5(h5)=(3h526h5).Figure 2
Network topology for an example.Takingh*=(2,2,2,2,2)′∈H, then there exists φ-=(1,1)∈intR+2 such that the flow h* is in φ--parametric equilibrium. Thus, by Theorem 3.5, we have that the flow h* is in vector equilibrium.For weak vector equilibrium flows, we have following similar results.Theorem 3.7.
A path flowh∈H is in weak vector equilibrium if and only if the flow h is in S+∖{0}-parametric equilibrium.Theorem 3.8.
If there existsφ∈S+∖{0} such that a path flow h∈H is in φ-parametric equilibrium, then the flow h is in weak vector equilibrium.From Theorems3.4–3.8, we can get immediately the following corollaries.Corollary 3.9.
If there existsφ∈intS+ such that a flow h∈H is in φ-parametric equilibrium, then the flow h is in intS+-parametric equilibrium.Corollary 3.10.
If there existsφ∈S+∖{0} such that a flow h∈H is in φ-parametric equilibrium, then the flow h is in S+∖{0}-parametric equilibrium.Remark 3.11.
When a flowh∈H is in intS+-parametric equilibrium, then, the flow h may not be in φ-parametric equilibrium for some φ∈intS+. Of course, when a flow h∈H is in S+∖{0}-parametric equilibrium, then, the flow h may not be in φ-parametric equilibrium for some φ∈S+∖{0}. The following example can explain these cases.Example 3.12.
Consider the network problem depicted in Figure1. N={1,2,3,4}, E={e1,e2,e3,e4,e5,}, C=(3,3,2,4,3,), W={{1,4},{3,4}}, D={3,4}. Let the cost functions of arcs are defined as follows:
(3.9)te1(h1)=(h12+2h12+3),te2(h2)=(h22+h2+2h2+2),te3(h3)=(3h32+22h3+2),te4(h4)=(2h4+4h4+1),te5(h1)=(h12+22h1),te5(h3)=(h32+22h3).
Then, we have(3.10)T1(h)=te1(h1)+te6(h1)=(2h12+4h12+2h1+3),T2(h)=te2(h2)=(h22+h2+2h2+2),T3(h)=te3(h3)=te3(h3)+te5(h3)=(4h32+44h3+2),T4(h)=te4(h4)=(2h4+4h4+1).Taking(3.11)h*=(1,2,1,3)′,
we have
(3.12)T1(h*)=(66),T2(h*)=(84),T3(h*)=(86),T4(h*)=(104).
Thus, by Definitions 3.1 and 3.2, we know that the flow h* is a intS+-parametric equilibrium flow and is a S+∖{0}-parametric equilibrium flow as well. On the other hand, for φ=(1,1/2)′∈intS+⊂S+∖{0}, there exists w={1,4} and path 1,2∈Pw, we have
(3.13)φ[T2(h*)-T1(h*)]=1>0.
But, h2=2>0 and path 1 is nonsaturated path of h*. Thus, it follows from Definition 3.3 that the flow h* is not in φ-parametric equilibrium.Theorem 3.13.
Letφ∈S+∖{0} be given. A flow h∈H is in φ-parametric equilibrium if the flow h solves the following scalar variational inequality:
(3.14)∑w∈W‍∑p∈Pw‍φ(Tp(h))(fp-hp)≥0,∀f∈H.Proof.
Assume thath∈H solves above scalar variational inequality problem. For all w∈W, for all k,j∈Pw, if φ[Tk(h)-Tj(h)]=φ[Tk(h)]-φ[Tj(h)]>0 and path j is nonsaturated path of flow h, we need to prove that hk=0. Denote that pj={e∈E∣arce belongs to path j}. If the conclusion is false, then
(3.15)ϵ=min{mine∈pj(ce-ve),hk}>0.
Construct a flow f as follows:
(3.16)f=(fl)={hl,ifl≠korj,(hk-ϵ),ifl=k,(hj+ϵ),ifl=j.
It is easy to verify that
(3.17)f∈H.
It follows readily that
(3.18)∑w∈W‍∑p∈Pw‍φ(Tp(h))(fp-hp)=φ(Tk(h))(fk-hk)+φ(Tj(h))(fj-hj)=ϵ(φ[Tj(h)]-φ[Tk(h)])<0,
which contradicts (3.14). Thus, h is in φ-parametric equilibrium and the proof is complete.From Theorems3.4–3.13, we can get the following corollary.Corollary 3.14.
If there existsφ∈intS+ (φ∈S+∖{0}) such that a flow h∈H is a solution of the following scalar variational inequality:
(3.19)∑w∈W∑p∈Pw‍φ(Tp(h))(fp-hp)≥0,∀f∈H,
then the flow h is in (weak) vector equilibrium.Remark 3.15.
We can prove that the the converse of Theorem3.13 is valid when the traffic network equilibrium problem without capacity constraints of arcs, such as traffic network equilibrium problems without capacity constraints or with capacity constraints of paths. The result will be showed on Theorem 3.18. But, if the traffic network equilibrium problem with capacity constraints of arcs, then the converse of Theorem 3.13 may not hold. The following example is given to illustrate the case.Example 3.16.
Consider the network problem depicted in Figure1. N={1,2,3,4}, E={e1,e2,e3,e4,e5}, C=(3,2,2,4,3), W={{1,4},{3,4}}, D={3,4}. Let the cost functions of arcs are defined as follows:
(3.20)te1(h1)=(h1h12),te2(h2)=(h22+3h2+5h23+4h2+3),te3(h3)=(h33+3h32+4),te4(h4)=(h4+4h4+4),te5(h1)=(h12+1h1),te5(h3)=(h32+1h3).Then, we have(3.21)T1(h)=te1(h1)+te5(h1)=(h12+h1+1h12+h1),T2(h)=te2(h2)=(h22+3h2+5h23+4h2+3),T3(h)=te3(h3)+te5(h3)=(h33+h32+4h32+h3+4),T4(h)=te4(h4)=(h4+4h4+4).
Taking
(3.22)h*=(2,1,1,3)′,
we have
(3.23)T1(h*)=(76),T2(h*)=(98),T3(h*)=(66),T4(h*)=(77).
Then for any φ∈intS+(φ∈S+∖{0}), we have
(3.24)φ[T2(h*)-T1(h*)]>0,φ[T4(h*)-T3(h*)]>0,
and path 1 is a saturated arc path of h*, and path 3 is a saturated arc path of h* as well. Thus, the flow h* is a φ-parametric equilibrium flow by Definition 3.3. However, taking f=(3,0,0,4)′∈H, we have
(3.25)∑w∈W‍∑p∈Pw‍Tp(h*)(fp-hp*)=(-1,-1)′.
Thus, for any φ∈intS+(φ∈S+∖{0}), we can always get
(3.26)∑w∈W‍∑p∈Pw‍φ(Tp(h*))(fp-hp*)<0.
Therefore, the converse of Theorem 3.13 is not valid.The following theorem shows that the converse of Theorem3.13 is valid when the traffic equilibrium problem with capacity constraints of paths. The proof is similar when the traffic network equilibrium problem without capacity constraints. Let
(3.27)K:={h∣λ≤h≤μ,∑p∈Pw‍hp=dw,∀w∈W},
be the feasible set of traffic network equilibrium problem with capacity constraints of paths, where λ=(λ1,λ2,…,λm) and μ=(μ1,μ2,…,μm) are lower and upper capacity constraints of paths, respectively. The φ-parametric equilibrium principle of traffic equilibrium problem with capacity constraints of paths is as follows.Definition 3.17.
Let aφ∈S+∖{0} be given. A flow h∈H is said to be in φ-parametric equilibrium flow if for all w∈W and for all k,j∈Pw, we have
(3.28)φ(Tk(h)-Tj(h))>0⇒hj=μjorhk=λk.Theorem 3.18.
Letφ∈S+∖{0} be given. A path h∈K is in φ-parametric equilibrium if and only if the flow h solves the following scalar variational inequality:
(3.29)∑w∈W‍∑p∈Pw‍φ(Tp(h))(fp-hp)≥0,∀f∈K.Proof.
From Theorem3.13, we only prove necessity. So, we set
(3.30)Aw:={v∈Pw∣hv>λv},Bw:={u∈Pw∣hu<μu}.
It follows from the definition of the φ-parametric equilibrium flow that
(3.31)φ[Tu(h)]≥φ[Tv(h)],∀u∈Bw,v∈Aw.
Thus, there exists a γw∈R such that
(3.32)minu∈Bwφ[Tu(h)]≥γw≥maxv∈Awφ[Tv(h)].
Let f∈K be arbitrary. Then, for every r∈Pw, we consider three cases.
Case  1. If φ[Tr(h)]<γw, then r∉Bw. Hence, hr=μr, fr-hr≤0 and
(3.33)[φ(Tk(h))-γw](fr-hr)≥0.
Case  2. If φ[Tr(h)]>γw, then r∉Aw. Hence, hr=λr, fr-hr≥0 and
(3.34)[φ(Tk(h))-γw](fr-hr)≥0.
Case  3. If φ[Tr(h)]=γw, then we have
(3.35)[φ(Tk(h))-γw](fr-hr)≥0.
From (3.33), (3.34), and (3.35), we have
(3.36)∑w∈W‍∑p∈Pw‍φ(Tp(h))(fp-hp)≥∑w∈W‍∑p∈Pw‍γw(dw-dw)=0.
Thus, the proof is complete.


## 4. Conclusions

In this paper, we have studied traffic network equilibrium problems with capacity constraints of arcs. We have introduced some new parametric equilibrium flows, such as:S+∖{0}-parametric equilibrium flows, intS+-parametric equilibrium flows, and φ-parametric equilibrium flows. By using these new concepts, we have characterized vector equilibrium problems on networks and derived some necessary and sufficient conditions for a (weak) vector equilibrium flow.



---

*Source: 612142-2012-12-04.xml*