1 Introduction

Traffic congestion is a severe problem confronted with in many large urban areas, which leads to high levels of fuel consumption, air pollution, economic loss and crashes. Cordon-based congestion pricing has been widely recognized as an efficient way to ameliorate urban traffic congestion^[1-5]. Currently most countries have implemented daily license^[6] or entry-based congestion pricing schemes^[3], which are not equitable because drivers have different levels of usage of toll roads. Hence, May and Milne^[7] proposed and explored three alternative toll charge schemes: time-based, congestion-based and distance-based schemes to replace the current congestion pricing schemes. The first two schemes may have negative impacts on drivers because they can encourage aggressive driving behavior drivers leading to the increased safety problems. Compared to time and congestion based schemes, distance-based toll charging schemes are linked with the distance travelled inside a pricing cordon and thus are more reasonable and practical than the first two schemes in the real world.

The issue of equity is quite crucial for public acceptance of congestion pricing schemes^[8]. Although the theoretical soundness of congestion pricing has been well recognized by researchers^[9-10], political and public resistance are still major hurdles for its practical implementation, due to concerns that congestion pricing is not equitable, resulting in fears that car travel will become a privilege only for the rich. Therefore, it is of considerable importance to perform in-depth research on the equity of distance tolls. The aim of this paper is to present a methodology for addressing the optimal nonlinear distance toll that can optimize the level of equity over an entire traffic network.

2 Distance-Based Toll Design Problem 2.1 Problem Description

A strongly connected urban transportation network is denoted by G=(N, A), where N and A are the sets of nodes and links, respectively. Cordon-based congestion pricing divides the network G=(N, A) into two parts: an external network ${{{\hat{G}}}^{=}}({{{\hat{N}}}^{,}}\hat{A})$ and a cordon network G=(N, A). Links and nodes in the cordon network are termed internal links and nodes, while the other links and nodes in external network are termed external links and nodes. Let d_k^w be the length of path k∈R_w in the congestion pricing cordon, where R_w is the set of all the paths connecting OD pair w∈W. Based on the length of the used path in the pricing cordon, the distance-based toll charge function is assumed to be φ(d), where φ(d) is a nonlinear and non-decreasing function. Hence, for any given toll charge function, the toll charged on each path k∈R_w between OD pair w∈W can be calculated by:

${{\tau }_{wk}}\left( \varphi \right)=\varphi ({{d}_{k}}^{w})$

(1)

Different toll charge functions φ(d) yield different impacts on the network. Thus, how to determine the optimal function that can improve the equity level of the transport network is a critical issue. The nonlinear function has no specific functional form, and there is also no practical data to calibrate this function, making the toll design problem for distance tolls a challenging one. Following the ideas from previous studies by Meng^[11] and Lawphongpanich and Yin^[12], a piecewise linear function is adopted to approximate a nonlinear function form. Specific details of the piecewise linear approximation method are illustrated in Fig. 1.

As claimed by Lawphongpanich and Yin^[12], compared with a highly nonlinear function, such a piecewise linear function is easier to understand by users and is more practical for implementation whilst having most of the advantages of a general nonlinear pricing function. It starts with defining the minimum and maximum length on the path in the pricing cordon and then the nonlinear toll charge function is evenly divided into n intervals, using a linear function within each interval as an approximation.

$[{{d}_{min}},\text{ }{{d}_{2}}\left] ,\text{ } \right[{{d}_{2}},\text{ }{{d}_{3}}\left] ,\text{ }\ldots ,\text{ } \right[{{d}_{i}},\text{ }{{d}_{i+1}}\left] ,\text{ }\ldots ,\text{ } \right[{{d}_{n}},\text{ }{{d}_{max}}]$

Secondly, based on the principle of piecewise linear approximation method, tolls on any path can be uniquely determined. It is noted that if the interval is set to be n, then there are n+1 vertex values in the piecewise linear approximation function. Thus the piecewise linear approximation function is defined accordingly as follows:

$\begin{align} & {{{\bar{\varphi }}}_{n}}\left( d,\text{ }y \right)={{y}_{i}}+\frac{{{y}_{i+1}}-{{y}_{i}}}{{{d}_{i+1}}-{{d}_{i}}}(d-{{d}_{i}}),{{d}_{i}}\le d ＜{{d}_{i+1}} \\ & i=1,\text{ }2,\text{ }\ldots ,\text{ }n \\ \end{align}$

(2)

where d₁=d_min and d_n+1=d_max. The column vector of vertex values y is defined as y=(y₁, y₂, …, y_n+1)^T. Therefore, tolls on any paths k∈R_w can be calculated using Eq.(2) , as an approximation of Eq.(1) .

2.2 User Equilibrium Traffic Assignment with Distance Tolls

Before introducing the UE traffic assignment model with distance tolls, we define the generalized travel time and the corresponding user equilibrium condition after imposing the distance tolls. For any given toll charge function, the overall travel impedance on each path k∈R_w consists of the path travel time c_wk(v) and the distance tolls τ_wk(φ). Thus the generalized travel time along the path k∈R_w between OD pair w∈W is defined as:

${{C}_{wk}}(v,\text{ }{{\tau }_{wk}}\left( \varphi \right))={{c}_{wk}}\left( v \right)+{{\tau }_{wk}}\left( \varphi \right)/\alpha $

(3)

where α is the drivers’ value of time, used to convert the toll charge into time-units. The principle of assigning the link flow to the network follows the user equilibrium, which has been explained in Sheffi^[13].

Let the number of users traveling between each OD pair or the demand function be q_w=D_w(u_w). This demand function is assumed to be a strictly decreasing function of the minimum generalized OD travel time u_w and nonnegative for all OD pairs. The travel time on link a∈A is defined as t_a(v_a). v_a denotes the flow on link a and f_w^w denotes the flow on path k between OD pair w∈W. The following conditions should be satisfied by the equilibrium flows:

$\left\{ \begin{align} & {{c}_{wk}}\left( v \right)+{{\tau }_{wk}}\left( \varphi \right)/\alpha ={{u}_{w}},~if~{{f}_{w}}^{w}>0,\text{ }\forall k\in {{R}_{w}},\text{ }w\in W \\ & {{c}_{wk}}\left( v \right)+{{\tau }_{wk}}\left( \varphi \right)/\alpha \ge {{u}_{w}},~if~{{f}_{w}}^{w}=0,\text{ }\forall k\in {{R}_{w}},\text{ }w\in W \\ & {{u}_{w}}={{D}_{1}}^{-1}\left( {{q}_{w}} \right),~if~{{q}_{w}}>0,\text{ }\forall k\in {{R}_{w}},\text{ }w\in W \\ & {{u}_{w}}\ge {{D}_{1}}^{-1}\left( {{q}_{w}} \right),~if~{{q}_{w}}=0,\text{ }\forall k\in {{R}_{w}},\text{ }w\in W \\ \end{align} \right.$

(4)

We propose an optimization model for the toll user equilibrium (TUE) problem with elastic demand, based on a given toll charge τ_wk, r∈R_w, w∈W, which is formulated as follows:

TUE:

$\begin{align} & \text{min }\!\!~\!\!\text{ }Z=\sum\limits_{a\in A}^{{}}{\int_{0}^{{{v}_{a}}}{{{t}_{a}}}}\left( v \right)dv+\sum\limits_{w\in W}{\sum\limits_{k\in {{R}_{w}}}{{{\tau }_{wk}}{{f}_{k}}^{w}}}- \\ & \sum\limits_{w\in W}{\int_{0}^{{{q}_{w}}}{{{D}_{w}}^{-1}\left( x \right)dx}} \\ \end{align}$

(5)

s.t.

$\sum\limits_{k\in {{R}_{w}}}{{{f}_{k}}^{w}}={{q}_{w}},\text{ }\forall w\in W$

(6)

${{v}_{a}}=\sum\limits_{w\in W}{\sum\limits_{k\in {{R}_{w}}}{{}}}{{f}_{k}}^{w}{{\delta }_{ak}}^{w},\text{ }\forall a\in A$

(7)

${{f}_{k}}^{w}\ge 0,\text{ }\forall k\in {{R}_{w}},\text{ }w\in W$

(8)

${{q}_{w}}\le {{{\bar{q}}}_{w}}$

(9)

where q_w represents the upper bound of demand. Eq.(6) represents the set flow conservation constraints, which state that the flow on all paths connecting each O-D pair has to equal the O-D trip rate. Eq.(7) indicates that the flow on each link is the sum of the flows on all paths going through that link, known as the path-link incidence relationships, which can convert path flows into aggregate link flows. The nonnegative condition in Eq.(8) is required to ensure that the solution of the program will be physically meaningful.

This optimization model is an extension of model used by Sheffi^[13] for un-tolled UE with elastic demand. This model is evidently convex in terms of the link flows and OD demands. Its KKT (Karush-Kuhn-Tucker) conditions show that the optimal solution can fulfill the equilibrium conditions in Eq.(4) . Thus, solving this model gives the equilibrium flows associated with any given toll charge function φ(d), and these equilibrium flows are used to assess the impacts of φ(d) on the network flows and its equity level.

3 Equity Impact Evaluation 3.1 Specification of Equity Constraint

Yang and Zhang^[14] used an example to explain the inequity problems with a simple network. This shows the travel costs for several OD pairs increasing and their percentage increase are different. In order to ensure the relative equity of all network users, a simple practicable method is used to prevent the percentage increase of travel cost of critical network users from exceeding a pre-specified threshold in determining the distance tolls. As a consequence of the complexity of the problem, it is not possible to design a completely equitable toll charge scheme, but the inequity impacts from the toll charge scheme can be limited to a certain level set by the authority or government. Therefore, these kinds of equity issues considering changes in the OD travel costs can be incorporated into the upper level as a constraint. The change of the generalized OD travel time is termed as the OD travel cost ratio and is defined as:

${{r}_{w}}\left( s \right)=\frac{{{\mu }_{w}}\left( s \right)}{{{{\tilde{\mu }}}_{w}}},\text{ }w\in W$

where r_w(s) represents the OD travel cost ratio under a toll charge scheme s; μ_w(s), w∈W is the equilibrium generalized OD travel time for given scenario s and correspondingly, ${\tilde{\mu }}$_w, w∈W is the equilibrium generalized OD travel time before implementing the toll charging scheme y. It is easy to see that this OD travel cost ratio may be different among different OD pairs, which means that the impacts of a toll charge scheme on each OD travel cost is unknown.

In order to find the critical network users who suffer the most additional costs, the critical OD travel cost ratio is defined as the maximum among all OD pairs:

$r\left( s \right)=\underset{w\in W}{\mathop{\text{max}}}\,\left\{ {{r}_{w}}\left( s \right) \right\}$

where r(s) is the critical ratio of OD travel cost.

Based on those specifications above, the equity constraint is defined as:

$r\left( s \right)\le \beta $

where β is a predetermined threshold. When β is set as β＜1.0, then each road user will have access to the benefits from the toll charging scheme; however, if β is set to be β>1.0, it means that users from some OD pairs may incur the increased travel costs induced by the toll charging scheme.

3.2 Lorenz Curve and Gini Coefficient

Although there are some literatures using different equity indicator to study the equity issue^[15-18], these methods cannot capture the loss in consumer surplus from the depressed demand and do not provide a measurable index for estimating the network level of the equity impacts. Hence, Lorenz curve and the Gini coefficient are adopted to evaluate the spatial equity at a network level^[19-22]. Firstly, a Lorenz curve is developed to represent the cumulative distribution function of wealth across a population as shown in Fig. 2. The area between the straight line and curve represents the skew of the actual income distribution from the ideal equitable distribution. The Gini coefficient (G) is defined as the ratio of this area between the curves divided by the total area under the line of equality to measure the degree of equity. In this way, the distribution of two different curves can be mathematically compared and thus the Gini function is formulated as^[23]:

$G=\frac{\sum\limits_{i}{\sum\limits_{j}{\left| {{x}_{i}}-{{x}_{j}} \right|}}}{2{{n}^{2}}\mu }$

(10)

where x_i and x_j are the income level of individual i and j, respectively; n is the total number of individuals in the population and μ is the mean of the income in the population.

In order to estimate the Gini coefficient to be used in the distance-based toll design model, the variable of interest regarding equity, namely x_i, needs to be defined. The aggregate total user benefit for each OD pair w∈W can be defined as:

$U{{B}_{w}}=\int_{0}^{{{q}_{w}}}{{{D}_{w}}^{-1}}\left( x \right)dx-\sum\limits_{k}{{{C}_{wk}}{{f}_{k}}^{w}}$

where C_wk is the generalized travel cost for path k shown by Eq.(3) (consisting of travel time and toll fare). Then, the income level of individual in the original Gini coefficient x_i, can be replaced by the disaggregate average user benefit for each traveler belonging to the OD pair w∈W as follows:

$u{{b}_{w}}=\frac{1}{{{q}_{w}}}\int_{0}^{{{q}_{w}}}{{}}{{D}_{w}}^{-1}\left( x \right)dx-\sum\limits_{k}{{{C}_{wk}}{{f}_{k}}^{w}}$

(11)

Finally, based on Eqs.(10) and (11) , the modified Gini coefficient for the distribution of user benefits can be expressed as:

$G=\frac{\sum\limits_{w}{\sum\limits_{{{w}^{\prime }}}{{{q}_{w}}{{q}_{{{w}^{\prime }}}}\left| u{{b}_{w}}-u{{b}_{{{w}^{\prime }}}} \right|}}}{2{{(\sum\limits_{w}{{{q}_{w}}})}^{2}}\overline{ub}}$

4 Bi-level Programming for the Optimal Distance-Based Toll Design

For the optimal toll charge design, we want to obtain the optimal distance-based toll charging scheme with the best Gini coefficient at a network level and restrict the critical OD travel cost ratio to be less than a given positive value, the aim of which is to make users of most OD pairs enjoy more benefits from the optimal toll charge scheme. This kind of toll charge design can be formulated by the following bi-level programming model:

Upper level

$\text{min}~G({{{\bar{\varphi }}}_{n}}\left( d,\text{ }y \right))=\frac{\sum\limits_{w}{\sum\limits_{w}{{{q}_{w}}{{q}_{w'}}\left| u{{b}_{w}}-u{{b}_{w'}} \right|}}}{2{{(\sum\limits_{w}{{{q}_{w}}})}^{2}}\overline{ub}}$

s.t.

$\begin{align} & r\left( s \right)\le \beta \\ & {{y}_{\text{min}}}\le {{y}_{1}} \\ & {{y}_{i-1}}\le {{y}_{i}}\le {{y}_{i+1}},\text{ }\forall i=2,\text{ }3,\text{ }\ldots ,\text{ }n-1 \\ & {{y}_{n}}\le {{y}_{\text{max}}} \\ & n\text{ }~is\text{ }a\text{ }constant \\ \end{align}$

Lower level

Equations(5)-(9)

It is noted that a toll charge scheme is regarded as optimum if it can give rise to the minimum Gini coefficient under the constraint of equity measured by the critical OD travel cost ratio.

5 Solution Method 5.1 Solution Algorithm for Traffic Assignment with Distance Tolls

As previously mentioned, the distance-based toll charge method is non-additive. Hence, the link-based algorithms cannot be used to solve this traffic assignment model independently. In order to use the link-based Frank-Wolfe algorithm to solve this non-additive problem, a new network transformation technique is adopted by replacing the paths in the cordon by dummy links^{[11, 24]}. In this way, the non-additive path-based toll charges are converted into link-based ones in the transformed network. Details of the network transformation method can be found in Meng et al.^[11]. The Frank-Wolfe method for solving user equilibrium problems in the transformed network is summarized as follows:

Step 1 (Initialization). Assuming that the traffic flow on the original network G=(N, A) is zero. Based on the link travel time function t_a=t_a(0) , the free flow travel time can be obtained. Then the travel time on the dummy link is sum of the travel time on the corresponding links. Thus the generalized travel time on the dummy link is defined as the sum of the travel time on the dummy link and toll. Based on that, to perform the all-or-nothing loading and obtain the link flows on the composite network {x′_a¹}.

Step 2 (Link flow conversion). To assign the link flows on the composite network to the corresponding links on the original network and obtain the link flows on the original network {x_a¹}. Set counter n=1.

Step 3 (Updating). According to the link flow on the original network as shown by Step 2, update the link travel time based on the t_aⁿ=t_a(v_aⁿ). Then the travel time on the dummy link is sum of the travel time on the corresponding links. Thus the generalized travel time on the dummy link is defined as the sum of the travel time on the dummy link and toll.

Step 4 (Direction finding). On the composite network G′=(N′, A′), to conduct an all-or-nothing loading and obtain the auxiliary traffic flow on each link {y′_aⁿ}. After that, to perform Step 2 again to obtain the auxiliary link flows on the original network {y_aⁿ}.

Step 5 (Line search). To find α_n that solves

$\begin{align} & \underset{0\le \alpha \le 1}{\mathop{\text{min}}}\,\sum\limits_{a\in A}{{{\int }_{0}}^{{{x}^{n}}+\alpha ({{y}_{a}}^{n}-{{x}_{a}}^{n})}}{{t}_{a}}\left( w \right)dw+\sum\limits_{w\in W}{\sum\limits_{k\in {{R}_{w}}}{{{\tau }_{wk}}}} \\ & [x{{\prime }_{a}}^{n}+\alpha \left( y{{\prime }_{a}}^{n}-x{{\prime }_{a}}^{n} \right)] \\ \end{align}$

Step 6 (Move). Set

$\left\{ \begin{array}{*{35}{l}} {{x}_{a}}^{n+1}={{x}_{a}}^{n}+{{\alpha }_{n}}\left( {{y}_{a}}^{n}-{{x}_{a}}^{n} \right)\text{ }\forall a\in A \\ x{{\prime }_{a}}^{n+1}=x{{\prime }_{a}}^{n}+{{\alpha }_{n}}\left( y{{\prime }_{a}}^{n}-x{{\prime }_{a}}^{n} \right)\forall a\in A \\ \end{array} \right.$

Step 7 (Convergence test). If a criterion that is based on the change in flows is met, stop; otherwise, go to the Step 3.

$\frac{\sum\limits_{a}{{{x}_{a}}^{n}}{{({{x}_{1}}^{n+1}-{{x}_{a}}^{n})}^{2}}}{\sum\limits_{a}{{{x}_{a}}^{n}}}\le \varepsilon $

where ε is the predetermined precision parameter.

5.2 Solution Algorithm for the Bi-level Model

Due to the complexity of the proposed bi-level model, it is difficult to adopt any gradient-based algorithm^[25]. Thus a heuristic Genetic Algorithm (GA) is used as solution method for this model.

The chromosome for the GA is developed as follows. Firstly, each feasible chromosome represents the piecewise-linear toll charge function φ_n(d, y). A feasible chromosome is given as (y₁, y₂, …, y_i, y_i+1, …, y_n+1), where y_i represents the boundary value in the piecewise-linear toll charge function and is defined as a gene of one chromosome.

For each chromosome, tolls on the different paths inside the pricing cordon can be obtained and thus lead to different values of the critical OD travel cost ratio r(s) and the Gini coefficient. If the value of the critical OD travel cost ratio, as the constraint of the Gini coefficient, exceeds the predetermined value β, the corresponding value of the Gini coefficient and the chromosome will be deleted (the Gini coefficient can be set to 1 in the coding if the constraint r(s)≤β, is not satisfied). Calculation of the Gini coefficient is a TUE problem, which can be solved by the network transformation and Frank-Wolfe method outlined in Section 5.1.

6 Numerical Example 6.1 Data Description

To numerically validate the proposed methodology, one example network (as shown in Fig. 3) from Yang et al.^[24] and Meng et al.^[11] is adopted. The travel demand function between each OD pair w∈W and link travel time function on link a∈A are identical to those in Yang et al.^[24] The length of each link in the pricing cordon is shown in Table 1 that can be used to measure the drivers’ total travel distance in the pricing cordon. It is noted that the minimum and maximum of path lengths are 480 and 2 563, respectively. The lower and upper bound value of toll charges are set to be y_min=1 and y_max=20. The number of intervals is set to be n=8. The parameters used in the GA for the numerical test are shown in Table 2.

In order to test and validate the proposed model and algorithm, the experiment was run on the Intel Core i7-3770/3.4 GHz, 8 GB Ram the computer, using C programming language in Visual Studio 2012.

6.2 Result Analysis

According to the different value of β, the corresponding value of minimum Gini coefficient and toll charge function can be obtained, as shown in Table 3.

The Gini coefficient at the network with non-toll is calculated to be 0.338 7 in advance. It is evident based on Table 3 that when β is set to be 1.05, the minimum Gini coefficient can be reached to be 0.318 4 and the inequity level is decreased by 5.99%. Accordingly, the toll charge function is shown in Fig. 4(a). It is straightforward to see from Fig. 4(a) that the optimal distance-based toll charge function is displayed to be highly nonlinear. Compared with the optimal uniform toll function based on Maruyama and Sumalee^[19-22], the improvement of equity level with nonlinear distance-based toll function is more obvious and effective. In addition, by comparing the corresponding shape of toll charge function with different Gini coefficient based on Fig. 4, it can be concluded that as Gini coefficient is increased, namely inequity level is increased, and the optimal toll charge function is approximate to linear function although it still displays nonlinear form.

7 Conclusions and Future Work

This paper addresses how to optimize equity within the toll charge design problem for a cordon-based congestion pricing scheme with distance toll. A bi-level model is developed for solving the optimal toll charge design problem. The upper level of bi-level model is associated with equity issues, the aim of which is to obtain the optimal toll charge function with the best Gini coefficient under the constraint of the spatial equity. Previous researches investigating the impacts from congestion pricing have not fully incorporated equity impacts for travelers. This paper presents a measureable index at the network level of the equity impact and combines it with spatial equity. In the upper level, the OD travel cost ratio is used as the constraint to ensure all road users experience a travel cost reduction. Under this condition, the Gini coefficient is used to identify the optimal charging scheme.

The results show that the proposed model and algorithm can be demonstrated to be efficient by the numerical example. The optimal distance-based toll charge function is highly nonlinear when the minimum Gini coefficient is reached. By comparing the toll charge function with different Gini coefficient, it is evident that the toll charge function is approximate to linear form as the inequity level increases.

Distance-based congestion pricing has various impacts on many considerations, which is a complicated and difficult problem. This paper, just only from theoretical perspective, presents some initial steps towards incorporating equity issues in determining nonlinear distance tolls. Further work is required to further extend these models to consider more practical issues such as multi-objective problem, dynamic traffic networks, heterogeneous or continuous values-of-time and multi-vehicle types. In addition, regarding the final solution in the conclusion part, we present the optimal distance-based congestion pricing scheme only considering the equity issues. Although this final result cannot be applied in the real world immediately, it indeed provides a method, idea and direction for further research in the future.