# Dynamics of a Transportation Network Model with Homogeneous and Heterogeneous Users

Authors: Yingguo Li; Zhijia Tan; Qiong Chen
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

This paper studies the dynamics of the traveler's day-to-day route adjustment process in the general transportation network with fixed or elastic demand and homogeneous or heterogeneous users. Each traveler is assumed to adjust his/her route choice according to the excess travel cost between the instantaneous experienced travel cost and a certain referred level, which induces an aggregate path flow dynamics. We call the path flow dynamics the excess travel cost dynamics, which corresponds to the excess payoff dynamics in evolutionary games and serves a general framework of modeling the homogeneous or heterogeneous route choice behavior of travelers.


---

## Body

## 1. Introduction

Network equilibrium models have a long history, both in the transport research literature and in practical studies of scheme assessment, since the notion of user equilibrium (UE) was proposed [1]. At equilibrium, all travelers on the same origin-destination pair experience the same travel cost, while all unused routes have equal or higher travel costs. Wardrop equilibrium has been extended in different senses to address real world needs in transportation planning, analysis, and management, including stochastic user equilibrium (SUE) to allow imperfect information or user perception error in their route choice [2]; dynamic user equilibrium within-day to incorporate the departure time choice in route choice [3, 4].To model the travelers' response to exogenous information, the growing interest in day-to-day dynamics has received much study after the original research of Horowitz [5], in which a two-link transportation network is adopted to explain the day-to-day dynamic link and path flow patterns and the stability issue. The evolution over days of travel choices or a learning rule based on the past experience associated with the traffic assignment model are the main methodologies to capture the day-to-day behavior. A comprehensive literature review on the day-to-day dynamics is made by Bie and Lo [6]. In the literature, travelers' day-to-day route choice adjustment behavior is modeled as either a deterministic dynamic process, such as the simplex gravity flow dynamics [7], the proportional-switch adjustment process [8, 9], the network tatonnement process [10], the projected dynamical system [11], and evolutionary traffic dynamics [12], or a stochastic dynamic process [13, 14]. Yang and Zhang [15] focused on the deterministic dynamic route adjustment process on modeling drivers dynamic route choice adjustment behavior and proved that many commonly used dynamic processes are so-called Rational Behavior Adjustment Process (RBAP) since the aggregated travel cost of the entire network decreases over days except that the path flow becomes stationary and is the user equilibrium path flow. He et al. [16] developed a link-based day-to-day dynamic traffic assignment model to copy with two essential pitfalls of the path-based model, that is, the initial path flow pattern is typically unidentifiable and different initial path flow patterns constituting the same link flow pattern generally give different day-to-day link flow evolutions; the path-based models ignore the interdependence among paths and thus can give very unreasonable results for networks with paths overlapping with each other. The day-to-day route adjustment process provides a useful tool for transportation management. Peeta and Yang [17] demonstrated that providing properly advanced travel information to the road users can result in the social optimal link flow pattern by assuming that the travelers' day-to-day route adjustment behavior follows the proportional-switch adjustment process. Using the potential games theory, Sandholm [12] proposed an evolutionary implementation mechanism for continuous dynamic route-based pricing policy to ensure the efficient use of the roadway system, while allowing for users to follow any reasonable myopic adjustment process. Apart from the unknown demand or demand function, he assumed that the individual traveler's day-to-day route choice adjustment process is not known to the planner either.However, if the road pricing scheme is adopted in the transportation network as Sandholm [12], the day-to-day route adjustment process should incorporate the travelers' heterogeneous behavior since they value the monetary and time costs in different ways. With this consideration, we assume that all travelers in the transportation network can be classified into several discrete classes, the user in each class is captured by a parameter, value-of-time (VOT) which converts the travel time cost into the equivalent monetary cost [18]. It is easy to understand that the users in different user classes adjust their route choice in different ways according to their VOT values. In this paper, we develop a general model framework to capture the travelers' day-to-day route choice behavior, which considers the general transportation network with fixed or elastic demand, homogeneous or heterogeneous users. In this study, each traveler is assumed to adjust his/her route choice according to the excess travel cost between the instantaneous experienced travel cost and a certain referred level. The aggregate path flow dynamics induced by this model can be viewed as a natural extension of the so-called rational behavior adjustment process proposed by [15]. We call this path flow dynamics the excess travel cost dynamics, which corresponds to the excess payoff dynamics in evolutionary game [19]. The excess travel cost dynamics serves as a more general framework than the rational behavior adjustment process for modeling the travelers' dynamic route choice behavior in the transportation network with fixed or elastic demand, homogeneous or heterogeneous users. The Lyapunov function method is commonly used to study the stability of the equilibrium solutions [8, 10]. LaSalle's theorem addressing system stability over a set of equilibrium solutions rather than an isolated point [20] has been adopted by several researchers to study the stability of dynamic transportation network [6, 17, 21]. In this study, we use LaSalle's theorem to study the stability of the excess travel cost dynamics.The paper is organized as follows. Section2 introduces the definition of the excess travel cost dynamics. The stability issue for the proposed dynamic system is addressed in Section 3. Finally, conclusions are given in Section 4.


## 2. Day-to-Day Dynamical Route Adjustment Process

### 2.1. Excess Travel Cost Dynamics with Homogeneous Users

Consider a general transportation network,G(N,A), where N is the set of nodes and A is the set of links. Denote W by the set of origin-destination (OD) pairs Rw by the set of routes between O-D pair w, and R=⋃w∈WRw. Let frw, va, and τa be the path flow on route r, r∈Rw, the flow and toll of link a, a∈A, |A|=m. The corresponding vectors of path flows, link flows and toll charges are denoted by f, v, and τ. Each link a, a∈A, is associated with a strictly increasing and convex link travel time cost function, ta(va) of the link flow, va. The total aggregate link flow is va=∑w∈W‍∑r∈Rw‍frwδarw, where δarw equals 1 if route r between OD pair w uses link a; 0 otherwise. Without confusion, let Trw and Crw be the total travel time and total cost (travel time plus the monetary cost, if any) of path r∈Rw between OD pair. Each OD pair w∈W is associated with a demand, which is fixed or is elastic. In the latter case the demand is given by an invertible strictly decreasing function of the generalized travel cost cw alone, qw=Dw(cw). The set of all feasible path flow patterns is denoted by
(2.1)Ω={f≥0:qw=∑r∈Rw‍frw,w∈W}.
Denote the day-to-day path flow dynamics by f˙(s)=(f˙rw(s),r∈Rw,w∈W), say, the derivative of path flow vector f(s) with respect to day to day time s.Three assumptions on travelers' route adjustment process are proposed and compared by Nagurney and Zhang [11]. The third one among those assumptions is suggested to be the most reasonable and defined by Yang and Zhang [15] as the rational behavior adjustment process (RBAP) with fixed demand. The day-to-day route choice adjustment process is the RBAP 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; otherwise, if path flow becomes stationary over day, then it is equivalent to the user equilibrium path flow. That is to say, if the current path flow pattern is not UE path flow, then ∑w∈W‍∑r∈Rw‍Crw(f)f˙rw<0. The RBAP is mild and includes various commonly used route choice adjustment process as its special cases, such as the proportional-switch adjustment process [17], the projected dynamical system [11], and the Brown-von Neumann-Nash dynamics [22].Suppose that a well-defined excess travel cost is associated with each path, such as the difference between the travel cost and the average travel cost corresponding to a specific OD pair. It is easy to check that, both the aggregated travel cost and excess travel cost of the entire network decreases based on the previous day's path travel costs when path flow pattern changes from day to day, whenever the process is RBAP. The logic is intuitive since the flow process follows the conservation constraint if the excess travel cost is defined as the difference between the path cost and average OD-specific travel cost, namely,(2.2)∑w∈W‍∑r∈Rw‍(Crw(f)-C-w(f))f˙rw=∑w∈W‍∑r∈Rw‍Crw(f)f˙rw<0.
since ∑r∈Rw‍f˙rw=0 and C-w(f)=(1/qw)∑r∈Rw‍Crw(f)frw. In fact, the reference travel cost level, C-w(f), may be altered as the current minimal travel cost. A more general definition of the excess travel cost is given in [19], in which, at least one traveler travels with a positive excess travel cost whenever the stationary equilibrium is not achieved. For simplification of our representation, we only refer the excess travel cost to the difference between the travel cost and the average travel cost associated a specific OD pair for the case with fixed demand, namely, ETCrw(f)=Crw(f)-C-w(f).For the case with elastic demand, notably, the inverse demand function,Dw-1(qw), is the current travel benefit between OD pair w if the demand is qw. We thus define the excess travel cost of path r∈Rw as Crw(f)-Dw-1(qw),w∈W or ETCrw(f)=Crw(f)-Dw-1(qw). To incorporate the cases with both fixed and elastic demands, we now extend the definition of rational behavior adjustment process proposed by Yang and Zhang [15]. Denote the path flow dynamics as the following equation:
(2.3)f˙=F(f).
The day-to-day route adjustment process (2.3) is the excess travel cost dynamics if the following three conditions are satisfied:(A1)
dynamic system (2.3) admits a unique solution trajectory for any given initial condition, and the trajectory is Lipschitz continuous;(A2)
∑w∈W‍∑r∈Rw‍ETCrwFrw<0 whenever F(f)≠0 where the excess travel cost, ETCrw, of path r∈Rw between w∈W is a well-defined function of link flow vector f;(A3)
f* is an equilibrium point of system (2.3) if F(f*)=0.With the excess travel cost dynamics, the aggregated excess travel cost of the entire network must decrease from the previous day's path travel costs when path flows change from day to day; otherwise, if path flow becomes stationary over days, then it is equivalent to the user equilibrium path flow. Define the excess payoff for using each path as-ETC, then the excess travel cost dynamics is the excess payoff dynamics, which is a special case of the well-behaved dynamics proposed by Sandholm [19].


### 2.2. Excess Travel Cost Dynamics with Heterogeneous Users

The excess travel cost dynamics, described above, assumes that all travelers perceive the path travel cost identically (travel time plus a discount monetary cost). However, it is well known that travelers may value travel time differently, depending on their income levels or travel purposes. Thus, when a toll policy is introduced into the network, heterogeneous users with different value of time (VOT) have to be considered in converting travel time into equivalent monetary cost. In this subsection, we focus our discussion on the behavior assumption of the route choice adjustment process in presence of the user heterogeneity. Furthermore, we consider a discrete set of user classes corresponding to the groups of users with different socioeconomic characteristics, such as income level.LetM denote such user classes, and βm, βm>0, be the average VOT for users of class m∈M. The travelers of each class adjust their routes according to their owner perception for any given and fixed link toll pattern, τ={τa,a∈A}. Let Trw(f) and τrw denote the travel time and toll of path r∈Rw between OD pair w∈W, where we further suppose that each OD pair and user class is associated with a fixed or elastic demand. In the latter case, the classic-specific demand is given by a strictly decreasing function qwm=Dwm(μwm), where μwm is the generalized travel cost in time unit for user class m∈M between OD pair w∈W. The set of the feasible path flow pattern is now expressed as
(2.4)Ω={f≥0:qwm=∑r∈Rw‍frw,m,w∈W,m∈M}.
Notably, the travelers with different VOT may estimate their excess travel cost differently. The average travel cost of OD pair w∈W estimated by the users of class m is C-wm(f)=(1/qwm)∑r∈Rw‍(Trw(f)+(τrw/βm))frw. The excess travel cost for user class m to use path r∈Rw between OD pair w∈W with fixed demand can be expressed as ETCrw,m(f)=Crw,m(f)-C-wm. As before for the case with elastic demand, the excess travel cost of path r∈Rw between OD pair w∈W for user class m∈M is ETCrw,m(f)=Crw,m(f)-Dw,m-1(qwm). Note that, for the multiclass day-to-day dynamic route choice adjustment process (2.3), the term, f˙=(f˙rw,m,r∈Rw,w∈W,m∈M), is class-specific path flow derivative. Similarly, the aggregate class-specific link flow vM, vM=(vam,a∈A,m∈M), where the aggregate link flow of user class m is vam=∑w∈W‍∑r∈Rw‍frw,mδarw. The multiclass day-to-day route adjustment process (2.3) is rational if assumptions (A1), (A3), and the following (A2) are satisfied:(A2′)
∑w∈W‍∑r∈Rw‍∑m∈M‍ETCrw,mFrw,m<0 whenever F(f)≠0.Assumption (A2′) says that, for any given and fixed link toll pattern,τ={τa,a∈A}, each user adjusts his/her route choice according to his/her own preference, which results in the decrease in aggregated excess travel cost of the entire network in time unit in comparison with that on previous day when path flows change from day to day. A stronger behavior assumption is that the flow on those paths on which travelers experienced positive excess travel cost strictly decreases, and vice versa. Assumption (A2′) is a direct extension of the homogeneous case, in which all travelers have an identical VOT.Example 2.1.
The proportional-switch adjustment process (PSAP) was first introduced by Smith [8] to suppose that the drivers on a higher cost path switch to other lower cost paths in a rate that is proportional to the cost difference between this path and the other lower cost paths. Peeta and Yang [17] modeled the dynamical traffic flow switch rate of the PSAP with fixed demand as:
(2.5)f˙rw=∑r′∈Rw(fr′w[Cr′w(f)-Crw(f)]+-frw[Crw(f)-Cr′w(f)]+),
where Crw is the travel cost of path r∈Rw between OD pair w, and [y]+=max{0,y}. By introducing the excess travel cost, ETCrw, for each path, dynamic system (2.5) can be rewritten as:
(2.6)f˙rw=∑r′∈Rw(fr′w[ETCr′w(f)-ETCrw(f)]+-frw[ETCrw(f)-ETCr′w(f)]+).
Furthermore, the PSAP with fixed demand, given by (2.6), can be extended to the multiclass user case. Given a toll pattern τ=(τa,a∈A), the travel cost and excess travel cost in time unit for the travellers with VOT βm are Crw,m=Trw+τrw/βm and C-w,m(f)=(1/qw)∑r∈Rw‍(Trw+τrw/βm)frw. The multiclass PSAP with fixed demand, for all m∈M, r∈Rw and w∈W, is
(2.7)f˙rw,m=∑r′∈Rw‍fr′w,m[ETCr′w,m(f)-ETCrw,m(f)]+-frw,m∑r′∈Rw‍[ETCrw,m(f)-ETCr′w,m(f)]+.
We now consider the elastic demand based on the simple model of PSAP. Suppose that there is a dummy link associated with each OD pair and the latent noncar travelers traverse from the origin to the destination by the dummy link. Suppose there is a large potential demand for each OD pair,Qw. The dummy link, rw-, is associated with the travel cost of Dw-1(qw) and flow q^w, where qw and q^w denote the revealed and latent demand between OD pair, w∈W, respectively. Namely, Crw-w=Dw-1(qw) and frw-w=q^w=Qw-qw. Let the average travel cost be C-w(f)=(1/Qw)(∑r∈Rw‍Crwfrw+Dw-1(qw)q^w). Like the case with fixed demand, the excess travel cost is defined as the difference between the travel cost and the average travel cost associated with the specific path. The PSAP with elastic demand can be revised, for r∈Rw∪{rw-} and w∈W, as
(2.8)f˙rw=∑r′∈Rw∪{rw-}(fr′w[ETCr′w(f)-ETCrw(f)]+-frw[ETCrw(f)-ETCr′w(f)]+).
Like the case with fixed demand again, the PASP with elastic demand, given by (2.8), can be extended to the multiclass PSAP indexed by user class m∈M. Following the method described above and the definition of the excess travel cost with multiclass users, the Brown and von Neumann process can be extended to the cases with elastic demand and user heterogeneity.


## 2.1. Excess Travel Cost Dynamics with Homogeneous Users

Consider a general transportation network,G(N,A), where N is the set of nodes and A is the set of links. Denote W by the set of origin-destination (OD) pairs Rw by the set of routes between O-D pair w, and R=⋃w∈WRw. Let frw, va, and τa be the path flow on route r, r∈Rw, the flow and toll of link a, a∈A, |A|=m. The corresponding vectors of path flows, link flows and toll charges are denoted by f, v, and τ. Each link a, a∈A, is associated with a strictly increasing and convex link travel time cost function, ta(va) of the link flow, va. The total aggregate link flow is va=∑w∈W‍∑r∈Rw‍frwδarw, where δarw equals 1 if route r between OD pair w uses link a; 0 otherwise. Without confusion, let Trw and Crw be the total travel time and total cost (travel time plus the monetary cost, if any) of path r∈Rw between OD pair. Each OD pair w∈W is associated with a demand, which is fixed or is elastic. In the latter case the demand is given by an invertible strictly decreasing function of the generalized travel cost cw alone, qw=Dw(cw). The set of all feasible path flow patterns is denoted by
(2.1)Ω={f≥0:qw=∑r∈Rw‍frw,w∈W}.
Denote the day-to-day path flow dynamics by f˙(s)=(f˙rw(s),r∈Rw,w∈W), say, the derivative of path flow vector f(s) with respect to day to day time s.Three assumptions on travelers' route adjustment process are proposed and compared by Nagurney and Zhang [11]. The third one among those assumptions is suggested to be the most reasonable and defined by Yang and Zhang [15] as the rational behavior adjustment process (RBAP) with fixed demand. The day-to-day route choice adjustment process is the RBAP 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; otherwise, if path flow becomes stationary over day, then it is equivalent to the user equilibrium path flow. That is to say, if the current path flow pattern is not UE path flow, then ∑w∈W‍∑r∈Rw‍Crw(f)f˙rw<0. The RBAP is mild and includes various commonly used route choice adjustment process as its special cases, such as the proportional-switch adjustment process [17], the projected dynamical system [11], and the Brown-von Neumann-Nash dynamics [22].Suppose that a well-defined excess travel cost is associated with each path, such as the difference between the travel cost and the average travel cost corresponding to a specific OD pair. It is easy to check that, both the aggregated travel cost and excess travel cost of the entire network decreases based on the previous day's path travel costs when path flow pattern changes from day to day, whenever the process is RBAP. The logic is intuitive since the flow process follows the conservation constraint if the excess travel cost is defined as the difference between the path cost and average OD-specific travel cost, namely,(2.2)∑w∈W‍∑r∈Rw‍(Crw(f)-C-w(f))f˙rw=∑w∈W‍∑r∈Rw‍Crw(f)f˙rw<0.
since ∑r∈Rw‍f˙rw=0 and C-w(f)=(1/qw)∑r∈Rw‍Crw(f)frw. In fact, the reference travel cost level, C-w(f), may be altered as the current minimal travel cost. A more general definition of the excess travel cost is given in [19], in which, at least one traveler travels with a positive excess travel cost whenever the stationary equilibrium is not achieved. For simplification of our representation, we only refer the excess travel cost to the difference between the travel cost and the average travel cost associated a specific OD pair for the case with fixed demand, namely, ETCrw(f)=Crw(f)-C-w(f).For the case with elastic demand, notably, the inverse demand function,Dw-1(qw), is the current travel benefit between OD pair w if the demand is qw. We thus define the excess travel cost of path r∈Rw as Crw(f)-Dw-1(qw),w∈W or ETCrw(f)=Crw(f)-Dw-1(qw). To incorporate the cases with both fixed and elastic demands, we now extend the definition of rational behavior adjustment process proposed by Yang and Zhang [15]. Denote the path flow dynamics as the following equation:
(2.3)f˙=F(f).
The day-to-day route adjustment process (2.3) is the excess travel cost dynamics if the following three conditions are satisfied:(A1)
dynamic system (2.3) admits a unique solution trajectory for any given initial condition, and the trajectory is Lipschitz continuous;(A2)
∑w∈W‍∑r∈Rw‍ETCrwFrw<0 whenever F(f)≠0 where the excess travel cost, ETCrw, of path r∈Rw between w∈W is a well-defined function of link flow vector f;(A3)
f* is an equilibrium point of system (2.3) if F(f*)=0.With the excess travel cost dynamics, the aggregated excess travel cost of the entire network must decrease from the previous day's path travel costs when path flows change from day to day; otherwise, if path flow becomes stationary over days, then it is equivalent to the user equilibrium path flow. Define the excess payoff for using each path as-ETC, then the excess travel cost dynamics is the excess payoff dynamics, which is a special case of the well-behaved dynamics proposed by Sandholm [19].


## 2.2. Excess Travel Cost Dynamics with Heterogeneous Users

The excess travel cost dynamics, described above, assumes that all travelers perceive the path travel cost identically (travel time plus a discount monetary cost). However, it is well known that travelers may value travel time differently, depending on their income levels or travel purposes. Thus, when a toll policy is introduced into the network, heterogeneous users with different value of time (VOT) have to be considered in converting travel time into equivalent monetary cost. In this subsection, we focus our discussion on the behavior assumption of the route choice adjustment process in presence of the user heterogeneity. Furthermore, we consider a discrete set of user classes corresponding to the groups of users with different socioeconomic characteristics, such as income level.LetM denote such user classes, and βm, βm>0, be the average VOT for users of class m∈M. The travelers of each class adjust their routes according to their owner perception for any given and fixed link toll pattern, τ={τa,a∈A}. Let Trw(f) and τrw denote the travel time and toll of path r∈Rw between OD pair w∈W, where we further suppose that each OD pair and user class is associated with a fixed or elastic demand. In the latter case, the classic-specific demand is given by a strictly decreasing function qwm=Dwm(μwm), where μwm is the generalized travel cost in time unit for user class m∈M between OD pair w∈W. The set of the feasible path flow pattern is now expressed as
(2.4)Ω={f≥0:qwm=∑r∈Rw‍frw,m,w∈W,m∈M}.
Notably, the travelers with different VOT may estimate their excess travel cost differently. The average travel cost of OD pair w∈W estimated by the users of class m is C-wm(f)=(1/qwm)∑r∈Rw‍(Trw(f)+(τrw/βm))frw. The excess travel cost for user class m to use path r∈Rw between OD pair w∈W with fixed demand can be expressed as ETCrw,m(f)=Crw,m(f)-C-wm. As before for the case with elastic demand, the excess travel cost of path r∈Rw between OD pair w∈W for user class m∈M is ETCrw,m(f)=Crw,m(f)-Dw,m-1(qwm). Note that, for the multiclass day-to-day dynamic route choice adjustment process (2.3), the term, f˙=(f˙rw,m,r∈Rw,w∈W,m∈M), is class-specific path flow derivative. Similarly, the aggregate class-specific link flow vM, vM=(vam,a∈A,m∈M), where the aggregate link flow of user class m is vam=∑w∈W‍∑r∈Rw‍frw,mδarw. The multiclass day-to-day route adjustment process (2.3) is rational if assumptions (A1), (A3), and the following (A2) are satisfied:(A2′)
∑w∈W‍∑r∈Rw‍∑m∈M‍ETCrw,mFrw,m<0 whenever F(f)≠0.Assumption (A2′) says that, for any given and fixed link toll pattern,τ={τa,a∈A}, each user adjusts his/her route choice according to his/her own preference, which results in the decrease in aggregated excess travel cost of the entire network in time unit in comparison with that on previous day when path flows change from day to day. A stronger behavior assumption is that the flow on those paths on which travelers experienced positive excess travel cost strictly decreases, and vice versa. Assumption (A2′) is a direct extension of the homogeneous case, in which all travelers have an identical VOT.Example 2.1.
The proportional-switch adjustment process (PSAP) was first introduced by Smith [8] to suppose that the drivers on a higher cost path switch to other lower cost paths in a rate that is proportional to the cost difference between this path and the other lower cost paths. Peeta and Yang [17] modeled the dynamical traffic flow switch rate of the PSAP with fixed demand as:
(2.5)f˙rw=∑r′∈Rw(fr′w[Cr′w(f)-Crw(f)]+-frw[Crw(f)-Cr′w(f)]+),
where Crw is the travel cost of path r∈Rw between OD pair w, and [y]+=max{0,y}. By introducing the excess travel cost, ETCrw, for each path, dynamic system (2.5) can be rewritten as:
(2.6)f˙rw=∑r′∈Rw(fr′w[ETCr′w(f)-ETCrw(f)]+-frw[ETCrw(f)-ETCr′w(f)]+).
Furthermore, the PSAP with fixed demand, given by (2.6), can be extended to the multiclass user case. Given a toll pattern τ=(τa,a∈A), the travel cost and excess travel cost in time unit for the travellers with VOT βm are Crw,m=Trw+τrw/βm and C-w,m(f)=(1/qw)∑r∈Rw‍(Trw+τrw/βm)frw. The multiclass PSAP with fixed demand, for all m∈M, r∈Rw and w∈W, is
(2.7)f˙rw,m=∑r′∈Rw‍fr′w,m[ETCr′w,m(f)-ETCrw,m(f)]+-frw,m∑r′∈Rw‍[ETCrw,m(f)-ETCr′w,m(f)]+.
We now consider the elastic demand based on the simple model of PSAP. Suppose that there is a dummy link associated with each OD pair and the latent noncar travelers traverse from the origin to the destination by the dummy link. Suppose there is a large potential demand for each OD pair,Qw. The dummy link, rw-, is associated with the travel cost of Dw-1(qw) and flow q^w, where qw and q^w denote the revealed and latent demand between OD pair, w∈W, respectively. Namely, Crw-w=Dw-1(qw) and frw-w=q^w=Qw-qw. Let the average travel cost be C-w(f)=(1/Qw)(∑r∈Rw‍Crwfrw+Dw-1(qw)q^w). Like the case with fixed demand, the excess travel cost is defined as the difference between the travel cost and the average travel cost associated with the specific path. The PSAP with elastic demand can be revised, for r∈Rw∪{rw-} and w∈W, as
(2.8)f˙rw=∑r′∈Rw∪{rw-}(fr′w[ETCr′w(f)-ETCrw(f)]+-frw[ETCrw(f)-ETCr′w(f)]+).
Like the case with fixed demand again, the PASP with elastic demand, given by (2.8), can be extended to the multiclass PSAP indexed by user class m∈M. Following the method described above and the definition of the excess travel cost with multiclass users, the Brown and von Neumann process can be extended to the cases with elastic demand and user heterogeneity.


## 3. Stability of the Excess Travel Cost Dynamics

The stability is a central issue for the dynamic system analysis. Peeta and Yang [17] investigated the system stability over a set of desirable states rather than an isolated point, applying LaSalle's invariant set theorem for the dynamic traffic assignment problem with fixed demand by assuming the proportional-switch adjustment process, given by (2.5). The objective functions of the system optimum and user equilibrium problem are adopted as the Lyapunov functions to conduct the stability analysis, which is physically meaningful. Similar method of constructing Lyapunov function is also used by Jin [21] to examine the system stability of the dynamic traffic assignment problem under OD first-in-first-out violation situation. In this section, in a similar spirit of [17], the system stability of the excess travel cost dynamics proposed in Section 2 is addressed.A setΠ is an invariant set of dynamic system (2.3) if every system trajectory which starts from a point in Π remains in Π for all future time [20]. For instant, any equilibrium point of system (2.3) or, F(f)=0, as a set is an invariant set. LaSalle's invariant set theorem is stated as the follows.Lemma 3.1 (LaSalle’s invariant set theorem [20]).
Consider the autonomous systemx˙=F(x). Let V(x) be a scalar continuously differentiable function such that(1)
lim|x|→∞V(x)=∞, or, function V(x) is radically unbounded;(2)
V˙(x)≤0 for all x∈Ω.Let S={x∈Rn|V˙(x)=0} and Π is the largest invariant set contained in S, namely, Π is the union of all invariant sets within S. Then every solution x(s) is bounded and converges to Π.The standard LaSalle's invariant set theorem described above is in general not applicable in the case of discontinuous right-hand side, such as, projected dynamic system [11] and the network tatonnement process [10]. In this case, the generalized invariant set theorem [23] is applicable, only requiring the existence, uniqueness, and continuity of the solution of dynamic system that are guaranteed by assumption (A1). In this study, the standard LaSalle's invariant set theorem is adopted to investigate the stability issues of dynamic system (2.3).


### 3.1. Stability Property of the Dynamic System with Homogeneous Users

It is well known that the user equilibrium path flow pattern with elastic (fixed) demand can be identified by solving the following typical elastic (fixed) demand traffic assignment problem(3.1)min⁡f∈ΩL=∑a∈A‍∫0va‍ta(ω)dω-∑w∈W‍∫0qw‍Dw-1(ω)dω
or
(3.2)min⁡f∈ΩL=∑a∈A‍∫0va‍ta(ω)dω.
Under the assumptions that Dw-1(·) is strictly decreasing and ta(·) is strictly increasing, we know that the Wardrop user equilibrium link flow pattern is unique for the case with fixed demand, and the UE demand level is also unique for the case with elastic demand. Denote the set of user equilibrium path flow patterns as
(3.3)Π={f≥Ω:∑w∈W‍∑r∈Rw‍frwδarw=v-a,a∈A;∑w∈W‍frw=q-w,w∈W},
where v-={v-a,a∈A} and q-={q-w,w∈W} are unique UE link flow pattern and corresponding OD demand vector, respectively. It is must be pointed out that, for the case with fixed demand, q- is the OD demand matrix, and thus, definition (3.3) is suit for both cases with fixed and elastic demand. We first prove that the set (3.3) is an invariant set of system (2.3), that is to say, if any solution with an initial state in set Π will reside in Π for ever, which is depicted in the following lemma.Lemma 3.2.
The setΠ, defined by (3.3), is an invariant set of system (2.3), namely, f(0)∈Π implies that f(s)∈Π, for all s≥0.Proof.
From assumptions (A2)-(A3), we know thatF(f)≠0⇒ETC(f)∘F(f)<0 and, conversely, ETC(f)∘F(f)=0⇒F(f)=0, which implies that f is an equilibrium point. It is clear that Π={f∈Ω:ETC(f)=0}={f∈Ω:F(f)=0} is an invariant set of system (2.3). The proof is completed.From Lemma3.2, we now investigate the stability of system (2.3).Theorem 3.3.
Under assumptions (A1)–(A3), any solution of system (2.3) converges to the invariant set, Π, defined by (3.3), and, thus, the dynamic path flow pattern with any initial state induces the user equilibrium link flow pattern of static traffic assignment problem.Proof.
Consider the following continuously differentiable function (we only consider the case with elastic demand):(3.4)V(f)=∑a∈A‍∫0va(f)‍ta(ω)dω-∑w∈W‍∫0qw(f)‍Dw-1(ω)dω-min⁡{L},
where L is the objective function of mathematical programming problem (3.1); qw, w∈W, and va, a∈A, are functions of path flow pattern f. Let S={f∈Rn∣V˙(f)=0}, and from Lemma 3.2, the largest invariant set contained in S is Π. In fact, Π=S since S is the solution set of the minimization problem (3.1). Furthermore, note that V(f)>0 for all f∈Ω∖S, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). Taking derivative of V(f) in day-to-day time, and from assumption (A2), we get, for all f∈Ω,
(3.5)V˙(f)=(∂V∂frw,r∈Rw,w∈W)f˙=∑w∈W‍∑r∈Rw‍(ETCrwFrw(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). According to the LaSalle's invariant set theorem, we know that all solutions of system (2.3) converge to Π, which induces the UE link flow pattern. For the case with fixed demand, we can also show that the derivative of V(f) is nonpositive since ∑r∈Rw‍f˙rw=0 according to the flow conservation condition. The proof is completed.The rational behaviour adjustment process proposed by Yang and Zhang [15] is a useful concept frame to model the rational behaviour of the travellers under which the route adjustment process must reduce the aggregate total travel cost of the whole network day by day. However, the definition is suitable only for the case with fixed demand. More generally, the excess travel cost dynamics, or, excess payoff dynamics introduced by Sandholm [19] can incorporate the cases with fixed and elastic demand. Theorem 3.3 depicts that for the excess travel cost dynamics satisfying assumptions (A1)–(A3), any dynamic path flow pattern must move to a certain UE path flow pattern, which induces the UE link flow pattern. Therefore, the set of all UE path flow patterns is a stable invariant set.Furthermore, for any given link toll pattern,τ={τa,a∈A}, the travel cost of path r∈Rw between OD pair w∈W is the full travel cost (the time cost plus the monetary cost), and the excess travel cost can be defined similarly as the case τ=0, namely, Crw(f)=∑w∈W‍∑r∈Rw‍(ta(va(f))+τa/β)δarw. Then the set of the UE path flow patterns corresponding to the toll vector τ={τa,a∈A} is a stable invariant set of system (2.3) or any dynamic path flow pattern must converge to the set. Specially, if the system optimal and fixed link toll pattern, τ~={τa=MCP(va(f~)),a∈A} is imposed, where f~ is the SO path flow pattern for fixed- or elastic-demand case, then any dynamic path flow pattern converges to a certain SO path flow pattern, in this case, the invariant set is
(3.6)Π~={f≥Ω:∑w∈W‍∑r∈Rw‍frwδarw=v~a,a∈A;∑w∈W‍frw=q~w,w∈W},
where v~={v~a,a∈A} and q~={q~w,w∈W} are unique SO link flow pattern and corresponding OD demand vector, respectively.Example 3.4.
Consider that the following simple network example, shown in Figure1, consists of 4 links, 4 nodes, and 2 OD pairs. The OD pairs and the corresponding path are listed in Table 1. Each OD pair has one unit fixed demand. Since all links have the same link travel time function, ti(vi)=vi, it is clear that the user equilibrium path flow pattern is not unique although there is a unique link flow pattern.Table 1
OD pairs and path sets.
OD pair
Path
1
→4
Path 1:{1,3},f1
q
1
→
4 = 1
Path 3:{1,4},f3
2→4
Path 2:{2,3},f2
q
2
→
4 = 1
Path 4:{2,4},f4Figure 1
The network for Example3.4.By simple calibration, we know that all nonnegative path flow pattern satisfying conditionf1+f2=1, f1=f4 and f2=f3 are user equilibrium path flow pattern, which induces the unique link flow pattern, vi=1 for all links, i∈{1,2,3,4}. The proportional-switch adjustment process (2.5) is expressed as
(3.7)(f˙1f˙2)=([Y]+-([Y]++[-Y]+)f1[Y]+-([Y]++[-Y]+)f2),
where
(3.8)Y=2-2(f1+f2).Using MATLAB Simulink, the behavior of the dynamic system (3.7) starting from 500 randomly selected initial states in the all feasible domain is shown in Figure 2. It is clear that, for the path flow dynamic system (3.7), the equilibrium states consist of a set rather than an isolated equilibrium point is an invariant set, and no equilibrium state is stable for path flow pattern in the sense of Lyapunov stability although the link flow is stable.Figure 2
State trajectories demonstrating stability of equilibria.


### 3.2. Stability Property of the Dynamic System with Heterogeneous Users

We now move to examine the system stability when the travelers are heterogeneous in valuation of travel time. It is well known [24] that the static multiclass traffic assignment problem with fixed demand can be formulated as the following equivalent minimization problem
(3.9)min⁡f∈Ω⁡L=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A∑m∈Mτaβmvam(f),
where the feasible path flow set Ω is given by (2.4). The objective function (3.9) is strictly convex in aggregate link flow v for monotone link travel time function ta(va). Thus, under a given link toll pattern τ, the equilibrium aggregate link flow is unique. However, the class-specific link flow vM is generally not unique (neither is the UE path flow).Consider the following continuously differentiable function:(3.10)V(f)=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A‍∑m∈M‍τaβmvam(f)-min⁡{L}.
From the proof of Lemma 3.2, we know that S={f∈Rn∣V˙(f)=0} is the largest invariant set of multiclass dynamic system (2.3), which is the solution of minimization problem (3.9). Note that V(f)>0 for all f∈Ω, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). Furthermore, from the assumption (A2′) and the flow conservation ∑r∈Rw‍f˙rw,m=0, we know, for all f∈Ω, that
(3.11)V˙(f)=(∂V∂frw,m,m∈M,r∈Rw,w∈W)f˙=∑w∈W‍∑r∈Rw‍∑m∈M‍(ETCrw,mFrw,m(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). In (3.11), ETCrw,m is the excess travel cost of path r∈Rw between OD pair w∈W for user class m∈M defined in Section 2.2. Similar to (3.3), we still denote Π as the set of multiclass user equilibrium path flow patterns as
(3.12)Π={f≥Ω:∑w∈W‍∑r∈Rw‍∑m∈M‍frw,mδarw=v-a,a∈A;∑w∈W‍frw,m=q-wm,w∈W},
where v-={v-a,a∈A} and q-M={q-wm,w∈W,m∈M} are unique aggregate UE link flow pattern and class-specific OD demand vector, respectively. According to the LaSalle's invariant set theorem, we know that all solutions of system (2.3) converge to Π, which induces the UE link flow pattern. Therefore, dynamic class-specific path flow pattern with any initial state induces the multiclass user equilibrium link flow pattern by the day-to-day route adjustment process.Similar analysis can be conducted for the case with elastic demand. In this case, the static multiclass traffic assignment problem with elastic demand can be formulated as the following equivalent minimization problem [24]:
(3.13)min⁡f∈Ω⁡L=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A‍∑m∈M‍τaβmvam(f)-∑w∈W‍∑m∈M‍∫0qwm‍Dw,m-1(ω)dω,
where Dw,m-1(·) is the inverse demand function for user class m∈M between OD pair w∈W. Define the candidate Lyapunov function as
(3.14)V(f)=∑a∈A∫0va(f)ta(ω)dω‍+∑a∈A‍∑m∈M‍τaβmvam(f)-∑w∈W‍∑m∈M‍∫0qwm‍Dw,m-1(ω)dω-min⁡{L}.
The multiclass UE path flow S={f∈Rn∣V˙(f)=0} is the largest invariant set. It is clear that, V(f)>0 for all f∈Ω∖S, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). By direct calibration, we know, for all f∈Ω,
(3.15)V˙(f)=∑w∈W∑r∈Rw∑m∈M((∑a‍(ta(va)+τaβm)δar-Dw,m-1(qwm))f˙rw,m)=∑w∈W∑r∈Rw∑m∈M(ETCrw,mFrw,m(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). From LaSalle's invariant set theorem, we have the following stability property for the dynamic system with heterogeneous users.Theorem 3.5.
Under assumptions (A1), (A2′), and (A3), for any given and fixed link toll pattern, any solution of system (2.3) with heterogeneous users converges to a certain user equilibrium path flow pattern, which results in the multiclass user equilibrium link flow pattern.Although the route adjustment behavior assumption is relaxed to consider the heterogeneity of travelers, that is to say the individual traveler adjusts his/her route choice based on his/her own perception, the multiclass UE link flow pattern is obtained. Theorem3.5 also provides a method to calculate the multiclass UE link flow pattern.Example 3.6.
Consider the network example [18], shown in Figure 3, consisting of 5 links, 4 nodes, and 2 OD pairs. The link cost functions are given by
(3.16)t1=20+2v1,t2=v2,t3=v3,t4=20+v4,t5=2v5.
There are two classes of travelers with different values of time, class 1 consists of travelers with a lower value of time of β1=1.0 (Yuan/min) and class 2 consists of travelers with a higher value of time of β2=2.0 (Yuan/min). The OD pairs and the corresponding path are listed in Table 2. Let frw,m denote the flow of path r∈{1,2,3,4} between OD pair w∈{1,2}, with user class m∈{1,2}. The demand for each user class between each OD pair is q11=10, q12=10, q21=20, and q22=10. Given the link toll pattern of τ1=τ3=τ4=0, and τ2=τ5=10 Yuan, which results in the static multiclass user equilibrium link flow pattern, v1=10, v2=10, v3=20, v4=10 and v5=20. Here we still adopt the proportional-switch adjustment process (PSAP) to model the multiclass path flow dynamics. From the flow conservation, we only consider four free variables, f11,1, f11,2, f22,1, and f22,2. The PSAP (2.5) is expressed as:
(3.17)(f˙11,1f˙11,2f˙22,1f˙22,2)=((10-f11,1)[Y1]+-f11,1[-Y1]+(10-f11,2)[Y2]+-f11,2[-Y2]+(20-f22,1)[Y3]+-f22,1[-Y3]+(10-f22,2)[Y4]+-f22,2[-Y4]+),
where
(3.18)Y1=(T31(f)-T11(f))+(τ31-τ11)β1Y2=(T31(f)-T11(f))+(τ31-τ11)β2Y3=(T42(f)-T22(f))+(τ42-τ22)β1Y4=(T42(f)-T22(f))+(τ42-τ22)β2,
and Trw(f) and τrw are the total travel time and toll of path r∈Rw between OD pair w∈{1,2}, respectively. Using MATLAB Simulink, the path flow pattern of the dynamic system (2.5) starting randomly from selected initial state converges to the unique solution, in which, f11,1=0, f11,2=10, f22,1=10 and f22,2=0. Denote C-wm as the class-specific average travel cost in time unit between OD pair w∈{1,2}, such as, for m∈{1,2},
(3.19)C-1m=((T11(f)+τ11/βm)f11+(T31(f)+τ31/βm)f31)q1,
The day-to-day aggregate excess travel cost in time unit can be calculated as
(3.20)ΔETC=∑w=1,2r∈Rwm=1,2(Trw(f)+τrwβm-C-wm)f˙rw,m
which approaches zero. The behavior of the dynamic system (3.17), starting from 200 randomly selected initial states in all the feasible domain, is shown in Figures 4 and 5. Observed from the two figures for the multiclass case, the state trajectories become chaotic since the individual traveler adjusts his/her route choice based on his/her own value of time. However, the trajectories with any initial states solution for the path flow dynamic system (3.17) converge to the UE path flow pattern.Table 2
OD pairs and path sets.
OD pair
Path
1→4
Path 1:{1}
q
1
Path 3:{2,3}
2→4
Path 2:{4,3}
q
2
Path 4:{5}Figure 3
The network for Example3.6.Figure 4
State trajectories demonstrating stability of UE flow on Path 1.Figure 5
State trajectories demonstrating stability of UE flow on Path 4.


## 3.1. Stability Property of the Dynamic System with Homogeneous Users

It is well known that the user equilibrium path flow pattern with elastic (fixed) demand can be identified by solving the following typical elastic (fixed) demand traffic assignment problem(3.1)min⁡f∈ΩL=∑a∈A‍∫0va‍ta(ω)dω-∑w∈W‍∫0qw‍Dw-1(ω)dω
or
(3.2)min⁡f∈ΩL=∑a∈A‍∫0va‍ta(ω)dω.
Under the assumptions that Dw-1(·) is strictly decreasing and ta(·) is strictly increasing, we know that the Wardrop user equilibrium link flow pattern is unique for the case with fixed demand, and the UE demand level is also unique for the case with elastic demand. Denote the set of user equilibrium path flow patterns as
(3.3)Π={f≥Ω:∑w∈W‍∑r∈Rw‍frwδarw=v-a,a∈A;∑w∈W‍frw=q-w,w∈W},
where v-={v-a,a∈A} and q-={q-w,w∈W} are unique UE link flow pattern and corresponding OD demand vector, respectively. It is must be pointed out that, for the case with fixed demand, q- is the OD demand matrix, and thus, definition (3.3) is suit for both cases with fixed and elastic demand. We first prove that the set (3.3) is an invariant set of system (2.3), that is to say, if any solution with an initial state in set Π will reside in Π for ever, which is depicted in the following lemma.Lemma 3.2.
The setΠ, defined by (3.3), is an invariant set of system (2.3), namely, f(0)∈Π implies that f(s)∈Π, for all s≥0.Proof.
From assumptions (A2)-(A3), we know thatF(f)≠0⇒ETC(f)∘F(f)<0 and, conversely, ETC(f)∘F(f)=0⇒F(f)=0, which implies that f is an equilibrium point. It is clear that Π={f∈Ω:ETC(f)=0}={f∈Ω:F(f)=0} is an invariant set of system (2.3). The proof is completed.From Lemma3.2, we now investigate the stability of system (2.3).Theorem 3.3.
Under assumptions (A1)–(A3), any solution of system (2.3) converges to the invariant set, Π, defined by (3.3), and, thus, the dynamic path flow pattern with any initial state induces the user equilibrium link flow pattern of static traffic assignment problem.Proof.
Consider the following continuously differentiable function (we only consider the case with elastic demand):(3.4)V(f)=∑a∈A‍∫0va(f)‍ta(ω)dω-∑w∈W‍∫0qw(f)‍Dw-1(ω)dω-min⁡{L},
where L is the objective function of mathematical programming problem (3.1); qw, w∈W, and va, a∈A, are functions of path flow pattern f. Let S={f∈Rn∣V˙(f)=0}, and from Lemma 3.2, the largest invariant set contained in S is Π. In fact, Π=S since S is the solution set of the minimization problem (3.1). Furthermore, note that V(f)>0 for all f∈Ω∖S, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). Taking derivative of V(f) in day-to-day time, and from assumption (A2), we get, for all f∈Ω,
(3.5)V˙(f)=(∂V∂frw,r∈Rw,w∈W)f˙=∑w∈W‍∑r∈Rw‍(ETCrwFrw(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). According to the LaSalle's invariant set theorem, we know that all solutions of system (2.3) converge to Π, which induces the UE link flow pattern. For the case with fixed demand, we can also show that the derivative of V(f) is nonpositive since ∑r∈Rw‍f˙rw=0 according to the flow conservation condition. The proof is completed.The rational behaviour adjustment process proposed by Yang and Zhang [15] is a useful concept frame to model the rational behaviour of the travellers under which the route adjustment process must reduce the aggregate total travel cost of the whole network day by day. However, the definition is suitable only for the case with fixed demand. More generally, the excess travel cost dynamics, or, excess payoff dynamics introduced by Sandholm [19] can incorporate the cases with fixed and elastic demand. Theorem 3.3 depicts that for the excess travel cost dynamics satisfying assumptions (A1)–(A3), any dynamic path flow pattern must move to a certain UE path flow pattern, which induces the UE link flow pattern. Therefore, the set of all UE path flow patterns is a stable invariant set.Furthermore, for any given link toll pattern,τ={τa,a∈A}, the travel cost of path r∈Rw between OD pair w∈W is the full travel cost (the time cost plus the monetary cost), and the excess travel cost can be defined similarly as the case τ=0, namely, Crw(f)=∑w∈W‍∑r∈Rw‍(ta(va(f))+τa/β)δarw. Then the set of the UE path flow patterns corresponding to the toll vector τ={τa,a∈A} is a stable invariant set of system (2.3) or any dynamic path flow pattern must converge to the set. Specially, if the system optimal and fixed link toll pattern, τ~={τa=MCP(va(f~)),a∈A} is imposed, where f~ is the SO path flow pattern for fixed- or elastic-demand case, then any dynamic path flow pattern converges to a certain SO path flow pattern, in this case, the invariant set is
(3.6)Π~={f≥Ω:∑w∈W‍∑r∈Rw‍frwδarw=v~a,a∈A;∑w∈W‍frw=q~w,w∈W},
where v~={v~a,a∈A} and q~={q~w,w∈W} are unique SO link flow pattern and corresponding OD demand vector, respectively.Example 3.4.
Consider that the following simple network example, shown in Figure1, consists of 4 links, 4 nodes, and 2 OD pairs. The OD pairs and the corresponding path are listed in Table 1. Each OD pair has one unit fixed demand. Since all links have the same link travel time function, ti(vi)=vi, it is clear that the user equilibrium path flow pattern is not unique although there is a unique link flow pattern.Table 1
OD pairs and path sets.
OD pair
Path
1
→4
Path 1:{1,3},f1
q
1
→
4 = 1
Path 3:{1,4},f3
2→4
Path 2:{2,3},f2
q
2
→
4 = 1
Path 4:{2,4},f4Figure 1
The network for Example3.4.By simple calibration, we know that all nonnegative path flow pattern satisfying conditionf1+f2=1, f1=f4 and f2=f3 are user equilibrium path flow pattern, which induces the unique link flow pattern, vi=1 for all links, i∈{1,2,3,4}. The proportional-switch adjustment process (2.5) is expressed as
(3.7)(f˙1f˙2)=([Y]+-([Y]++[-Y]+)f1[Y]+-([Y]++[-Y]+)f2),
where
(3.8)Y=2-2(f1+f2).Using MATLAB Simulink, the behavior of the dynamic system (3.7) starting from 500 randomly selected initial states in the all feasible domain is shown in Figure 2. It is clear that, for the path flow dynamic system (3.7), the equilibrium states consist of a set rather than an isolated equilibrium point is an invariant set, and no equilibrium state is stable for path flow pattern in the sense of Lyapunov stability although the link flow is stable.Figure 2
State trajectories demonstrating stability of equilibria.


## 3.2. Stability Property of the Dynamic System with Heterogeneous Users

We now move to examine the system stability when the travelers are heterogeneous in valuation of travel time. It is well known [24] that the static multiclass traffic assignment problem with fixed demand can be formulated as the following equivalent minimization problem
(3.9)min⁡f∈Ω⁡L=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A∑m∈Mτaβmvam(f),
where the feasible path flow set Ω is given by (2.4). The objective function (3.9) is strictly convex in aggregate link flow v for monotone link travel time function ta(va). Thus, under a given link toll pattern τ, the equilibrium aggregate link flow is unique. However, the class-specific link flow vM is generally not unique (neither is the UE path flow).Consider the following continuously differentiable function:(3.10)V(f)=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A‍∑m∈M‍τaβmvam(f)-min⁡{L}.
From the proof of Lemma 3.2, we know that S={f∈Rn∣V˙(f)=0} is the largest invariant set of multiclass dynamic system (2.3), which is the solution of minimization problem (3.9). Note that V(f)>0 for all f∈Ω, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). Furthermore, from the assumption (A2′) and the flow conservation ∑r∈Rw‍f˙rw,m=0, we know, for all f∈Ω, that
(3.11)V˙(f)=(∂V∂frw,m,m∈M,r∈Rw,w∈W)f˙=∑w∈W‍∑r∈Rw‍∑m∈M‍(ETCrw,mFrw,m(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). In (3.11), ETCrw,m is the excess travel cost of path r∈Rw between OD pair w∈W for user class m∈M defined in Section 2.2. Similar to (3.3), we still denote Π as the set of multiclass user equilibrium path flow patterns as
(3.12)Π={f≥Ω:∑w∈W‍∑r∈Rw‍∑m∈M‍frw,mδarw=v-a,a∈A;∑w∈W‍frw,m=q-wm,w∈W},
where v-={v-a,a∈A} and q-M={q-wm,w∈W,m∈M} are unique aggregate UE link flow pattern and class-specific OD demand vector, respectively. According to the LaSalle's invariant set theorem, we know that all solutions of system (2.3) converge to Π, which induces the UE link flow pattern. Therefore, dynamic class-specific path flow pattern with any initial state induces the multiclass user equilibrium link flow pattern by the day-to-day route adjustment process.Similar analysis can be conducted for the case with elastic demand. In this case, the static multiclass traffic assignment problem with elastic demand can be formulated as the following equivalent minimization problem [24]:
(3.13)min⁡f∈Ω⁡L=∑a∈A∫0va(f)‍ta(ω)dω+∑a∈A‍∑m∈M‍τaβmvam(f)-∑w∈W‍∑m∈M‍∫0qwm‍Dw,m-1(ω)dω,
where Dw,m-1(·) is the inverse demand function for user class m∈M between OD pair w∈W. Define the candidate Lyapunov function as
(3.14)V(f)=∑a∈A∫0va(f)ta(ω)dω‍+∑a∈A‍∑m∈M‍τaβmvam(f)-∑w∈W‍∑m∈M‍∫0qwm‍Dw,m-1(ω)dω-min⁡{L}.
The multiclass UE path flow S={f∈Rn∣V˙(f)=0} is the largest invariant set. It is clear that, V(f)>0 for all f∈Ω∖S, and V(f)=0 for all f∈S. Therefore V(f) is a Lyapunov function candidate of system (2.3). By direct calibration, we know, for all f∈Ω,
(3.15)V˙(f)=∑w∈W∑r∈Rw∑m∈M((∑a‍(ta(va)+τaβm)δar-Dw,m-1(qwm))f˙rw,m)=∑w∈W∑r∈Rw∑m∈M(ETCrw,mFrw,m(f))≤0,
which implies that V(f) is a Lyapunov function of system (2.3). From LaSalle's invariant set theorem, we have the following stability property for the dynamic system with heterogeneous users.Theorem 3.5.
Under assumptions (A1), (A2′), and (A3), for any given and fixed link toll pattern, any solution of system (2.3) with heterogeneous users converges to a certain user equilibrium path flow pattern, which results in the multiclass user equilibrium link flow pattern.Although the route adjustment behavior assumption is relaxed to consider the heterogeneity of travelers, that is to say the individual traveler adjusts his/her route choice based on his/her own perception, the multiclass UE link flow pattern is obtained. Theorem3.5 also provides a method to calculate the multiclass UE link flow pattern.Example 3.6.
Consider the network example [18], shown in Figure 3, consisting of 5 links, 4 nodes, and 2 OD pairs. The link cost functions are given by
(3.16)t1=20+2v1,t2=v2,t3=v3,t4=20+v4,t5=2v5.
There are two classes of travelers with different values of time, class 1 consists of travelers with a lower value of time of β1=1.0 (Yuan/min) and class 2 consists of travelers with a higher value of time of β2=2.0 (Yuan/min). The OD pairs and the corresponding path are listed in Table 2. Let frw,m denote the flow of path r∈{1,2,3,4} between OD pair w∈{1,2}, with user class m∈{1,2}. The demand for each user class between each OD pair is q11=10, q12=10, q21=20, and q22=10. Given the link toll pattern of τ1=τ3=τ4=0, and τ2=τ5=10 Yuan, which results in the static multiclass user equilibrium link flow pattern, v1=10, v2=10, v3=20, v4=10 and v5=20. Here we still adopt the proportional-switch adjustment process (PSAP) to model the multiclass path flow dynamics. From the flow conservation, we only consider four free variables, f11,1, f11,2, f22,1, and f22,2. The PSAP (2.5) is expressed as:
(3.17)(f˙11,1f˙11,2f˙22,1f˙22,2)=((10-f11,1)[Y1]+-f11,1[-Y1]+(10-f11,2)[Y2]+-f11,2[-Y2]+(20-f22,1)[Y3]+-f22,1[-Y3]+(10-f22,2)[Y4]+-f22,2[-Y4]+),
where
(3.18)Y1=(T31(f)-T11(f))+(τ31-τ11)β1Y2=(T31(f)-T11(f))+(τ31-τ11)β2Y3=(T42(f)-T22(f))+(τ42-τ22)β1Y4=(T42(f)-T22(f))+(τ42-τ22)β2,
and Trw(f) and τrw are the total travel time and toll of path r∈Rw between OD pair w∈{1,2}, respectively. Using MATLAB Simulink, the path flow pattern of the dynamic system (2.5) starting randomly from selected initial state converges to the unique solution, in which, f11,1=0, f11,2=10, f22,1=10 and f22,2=0. Denote C-wm as the class-specific average travel cost in time unit between OD pair w∈{1,2}, such as, for m∈{1,2},
(3.19)C-1m=((T11(f)+τ11/βm)f11+(T31(f)+τ31/βm)f31)q1,
The day-to-day aggregate excess travel cost in time unit can be calculated as
(3.20)ΔETC=∑w=1,2r∈Rwm=1,2(Trw(f)+τrwβm-C-wm)f˙rw,m
which approaches zero. The behavior of the dynamic system (3.17), starting from 200 randomly selected initial states in all the feasible domain, is shown in Figures 4 and 5. Observed from the two figures for the multiclass case, the state trajectories become chaotic since the individual traveler adjusts his/her route choice based on his/her own value of time. However, the trajectories with any initial states solution for the path flow dynamic system (3.17) converge to the UE path flow pattern.Table 2
OD pairs and path sets.
OD pair
Path
1→4
Path 1:{1}
q
1
Path 3:{2,3}
2→4
Path 2:{4,3}
q
2
Path 4:{5}Figure 3
The network for Example3.6.Figure 4
State trajectories demonstrating stability of UE flow on Path 1.Figure 5
State trajectories demonstrating stability of UE flow on Path 4.


## 4. Conclusion

We presented an excess travel cost dynamics to model travelers' route choice behavior in a transportation network with fixed or elastic demand and homogeneous or heterogeneous users. The excess travel cost dynamics is a natural extension of the rational behavior adjustment process proposed by Yang and Zhang [15], which corresponds to the excess payoff dynamics in evolutionary game [19]. The excess travel cost dynamics serves as a more general framework than the rational behavior adjustment process for modeling the travelers' dynamic route choice behavior in the transportation network with fixed or elastic demand, homogeneous or heterogeneous users. LaSalle's theorem is adopted to study the dynamic system stability. We proved that the trajectories of the excess travel cost dynamics with any initial state converge to the user equilibrium link flow pattern in various scenarios (fixed or elastic demand, homogeneous or heterogeneous users).It is an interesting challenge to design the system optimum pricing scheme in a transportation network by taking into account both the hidden actions of travelers' day-to-day route choice adjustment and the true but unknown demands, specially, with heterogeneous users. Another research direction is to model the heterogeneous behavior of the travelers on their perceived travel cost except the way valuing the monetary and time costs, which requires a stochastic dynamic route choice process incorporating the user heterogeneity.



---

*Source: 918405-2012-07-24.xml*