# Nonlinear Min-Cost-Pursued Route-Swapping Dynamic System

Authors: Wenyi Zhang; Wei Guan; Jihui Ma; Tao Wang
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

This study proposes a nonlinear min-cost-pursued swapping dynamic (NMSD) system to model the evolution of selfish routing games on traffic network where travelers only swap from previous costly routes to the least costly ones. NMSD is a rational behavior adjustment process with stationary link flow pattern being the Wardrop user equilibrium. NMSD is able to prevent two behavioral deficiencies suffered by the existing min-cost-oriented models and keep solution invariance. NMSD relaxes the homogeneous user assumption, and the continuous-time NMSD (CNMSD) and discrete-time NMSD (DNMSD) share the same revision protocol. Moreover, CNMSD is Lyapunov-stable. Two numerical examples are conducted. The first one is designed to characterize the NMSD-conducted network traffic evolution and test the stability of day-to-day NMSD. The second one aims to explore the impacts of network scale on the stability of route-swaps conducted by pairwise and min-cost-pursed swapping behaviors.


---

## Body

## 1. Introduction

Smith [1] proposed the classical proportional-switch adjustment process (PAP) to describe the evolution of network traffic. PAP assumes traffic swaps from the previous costly routes to less costly ones with swapping rate being proportional to the pairwise absolute cost differences. PAP is viewed as (perhaps) the most natural route-swapping process [2]. It has a simple mathematic formulation and an intuitive behavior basis; in addition, PAP explicitly addresses the original micromechanism of network traffic evolution, that is, how and how much traffic will swap from the being-used routes to the other ones. Based on PAP, Cho and Hwang [3, 4] presented a stimulus-reaction dynamic, where an artificial constraint was added to prevent negative path flows. However, the revision protocol had no change and the artificial constraint lacks reasonable behavior basis. More extensions and applications can be found in [2, 5–8] and so forth.Walting and Hazelton [11] mentioned the superiorities of day-to-day traffic modeling method; however, they also summarized two major limitations for the continuous (PAP included) models, that is, the continuous-time trip adjustment and homogeneous user assumption. Recently, Zhang et al. [9] pointed out another two behavior deficiencies of PAP, namely, the weak robustness and over-swapping, and developed a nonlinear pair-wise swapping dynamic (NPSD) which was able to overcome the abovementioned two limitations and two behavior deficiencies. Moreover, NPSD inherited the advantages of PAP.Different from PAP and NPSD, this study investigates another route-swapping behavior; that is, travelers only swap from the previous costly routes to the least costly alternatives. This kind of greedy route-swapping behavior (compared with the pair-wise swapping behavior) was studied by Mounce and Carey [2]. In their dynamic model, the swapping traffic from a costly route to one of the least costly ones was proportional to the absolute difference, just analogous to PAP. Therefore, it still suffered from the PAP shortcomings. Considering this, this study develops a nonlinear min-cost-pursued swapping dynamic (NMSD). Since NMSD is revised from NPSD, it avoids those shortcomings suffered by the existing PAP-revised min-cost-pursued models.The remainder of this paper is organized as follows. In Section2, NMSD system is comprehensively illustrated. In Section 3, the proof of Lyapunov stability for continuous-time NMSD (CNMSD) is presented. Applying the day-to-day NMSD, two numerical examples are conducted in Sections 4 and 5 to characterize the NMSD-conducted network traffic evolution and explore the impacts of network scale on the route-swaps. Section 6 concludes the whole study.


## 2. Nonlinear Min-Cost-Pursued Route-Swapping Dynamic

Firstly, we present four assumptions for NMSD: (a) a traveler only changes his route to the least costly one, and at least some travelers, if not all, will do so unless all the travelers were all on the least costly routes the previous day; (b) the travel demand is inelastic; (c) every driver has perfect information on the previous and current traffic networks; (d) the route-swap decision is based on the travel experiences of the previous day. The latter three assumptions are also contained in PAP and NPSD.Based on the above four assumptions, define(1)C*wt=min{Ckwt∣k∈Kw},K*wt={k∈Kw∣Ckwt=C*wt},∀w∈W,t,
where t is the time index, W(w∈W) is the OD-pair set, Kw(k,p∈Kw) is the set of simple and acyclic routes between OD-pair w, and Ckwt is the real cost of route k between OD-pair w at time t. Moreover, define K-wt as the complementary set of K*wt under the universal set Kw and |K*wt| as the number of elements in set K*wt; then the continuous-time NMSD (CNMSD) is formulated as follows:
(2)f˙kwt={1|K*wt|∑p∈K-wtfpwtρpwtifk∈K*wt-fkwtρkwtifk∈K-wt∀k,w,t
with nonlinear revision protocol
(3)ρkwt=1-exp(-θwCkwt-C*wtCkwt)∀k,w,t
and the feasible route flow set Ω defined by
(4)∑kfkwt=dw∀w,t,fkwt≥0∀k,w,t.
Here, θw is a dimensionless parameter reflecting the travelers’ reaction sensitivity between OD-pair w, dw is the travel demand between w,  f is the route flow, and f˙ is the derivative of f with respect to t; revision protocol ρkwt computes the swap-out flow percentage from route k. In (3), (Ckwt-C*wt)/Ckwt denotes the reduction rate of cost swapping from k to the shortest route. In (4), the first equation is the equilibrium constraint of travel demand; the second inequality is the nonnegative constraint of path flow. Usually, we also define vat=∑w∑kδakwfkwt  for all  a,t, where vat is the flow on link a at day t, and 0-1 indicator δakw=1 if route k between w uses link a, and 0, otherwise.Replacingf˙kwt=fkw(t+1)-fkwt in (2) and joining (2)–(4) together, we obtain the discrete-time NMSD (DNMSD) system.Property 1 (non-over-swapping).
For NMSD (without extra notice, something holding for NMSD means it holds for both CNMSD and DNMSD below), during every swap process, the total swap-out flow from a route cannot spill its initial value, mathematically, that is,0≤ρkwt≤1,  for all  k,w,t.Proof.
Since1-exp(-θw(Ckwt-C*wt)/Ckwt)≤1, we have 0≤ρkwt≤1  for all  k,w,t. Then, Property 1 is proved.Property 2.
For NMSD, the revision protocolρkwt>0 if k∈K-wt and ρkwt=0 if k∈K*wt.Proof.
From (1), it can be concluded Ckwt>C*wt if k∈K-wt that Ckwt=C*wt if k∈K*wt,  1-exp(-θw(Ckwt-C*wt)/Ckwt)>0 if k∈K-wt, and 1-exp(-θw(Ckwt-C*wt)/Ckwt)=0 if k∈K*wt further. Recalling (2), Property 2 is proved.Property 3 (solution invariance).
For NMSD, if the initial flow pattern lies in feasible setΩ, then so do the remaining route flow patterns.Proof.
Given a feasible initial route flow pattern, Property3 requires that the remaining route flows are still nonnegative and the travel demands are still conservative. Define a small real number τ>0. Firstly, we prove that Property 3 is possessed by CNMSD.
Nonnegativity. From Property 1 and (2), we have, for all k, w, and t, fkw(t+τ)=fkwt+(1/|K*wt|)∑p∈K-wtfpwtρpwt≥0 if k∈K*wt and fkw(t+τ)=fkwt-fkwtρkwt=fkwt(1-ρkwt)≥0 if k∈K-wt. Then the nonnegativity of path flow is proved.
Conservation. According to (2), we have
(5)∑kfkw(t+τ)=∑k∈K*wtfkwt+∑k∈K*wt∑p∈K-wt1|K*wt|fpwtρpwt+∑k∈K-wtfkwt-∑k∈K-wtfkwtρkwt=∑kfkwt+∑p∈K-wtfpwtρpwt∑k∈K*wt1|K*wt|-∑k∈K-wtfkwtρkwt=∑kfkwt+∑p∈K-wtfpwtρpwt-∑k∈K-wtfkwtρkwt=∑kfkwt=⋯=∑kfkw0=dw.
Then the conservation for travel demand is proved.
For the previous proof whenτ and t orderly takes 1 and integers, solution-invariance will hold for DNMSD. Accordingly, Property 2 is owned by NMSD.Definition 1 (stationary path-flow pattern).
The stationary path-flow pattern of NMSD is a set of network path-flow states; starting from these path-flow states, NMSD reproduces them.Corollary 2.
For NMSD, iff˙kwt=0(orfkw(t+1)=fkwt)  for all  k,w,t, then ft (groups fkwt  for all  k,w,t) belongs to the stationary path-flow pattern and vice versa.Proof.
Since NMSD is a determined one-to-one dynamic model (i.e., an input produces a single determined output), then the sufficiency of Corollary2 can be easily proved by recurrence. The necessity can be concluded by Definition 1.Subsequently, we present the relationship between stationary path flow pattern of NMSD and Wardrop user equilibrium.Theorem 3.
For NMSD, the stationary path flow pattern is equivalent to Wardrop user equilibrium [12].Proof.
Firstly, we prove that Theorem3 holds for CNMSD. For this, based on Corollary 2, we only need to prove that ftwith f˙kwt=0  for all  k,w,t is equivalent to Wardrop user equilibrium.
Sufficiency. When f˙kwt=0  for all  k,w,t, according to (2), we can conclude that ∑p∈K-wtfpwtρpwt=0 if k∈K*wt and fkwtρkwt=0 if k∈K-wt. Recalling Property 2, we have fkwt=0 if k∈K-wt; that is, fkwt=0 if Ckwt>C*wt, which further yields Ckwt=C*wt if fkwt>0. We can also conclude that Ckwt≥C*wt if fkwt≥0 from Ckwt≥C*wt  for all  k∈Kw, deducing Ckwt≥C*wt if fkwt=0.
Necessity. Suppose that ft is a Wardrop user equilibrium; then we have Ckwt=C*wt if fkwt>0 and Ckwt≥C*wt if fkwt=0, which means that traffic solely distributes on the least costly routes and there is no traffic on the more costly ones; that is, fkwt=0 if k∈K-wt, further yielding ∑p∈K-wtfpwtρpwt=0. As a result, according to (2), f˙kwt=0  for all  k,w,t.
Collecting the previous proofs, Theorem3 holds for CNMSD. Let f˙kwt=fkw(t+1)-fkwt above; then we obtain the proof of Theorem 5 for DNMSD.Definition 4 (rational behavior adjustment process [13]).
A day-to-day route-swap process is called a rational behavior adjustment process with fixed travel demand if the aggregated travel cost of the entire network decreases based on the previous day’s path travel costs when path flows change from day to day. Moreover, if a path flow becomes stationary over days, then it is equivalent to the user equilibrium path flow.Theorem 5.
NMSD is a rational behavior adjustment process.Proof.
Firstly, we prove that CNMSD is a rational behavior adjustment process. Based on Theorem3, to prove Theorem 5 mathematically, we only need to prove ∑w∑kCkwtf˙kwt≤0. For this, expand ∑w∑kCkwtf˙kwt as follows:
(6)∑w∑kCkwtf˙kwt=∑w(∑k∈K*wtCkwtf˙kwt+∑p∈K-wtCpwtf˙pwt)=∑w(∑k∈K*wtCkwt1|K*wt|∑p∈K-wtfpwtρpwt-∑p∈K-wtCpwtfpwtρpwt)=∑w∑p∈K-wt(1|K*wt|∑k∈K*wtCkwt-Cpwt)fpwtρpwt=∑w∑p∈K-wt(C*wt-Cpwt)fpwtρpwt.
Recalling (1), we can conclude that ∑w∑p∈K-wt(C*wt-Cpwt)fpwtρpwt≤0, which proves that CNMSD is a rational behavior adjustment process. Let f˙kwt=fkw(t+1)-fkwt above; then we obtain the proof of Theorem 5 for DNMSD.Corollary 6.
For NMSD, the stationary link flow pattern is also equivalent to Wardrop user equilibrium.Proof.
Since NMSD is a rational behavior adjustment process, Corollary6 holds (according to [14]).As it is known to all, without imposing extra behavioral conditions, Wardrop user equilibria are not unique for path flow pattern but only for link flow pattern. However, according to Theorem5 and Corollary 6, we can judge whether NMSD has arrived at equilibrium state or not by detecting the states of link flows.


## 3. Lyapunov Stability

Lyapunov method is an acknowledged methodology to analyze the stability of a dynamic system [15]. The essence of this method is to identify a proper Lyapunov function. Peeta and Yang [7] introduced (7) to analyze the stability of continuous-time PAP, namely,
(7)V(f)=∫0Δfc(y)dy,
where y is the integration variable, Δ is the path-link incidence matrix, and vectors f and c(·) group path flows and link travel times, respectively.In this study, we still employ the Lyapunov function defined by (7) to analyze the stability of the present CNMSD system. By this way, we can obtain the following theorem.Theorem 7.
All solutions of CNMSD system defined by (2)–(4) together are bounded and converge to Wardrop user equilibria.Proof.
Sincec(·) in (7) is non-negative and V(f)→∞ if f→∞, then V(f) is non-negative and radically unbounded. According to (6), taking derivative of V(f) with respect to t, we have V˙(f)=V′(f)Δf˙=cΔf˙=Cf˙≤0, where vector C groups route flows. Let Z={f∣V˙(f)=0} and let E be the largest invariant set contained in set Z, according to LaSalle’s theorem [15]; all solutions of CNPSD system will be bounded and converge to set E. Then, to prove that Theorem 7, we only need to prove E is equivalent to Wardrop user equilibria.
SinceV˙(f)=Cf˙=∑w∑kCkwtf˙kwt≤0, according to (6), we have V˙(f)=0 if and only if
(8)(Ckwt-C*wt)fkwtρkwt=0∀k,w,t.
According to (8), we have Ckwt=C*wt if and only if fkwt>0 and Ckwt≥C*wt if and only if fkwt=0, which means those used paths have the same and the minimum cost, concluding that Z is equivalent to Wardrop user equilibria. From Property 3, the invariant set of CNMSD system is the feasible set Ω itself. Hence, the largest invariant set E=Ω∩Z=Z. Then Theorem 7 is proved.Note that Theorem7 only promises the stability of CNMSD. However, we cannot conclude that DNMSD is also Lyapunov-stable from Theorem 7. For DNMSD, we will demonstrate it through the numerical experiment in Section 4.


## 4. Numerical Study I

In this section, using the day-to-day NMSD, we conduct some numerical sensitivity analyses on a hypothetical network to analyze the impacts of reaction sensitivity on traffic evolutions and test the stability of DNMSD. For this, various levels of one-day capacity reductions are imposed on the present network.


### 4.1. Testing Network and Scenarios

The present network (Figure1) has 12 nodes, 17 links, 2 OD-pairs, and 8 paths, where OD-pair (1, 11) is connected by Path 1 (1→9→14), Path 2 (1→5→10), Path 3 (2→6→10), and Path 4 (2→11→15); OD-pair (2, 12) is connected by Path 5 (3→11→16), Path 6 (3→7→12), Path 7 (4→8→12), and Path 8 (4→13→17).Figure 1
A medium testing network (also applied in Zhang et al. [9]).The travel demands for both OD-pairs are 90 (pcu/min). In Figure1, the bracketed numbers in each link correspond orderly to its label, free-flow time (min), and normal capacity (pcu/min). The travel time of each link is computed by BPR function:
(9)ca=ca0[1+0.15(vaOa)4]∀a∈A,
where A is the set of links, ca0, va, and Oa are orderly the free-flow time, traffic flow, and initial capacity on link a. For brevity, we will omit the units in the remaining presentation.It can be concluded from Figure1 that the flow of Routes 1–4 are orderly equal to that of Routes 8–5 when it is symmetric. This property will be often quoted below without extra notice. Given that the initial traffic flow pattern of network is at UE state with f0=(20,20,25,25,25,25,20,20)T and all travelers have the same reaction sensitivity θ, let vector Cap=(Cap9,Cap11), where Cap9 and Cap11 denote the ratio of capacity reduction on links 9 and 11, respectively. In the present numerical example, we design two scenarios which are parameterized as follows:asymmetric capacity reduction (ACR):(10)Cap=([0.1:0.1:0.9],0.0)whenθ=[0.1:0.1:3.0],symmetric capacity reduction (SCR):(11)Cap=(0.0,[0.1:0.1:0.9])whenθ=[0.1:0.1:3.0].Note that the capacity reduces just at day 0 and goes back to normal after day 0. Also, only one link suffers from the capacity reduction at a time. Obviously, Figure1 remains symmetric under SCR, but it will become asymmetric under ACR. Based on Theorem 3, the convergence criterion is set to be ∥f(n+1)-fn∥≤1.0E-004.


### 4.2. Numerical Results

Figure2 displays the traffic evolutions under medium SCR and different reaction sensitivities. Figure 2 suggests that traffic on the routes suffering from direct interferences will suffer different degrees of flow loss, causing the sudden drops on those curves on Day 1. Figure 2 also suggests that the traffic evolutions on the symmetric routes are identical under SCR. In addition, when θ=[0.4:0.4:1.6], the route-swaps are convergable, whereas the smoothness of route-swaps becomes worse as θ rises. When θ=[2.0:0.4:2.4], the route-swaps fail to converge but finally reach the 6-day cycle of periodical oscillations, and the amplitudes increase as θ rises.Figure 2
Traffic evolutions under one-day medium SCR.Our numerical results uniformly report that the route-swaps finally reach the 6-day cycle of periodical oscillations unless convergence is reached. For this, we introduce the average deviation (AD) to measure the degrees of final oscillations; that is,(12)AD=12×4×6∑w∑k∑i=16(f~kiw-fkw0)2,
where 2, 4, and 6 in the denominator orderly denote the number of OD-pairs, the number of routes contained in each OD-pair, and the cycle of periodical oscillation. f~kiw denotes the ith flow element in the periodical oscillation on route k between w.Figure3 suggests that AD is not uniformly equal to 0 but depends on θ and the capacity reduction, which demonstrates that the stability of DNMSD does not hold in general. On the whole, we can divide the final flow states into three regions, that is, stable region with θ≤1.6, metastable region with θ∈[1.7,1.8], and unstable region with θ≥1.9. In the stable region, route-swaps can converge to the initial UE state for all capacity reductions. In the metastable region, both convergence and oscillation exist, and route-swaps only converge for small capacity reductions. In the unstable region, route-swaps cannot converge to the initial UE state but step into the 6-day cycle of periodical oscillations for all capacity reductions. In addition, it is shown from two subfigures that the final AD mainly depends on the reaction sensitivity more than the capacity reduction, and AD grows more and more slowly as θ increases.Final average deviation under different(θ,Cap).
(a)
(b)Tables1 and 2 orderly present the final flow states produced by day-to-day NMSD under ACR and SCR when θ=2.5.Table 1
Final flow states under different ACRs andθ=2.5.
θ
Cap9 (%)
Final path flows (pcu/min)
Path 1
Path 2
Path 3
Path 4
Path 5
Path 6
Path 7
Path 8
2.50
10 and 40–90
74.8243
1.3342
11.1557
2.6858
9.7170
1.3738
7.6246
71.2847
6.7909
0.6582
11.1167
71.4342
9.6895
70.2239
3.4885
6.5981
6.7699
67.3692
5.9334
9.9276
3.4381
11.3381
1.4553
73.7685
3.5258
7.6638
2.5071
76.3033
71.2334
11.2976
0.7361
6.7329
72.8012
7.6437
1.4564
8.0986
7.7571
6.0320
69.4974
6.7134
6.6764
3.3534
71.8913
8.0789
76.6707
2.3772
7.6447
3.3074
20–30
73.7685
1.4553
11.3381
3.4381
9.9276
5.9334
67.3692
6.7699
6.7329
0.7361
11.2976
71.2334
76.3033
2.5071
7.6638
3.5258
6.7134
69.4974
6.0320
7.7571
8.0986
1.4564
7.6437
72.8012
3.3074
7.6447
2.3772
76.6707
8.0789
71.8913
3.3534
6.6764
71.2847
7.6246
1.3738
9.7170
2.6858
11.1557
1.3342
74.8243
6.5981
3.4885
70.2239
9.6895
71.4342
11.1167
0.6582
6.7909Table 2
Final flow states under different SCRs andθ=2.5.
θ
Cap11 (%)
Final path flows (pcu/min)
Path 1
Path 2
Path 3
Path 4
Path 5
Path 6
Path 7
Path 8
2.50
10–90
73.0483
7.6258
1.3517
7.9742
7.9742
1.3517
7.6258
73.0483
6.6895
3.3245
72.0310
7.9550
7.9550
72.0310
3.3245
6.6895
73.0299
1.3182
11.1420
4.5098
4.5098
11.1420
1.3182
73.0299
6.6933
0.6822
11.1000
71.5245
71.5245
11.1000
0.6822
6.6933
6.6740
69.4958
5.9146
7.9156
7.9156
5.9146
69.4958
6.6740
3.2919
7.6460
2.3397
76.7225
76.7225
2.3397
7.6460
3.2919Table1 shows that although the network recovers symmetry after one-day of ACR on Link 9, the oscillation manners on the symmetric routes are obviously asymmetric for all levels of ACRs. This phenomenon indicates that ACR causes asymmetric route-swapping for two OD-pair users, which finally results in asymmetric evolutionary results.Table2 shows that the final oscillation manners on the symmetric routes are identical under SCR; that is, SCR finally results in symmetric oscillations.Figure3 and Tables 1 and 2 jointly demonstrate that the final oscillation manners depend on both θ and the characters of capacity reductions. Different oscillation manners are reached for different θ; even though θ is given, the final oscillation manners can be different under different capacity reductions. This phenomenon is especially obvious under SCR. Moreover, θ has a larger impact on the traffic evolution than the capacity reduction.Figure4 displays impacts of capacity reduction and reaction sensitivity on the convergent rate of route-swaps in the stable region (i.e., θ≤1.6).Convergence under different(θ,Cap).
(a)
(b)Figure4 shows that, given a capacity reduction the rate of convergence increases at first and then decreases as θ increases from 0.1 to 1.6, and this variation is more and more obvious as capacity reduction rises; given a θ, the rate of convergence increases overall as the capacity reduction grows, but this trend weakens as θ increases. Overall, the reaction factor θ has more significant impacts on the convergent rates of route-swaps than the extents of capacity reduction. The above findings can provide some useful insights for developing DNMSD-based traffic assignment algorithms. Since the value of θ cannot impact the feasibility of flow sequences, we can fix θ at a relative (rather than a very) small level (e.g., θ∈[0.5,1.0]) to guarantee convergence and still maintain a fast rate.Figure5 displays the traffic evolution under one-day medium ACRs in stable region.Figure 5
Convergable traffic evolutions under one-day medium ACR.See each column in Figure5 alone; it shows analogous trends as Figure 2 does. Comparing two columns of Figure 5, it shows that asymmetric interferences lead to asymmetric reactions. As θ increases from 0.4 to 1.6, due to undertaking direct interferences, the travelers between OD-pair (1, 11) react oneday earlier than those between OD-pair (2, 12), and the former also reacts much stronger than the latter. Figure 5 also suggests that any interference in a correlated traffic network will transfer to the whole network, and the impact of interference is degressive.


## 4.1. Testing Network and Scenarios

The present network (Figure1) has 12 nodes, 17 links, 2 OD-pairs, and 8 paths, where OD-pair (1, 11) is connected by Path 1 (1→9→14), Path 2 (1→5→10), Path 3 (2→6→10), and Path 4 (2→11→15); OD-pair (2, 12) is connected by Path 5 (3→11→16), Path 6 (3→7→12), Path 7 (4→8→12), and Path 8 (4→13→17).Figure 1
A medium testing network (also applied in Zhang et al. [9]).The travel demands for both OD-pairs are 90 (pcu/min). In Figure1, the bracketed numbers in each link correspond orderly to its label, free-flow time (min), and normal capacity (pcu/min). The travel time of each link is computed by BPR function:
(9)ca=ca0[1+0.15(vaOa)4]∀a∈A,
where A is the set of links, ca0, va, and Oa are orderly the free-flow time, traffic flow, and initial capacity on link a. For brevity, we will omit the units in the remaining presentation.It can be concluded from Figure1 that the flow of Routes 1–4 are orderly equal to that of Routes 8–5 when it is symmetric. This property will be often quoted below without extra notice. Given that the initial traffic flow pattern of network is at UE state with f0=(20,20,25,25,25,25,20,20)T and all travelers have the same reaction sensitivity θ, let vector Cap=(Cap9,Cap11), where Cap9 and Cap11 denote the ratio of capacity reduction on links 9 and 11, respectively. In the present numerical example, we design two scenarios which are parameterized as follows:asymmetric capacity reduction (ACR):(10)Cap=([0.1:0.1:0.9],0.0)whenθ=[0.1:0.1:3.0],symmetric capacity reduction (SCR):(11)Cap=(0.0,[0.1:0.1:0.9])whenθ=[0.1:0.1:3.0].Note that the capacity reduces just at day 0 and goes back to normal after day 0. Also, only one link suffers from the capacity reduction at a time. Obviously, Figure1 remains symmetric under SCR, but it will become asymmetric under ACR. Based on Theorem 3, the convergence criterion is set to be ∥f(n+1)-fn∥≤1.0E-004.


## 4.2. Numerical Results

Figure2 displays the traffic evolutions under medium SCR and different reaction sensitivities. Figure 2 suggests that traffic on the routes suffering from direct interferences will suffer different degrees of flow loss, causing the sudden drops on those curves on Day 1. Figure 2 also suggests that the traffic evolutions on the symmetric routes are identical under SCR. In addition, when θ=[0.4:0.4:1.6], the route-swaps are convergable, whereas the smoothness of route-swaps becomes worse as θ rises. When θ=[2.0:0.4:2.4], the route-swaps fail to converge but finally reach the 6-day cycle of periodical oscillations, and the amplitudes increase as θ rises.Figure 2
Traffic evolutions under one-day medium SCR.Our numerical results uniformly report that the route-swaps finally reach the 6-day cycle of periodical oscillations unless convergence is reached. For this, we introduce the average deviation (AD) to measure the degrees of final oscillations; that is,(12)AD=12×4×6∑w∑k∑i=16(f~kiw-fkw0)2,
where 2, 4, and 6 in the denominator orderly denote the number of OD-pairs, the number of routes contained in each OD-pair, and the cycle of periodical oscillation. f~kiw denotes the ith flow element in the periodical oscillation on route k between w.Figure3 suggests that AD is not uniformly equal to 0 but depends on θ and the capacity reduction, which demonstrates that the stability of DNMSD does not hold in general. On the whole, we can divide the final flow states into three regions, that is, stable region with θ≤1.6, metastable region with θ∈[1.7,1.8], and unstable region with θ≥1.9. In the stable region, route-swaps can converge to the initial UE state for all capacity reductions. In the metastable region, both convergence and oscillation exist, and route-swaps only converge for small capacity reductions. In the unstable region, route-swaps cannot converge to the initial UE state but step into the 6-day cycle of periodical oscillations for all capacity reductions. In addition, it is shown from two subfigures that the final AD mainly depends on the reaction sensitivity more than the capacity reduction, and AD grows more and more slowly as θ increases.Final average deviation under different(θ,Cap).
(a)
(b)Tables1 and 2 orderly present the final flow states produced by day-to-day NMSD under ACR and SCR when θ=2.5.Table 1
Final flow states under different ACRs andθ=2.5.
θ
Cap9 (%)
Final path flows (pcu/min)
Path 1
Path 2
Path 3
Path 4
Path 5
Path 6
Path 7
Path 8
2.50
10 and 40–90
74.8243
1.3342
11.1557
2.6858
9.7170
1.3738
7.6246
71.2847
6.7909
0.6582
11.1167
71.4342
9.6895
70.2239
3.4885
6.5981
6.7699
67.3692
5.9334
9.9276
3.4381
11.3381
1.4553
73.7685
3.5258
7.6638
2.5071
76.3033
71.2334
11.2976
0.7361
6.7329
72.8012
7.6437
1.4564
8.0986
7.7571
6.0320
69.4974
6.7134
6.6764
3.3534
71.8913
8.0789
76.6707
2.3772
7.6447
3.3074
20–30
73.7685
1.4553
11.3381
3.4381
9.9276
5.9334
67.3692
6.7699
6.7329
0.7361
11.2976
71.2334
76.3033
2.5071
7.6638
3.5258
6.7134
69.4974
6.0320
7.7571
8.0986
1.4564
7.6437
72.8012
3.3074
7.6447
2.3772
76.6707
8.0789
71.8913
3.3534
6.6764
71.2847
7.6246
1.3738
9.7170
2.6858
11.1557
1.3342
74.8243
6.5981
3.4885
70.2239
9.6895
71.4342
11.1167
0.6582
6.7909Table 2
Final flow states under different SCRs andθ=2.5.
θ
Cap11 (%)
Final path flows (pcu/min)
Path 1
Path 2
Path 3
Path 4
Path 5
Path 6
Path 7
Path 8
2.50
10–90
73.0483
7.6258
1.3517
7.9742
7.9742
1.3517
7.6258
73.0483
6.6895
3.3245
72.0310
7.9550
7.9550
72.0310
3.3245
6.6895
73.0299
1.3182
11.1420
4.5098
4.5098
11.1420
1.3182
73.0299
6.6933
0.6822
11.1000
71.5245
71.5245
11.1000
0.6822
6.6933
6.6740
69.4958
5.9146
7.9156
7.9156
5.9146
69.4958
6.6740
3.2919
7.6460
2.3397
76.7225
76.7225
2.3397
7.6460
3.2919Table1 shows that although the network recovers symmetry after one-day of ACR on Link 9, the oscillation manners on the symmetric routes are obviously asymmetric for all levels of ACRs. This phenomenon indicates that ACR causes asymmetric route-swapping for two OD-pair users, which finally results in asymmetric evolutionary results.Table2 shows that the final oscillation manners on the symmetric routes are identical under SCR; that is, SCR finally results in symmetric oscillations.Figure3 and Tables 1 and 2 jointly demonstrate that the final oscillation manners depend on both θ and the characters of capacity reductions. Different oscillation manners are reached for different θ; even though θ is given, the final oscillation manners can be different under different capacity reductions. This phenomenon is especially obvious under SCR. Moreover, θ has a larger impact on the traffic evolution than the capacity reduction.Figure4 displays impacts of capacity reduction and reaction sensitivity on the convergent rate of route-swaps in the stable region (i.e., θ≤1.6).Convergence under different(θ,Cap).
(a)
(b)Figure4 shows that, given a capacity reduction the rate of convergence increases at first and then decreases as θ increases from 0.1 to 1.6, and this variation is more and more obvious as capacity reduction rises; given a θ, the rate of convergence increases overall as the capacity reduction grows, but this trend weakens as θ increases. Overall, the reaction factor θ has more significant impacts on the convergent rates of route-swaps than the extents of capacity reduction. The above findings can provide some useful insights for developing DNMSD-based traffic assignment algorithms. Since the value of θ cannot impact the feasibility of flow sequences, we can fix θ at a relative (rather than a very) small level (e.g., θ∈[0.5,1.0]) to guarantee convergence and still maintain a fast rate.Figure5 displays the traffic evolution under one-day medium ACRs in stable region.Figure 5
Convergable traffic evolutions under one-day medium ACR.See each column in Figure5 alone; it shows analogous trends as Figure 2 does. Comparing two columns of Figure 5, it shows that asymmetric interferences lead to asymmetric reactions. As θ increases from 0.4 to 1.6, due to undertaking direct interferences, the travelers between OD-pair (1, 11) react oneday earlier than those between OD-pair (2, 12), and the former also reacts much stronger than the latter. Figure 5 also suggests that any interference in a correlated traffic network will transfer to the whole network, and the impact of interference is degressive.


## 5. Numerical Study II

In this section, we discuss the influence of network scale on the convergence of route-swaps through a numerical comparison between two hypothetical networks. For this, besides Figure1, another testing network (see Figure 6) is introduced.Figure 6
A simple testing network (modified from Zhou and Chen [10]).


### 5.1. Contrastive Network

The contrastive network (Figure6) consists of 10 nodes, 11 links, 2 OD-pairs, and 4 paths.In Figure6, the bracketed numbers in every link mean the same as those of Figure 1. OD-pairs and paths are organized as follows:OD-pair (1, 9) is connected by Path 1 (1→5→8) and Path 2 (2→6→9);OD-pair (2, 10) is connected by Path 3 (3→6→10) and Path 4 (4→7→11).Obviously, in contrast with Figure1, Figure 6 has smaller scale.


### 5.2. Scenarios and Results

This numerical example is to identify the difference in convergence region ofθ for Figures 1 and 6. In present contrastive experiment, the travel time of each link is computed by (9); all travelers have the same reaction sensitivity θ; the initial network states for two networks are both at UE states; the convergence criterion is the ∥f(n+1)-fn∥≤1.0E-004. Initial conditions for Figure1 (the same as that of Section 4) are
the travel demands for both OD-pairs are 90 (pcu/min);the initial path flow patternf0=(20,20,25,25,25,25,20,20)T;the capacity reduction vectorCap=(Cap9,Cap11).Initial conditions for Figure6 are
the travel demands for both OD-pairs are 45 (pcu/min);the initial path flow patternf0=(20,25,25,20)T;the capacity reduction vectorCap=(Cap5,Cap6).Just the same as Section4, here the capacity reduces at Day 0 and goes back to normal after Day 0. Also, only one link suffers from the capacity reduction at a time. Two designed capacity reduction scenarios are parameterized as follows:asymmetric capacity reduction (ACR):(13)Cap=([0.1:0.1:0.9],0.0)whenθ=[0.005:0.005:5.0],symmetric capacity reduction (SCR):(14)Cap=(0.0,[0.1:0.1:0.9])whenθ=[0.005:0.005:5.0].Obviously, Figures1 and 6 remain symmetric under SCR but become asymmetric under ACR. Table 3 presents the numerical results for two networks.Table 3
The uniform convergence supremums ofθ.
Route-swapping dynamics
Interference
Figure6
Figure1
Day-to-day NMSD
ACR
1.915
1.670
SCR
1.915
1.620
Day-to-day NPSD
ACR
3.835
3.690
SCR
3.835
3.690Here the uniform convergence supremum ofθ is the supremum of θ promising the convergence of route-swaps for Cap9/Cap11=[0.1:0.1:0.9]. Table 3 indicates that the uniform convergence supremums of NMSD vary with both interferences and network scales. As the network scale increases, the uniform convergence supremum of θ reduces by 12.79% under ACR and 15.40% under SCR. For NPSD, The two numbers are both 3.78%, with both reducing from 3.835 to 3.690 and having no relation with the capacity reduction. These results suggest that the instability of traffic network can become worse as the scale of network increases, and such a possibility for the NMSD network is larger than that for the NPSD network. In some degree, this implies that the pair-wise route-swapping behavior is more robust than the min-cost-pursed behavior. In addition, the convergence region for NPSD has no relation to the characters of interference. Hence, NPSD is more suitable to develop algorithmic devices for the UE-oriented traffic assignment problems.


## 5.1. Contrastive Network

The contrastive network (Figure6) consists of 10 nodes, 11 links, 2 OD-pairs, and 4 paths.In Figure6, the bracketed numbers in every link mean the same as those of Figure 1. OD-pairs and paths are organized as follows:OD-pair (1, 9) is connected by Path 1 (1→5→8) and Path 2 (2→6→9);OD-pair (2, 10) is connected by Path 3 (3→6→10) and Path 4 (4→7→11).Obviously, in contrast with Figure1, Figure 6 has smaller scale.


## 5.2. Scenarios and Results

This numerical example is to identify the difference in convergence region ofθ for Figures 1 and 6. In present contrastive experiment, the travel time of each link is computed by (9); all travelers have the same reaction sensitivity θ; the initial network states for two networks are both at UE states; the convergence criterion is the ∥f(n+1)-fn∥≤1.0E-004. Initial conditions for Figure1 (the same as that of Section 4) are
the travel demands for both OD-pairs are 90 (pcu/min);the initial path flow patternf0=(20,20,25,25,25,25,20,20)T;the capacity reduction vectorCap=(Cap9,Cap11).Initial conditions for Figure6 are
the travel demands for both OD-pairs are 45 (pcu/min);the initial path flow patternf0=(20,25,25,20)T;the capacity reduction vectorCap=(Cap5,Cap6).Just the same as Section4, here the capacity reduces at Day 0 and goes back to normal after Day 0. Also, only one link suffers from the capacity reduction at a time. Two designed capacity reduction scenarios are parameterized as follows:asymmetric capacity reduction (ACR):(13)Cap=([0.1:0.1:0.9],0.0)whenθ=[0.005:0.005:5.0],symmetric capacity reduction (SCR):(14)Cap=(0.0,[0.1:0.1:0.9])whenθ=[0.005:0.005:5.0].Obviously, Figures1 and 6 remain symmetric under SCR but become asymmetric under ACR. Table 3 presents the numerical results for two networks.Table 3
The uniform convergence supremums ofθ.
Route-swapping dynamics
Interference
Figure6
Figure1
Day-to-day NMSD
ACR
1.915
1.670
SCR
1.915
1.620
Day-to-day NPSD
ACR
3.835
3.690
SCR
3.835
3.690Here the uniform convergence supremum ofθ is the supremum of θ promising the convergence of route-swaps for Cap9/Cap11=[0.1:0.1:0.9]. Table 3 indicates that the uniform convergence supremums of NMSD vary with both interferences and network scales. As the network scale increases, the uniform convergence supremum of θ reduces by 12.79% under ACR and 15.40% under SCR. For NPSD, The two numbers are both 3.78%, with both reducing from 3.835 to 3.690 and having no relation with the capacity reduction. These results suggest that the instability of traffic network can become worse as the scale of network increases, and such a possibility for the NMSD network is larger than that for the NPSD network. In some degree, this implies that the pair-wise route-swapping behavior is more robust than the min-cost-pursed behavior. In addition, the convergence region for NPSD has no relation to the characters of interference. Hence, NPSD is more suitable to develop algorithmic devices for the UE-oriented traffic assignment problems.


## 6. Conclusions

This study develops a nonlinear min-cost-pursued swapping dynamic (NMSD) to describe such a kind of rerouting behavior solely rerouting to the least costly routes connecting a certain OD-pair. NMSD swaps traffic to the shortest routes by a nonlinear function of the relative (rather than absolute) cost-differences. NMSD can prevent two behavioral deficiencies (i.e., weak robustness and overswapping) suffered by the existing analogous models. NMSD is a rational behavior adjustment process with stationary link flow pattern corresponding to Wardrop user equilibrium and can promise solution-invariance. In addition, both continuous-time and discrete-time NMSDs (abbreviated as CNMSD and DNMSD, resp.) share the same revision protocol and can capture heterogeneous rerouting behaviors. Also, CNMSD is Lyapunov-stable.The first numerical example conducted by the day-to-day NMSD suggests the following: (1) as reaction factorθ increases, the traffic evolution results can be divided into three regions, that is, the stable region, meta-stable region, and unstable region; (2) the final traffic states depend on both θ and the characters of interference, and θ plays a more important role. The second numerical study suggests that as the network scale increases, the convergence region of reaction factor for both NPSD and NMSD reduces. However, the convergence region for NPSD has no relation to the characters of interference and reduces much slower. In addition, there is no need for NPSD to identify the shortest route. Hence, NPSD is more suitable to develop algorithmic devices for the UE-oriented traffic assignment problems than NMSD.



---

*Source: 162128-2013-05-28.xml*