# A Trial-and-Error Congestion Pricing Method for Day-to-Day Dynamic Network Flows considering Travelers’ Heterogeneous Inertia Patterns

Authors: Bojian Zhou; Min Xu; Yong Zhang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This study proposes a trial-and-error congestion pricing method to achieve system optimum under day-to-day flow dynamics with unknown demand. Travelers are assumed to adjust their route choice day by day so that the resultant traffic flow under a trial of tolls evolves from one day to another. We rigorously demonstrate that if psychological inertia is considered in travelers’ day-to-day route choice behavior, the convergence of the proposed trial-and-error congestion pricing method can be guaranteed without requiring the observed network flows to be in user equilibrium. Furthermore, the proposed method also allows tolls to be updated at irregular time intervals, which greatly relaxes the implementation requirements of existing congestion pricing schemes in the literature. This study is very significant from a practical point of view because it provides a flexibility approach that greatly reduces the implementation time of the traditional trial-and-error congestion pricing method. Numerical experiments are conducted to validate our theoretical findings.


---

## Body

## 1. Introduction

Congestion pricing has been recognized as an efficient approach to alleviate traffic congestion and improve social welfare [1–4]. The theoretical background of congestion pricing is based on the fundamental economic principle of marginal-cost pricing, which states that travelers using congested roads should pay a toll equal to the difference between the marginal social cost and the marginal private cost [5, 6]. The marginal-cost pricing internalizes the congestion externalities exerted by participants on each other so that a system optimum flow pattern can be achieved in the network.Traditionally, the determination of the marginal-cost toll requires to solve a system optimal traffic equilibrium problem, which takes the link travel time function and the OD demand as its inputs. However, in practice, it is time consuming, expensive, and challenging to evaluate the accurate demand for each OD pair [7–10]. To circumvent this problem, trial-and-error congestion pricing methods, which do not require explicit knowledge of the OD demand, are proposed [11–13]. The general procedure of these methods is as follows: observe the traffic flow on each link, based on which a trial link flow pattern is generated. The toll for each link is then set using the trial link flows and implemented for the next trial. This procedure is repeated until the system optimum is achieved.In the literature, the trial-and-error congestion pricing method was first proposed by Li [14], who used a bisection procedure to adjust the toll iteratively according to the observed UE flow on a single road link. Yang et al. [11] incorporated an iterative marginal-cost toll adjustment procedure into the method of successive averages (MSA) and demonstrated its convergence to a system optimum in a general network. Han and Yang [15] further extended Yang et al.’s method to networks with asymmetric, nonseparable link travel time functions and improved its convergence rate. In addition to driving a user equilibrium flow pattern to a system optimum, the trial-and-error method can also be used in congestion control. Based on the Lagrange dual theory, Meng et al. [16] put forward a practical trial-and-error method for seeking the desirable link tolls to restrict the link flows to some predetermined thresholds. Meng and Liu [17] further developed a trial-and-error method for cordon-based congestion pricing scheme under side-constrained probit-based SUE conditions. Yang et al. [18] proposed a variational inequality-based trial-and-error method for effective congestion control. This method enhances the convergence rate of the method of Meng et al. and allows for nonseparable, asymmetric link cost functions. Zhou et al. [19] developed a unified framework for the trial-and-error congestion pricing scheme, which not only considers the minimization of the total system cost but also addresses the problem of congestion control. Liu et al. investigates the nonlinear distance-based congestion pricing in a network considering stochastic day-to-day dynamics.In another branch of the literature, day-to-day dynamic models have also received much attention in the past two decades [20–22]. These models are widely used to simulate travelers’ learning behaviors and the traffic flow fluctuations from one day to another in a transportation network. Generally speaking, the day-to-day dynamic model can be divided into route-based or link-based models according to the type of variables in use. The route-based models are expressed using route flow variables. Examples of this type of models include the simplex gravity flow dynamics [23], the proportional-switch adjustment process [20], the network tatonnement process [24], the projected dynamical system [25], and the evolutionary traffic dynamics [26]. As a generalization of the aforementioned five models, Yang and Zhang [27] proposed a rational behavior adjustment process (RBAP) under the assumption that the aggregated travel cost of the entire network would decrease when the route flows change from day to day. They proved that RBAP includes as its special cases the aforementioned five continuous day-to-day route flow adjustment models. Xiao et al. [28] showed that the day-to-day flow dynamics is analogous to a damped oscillatory system. They developed a route-based day-to-day dynamical model by considering travelers’ learning process and route swapping behavior, which offers a new look at the network flow dynamics from the viewpoint of physics.The link-based day-to-day dynamic models are formulated in terms of link flows. The first link flow adjustment model was proposed by He et al. [29]. This model captures travelers’ cost-minimization behavior as well as their reluctance to make significant changes, which overcome the shortcomings of the route-based models. Han and Du [30] extended He et al.’s model to the case where the link travel cost functions are asymmetric, and they performed a stability analysis of the continuous link flow adjustment model by using Lyapunov stability theory. Cantarella [31] introduced a discrete dynamic process model in terms of link flows and costs to investigate the evolution of the total user surplus. Guo et al. [32] put forward a discrete link-based day-to-day dynamic model called the discrete rational adjustment process (DRAP). The DRAP is very general in its form such that it can deal with the cases such as UE or SUE principle, fixed or elastic demand. Guo et al. [33] further extended the DRAP to a continuous link-based day-to-day dynamic traffic assignment model. Several properties of this model are established in their research, including the invariance of its evolutionary trajectories, the uniqueness, and the stability of its stationary points.So far, there is only limited research that simultaneously addresses trial-and-error congestion pricing and day-to-day dynamics of network flows. The motivation of the joint study of these two problems is to relax an implementation requirement of traditional trial-and-error congestion pricing schemes. This requirement emphasizes that after imposing each trial of link tolls, equilibrium link flows can be achieved and observed. However, in reality, travelers take time to learn the effect of the link tolls so that their route choices are adjusted from one day to another. Therefore, it requires an extended period for the resultant link flow pattern to evolve towards an equilibrium state. If the interval between two consecutive trials is not long enough, the link flows observed by the planner may not be in equilibrium. Under such a circumstance, the global convergence of the trial-and-error congestion pricing method cannot be achieved. To overcome this problem, Ye et al. [34] assumed that the adjustment process of the day-to-day dynamic network flow is fast enough such that the relative decreasing rate along the path flow trajectory is not larger than 1 (cf. equation (18) in [34]). Based on this assumption, Ye et al. demonstrated that the trial-and-error congestion pricing method still converges to system optimum, even with disequilibrium observed network flows. However, note that this assumption is artificial and idealistic and it has not been validated in reality, which weakens the usefulness of the trial-and-error method.In this research, we will drop the assumption that was adopted in Ye et al. [34]. Instead, we assume that travelers have some degree of psychological inertia. That is to say, travelers (especially commuters) who are familiar with their routes tend to avoid the effort of making a new route decision, and hence are usually not willing to reconsider their route choice every day. We use a 0-1 sequence to represent a specific inertia pattern and propose a day-to-day dynamic flow adjustment model that considers travelers’ heterogeneous inertia patterns. On top of that, we develop a new trial-and-error congestion pricing method by incorporating the day-to-day dynamic flow adjustment process with heterogeneous inertia patterns. This method inherits the merit of Ye et al.’s approach, i.e., it does not require the observed flows to be in equilibrium. Furthermore, it extends Ye et al.’s approach to the case where the tolls are allowed to be updated at irregular time intervals, which further relaxes the implementation requirements of the trial-and-error method. We show that the proposed trial-and-error congestion pricing method can be interpreted as the solution procedure of the truncated cost approximation method and rigorously demonstrated the convergence of the trial-and-error congestion pricing method by using the theory of cost approximation [35]. Therefore, the result of this study greatly facilitates the application of the trial-and-error congestion pricing method in both theoretical and practical perspectives.The rest of the paper is organized as follows. Section2 proposes a day-to-day dynamic model with heterogeneous travel inertia. Section 3 develops a trial-and-error congestion pricing method that incorporates the inertia-based day-to-day dynamic model. The convergence of the proposed trial-and-error method is rigorously demonstrated in Section 4. Section 5 provides a numerical example to evaluate the performance of the trial-and-error method under different circumstances. Conclusions are drawn in Section 6.


## 2. A Day-to-Day Dynamic Model considering Heterogeneous Travel Inertia

Travelers are a fundamental component of road traffic. Their decisions and actions affect the traffic flows on the network every day. To describe the response of travelers to exogenous traffic factors, e.g., congestion pricing, day-to-day dynamic models have been proposed to formulate the daily route adjustment process of travelers. For the sake of simplicity, it is usually assumed in the traditional day-to-day dynamic models that travelers are sufficiently active to reconsider their routes of the next day. However, in reality, everyone has some degree of psychological inertia. Some travelers (especially the commuters, for example) are not accustomed to evaluating and comparing different routes every day. They generally use the same route for a few days after which they decide whether or not to change their routes.In this study, the psychological inertia of a traveler will be characterized by a binary variable (0 or 1), which indicates whether the traveler is willing to evaluate and reconsider his/her route choice on a particular day. As such, the traveler’s inertia pattern can be defined as a series of binary variables that represent the evolution of the traveler’s psychological inertia over time. For example, Figure1 shows the inertia patterns of three typical travelers. The inertia pattern of Traveler 1 is described by the sequence (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, …), which implies that this traveler makes a route choice evaluation every two days. The inertia pattern of Traveler 2 is represented by the sequence (1, 0, 0, 1, 0, 0, 1, 0, 0, …), meaning that he/she reconsiders his/her route choice every three days. According to the same logic, we can see that the inertia pattern of Traveler 3 is (1, 0, 1, 1, 1, 1, 0, 1, 0, 1, …), which indicates that his/her route choice evaluation is irregularly conducted on different days. It is worth noting that even if a traveler is willing to evaluate his/her route choice, he/she does not have to take different routes because, after evaluation, he/she may end up using the same route as before. Conversely, if the traveler is unwilling to make a route choice evaluation, he/she must travel on the same route as before.Figure 1
Inertia patterns for 3 typical travelers.Consider a general transportation network denoted byGN,A, where N and A are the sets of nodes and links, respectively. Let W be the set of all OD pairs in the network and Rw be the set of routes between OD pair w∈W. Without loss of generality, we assume that there are m classes of travelers with each class being represented by i. Travelers in each class have the same inertia pattern. All class indices are grouped into a set denoted by M=1,2,…,m, and accordingly, we have i∈M. Also, the demand of class i for OD pair w∈W is denoted by dwi, and the flow of class i on route r∈Rw, w∈W is represented by frwi. With the above notation, the multiclass route flows should satisfy the flow conservation and nonnegativity constraints given by(1)∑r∈Rwfrwi=dwi,∀w∈W,i∈M,(2)frwi≥0,∀w∈W,r∈Rw,i∈M.Letxai denote the flow of user class i on link a and xa be the total flow on link a; we have the following equality linking the link flow and route flows of user class i:(3)xai=∑w∈W∑r∈Rwfrwiδar,∀a∈A,i∈M,where δar=1 if route r traverses link a and 0 otherwise.In addition, the total flow on linka can be expressed by the summation of link flows of all user classes, i.e.,(4)xa=∑i∈Mxai,∀a∈A.Denotecaxa, a∈A as the link cost function and caxai≜cai as the link travel cost of user class i. Assume that caxa is nonnegative, twice continuously differentiable, strictly increasing, and convex with respect to xa. Clearly, for any link in the network, its travel cost is the same for all classes of travelers, i.e.,(5)ca1=ca2=⋯=cam=ca,∀a∈A.The route cost of user classi, denoted by prwi, r∈Rw, w∈W, can be expressed as follows:(6)prwi=∑a∈Acaiδar,∀a∈A.LetMt⊆M be the set of class indices of travelers whose inertias at day t are represented by 1, i.e., the set of class indices of travelers who are willing to evaluate and reconsider their route choice. It follows that Mt is a nonempty subset of M=1,2,…,m, i.e., Mt⊂M.In order to facilitate the presentation of related formulations, for a particular classi, we introduce the class-specific link flow vector xi and class-specific link cost vector ci, which are denoted by(7)xi=x1i,x2i,…,xAiT,ci=c1i,c2i,…,cAiT.Based on the above class-specific flow variable, the day-to-day dynamic model with heterogeneous travel inertia is proposed as follows:(8)xit+1−xit=ltyit−xit,i∈Mt,xit+1=xit,i∉Mt,where xit denotes the link flow of user class i on day t, yit represents the target link flow of user class i for the next day (which is determined on day t when travelers finish their trip), lt∈0,1 indicates the flow changing rate, and xit+1 is the actual link flow of user class i on day t+1. The upper equation in equation (8) implies that if travelers of class i are willing to reconsider their routes on day t (i.e., i∈Mt), the link flows of these travelers will move from the current flow xit on day t to a future flow xit+1 on day t+1 with a flow changing direction yit−xit and a flow changing rate lit. On the contrary, the lower equation in equation (8) suggests that if travelers of class i are reluctant to reconsider their routes on day t (i.e., i∉Mt), the link flows of this user class will remain unchanged on day t+1 because they will use the same routes on day t+1.The determination of the target flowyit in equation (8) adopts the approach in He et al. [29]. Specifically, yit is obtained by solving the following cost minimization problem given the current link flow xt:(9)minyi∈ΩicixtTyi+Diyi,xit,∀i∈Mt,where Ωi has the form of(10)Ωi=xixai=∑w∈W∑r∈Rwfrwiδar,∀a∈A;∑r∈Rwfrwi=dwi,frwi≥0,∀w∈W,r∈Rw,and Diyi,xit is a function that measures the distance between the target flow yi and the current flow xit of class i. The target flow yit has an interesting behavioral interpretation. It means when travelers seek to minimize their travel costs, they are reluctant to make significant changes and hence tend to form a flow that is closest to the current flow xit.Clearly,Diyi,xit is a function of two vector variables conditioned on the 2nd variable xit being known. In this study, we denote ∇1Diyi,xit as the gradient of Diyi,xit with respect to the 1st vector variable. As is indicated in He et al. [29], in order for the day-to-day dynamic model to be well defined, the following assumptions on Diyi,xit should be made:Assumption 1.
D
i
y
i
,
x
i
t is nonnegative and satisfies ∇1Diyi,xit=0 if and only if yi=xit.Assumption 2.
D
i
y
i
,
x
i
t is continuously differentiable and strongly convex on Ωi for every fixed xit. i.e.,(11)∇1Diyi,xit−∇1Dizi,xitTyi−zi≥mDiyi−zi2,∀yi∈Ωi,zi∈Ωi,i∈M,where mDi is a bounded modulus of the strongly convex function Di.
The above two assumptions have significant implications. As is discussed in He et al. [29], Assumption 1 implies that the distance function Diyi,xit becomes unnecessary if and only if travelers of class i do not have any incentive to reconsider their routes. Assumption 2 ensures that the solution to the cost minimization problem (9) is unique, which means the target flow can be reasonably predicted. Both assumptions are widely adopted in the literature.
Furthermore, we make an additional assumption on Lipschitz continuity of the class-specific link cost functioncix. This assumption is crucial to the convergence analysis of the trial-and-error congestion pricing method that will be discussed in Section 4.Assumption 3.
The class-specific link cost functioncix is Lipschitz continuous on Ω, that is,(12)cix−ciy≤Lcix−y,∀x,y∈Ω,i∈M,where Lci is a bounded modulus of the link cost function cix.
Assumption 3 can be fulfilled in common cases. In fact, if the link travel cost functioncaxa takes the following widely used BPR (Bureau of Public Roads, 1964) function form(13)caxa=ca01+βxaCan,where Ca and ca0 are the capacity and free-flow travel time of link and a, β, and n are deterministic parameters, then it is easy to verify that Assumption 3 holds.


## 3. A Trial-and-Error Congestion Pricing Method for the Inertia-Based Day-to-Day Dynamic Model

In this section, we first discuss the multiclass system optimum problem and some relevant concepts, and then propose a trial-and-error congestion pricing method for day-to-day dynamic network flows which takes into account the heterogeneous inertia patterns of travelers.


### 3.1. Multiclass System Optimum, Multiclass User Equilibrium, and Marginal-Cost Pricing on Networks

The multiclass system optimum problem aims at minimizing the total travel cost spent in the network subject to the flow conservation conditions. This problem can be formulated as follows [36]:[MC-SO](14)minx∈ΩZ1x=∑a∈Acaxaxa,where Ω has the form of(15)Ω=x=⋯,xai,…Txaisatisfies1,2,3,and4.Letxa∗, ∀a∈A be the optimal solution to [MC-SO]. Note that the travel cost for any link in the network is the same for all classes of travelers (cf. equation (5)); then, the first-order optimality conditions of [MC-SO] yield the following relationship:(16)∑a∈Acaxa∗+xa∗ca′xa∗δar==μwi,iffrwi>0,≥μwi,iffrwi=0,∀r∈Rw,w∈W,i∈M,where μwi is the Lagrange multiplier associated with constraint (1).If we define(17)c˜axa∗=caxa∗+xa∗ca′xa∗,a∈A,then c˜axa∗ can be regarded as a generalized link travel cost function on link a, which involves the true travel cost caxa∗ and an additional cost term xa∗ca′xa∗. In the literature, xa∗ca′xa∗ is referred to as the marginal-cost toll, which can be interpreted as the marginal contribution of an additional user on link a to the total link travel cost.Therefore, equation (16) can be simplified to(18)p˜rwi==μwi,iffrwi>0,≥μwi,iffrwi=0,∀r∈Rw,w∈W,i∈M,where p˜rwi≜∑a∈Ac˜axa∗δar,a∈A is the generalized route travel cost of OD pair w for travelers of class i.From equation (18), we know that, at system optimum, for any class i∈M, all used routes have the same generalized travel costs. This means if a marginal-cost toll xa∗ca′xa∗ is charged on each link, the first-order optimality conditions of [MC-SO] are consistent with the definition of the multiclass user equilibrium principle [36, 37].On the contrary, for any given link toll patternγa,∀a∈A, the equilibrium link flow pattern can be acquired by solving the following multiclass-tolled user equilibrium problem [34, 38]:[MC-TUE](19)minx∈Ω∑a∈A∫0xacas+γads.The link toll pattern in equation (19) can take different forms. A typical form is to let γa=xa∗ca′xa∗, where xa∗, a∈A is the optimal solution to the multiclass system optimum problem (14). In this case, it is easy to verify that [MC-SO] and [MC-TUE] coincide with each other. This implies that if there are different classes of travelers with heterogeneous inertia patterns, the corresponding multiclass system optimum problem can be supported as a multiclass user equilibrium problem by charging a marginal-toll xa∗ca′xa∗ on each link. Note that these tolls are identical for all classes of travelers, which means they can be efficiently implemented without considering travelers’ inertia patterns.Another form of the choice ofγak is to let γak=xakca′xak, where xak is any iterative point on Ω. We will see in Section 3.2 that the trial-and-error congestion pricing method is designed by employing γak in this form.


### 3.2. The Trial-and-Error Congestion Pricing Method with Day-to-Day Flow Dynamics

As discussed above, in order to obtain the optimal link tolls, we need to solve problem (14), which requires the demand for each OD pair as its input. However, existing origin-destination survey or data collection technology is not able to evaluate the OD demand precisely [39–42]. To deal with this issue, Yang et al. [11] developed a trial-and-error congestion pricing method to find the system optimal link flows and link tolls. This method does not need any knowledge of the OD demand. What is required is to observe the resultant equilibrium network flow after each trial of link toll pattern. However, in reality, it takes a long time for travelers to learn the traffic conditions and evolve to such an equilibrium state. If the planner chooses to observe the traffic flow just a short time after charging the link toll, the observed network flow may not be in equilibrium. In such a case, the convergence of the trial-and-error congestion pricing method is undetermined. Therefore, it is critical to investigate under what circumstances the trial-and-error congestion pricing method can still be implemented without requiring the observed link flows to be in equilibrium.Fortunately, if psychological inertia is considered in travelers’ day-to-day flow adjustment process, it can be shown that the aforementioned trial-and-error congestion pricing method still converges to system optimum, even if disequilibrium link flows are observed and used to update the interim congestion tolls. In what follows, we will elaborate on this trial-and-error method.Given a set of trial link flowsxak,∀a∈A, assume that a marginal-cost toll pattern xakca′xak,∀a∈A is charged at someday, called a “trial” day, and kept constant until the next trial. Let γik denote the class-specific toll pattern for user class i. Clearly, we have(20)γ1k=γ2k=⋯=γmk=x1kc1′x1k,x2kc2′x2k,…,xAkcA′xAkT,∀i∈M.During each intertrial period, the network flow evolves according to the inertia-based day-to-day dynamic model that is presented in Section2. Note that in this situation, the toll xakca′xak is regarded by travelers as an additional travel cost on each link, and the flow adjustment process (8) and (9) is hereby altered as(21)xit+1−xit=ltyit−xit,i∈Mt,xit+1=xit,i∉Mt.Here,yit is the target flow of class i at each day during the intertrial period under the toll pattern γik, and yit can be acquired by solving the following tolled cost minimization problem:(22)minyi∈Ωicixt+γikTyi+Diyi,xit,∀i∈Mt.The above inertia-based day-to-day flow adjustment process (21) and (22) evolves over an intertrial period of Δk days. At the end of this period, the disequilibrium link flows are observed, and the trial link flows are then updated according to some criterion. This procedure is repeated until system optimum flow is achieved.We would like to emphasize that from a mathematical point of view, the solution to equation (22) requires the travel demand and inertia patterns as its inputs. However, in practice, the flow adjustment process (21) and (22) is inherently determined by travelers on the network. Therefore, these inputs do not need to be known by the practitioner. The practitioner only needs to observe the resultant link flows at the end of the intertrial period, and then decide the marginal-cost link tolls for the next trial. The detailed step of the trial-and-error congestion pricing method with inertia-based day-to-day flow adjustment process is presented as in Algorithm 1:Algorithm 1:
Step 0 (initialization). Letxa0,∀a∈A be an initial set of trial link flows, and Δ¯ be the upper bound of the intertrial period. Set k=0.
Step 1 (impose link tolls). For each linka∈A, implement the marginal-cost toll γak by: γak=xakca′xak,∀a∈A.
Step 2 (observe link flows). After an intertrial period ofΔk (Δk≤Δ¯) days, observe the resultant link flows following the inertia-based day-to-day flow adjustment process (21) and (22). Let x¯ak,a∈A denote the set of observed link flows.
Step 3 (check convergence). Ifx¯k−xk/xk<ε, then stop; otherwise, continue with Step 4.
Step 4 (update the trial link flows). Setxak+1=xak+βkx¯ak−xak,a∈A, where βk≥0 is a step size that satisfies the following exact line search rule: βk=argminxk+βx¯k−xk∈ΩZ1xk+βx¯k−xk.
Setk=k+1 and go to Step 1.An essential feature of the proposed trial-and-error method is that it allows the trial tolls to be updated at irregular time intervals. This is different from the method used in Ye et al. [34], in which the tolls are adjusted on a given regular basis, i.e., daily or weekly. Evidently, updating tolls at irregular time intervals offers more options and flexibility for practical implementations. It is also worth to note that the upper bound Δ¯ that imposed on the intertrial period is a necessary condition for the convergence of the trial-and-error congestion method (cf. Proposition 6 in Section 4). However, from a practical point of view, this is not a restrictive condition. By choosing Δ¯ large enough, most intertrial periods that are met in reality can satisfy this condition.


## 3.1. Multiclass System Optimum, Multiclass User Equilibrium, and Marginal-Cost Pricing on Networks

The multiclass system optimum problem aims at minimizing the total travel cost spent in the network subject to the flow conservation conditions. This problem can be formulated as follows [36]:[MC-SO](14)minx∈ΩZ1x=∑a∈Acaxaxa,where Ω has the form of(15)Ω=x=⋯,xai,…Txaisatisfies1,2,3,and4.Letxa∗, ∀a∈A be the optimal solution to [MC-SO]. Note that the travel cost for any link in the network is the same for all classes of travelers (cf. equation (5)); then, the first-order optimality conditions of [MC-SO] yield the following relationship:(16)∑a∈Acaxa∗+xa∗ca′xa∗δar==μwi,iffrwi>0,≥μwi,iffrwi=0,∀r∈Rw,w∈W,i∈M,where μwi is the Lagrange multiplier associated with constraint (1).If we define(17)c˜axa∗=caxa∗+xa∗ca′xa∗,a∈A,then c˜axa∗ can be regarded as a generalized link travel cost function on link a, which involves the true travel cost caxa∗ and an additional cost term xa∗ca′xa∗. In the literature, xa∗ca′xa∗ is referred to as the marginal-cost toll, which can be interpreted as the marginal contribution of an additional user on link a to the total link travel cost.Therefore, equation (16) can be simplified to(18)p˜rwi==μwi,iffrwi>0,≥μwi,iffrwi=0,∀r∈Rw,w∈W,i∈M,where p˜rwi≜∑a∈Ac˜axa∗δar,a∈A is the generalized route travel cost of OD pair w for travelers of class i.From equation (18), we know that, at system optimum, for any class i∈M, all used routes have the same generalized travel costs. This means if a marginal-cost toll xa∗ca′xa∗ is charged on each link, the first-order optimality conditions of [MC-SO] are consistent with the definition of the multiclass user equilibrium principle [36, 37].On the contrary, for any given link toll patternγa,∀a∈A, the equilibrium link flow pattern can be acquired by solving the following multiclass-tolled user equilibrium problem [34, 38]:[MC-TUE](19)minx∈Ω∑a∈A∫0xacas+γads.The link toll pattern in equation (19) can take different forms. A typical form is to let γa=xa∗ca′xa∗, where xa∗, a∈A is the optimal solution to the multiclass system optimum problem (14). In this case, it is easy to verify that [MC-SO] and [MC-TUE] coincide with each other. This implies that if there are different classes of travelers with heterogeneous inertia patterns, the corresponding multiclass system optimum problem can be supported as a multiclass user equilibrium problem by charging a marginal-toll xa∗ca′xa∗ on each link. Note that these tolls are identical for all classes of travelers, which means they can be efficiently implemented without considering travelers’ inertia patterns.Another form of the choice ofγak is to let γak=xakca′xak, where xak is any iterative point on Ω. We will see in Section 3.2 that the trial-and-error congestion pricing method is designed by employing γak in this form.


## 3.2. The Trial-and-Error Congestion Pricing Method with Day-to-Day Flow Dynamics

As discussed above, in order to obtain the optimal link tolls, we need to solve problem (14), which requires the demand for each OD pair as its input. However, existing origin-destination survey or data collection technology is not able to evaluate the OD demand precisely [39–42]. To deal with this issue, Yang et al. [11] developed a trial-and-error congestion pricing method to find the system optimal link flows and link tolls. This method does not need any knowledge of the OD demand. What is required is to observe the resultant equilibrium network flow after each trial of link toll pattern. However, in reality, it takes a long time for travelers to learn the traffic conditions and evolve to such an equilibrium state. If the planner chooses to observe the traffic flow just a short time after charging the link toll, the observed network flow may not be in equilibrium. In such a case, the convergence of the trial-and-error congestion pricing method is undetermined. Therefore, it is critical to investigate under what circumstances the trial-and-error congestion pricing method can still be implemented without requiring the observed link flows to be in equilibrium.Fortunately, if psychological inertia is considered in travelers’ day-to-day flow adjustment process, it can be shown that the aforementioned trial-and-error congestion pricing method still converges to system optimum, even if disequilibrium link flows are observed and used to update the interim congestion tolls. In what follows, we will elaborate on this trial-and-error method.Given a set of trial link flowsxak,∀a∈A, assume that a marginal-cost toll pattern xakca′xak,∀a∈A is charged at someday, called a “trial” day, and kept constant until the next trial. Let γik denote the class-specific toll pattern for user class i. Clearly, we have(20)γ1k=γ2k=⋯=γmk=x1kc1′x1k,x2kc2′x2k,…,xAkcA′xAkT,∀i∈M.During each intertrial period, the network flow evolves according to the inertia-based day-to-day dynamic model that is presented in Section2. Note that in this situation, the toll xakca′xak is regarded by travelers as an additional travel cost on each link, and the flow adjustment process (8) and (9) is hereby altered as(21)xit+1−xit=ltyit−xit,i∈Mt,xit+1=xit,i∉Mt.Here,yit is the target flow of class i at each day during the intertrial period under the toll pattern γik, and yit can be acquired by solving the following tolled cost minimization problem:(22)minyi∈Ωicixt+γikTyi+Diyi,xit,∀i∈Mt.The above inertia-based day-to-day flow adjustment process (21) and (22) evolves over an intertrial period of Δk days. At the end of this period, the disequilibrium link flows are observed, and the trial link flows are then updated according to some criterion. This procedure is repeated until system optimum flow is achieved.We would like to emphasize that from a mathematical point of view, the solution to equation (22) requires the travel demand and inertia patterns as its inputs. However, in practice, the flow adjustment process (21) and (22) is inherently determined by travelers on the network. Therefore, these inputs do not need to be known by the practitioner. The practitioner only needs to observe the resultant link flows at the end of the intertrial period, and then decide the marginal-cost link tolls for the next trial. The detailed step of the trial-and-error congestion pricing method with inertia-based day-to-day flow adjustment process is presented as in Algorithm 1:Algorithm 1:
Step 0 (initialization). Letxa0,∀a∈A be an initial set of trial link flows, and Δ¯ be the upper bound of the intertrial period. Set k=0.
Step 1 (impose link tolls). For each linka∈A, implement the marginal-cost toll γak by: γak=xakca′xak,∀a∈A.
Step 2 (observe link flows). After an intertrial period ofΔk (Δk≤Δ¯) days, observe the resultant link flows following the inertia-based day-to-day flow adjustment process (21) and (22). Let x¯ak,a∈A denote the set of observed link flows.
Step 3 (check convergence). Ifx¯k−xk/xk<ε, then stop; otherwise, continue with Step 4.
Step 4 (update the trial link flows). Setxak+1=xak+βkx¯ak−xak,a∈A, where βk≥0 is a step size that satisfies the following exact line search rule: βk=argminxk+βx¯k−xk∈ΩZ1xk+βx¯k−xk.
Setk=k+1 and go to Step 1.An essential feature of the proposed trial-and-error method is that it allows the trial tolls to be updated at irregular time intervals. This is different from the method used in Ye et al. [34], in which the tolls are adjusted on a given regular basis, i.e., daily or weekly. Evidently, updating tolls at irregular time intervals offers more options and flexibility for practical implementations. It is also worth to note that the upper bound Δ¯ that imposed on the intertrial period is a necessary condition for the convergence of the trial-and-error congestion method (cf. Proposition 6 in Section 4). However, from a practical point of view, this is not a restrictive condition. By choosing Δ¯ large enough, most intertrial periods that are met in reality can satisfy this condition.


## 4. The Convergence of the Trial-and-Error Congestion Pricing Method

In this section, we demonstrate the convergence of the trial-and-error congestion pricing method that is proposed in Section3. Throughout this section, it is assumed that Assumptions 1–3 hold. First, we will show that the trial-and-error congestion pricing method with inertia-based day-to-day flow adjustment process can be interpreted as solving the multiclass system optimum problem (14) through the truncated cost approximation method ([35], Chapter 5.3). The overall procedure of the truncated cost approximation method consists of two phases: the outer iteration phase applies the cost approximation framework to [MC-SO] and creates a cost approximation subproblem. The inner level iteration phase uses an essential cyclic-type Gauss–Seidel decomposition method to solve the subproblem inexactly.The following proposition is related to the outer iteration phase of the truncated cost approximation method.Proposition 1.
The trial-and-error congestion pricing method that is given in Algorithm1 can be regarded as solving the multiclass system optimum problem (14) with the cost approximation framework, in which the approximation function is specified by(23)Φkx=∑a∈Acaxaxa+∑a∈Axakca′xakxa−∑a∈A∫0xasca′sds.Proof.
The multiclass system optimum problem is
[MC-SO](24)minx∈ΩZ1x=∑a∈Acaxaxa.
At iterationk, we introduce a function Φkx:Ω⟼R, convex and continuously differentiable on Ω, and express the objective function of [MC-SO] as(25)Z1x=Φkx+Z1x−Φkx.
The second term in equation (25) can be seen as expressing the error when replacing the original objective Z1x by the function Φkx. The idea of the cost approximation method is to take this error into account by a linearization of the error term [35]. Replacing the second term in equation (25) with a first-order expansion around xk, the cost approximation subproblem solved in iteration k then is
[CA-SUB(k)](26)minx∈ΩZ1kx,where(27)Z1kx=Φkx+∇xZ1xk−∇xΦkxkTx−xk.
By choosing the functionΦkx in different forms, various methods can be obtained [35]. In order to coincide with the trial-and-error procedure investigated in this research, we choose(28)Φkx=Z1kx+∑a∈Axakca′xakxa−∑a∈A∫0xasca′sds=Z1kx+φkx.
Obviously,(29)∂φkx∂xa=∑a∈Axakca′xak−∑a∈Axaca′xa.
Then, it follows from equations (28) and (29) that(30)∇xZ1xk−∇xΦkxk=0.
As a result of equations (27) and (30), the objective function of [CA-SUB(k)] reduces to(31)Z1kx=Φkx=∑a∈Acaxaxa+∑a∈Axakca′xakxa−∑a∈A∫0xasca′sds=∑a∈A∫0xacas+sca′sds+∑a∈A∫0xaxakca′xakds−∑a∈A∫0xasca′sds=∑a∈A∫0xacas+xakca′xakds.
Hence [CA-SUB(k)] becomes(32)minx∈ΩZ1kx=∑a∈A∫0xacas+γakds,where γak=xakca′xak is the marginal-cost link toll evaluated at xak.
Comparing equation (32) with equation (19), it can be seen that [CA-SUB(k)] is, in essence, a multiclass-tolled user equilibrium problem. In this case, the toll pattern is given by a marginal-cost formulation that is evaluated at xak. If an appropriate method is employed, then the solution procedure of [CA-SUB(k)] can be viewed as simulating travelers’ day-to-day flow evolution process under the condition that γak is charged on each link (cf. Steps 1 and 2 in Algorithm 1). Assume that Δk inner iterations are performed to solve [CA-SUB(k)]. At the end of this process, the iterative point x¯k can thus be regarded as the link flow pattern that is observed after an intertrial period of Δk days (cf. Step 2 in Algorithm 1).
From Theorem 2.14 in [35], it is known that if the vector x¯k−xk is nonzero, it defines a descent direction with respect to the objective function Z1x. If the step size βk is chosen according to the exact line search rule (26), then the new iteration point can be given by(33)xk+1=xk+βkx¯k−xk,which coincides with Step 4 in Algorithm 1. In view of the above discussions, the equivalence between the trial-and-error congestion pricing method and the cost approximation framework is established.Proposition 2 below concerns the solution procedure of [CA-SUB(k)]. It corresponds to the inner iteration phase of the truncated cost approximation method.Proposition 2.
The inertia-based day-to-day flow adjustment process (21) and (22) for Step 2 of Algorithm 1 can be regarded as the procedure of solving the cost approximation subproblem (32) through an essential cyclic-type Gauss–Seidel decomposition method with constant step size.Proof.
Given an arbitrary set of link toll patternγak,∀a∈A, the cost approximation subproblem (32) is
[CA-SUB(k)](34)minx∈ΩZ1kx=∑a∈A∫0xacas+γakds.
Letxt be an iterative point for [CA-SUB(k)]. If we approximate Z1kx with a first-order Taylor series around xt and regulate the resultant series through the addition of a strongly convex function Dy,xt, the following subproblem can be obtained:
[CA-SUB(k)-GS-SUB(t)](35)miny∈Ωcxt+γkTy+Dy,xt,where c=c1T,c2T,…,cmTT and γ=γ1T,γ2T,…,γmTT are the vector of all class-specific link travel costs and link tolls.
Note that the feasible setΩ in equation (34) can be expressed as a Cartesian product of Ωi in equation (10), i.e.,(36)Ω=∏i=1mΩi.
If the functionDy,xt has the form(37)Dy,xt=∑i=1mDiyi,xit,then equation (35) can be decomposed into the following m independent problems:
[CA-SUB(k)-GS-SUB(t)-(i)](38)minyi∈Ωicixt+γikTyi+Diyi,xit.
From Chapter 8 in [35], a fundamental feature of the essential cyclic-type Gauss–Seidel decomposition method is that it allows only part of the above m problems to be solved at each inner iteration step. Clearly, at inner iteration t, if we gather equation (38) for all i∈Mt, then we recover the tolled cost minimization problem (22). Let yit be an optimal solution to [CA-SUB(k)-GS-SUB(t)-(i)] for all i∈Mt and yit=xit for all i∉Mt. By aggregating all yit that belongs or not belongs to Mt, the optimal solution yt to [CA-SUB(k)-GS-SUB(t)-(i)] can be obtained. Let yt−xt be the search direction for the inner iteration phase. By choosing a constant step size lt in this direction, the new iteration point would be(39)xt+1=xt+ltyt−xt.
Clearly, equation (39) can be decomposed into the following disaggregated form:(40)xit+1−xit=ltyit−xit,i∈Mt,xit+1=xit,i∉Mt,which is the same as the flow adjustment process presented in equation (21).
From the discussions above, we can conclude that the inertia-based day-to-day flow adjustment process (21) and (22) is equivalent to solving [CA-SUB(k)] through an essential cyclic-type Gauss–Seidel decomposition method.It is worth to note that in Step 2 of Algorithm1, the interval Δk between two consecutive trials is bounded above. This means only a finite number of inner iterations is performed to solve [CA-SUB(k)]. Hence, [CA-SUB(k)] cannot be solved exactly, which implies that the observed link flows are not in equilibrium. As is indicated in [35], the truncated cost approximation method is able to deal with this issue. The idea of this method is to bound the work performed on [CA-SUB(k)] by limiting the number of inner iterations, which introduces a trade-off between the computational effort spent on the subproblem and the quality of the generated search direction. However, convergence of the truncated cost approximation method relies on the algorithmic map that is used to solve [CA-SUB(k)]. Next, we will investigate the properties of this algorithmic map.Letxt∈Ω be an iterative point for [CA-SUB(k)] and Yxt be the solution set to [CA-SUB(k)-GS-SUB(t)]. Then, the target flow in equation (39) satisfies yt∈Yxt, and the search direction for the inner iteration phase can be expressed as dt=yt−xt.Denote(41)Bx=x,d,as the direction finding map and(42)Cx,d=lt,as the step size map.Clearly, the algorithmic mapA for the essential cyclic-type Gauss–Seidel decomposition method is the composition of B and C, i.e.,(43)A=C∘B.To prove the convergence of the truncated cost approximation method, we will apply Theorem 5.17 in [35]. To fulfill the assumptions of this theorem, we need to show the algorithmic map for the essential cyclic-type Gauss–Seidel decomposition method satisfies the properties of fixed point, descent, closedness, and finite termination. In what follows, we will verify these properties theoretically.Proposition 3 below provides a fixed point characterization of the optimal solution points to [CA-SUB(k)].Proposition 3.
Letxt∈Ω be an iterative point of the essential cyclic-type Gauss–Seidel decomposition method for the inner iteration phase. Then xt is an optimal solution to [CA-SUB(k)] if and only if it solves [CA-SUB(k)-GS-SUB(t)].Proof.
We first prove the “only if” part. Assuming thatxt is an optimal solution to [CA-SUB(k)-GS-SUB(t)], by Theorem 3.4.3 in [43], the following variational inequality holds:(44)cxt+γk+∇1Dxt,xtTz−xt≥0,∀z∈Ω.
In view of equations (36) and (37), this variational inequality can be decomposed into(45)cixt+γik+∇1Dixit,xitTzi−xit≥0,∀zi∈Ωi,∀i∈M.
By Assumption 1,∇1Dixit,xit=0, then it follows that(46)cixt+γikTzi−xit≥0,∀zi∈Ωi,∀i∈M.
Adding these inequalities over alli∈M, we have(47)cxt+γkTz−xt≥0,∀z∈Ω,which, by Theorem 3.4.3 in [43] and the convexity of [CA-SUB(k)], shows that xt is an optimal solution to [CA-SUB(k)].
By reversing the above proof, it is straightforward to establish the “if” part. Therefore, Proposition 3 holds.The following proposition establishes the descent property of the algorithmic mapA.Proposition 4.
LetmD=mini∈MmDi be the smallest modulus defined in equation (11) and Lc=maxi∈MtLci be the largest modulus defined in equation (12). If the step size lt belongs to a compact subset of 0,min1,2mD/Lc, then the objective function Z1kx for [CA-SUB(k)] is a descent function with respect to the map A.Proof.
The optimality conditions for [CA-SUB(k)-GS-SUB(t)-(i)] is(48)cixt+γik+∇1Diyit,xitTzi−yit≥0,∀zi∈Ωi,∀i∈Mt.
By substitutingzi=xit in the above equation, we obtain(49)cixt+γikTyit−xit≤−∇1Diyit,xitTyit−xit,∀i∈Mt.
Assumption 2 suggests that(50)∇1Diyi,xit−∇1Dizi,xitTyi−zi≥mDiyi−zi2,∀yi∈Ωi,zi∈Ωi.
By substitutingyi=yit and zi=xit in equation (50) and using Assumption 1, we have(51)∇1Diyit,xitTyit−xit=∇1Diyit,xit−∇1Dixit,xitTyit−xit≥mDiyit−xit2.
In view of equations (49) and (51), we get(52)cixt+γikTyit−xit≤−mDiyit−xit2,∀i∈Mt.
On the contrary, by applying Taylor’s formula, the difference of objective values of [CA-SUB(k)] in equation (32) between inner iteration t+1 and t can be expressed as(53)Z1kxt+1−Z1kxt=∫0ltyt−xtT∇Z1kxt+syt−xtds=∫0lt∑i∈Mtyit−xitT∇iZ1kxt+syt−xtds=∑i∈Mt∫0ltyit−xitT∇iZ1kxt+syt−xtds=∑i∈Mt∫0ltyit−xitTcixt+syt−xt+γikds.
Rearranging terms in equation (53) and taking norms, we have(54)Z1kxt+1−Z1kxt≤∑i∈Mt∫0ltyit−xitTcixt+γikds+∑i∈Mt∫0ltyit−xitcixt+syt−xt−cixtds.
SincemD=mini∈MmDi and Lc=maxi∈MtLci, it follows from equation (52) and Assumption 3 that(55)Z1kxt+1−Z1kxt≤−lt∑i∈MtmDyit−xit2+∑i∈Mtyit−xit∫0ltLcyit−xitsds=∑i∈Mt−mDlt+Lc2lt2Tyit−xit2.
Equation (21) implies that(56)yit−xit=0,∀i∉Mt.
Hence, equation (55) can be rewritten as(57)Z1kxt+1−Z1kxt≤∑i∈Mt−mDlt+Lc2lt2Tyt−xt2.
Sincelt belongs to a compact subset of 0,min1,2mD/Lc, we have(58)∑i∈Mt−mDlt+Lc2lt2Tyt−xt2≤0,which, together with (57), implies that Z1kxt is monotone decreasing.Proposition 5 below proves the closedness of the algorithmic mapA.Proposition 5.
The algorithmic mapA for the essential cyclic-type Gauss–Seidel decomposition method is closed on Ω.Proof.
Letxt∈Ω be an iterative point of the essential cyclic-type Gauss–Seidel decomposition method and Yixt be the solution set to [CA-SUB(k)-GS-SUB(t)-(i)]. We first show that the map Yix is closed on Ω. For an arbitrary x∈Ω, assume that xt⟶x, yit⟶yi, and yit∈Yixt.
Since [CA-SUB(k)-GS-SUB(t)-(i)] is convex, its first-order conditions are equivalent to the following variational inequality (Theorem 3.4.3 in [43]):(59)cixt+γik+∇1Diyit,xitTzi−yit≥0,∀zi∈Ωi,∀i∈Mt.
Using Proposition 1.3 in [35], this variational inequality can be equivalently written as(60)−cixt−γik−∇1Diyit,xit∈NΩiyit,∀zi∈Ωi,∀i∈Mt,where NΩiyit=ziziTxi−yit≤0,∀xi∈Ωi,yit∈Ωi∅,yit∉Ωi is the normal cone operator for the set Ωi.
Then, it follows from Theorem 24.4 in [44] and the continuity of cixt and ∇1Diyit,xit that(61)−cix−γik−∇1Diyi,xi∈NΩiyi,∀i∈M.
By the convexity of [CA-SUB(k)-GS-SUB(t)-(i)], Theorem 3.4.3 in [43] implies that(62)yi∈Yix.
Hence, the mapYix is closed on Ω.
Since the mapYx is the Cartesian product of Yix, it follows from Theorem 4.5 in [45] that Yx is also closed on Ω.
We are then in a position to show that the mapA is closed.
Let(63)G≜x,yy∈Yx,denote the graph of the map Yx.
It is clear that the graph of the mapBx in equation (41) is obtained from G through an affine transformation. According to Theorem 3 in Chapter 6 of [46], Bx is also closed on Ω. Evidently, the step size map Cx,d in equation (42) is, in essence, a continuous function. Applying Corollary 4.2.2 in [47], we can conclude that the composition map A=C∘B in equation (43) is closed on Ω.Up to now, all the assumptions that are required by Theorem 5.17 in [35] are established. We can invoke this theorem to prove the convergence of the trial-and-error congestion pricing method.Proposition 6.
The trial-and-error congestion pricing method with inertia-based day-to-day flow adjustment process can drive the aggregated link flows to system optimum.Proof.
By Propositions 1 and 2, the trial-and-error congestion pricing method with inertia-based day-to-day flow adjustment process can be interpreted as solving [MC-SO] through the truncated cost approximation method. Propositions 3–5 establish that the algorithmic map for the inner iteration phase of the truncated cost approximation method has fixed point, descent, and closedness properties. The upper boundΔ¯ on the intertrial period Δk implies that only a finite number of inner iterations are performed to solve [CA-SUB(k)], which verifies the finite termination property. Then, it follows from Theorem 5.17 in [35] that every limit point of the class-specific link flow sequence xt generated by the truncated cost approximation method is an optimal solution to [MC-SO]. Evidently, this optimal solution is unique in terms of the aggregated link flows. Therefore, applying Theorem 14.1.4 in [48], we can conclude that the sequence of the aggregated link flows generated by the trial-and-error congestion pricing method convergences to a steady state which is system optimum.


## 5. Numerical Experiments

This section examines the convergence performance of the proposed trial-and-error congestion pricing method under day-to-day flow dynamics incorporating travelers’ heterogeneous inertia patterns. The numerical experiments are conducted on two typical networks: The Hearn–Ramana network is adapted from [49]. It consists of 18 links, 8 nodes, and 4 OD pairs, as shown in Figure 2. The values in the parenthesis beside each link in Figure 2 represent the corresponding free-flow travel time and capacity. The Sioux Falls network is illustrated in Figure 3. It consists of 76 links, 24 nodes, and 528 OD pairs. This network is taken from [50].Figure 2
The Hearn–Ramana network.Figure 3
The Sioux Falls network.We consider four classes of travelers on both networks. The true but unknown demand for each class is, respectively, assumed to be 1/8, 3/8, 1/8, and 3/8 of the original demand. For both networks, the link travel cost function is expressed by equation (13) with β=0.15 and n=4. The distance function Diyi,xit in equation (22) is assumed to be a quadratic proximal function given by(64)Diyi,xit=yi−xit2,which offers a compromise between choosing the shortest route and being near to travelers’ current flow xit. It is easy to verify that Assumptions 1 and 2 are satisfied if Diyi,xit follows equation (64). The target flow for each class is determined by equations (22) and (64), and the flow changing rate in equation (21) is set to be 0.1. Based on the free-flow travel time, the class-specific OD demands are assigned to the shortest route to obtain the initial network condition.


### 5.1. Convergence Performance under Different Inertia Patterns

In order to explore the impact of different inertia patterns on the resultant flows and tolls under the proposed trial-and-error method, we consider the following two cases:Case 1.
The true but unknown inertia patterns for 4 classes of travelers are given by (1, 0, 0, 1, 0, 0, 1, 0, 0, 1, …), (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...), (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, …), and (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …), as depicted in Figure4.Figure 4
Inertia patterns for 4 classes of travelers in Case 1.Case 2.
The true but unknown inertia patterns for 4 classes of travelers are given by (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, …), (0, 1, 0, 0, 0, 1, 0, 0, 0, 1, …), (0, 0, 1, 0, 0, 0, 1, 0, 0, 0, …), and (0, 0, 0, 1, 0, 0, 0, 1, 0, 0, …), which are illustrated in Figure5.
The intertrial periodΔk for both cases is assumed to be 10 days. We first compare the resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Hearn–Ramana and Sioux Falls network. The results are presented in Tables 1 and 2. Due to space limitation, we only list the aggregated traffic flow on nine typical links in each table. It can be found that the resultant link flows and link tolls are almost identical in both cases. By substituting the aggregated link flows into equation (14), it is easy to verify that these flows do minimize the system cost for both networks. This validates the fact that if the flows on each link are treated as a whole, the optimal solution for the multiclass system optimum would be unique [36].
Figures6 and 7 display the evolution processes of aggregated flows on links 2–5 and 5–7 in Case 1 and Case 2 on the Hearn–Ramana network. By comparing the flow evolution on links 2–5 (or links 5–7), in both cases, we can see that the trajectories are different from each other. However, both of them evolve towards a unique link flow value. This phenomenon is similar to the numerical results presented in Ye et al. [34], in which distinct link flow evolution trajectories converge to the same equilibrium state under different parameter settings.
Figures8 and 9 illustrate the evolution processes of aggregated flows on links 9 and 10 and 15–19 in Case 1 and Case 2 on the Sioux Falls network. Similar to the results shown in Figures 6 and 7, the flows on both links of the Sioux Falls network can also evolve to a stable state which is system optimum. If we compare Figures 6 and 8 (or Figures 7 and 9) together, we find that it requires more trials for the flows on the Sioux Falls network to evolve to system optimum. This phenomenon may be attributed to the larger size and more congested network condition of the Sioux Falls network compared to the Hearn–Ramana network. It indeed needs a greater number of trials to drive its flows to system optimum.Figure 5
Inertia patterns for 4 classes of travelers in Case 2.Table 1
Resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Hearn–Ramana network.
Link
Link flows
Link
Link tolls
Case 1
Case 2
Case 1
Case 2
1–5
9.41
9.41
1–5
1.14
1.13
1–6
20.59
20.59
1–6
6.16
6.16
2–5
38.33
38.33
2–5
2.59
2.59
2–6
31.67
31.67
2–6
3.62
3.62
5–6
0.00
0.00
5–6
0.00
0.00
5–7
21.30
21.30
5–7
16.88
16.89
5–9
26.44
26.45
5–9
5.13
5.13
6–5
0.00
0.00
6–5
0.00
0.00
6–8
39.47
39.48
6–8
7.37
7.37Table 2
Resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Sioux Falls network.
Link
Link flows (×104)
Link
Link tolls
Case 1
Case 2
Case 1
Case 2
1–3
1.1240
1.1240
1–3
0.1277
0.1277
2–6
0.6620
0.6620
2–6
9.535
9.535
4–5
1.8732
1.8732
4–5
1.478
1.478
5–6
0.6995
0.6995
5–6
9.584
9.584
8–7
1.3225
1.3225
8–7
14.559
14.559
9–10
2.1765
2.1765
9–10
10.771
10.772
10–15
2.3361
2.3361
10–15
32.168
32.168
11–12
0.7325
0.7325
11–12
17.850
17.849
15–19
1.8557
1.8557
15–19
4.743
4.743Figure 6
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 1 on the Hearn–Ramana network (left).Figure 7
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 2 on the Hearn-Ramana network (right).Figure 8
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 1 on the Sioux Falls network (left).Figure 9
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 2 on the Sioux Falls network (right).


### 5.2. Convergence Performance under Different Intertrial Periods

To illustrate the effectiveness of the proposed trial-and-error method, in this section, we compare the performance of the classical trial-and-error method developed in Yang et al. [11] with the method proposed in this research. The two methods are termed as “exact method” and “inexact method,” respectively. Here, the exact method means the inner iteration phase (i.e., the subproblem [CA-SUB(k)]) of the truncated cost approximation method is solved exactly, which implies that after imposing each trial of link tolls, equilibrium link flows can be achieved and observed. Analogously, the inexact method means the inner iteration phase is solved inexactly, which suggests that the observed link flows are not in equilibrium. It is clear that the exact method requires a much longer intertrial period than the inexact method. In order to further evaluate the influence of different intertrial periods on the convergence speed of the inexact method, three forms of the inexact method with different intertrial periods are considered, i.e., Δ1k=5 days, Δ2k=15 days, and Δ3k=5+floork/10 days (floor⋅ is the round down function and k is the number of trials of link toll). Obviously, the lengths of Δ1k and Δ2k are fixed, whereas the length of Δ3k is dynamically changed according to the number of trials. We use the following convergence measure proposed by Leurent [51] to evaluate the performance of the trial-and-error congestion pricing method at different trial stages:(65)lnZkZ∗−1,where Zk is the objective value of [MC-SO] at the k-th trial and Z∗ is the minimum objective value of [MC-SO]. We will test both methods on the Hearn–Ramana network and the Sioux Falls network. In the numerical test, travelers’ inertia patterns are assumed to follow Case 1 introduced in Section 5.1.Figure10 shows the convergence performance of the exact and inexact method in terms of the number of trials on the Hearn–Ramana network. As can be observed in this figure, the inexact trial-and-error method can drive the network flow to system optimum no matter whether the intertrial period is variable (i.e., Δ3k=5+floork/10) or fixed (i.e., Δk=5 and Δk=15). This validates the theoretical results in Section 4 that the convergence of the proposed trial-and-error method can be achieved even if the tolls are updated at irregular time intervals. When comparing the convergence speed of the exact and inexact method, we can observe that at the early evolution stage, the convergence speed of the exact method and the inexact method with Δ2k=15 are similar, both of which are slightly higher than the inexact method with Δ1k=5 and Δ3k=5+floork/10. At the late evolution stage, the exact method converges faster than all the three forms of the inexact method. This means to achieve the same level of solution accuracy, the method with a longer intertrial period requires fewer trials. The reason for this phenomenon is that if the intertrial period is longer, travelers will have more time to learn the traffic conditions and adjust their route choice, so that the observed network flow at the end of each intertrial period becomes closer to the equilibrium state. Therefore, the generated search direction (cf. equation (33)) under longer intertrial period would be more effective in improving the convergence speed of the trial-and-error method.Figure 10
Convergence of the exact and inexact trial-and-error method in terms of number of trials on the Hearn–Ramana network (left).Figure11 depicts the convergence of the exact and inexact trial-and-error method in terms of the number of evolutionary days on the Hearn–Ramana network. We find from this figure that the performance of all the three forms of the inexact method is uniformly superior to the exact method. This is because in comparison with the exact method, although the inexact method consumes a little more trials to get to the same convergence tolerance (cf. Figure 10), it requires much less number of evolutionaryd days between any two consecutive trials. Therefore, the total number of evolutionary days for the inexact method will be greatly decreased. This explanation can also account for the phenomenon in Figure 10 that the performance of the inexact method with Δ1k=5 and Δ3k=5+floork/10 is similar and both of which outperform the inexact method with Δ2k=15.Figure 11
Convergence of the exact and inexact trial-and-error method in terms of number of evolutionary days on the Hearn–Ramana network (right).Figures12 and 13, respectively, depict the convergence of the exact and inexact method with respect to the number of trials and number of evolutionary days on the Sioux Falls network. Inspection of Figure 12 reveals that as far as the number of trials is concerned, the exact method is slightly faster than the inexact method with Δ2k=15, more faster than the inexact method with Δ1k=5 and Δ3k=5+floork/10. However, from Figure 13, it can be observed that all the three forms of the inexact method consume much less number of evolutionary days than the exact method, among which the inexact method with Δ1k=5 performs best. The two phenomena have already been observed in the performance analysis on the Hearn–Ramana network, and the reasons are similar. Therefore, in view of practical implementation, the selection of the trial-and-error congestion pricing method depends on the specific objective of a practitioner. If the purpose is to reduce the number of trials so as to minimize the inconvenience caused by the toll charge variation, then the exact method or the inexact method with a long interval is preferred. On the contrary, if the practitioner aims to reduce the implementation times so that system optimum can be achieved as soon as possible, then the inexact method with a short intertrial period is more attractive.Figure 12
Convergence of the exact and inexact trial-and-error method in terms of number of trials on the Sioux Falls network (left).Figure 13
Convergence of the exact and inexact trial-and-error method in terms of number of evolutionary days on the Sioux Falls network (right).


## 5.1. Convergence Performance under Different Inertia Patterns

In order to explore the impact of different inertia patterns on the resultant flows and tolls under the proposed trial-and-error method, we consider the following two cases:Case 1.
The true but unknown inertia patterns for 4 classes of travelers are given by (1, 0, 0, 1, 0, 0, 1, 0, 0, 1, …), (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...), (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, …), and (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …), as depicted in Figure4.Figure 4
Inertia patterns for 4 classes of travelers in Case 1.Case 2.
The true but unknown inertia patterns for 4 classes of travelers are given by (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, …), (0, 1, 0, 0, 0, 1, 0, 0, 0, 1, …), (0, 0, 1, 0, 0, 0, 1, 0, 0, 0, …), and (0, 0, 0, 1, 0, 0, 0, 1, 0, 0, …), which are illustrated in Figure5.
The intertrial periodΔk for both cases is assumed to be 10 days. We first compare the resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Hearn–Ramana and Sioux Falls network. The results are presented in Tables 1 and 2. Due to space limitation, we only list the aggregated traffic flow on nine typical links in each table. It can be found that the resultant link flows and link tolls are almost identical in both cases. By substituting the aggregated link flows into equation (14), it is easy to verify that these flows do minimize the system cost for both networks. This validates the fact that if the flows on each link are treated as a whole, the optimal solution for the multiclass system optimum would be unique [36].
Figures6 and 7 display the evolution processes of aggregated flows on links 2–5 and 5–7 in Case 1 and Case 2 on the Hearn–Ramana network. By comparing the flow evolution on links 2–5 (or links 5–7), in both cases, we can see that the trajectories are different from each other. However, both of them evolve towards a unique link flow value. This phenomenon is similar to the numerical results presented in Ye et al. [34], in which distinct link flow evolution trajectories converge to the same equilibrium state under different parameter settings.
Figures8 and 9 illustrate the evolution processes of aggregated flows on links 9 and 10 and 15–19 in Case 1 and Case 2 on the Sioux Falls network. Similar to the results shown in Figures 6 and 7, the flows on both links of the Sioux Falls network can also evolve to a stable state which is system optimum. If we compare Figures 6 and 8 (or Figures 7 and 9) together, we find that it requires more trials for the flows on the Sioux Falls network to evolve to system optimum. This phenomenon may be attributed to the larger size and more congested network condition of the Sioux Falls network compared to the Hearn–Ramana network. It indeed needs a greater number of trials to drive its flows to system optimum.Figure 5
Inertia patterns for 4 classes of travelers in Case 2.Table 1
Resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Hearn–Ramana network.
Link
Link flows
Link
Link tolls
Case 1
Case 2
Case 1
Case 2
1–5
9.41
9.41
1–5
1.14
1.13
1–6
20.59
20.59
1–6
6.16
6.16
2–5
38.33
38.33
2–5
2.59
2.59
2–6
31.67
31.67
2–6
3.62
3.62
5–6
0.00
0.00
5–6
0.00
0.00
5–7
21.30
21.30
5–7
16.88
16.89
5–9
26.44
26.45
5–9
5.13
5.13
6–5
0.00
0.00
6–5
0.00
0.00
6–8
39.47
39.48
6–8
7.37
7.37Table 2
Resultant link flows and link tolls generated by the trial-and-error method in Case 1 and Case 2 on the Sioux Falls network.
Link
Link flows (×104)
Link
Link tolls
Case 1
Case 2
Case 1
Case 2
1–3
1.1240
1.1240
1–3
0.1277
0.1277
2–6
0.6620
0.6620
2–6
9.535
9.535
4–5
1.8732
1.8732
4–5
1.478
1.478
5–6
0.6995
0.6995
5–6
9.584
9.584
8–7
1.3225
1.3225
8–7
14.559
14.559
9–10
2.1765
2.1765
9–10
10.771
10.772
10–15
2.3361
2.3361
10–15
32.168
32.168
11–12
0.7325
0.7325
11–12
17.850
17.849
15–19
1.8557
1.8557
15–19
4.743
4.743Figure 6
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 1 on the Hearn–Ramana network (left).Figure 7
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 2 on the Hearn-Ramana network (right).Figure 8
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 1 on the Sioux Falls network (left).Figure 9
Evolutionary trajectories of total flows on links 2–5 and 5–7 in Case 2 on the Sioux Falls network (right).


## 5.2. Convergence Performance under Different Intertrial Periods

To illustrate the effectiveness of the proposed trial-and-error method, in this section, we compare the performance of the classical trial-and-error method developed in Yang et al. [11] with the method proposed in this research. The two methods are termed as “exact method” and “inexact method,” respectively. Here, the exact method means the inner iteration phase (i.e., the subproblem [CA-SUB(k)]) of the truncated cost approximation method is solved exactly, which implies that after imposing each trial of link tolls, equilibrium link flows can be achieved and observed. Analogously, the inexact method means the inner iteration phase is solved inexactly, which suggests that the observed link flows are not in equilibrium. It is clear that the exact method requires a much longer intertrial period than the inexact method. In order to further evaluate the influence of different intertrial periods on the convergence speed of the inexact method, three forms of the inexact method with different intertrial periods are considered, i.e., Δ1k=5 days, Δ2k=15 days, and Δ3k=5+floork/10 days (floor⋅ is the round down function and k is the number of trials of link toll). Obviously, the lengths of Δ1k and Δ2k are fixed, whereas the length of Δ3k is dynamically changed according to the number of trials. We use the following convergence measure proposed by Leurent [51] to evaluate the performance of the trial-and-error congestion pricing method at different trial stages:(65)lnZkZ∗−1,where Zk is the objective value of [MC-SO] at the k-th trial and Z∗ is the minimum objective value of [MC-SO]. We will test both methods on the Hearn–Ramana network and the Sioux Falls network. In the numerical test, travelers’ inertia patterns are assumed to follow Case 1 introduced in Section 5.1.Figure10 shows the convergence performance of the exact and inexact method in terms of the number of trials on the Hearn–Ramana network. As can be observed in this figure, the inexact trial-and-error method can drive the network flow to system optimum no matter whether the intertrial period is variable (i.e., Δ3k=5+floork/10) or fixed (i.e., Δk=5 and Δk=15). This validates the theoretical results in Section 4 that the convergence of the proposed trial-and-error method can be achieved even if the tolls are updated at irregular time intervals. When comparing the convergence speed of the exact and inexact method, we can observe that at the early evolution stage, the convergence speed of the exact method and the inexact method with Δ2k=15 are similar, both of which are slightly higher than the inexact method with Δ1k=5 and Δ3k=5+floork/10. At the late evolution stage, the exact method converges faster than all the three forms of the inexact method. This means to achieve the same level of solution accuracy, the method with a longer intertrial period requires fewer trials. The reason for this phenomenon is that if the intertrial period is longer, travelers will have more time to learn the traffic conditions and adjust their route choice, so that the observed network flow at the end of each intertrial period becomes closer to the equilibrium state. Therefore, the generated search direction (cf. equation (33)) under longer intertrial period would be more effective in improving the convergence speed of the trial-and-error method.Figure 10
Convergence of the exact and inexact trial-and-error method in terms of number of trials on the Hearn–Ramana network (left).Figure11 depicts the convergence of the exact and inexact trial-and-error method in terms of the number of evolutionary days on the Hearn–Ramana network. We find from this figure that the performance of all the three forms of the inexact method is uniformly superior to the exact method. This is because in comparison with the exact method, although the inexact method consumes a little more trials to get to the same convergence tolerance (cf. Figure 10), it requires much less number of evolutionaryd days between any two consecutive trials. Therefore, the total number of evolutionary days for the inexact method will be greatly decreased. This explanation can also account for the phenomenon in Figure 10 that the performance of the inexact method with Δ1k=5 and Δ3k=5+floork/10 is similar and both of which outperform the inexact method with Δ2k=15.Figure 11
Convergence of the exact and inexact trial-and-error method in terms of number of evolutionary days on the Hearn–Ramana network (right).Figures12 and 13, respectively, depict the convergence of the exact and inexact method with respect to the number of trials and number of evolutionary days on the Sioux Falls network. Inspection of Figure 12 reveals that as far as the number of trials is concerned, the exact method is slightly faster than the inexact method with Δ2k=15, more faster than the inexact method with Δ1k=5 and Δ3k=5+floork/10. However, from Figure 13, it can be observed that all the three forms of the inexact method consume much less number of evolutionary days than the exact method, among which the inexact method with Δ1k=5 performs best. The two phenomena have already been observed in the performance analysis on the Hearn–Ramana network, and the reasons are similar. Therefore, in view of practical implementation, the selection of the trial-and-error congestion pricing method depends on the specific objective of a practitioner. If the purpose is to reduce the number of trials so as to minimize the inconvenience caused by the toll charge variation, then the exact method or the inexact method with a long interval is preferred. On the contrary, if the practitioner aims to reduce the implementation times so that system optimum can be achieved as soon as possible, then the inexact method with a short intertrial period is more attractive.Figure 12
Convergence of the exact and inexact trial-and-error method in terms of number of trials on the Sioux Falls network (left).Figure 13
Convergence of the exact and inexact trial-and-error method in terms of number of evolutionary days on the Sioux Falls network (right).


## 6. Conclusions and Future Research

In this study, we developed a trial-and-error congestion pricing method with day-to-day dynamic network flows which takes into account the heterogeneous inertia patterns of travelers. The implementation of this method does not require any knowledge of the OD demands. In addition, it allows the link tolls to be updated at irregular intervals without waiting for the network flow achieving the user equilibrium state. We presented a theoretical proof for the convergence of this method. The findings of this study can significantly facilitate the application of the trial-and-error congestion pricing method in practice.For further research, several extensions can be made in the following directions. First, the current method focuses on achieving system optimum by implementing the congestion pricing. To maintain the traffic flow on each link within a desirable threshold, it is highly anticipated to develop a trial-and-error method for the traffic restraint congestion pricing scheme with inertia-based day-to-day flow adjustment processes in the future. Second, the day-to-day flow adjustment model employed in the proposed trial-and-error congestion pricing method is based on link flows. It is interesting to develop a trial-and-error congestion pricing scheme under a route flow adjustment model, which also incorporates travelers’ heterogeneous inertia patterns. In addition, the concept of robust optimization can also be integrated into the trial-and-error congestion pricing scheme [52], which takes into account the inertia-based flow adjustment process on each day.



---

*Source: 8514765-2019-11-20.xml*