A multi-objective model for cordon-based congestion pricing schemes with nonlinear distance tolls
来源期刊:中南大学学报(英文版)2016年第5期
论文作者:别一鸣 孙鑫 刘志远 THOMPSON Russell G 翁金贤 陈淑燕
文章页码:1273 - 1282
Key words:distance-based toll charging schemes; equity; path-based gradient projection algorithm; non-additive; goal programming
Abstract: Congestion pricing is an important component of urban intelligent transport system. The efficiency, equity and the environmental impacts associated with road pricing schemes are key issues that should be considered before such schemes are implemented. This paper focuses on the cordon-based pricing with distance tolls, where the tolls are determined by a nonlinear function of a vehicles’ travel distance within a cordon, termed as toll charge function. The optimal tolls can give rise to: 1) higher total social benefits, 2) better levels of equity, and 3) reduced environmental impacts (e.g., less emission). Firstly, a deterministic equilibrium (DUE) model with elastic demand is presented to evaluate any given toll charge function. The distance tolls are non-additive, thus a modified path-based gradient projection algorithm is developed to solve the DUE model. Then, to quantitatively measure the equity level of each toll charge function, the Gini coefficient is adopted to measure the equity level of the flows in the entire transport network based on equilibrium flows. The total emission level is used to reflect the impacts of distance tolls on the environment. With these two indexes/measurements for the efficiency, equity and environmental issues as well as the DUE model, a multi-objective bi-level programming model is then developed to determine optimal distance tolls. The multi-objective model is converted to a single level model using the goal programming. A genetic algorithm (GA) is adopted to determine solutions. Finally, a numerical example is presented to verify the methodology.
J. Cent. South Univ. (2016) 23: 1273-1282
DOI: 10.1007/s11771-016-0377-4
SUN Xin(孙鑫)1, LIU Zhi-yuan(刘志远)1, THOMPSON Russell G2,
BIE Yi-ming(别一鸣)3, WENG Jin-xian(翁金贤)4, CHEN Shu-yan(陈淑燕)1
1. School of Transportation, Southeast University, Nanjing 210096, China;
2. Department of Infrastructure Engineering, the University of Melbourne, Victoria 3010, Australia;
3. School of Transportation Science and Engineering, Harbin Institute of Technology, Harbin 150090, China;
4. College of Transport and Communications, Shanghai Maritime University, Shanghai, China
Central South University Press and Springer-Verlag Berlin Heidelberg 2016
Abstract: Congestion pricing is an important component of urban intelligent transport system. The efficiency, equity and the environmental impacts associated with road pricing schemes are key issues that should be considered before such schemes are implemented. This paper focuses on the cordon-based pricing with distance tolls, where the tolls are determined by a nonlinear function of a vehicles’ travel distance within a cordon, termed as toll charge function. The optimal tolls can give rise to: 1) higher total social benefits, 2) better levels of equity, and 3) reduced environmental impacts (e.g., less emission). Firstly, a deterministic equilibrium (DUE) model with elastic demand is presented to evaluate any given toll charge function. The distance tolls are non-additive, thus a modified path-based gradient projection algorithm is developed to solve the DUE model. Then, to quantitatively measure the equity level of each toll charge function, the Gini coefficient is adopted to measure the equity level of the flows in the entire transport network based on equilibrium flows. The total emission level is used to reflect the impacts of distance tolls on the environment. With these two indexes/measurements for the efficiency, equity and environmental issues as well as the DUE model, a multi-objective bi-level programming model is then developed to determine optimal distance tolls. The multi-objective model is converted to a single level model using the goal programming. A genetic algorithm (GA) is adopted to determine solutions. Finally, a numerical example is presented to verify the methodology.
Key words: distance-based toll charging schemes; equity; path-based gradient projection algorithm; non-additive; goal programming
1 Introduction
Congestion pricing, acting as an economic lever for traffic demand management in urban metropolises, has received substantial interests in recent years both from academics and practitioners [1-7]. Existing practical implementations of congestion pricing are all cordon-based with entry-based tolls or daily licenses that are not equitable or efficient. Hence, three alternative toll charging schemes (time-based, congestion-based and distance-based) have been proposed as extensions [8], which can outperform the flat toll charge scheme. However, the first two methods encourage aggressive driving because less time in the pricing cordon means less toll costs. Thus, distance-based schemes are more suitable for practical implementation. With distance- based schemes, tolls are determined as a function of the vehicle’s travel distance in the cordon area, which is called the toll charge function. It is worthwhile noting that distance-based congestion pricing has already been targeted to be the extension of the current electronic road pricing system in Singapore, as the new generation of the congestion pricing system from 2020. With the in-vehicle positioning and communication system, the technology for distance-based toll within a pricing cordon is ready for implementations.
Recently, distance-based tolling schemes have attracted considerable attention [9-12]. A number of these studies assume a linear distance toll charge function. The linear toll function is a special case of nonlinear function. However, nonlinear distance tolls are not sufficiently investigated, which is the target of this paper.
The nonlinear distance toll is non-additive [7], which means that the overall travel cost on a path is not the sum of the link costs along that path. To cope with this problem in a real-size transport network, a network- representation based approach was proposed by Meng et al [7], where the possible paths in the cordon are enumerated and replaced by dummy links. However,such an approach requires path enumeration and storage, and when the size of the cordon area is sufficiently large, the computational burden is intensive. This paper therefore extends the solution methodology using a path-based gradient projection method based on column generation.
Two objectives are usually taken for the optimal congestion tolls, which are efficiency (minimize the total travel time [13]) and reducing the environmental impacts (e.g., the London Congestion Charging Scheme [14]). Apart from these two objectives, the issue of equity is quite crucial for public acceptance of congestion pricing schemes. Although the theoretical soundness of congestion pricing has been well recognized by researchers, political and public resistance is still major hurdles for its practical implementation. Hence, the issue of equity has attracted considerable interests. Although there are some studies on the equity of congestion pricing [15-16], the measurement index used to evaluate equity is not at aggregate level. Hence, the Gini coefficient is adopted as the indicator to measure the equity at network level [17-18]. The quantitative study of the equity of distance tolls is still an open question, although it has been claimed as a more equitable charge to the users [7]. Therefore, addressing these three objectives, this paper works on the optimal toll determination for cordon-based pricing with distance tolls.
The optimal toll determination problem can be formulated as a bi-level model with multiple objectives. The existence of multiple objectives has increased the challenge of solving this bi-level model. To solve this type of problem, a variety of methods and models have been developed in Refs. [19-24]. In this work, the goal programming method is adopted to convert the multiple objectives to a single objective based on the priority structure provided by the decision makers. Goal programming aims to minimize the deviations between actual values and target values according to the priority ranking of the goals [22-23].
The contributions of this work are twofold. First, this work investigates the equity impacts of a nonlinear distance toll charge scheme at aggregate level, and uses a modified path-based gradient projection algorithm evaluate the non-additive distance-based toll. Second, a multi-objective bi-level model incorporating new equity indicator is developed to achieve a more sustainable toll design solution.
2 Distance-based toll design problem description
2.1 Notation and assumptions
Consider a road network denoted by G(N, A) where N and A are the sets of nodes and directed links, respectively. Due to the presence of cordon-based congestion pricing, the network G=(N, A) is divided into two parts: an external network denoted by and a cordon network denoted by where and are the sets of external (out of cordons) nodes and directed links, respectively and and are the sets of internal (within cordons) nodes and directed links, respectively. Let W denote the set of OD pairs and then travel demand between OD pair is denoted by qw. Let Rw be set of paths between OD pair and then represents the traffic flow on path between OD pair The traffic flow on link is denoted by va, and the link travel time ta is defined as a function of va. The link travel time function, ta=ta(va) is assumed to be non-negative, monotonically increasing and continuously differentiable.
2.2 Distance-based toll charge function
Let denote the length of the portion of path in the pricing cordon and it thus can be expressed as follows:
(1)
where la is the length of link
Cordon-based congestion pricing with a distance toll can be expressed by the distance-based toll charge function f(d), where d is the distance travelled inside the pricing cordon. The distance-based toll charge function is allowed to be any increasing non-decreasing and positive function. Herein, the toll charge imposed on a path between OD pair is expressed by
(2)
For path k between OD pair w, if link a is a component of path k, then is 1 and 0, otherwise. The travel time of path k can then be defined as where represents the link-path incidence matrix. The total generalized path travel time on path thus can be defined as
(3)
where α is the drivers’ value of time (VOT).
2.3 Piecewise-linear approximation function
Due to the nonlinear toll charge function, the generalized path travel time (3) is not equal to the sum of generalized link travel time on this path, termed as the non-additivity. Note that the toll charge function does not follow any particular function form, thus it is difficult to formulate and solve this non-additive problem. Hence, we adopt a piecewise-linear approximation method to approximate the nonlinear toll charge function. Figure 1 illustrates the piecewise linear approximation [7], which can accurately approximate any particular nonlinear function on the left-hand-side.
Fig. 1 An illustration for piecewise-linear approximation function
The nonlinear toll charge function can be defined as follows. Firstly, define the minimum and maximum lengths on the path in the pricing cordon and then evenly divide the length range into n intervals.
(4)
Secondly, based on any toll charge function, tolls on any path can be uniquely determined. Note 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:
(5)
where d1=dmin and dn+1=dmax. The column vector of vertex values is defined as y=(y1, y2, …, yn+1)T. Therefore, tolls on any paths can be calculated using Eq. (5), as an approximation of Eq. (2).
3 Path-based toll user equilibrium formulation
3.1 Mathematical model
With a given toll charge function, the network users’ route choice behavior is assumed to follow the DUE with elastic demand [25]:
(6)
(7)
(8)
where the travel demand is determined by the demand function which is a non-increasing and nonnegative function of the minimum generalized OD travel costs uw. Hence, the path flows are optimal if and only if the following conditions hold:
(9)
(10)
(11)
(12)
Note that the generalized path travel time expression on the left hand side of Eqs. (9) and (10) is non-additive, thus the traffic equilibrium problems should be solved in the path-flow domain. For each path its travel distance within the tolling area, is fixed, implying that the toll τwk, for path k is also fixed. Then, the DUE problem with elastic demand in terms of a given toll charge pattern can be formulated in terms of path flows as follows:
DUE (13)
s.t.
(14)
(15)
(16)
It can be easily seen that this model is convex, which has unique optimal link flow solution. The Karush-Kuhn-Tucker (KKT) conditions show that the solution of this model can fulfill the DUE conditions (9)-(12). Therefore, the optimal solution of this model gives the UE flows in terms of the distance tolls τ.
3.2 Path-based solution algorithm
The nonlinear distance tolls have introduced non-additivity to the path travel costs. Hence, it is suitable to adopt the path-based traffic assignment algorithms as solution methods. There are various sound path-based traffic assignment algorithms in the literature [26-30], including the gradient projection (GP) and simplicity decomposition algorithms. In this section, the GP is taken as the solution method. Previous GP algorithms are mostly used to solve additive traffic assignment problems [26-27]. In order to solve the non-additive problem in this work, the k-shortest algorithm and column generation algorithm have been combined into the GP algorithm to generate new shortest path based on the generalized path travel time. The steps for this algorithm are given as follows.
Initialization:
Step 1) Set and define the path set
Step 2) Set iteration counter n=1.
Step 3) Solve the shortest path problem to generate an initial path set
Step 4) Load the travel demand to the shortest path
Step 5) Assign path flows to links
Column generation:
Step 6) Increment iteration counter n=n+1.
Step 7) Update link travel time
Step 8) In the case with path-specific costs
Solve the k-shortest path problem based on the additive path time;
Compute the distance of each k-shortest path and corresponding specific path toll;
Add the path-specific path toll to each of the k-shortest paths;
Identify the one with the smallest generalized travel time to be the new path
Step 9) If update path set otherwise, tag the shortest path among the paths in as
Equilibration:
Step 10) Compute the generalized path travel time and
Step 11) Compute the second derivative costs
Step 12) Direction finding
Step 13) Set the new path flows:
(17)
(18)
where λ(n) is a scalar step-size modifier and usually defined as 1. However, a step size of 1 might be inappropriate. The step-size was improved by using the following equation [31]:
(19)
Setp 14) If drop path
Convergence:
Setp 15) If
(20)
then stop; otherwise, go to step 6 (column generation).
4 Bi-level model
4.1 Goal programming
There are a number of studies in the literature integrating the various objectives into the decision making problem in transportation planning and management [19-23]. By reviewing these studies, the widely used goals are categorized into three classes: efficiency, environment and equity. As discussed in the introductions section, this work adopts all the three objectives for the optimal toll determination. To cope with the multi-objective problem, the goal programming technique is used here. Due to the space limit, rationale and detailed mechanism of goal programming are not covered here, and the readers are recommended to some outstanding papers in this field for reference [22-23].
We proceed to introduce the quantitative definitions of the three objectives.
1) Efficiency.
Total travel time or social welfare could be used as an efficiency measure of the transport network. Here, we use the total social welfare, defined as
(21)
A social welfare improvement constraint requiring that the change from before to after congestion pricing should reach a targeted level, which can be represented as
(22)
where and are the negative and positive deviation variables of the social welfare with associated with the stated goal value, respectively. Note that the subscripts “after” and “before” shown in the Eq. (22) respectively refer to the case of after and before implementing the congestion pricing scheme, which are also used in the following equations. The parameter β1 is a target value from the transport authority that defines the threshold of the change in social welfare.
2) Environment.
Transportation system actually poses a huge challenge on the environment protection. Fumes, dust and harmful gases generated from automobiles affect the environment to some extent and even the emission pricing has been proposed to reduce these harmful emissions [32]. Therefore, in order to investigate the effect of congestion pricing on the environment, evaluation models need to be formulated. For simplicity, this paper only considers the effects of emissions since they are typically a major factor contributing to the deterioration of the environment. Here, a nonlinear macroscopic model is adopted to estimate vehicular emissions [33]. Based on the related literature, carbon monoxide (CO) was chosen as the indicator to model vehicular emissions. The vehicular CO emissions model [33] is shown as follows:
(23)
where means the amount of CO pollution generated from link Based on the regression result, ρ1 and ρ2 are 0.2038 and 0.7962, respectively. Note that the unit of la is kilometers; ta(va) and ea(va) are measured in minutes and grams per hour, respectively. According to the disaggregated vehicular CO emissions model, the total CO emissions on a network can be formulated as an environmental objective function:
(24)
The environment constraint requires that the change after the congestion pricing should reach a desired level, which can be represented as
(25)
where and are the negative and positive deviational variables of the vehicular CO emissions with associated with stated goal value, respectively. The parameter β2 is a target value obtained from the transport authority that defines the threshold of the change in vehicular CO emissions.
3) Equity.
The most controversial problem of congestion pricing is its potential impacts on the equity. Many studies that have investigated equity and congestion pricing have focused on the impact of congestion pricing on the change of OD travel times. To measure the equity at an aggregate network level, the Gini coefficient is taken as an equity index. The Gini coefficient [16-17] is shown as follows:
(26)
where represents the social welfare improvement compared to the do-nothing scenario between OD pairs The equity constraint requires that the change in the Gini coefficient after congestion pricing should reach a desired level, which can be represented as
(27)
where and are the negative and positive deviational variables of the equity with associated with stated goal value, respectively. The parameter β3 is a target value obtained from the transport authority that defines the threshold of the change in Gini coefficient.
4.2 Multi-objective bi-level model formulation
The transport authority desires to make each objective achieve the expected value provided by decision makers. Using goal programming, the multi- objective bi-level model for seeking the optimal distance- based toll charge function is formulated as follows.
Upper level:
(28)
s.t.
(29)
(30)
(31)
(32)
(33)
(34)
Lower level:
(35)
s.t.
(36)
(37)
(38)
where is the preemptive priority factor representing the order of each objective that needs to be satisfied according to the priority structure. Due to the inconsistent units among the different goals, the relative deviation value is used to reach an agreement on the units, in which Ti is the target value provided by the decision maker. Then, the combined deviation in Eq. (28) with preemptive priority factor is taken as the fitness function in the genetic algorithm. Note that the objective function Eq. (28) is to minimize the total positive deviation, implying that the target value of each goal constraint is only slightly exceeded, where functions Eq.(29)-(31) are the goal constraints.
5 Solution algorithm
The proposed multi-objective bi-level model is actually a non-convex program. Due to the complexity of the proposed model, it is difficult to use any gradient-based algorithm. However, in view of the discrete property of genetic algorithms (GA) are convenient for solving the proposed bi-level model. GA is based on the science of genetics to describe the process of natural growth of organisms. GA has been successfully applied to network design problems [34]. Since each objective constraint shown by Eqs.(29)-(31) needs to be satisfied according to the priority ranking of the goals, GA is revised by incorporating a rearranging module. The entire GA procedure for solving the multiple objective network design problem is summarized as follows:
Step 1) (initialization): The GA starts with a group of chromosomes known as the population. Set the size of population to be k. Randomly generate an initial population representing the piecewise-linear function, and each population carries a feasible chromosome, which contains the toll fare. Then let the number of generations, k=1.
Step 2) (evaluation): based on the generated chromosome, the traffic assignment in the lower level is performed by the path-based algorithm and then based on the results of the traffic assignment, each of actual objectives in the upper level can be calculated. The deviation of each objective between the actual and target values can be obtained simultaneously. The fitness function is then evaluated using Eq. (28).
Step 3) (rearranging module): After the chromosome evaluation procedure, any deviation value for a given toll charge scheme can be obtained. The rearrangement of chromosomes is based on the pre- defined priority level. Chromosomes should be sorted and ranked based on the deviation value in priority 1. If there are some chromosomes with same deviation value in priority 1, record them and sort and rank these chromosomes according to the deviation value in priority 2; otherwise, terminate the rearranging step. In the same way, the rearranging module is preformed until the termination.
Step 4) (crossover): randomly choose parents from all the survivors, and conduct pairing between each parent, denoted by and which yields two new chromosomes, defined by the following function:
(39)
Step 5) (mutation): With lower probability, randomly choose genes from all the chromosomes in current generation, and then modify the value of these genes randomly in then proportionally change the value of other genes of this chromosome in the interval and This process also generates new chromosomes.
Step 6) (selection): among all the existing chromosomes, choose the top chromosomes with lower total deviation values as survivors for current generation and discard the rest.
Step 7) (stop test). If then stop and record the chromosome representing the toll charge function with the minimal total deviation, where kmax is a predetermined upper-bound for the number of generations; otherwise, set k=k+1 and go to step 2).
6 Numerical example
6.1 Network C description and parameter setting
To validate the proposed methodology, a simple network is adopted, which is Network C in the previous study [35] consisting of 14 nodes, 46 links and 8 OD pairs. This network has one pricing cordon, defined by the dashed line and shown by Fig. 2. Links in the cordon are listed by
Nodes 4, 5, 6 and 7 are entries as well as exits to the pricing cordon. These links in the pricing cordon constitute pricing paths in the network. Drivers are charged using the distance-based toll charge function when using these paths. If the drivers do not pass through this cordon, nothing needs to be paid regardless of distance travelled. Since one of objectives relates to the environment, the evaluation of which is related with link distance, each link distance needs to be pre-confirmed and shown in Table 1. It is used to calculate the vehicular CO emission levels. Other parameters are same as those in Ref. [15]. Theoretically, two links with same connected nodes have the same road length. Most of the pricing paths in the cordon have the same length when generating pricing paths for this example, which may hinder the generality of this example. Herein, the length of each link in the pricing cordon is modified slightly. It can be used to measure the drivers’ distance travelled in the pricing cordon. When determining the distance-based toll charge function shown by Eq. (5), the maximum and minimum path lengths in the pricing cordon need to be determined initially. Using Table 1, it is detected that the maximum and minimum path lengths in the pricing cordon are 405 and 2453 m, respectively.
Fig. 2 structure of Network C
Table 1 Length of links in network C
For this numerical example, the link travel time function on link is determined by the standard BPR function, defined as follows:
(40)
where is the free flow travel time on link and is the capacity of link flow. Here, the travel demand between OD pair is assumed to follow the function:
(41)
where is the upper bound of the travel demand between OD pair and γ is a constant parameter, set as 0.01.
Parameters associated with the link travel time function and OD demand function, such as the upper bound of OD demand free flow travel time and capacity ha on each link, are identical to Ref. [35], which are not provided here. Lower and upper bounds of the toll charges are set to be ymin=1 and ymax=20.
In terms of the GA algorithm, the population (chromosome), number of generations, crossover probability and mutation probability are set to be 30, 100, 0.8 and 0.15, respectively. In addition, as mentioned earlier, the value of intervals are set to be constant. In this example, interval n is chosen to be n=8, which means that there are 9 bound values for piecewise-linear approximation function. Each bound value represents one gene in the GA. When computing the fitness value in the evaluation step of the GA, the preemptive priority factor Pi needs to be set based on the priority structure. Following [23], Pi is defined in the following manner:
(42)
Equations (28) and (42) are combined as the fitness function in the GA. After describing the network attributes and defining the parameters, the proposed solution algorithm was coded in the programming language C with the aid of Visual Studio 2010 software on a personal computer to solve distance-based toll charge optimization problem.
6.2 Numerical results
Different policy makers may have different requirements for the priority of each evaluation objective. Thus based on the different goals, there are totally 6 scenarios that can be compared. In the multi-objective problems proposed in this work, the leading objective can be completely satisfied and second objective can be mostly reached while the third objective only can be completed in part. Hence, leading objective plays a determining impact on the optimal tariff. In the end, three scenarios with completely different leading objectives are chosen as an explanation to investigate the effect of distance-based congestion pricing on the performance of the transportation system. These three scenarios are shown in Table 2.
Table 2 Description of different priority structure
When using goal programming to formulate the multi-objective problem, the target value provided by the decision maker has to be pre-defined. In this example, firstly three bi-level models with a single objective from section 4.1 are developed to obtain the optimal objective results in the upper level (social welfare, vehicular CO emissions and Gini coefficient), regardless of the other two objective functions. These three optimal objective results are considered the target value that needs to be achieved in the multi-objective bi-level problem as much as possible. In Table 3, column S0 shows the optimal results of each objective in solving the single objective bi-level model with distance-based toll charge function. After that, the multi-objective bi-level model is solved using the proposed solution algorithm based on the different priority structure and calculated results with each corresponding scenario are summarized in Table 3. Rows 2, 3 and 4 represent each objective value with different scenarios when the multi-objective bi-level model has been solved. Moreover, rows 5, 6 and 7 present the relative deviation, where positive numbers represent underachievement and negative numbers represent overachievement. Final row shows the objective function result in the upper level.
Taking scenario 1 (S1) as example to illustrate the meaning of each row specifically, here, S1, the leading goal is efficiency, followed by environment and equity. As mentioned earlier, social welfare is used instead of total travel time as the measurement of efficiency. The final result for social welfare is 5120909 and relative deviation is -0.01%, which means the target value is overachieved slightly. In the same way, the relative deviation of total vehicular CO emissions is 0.67%, which indicates that the target of environment improvement has been largely attained. However, when achieving the last goal, it is implied that nearly half of deviation from the target has not realized based on the value of 53.57%. From Table 3, it is concluded that the different priority structures will result in distinct solutions, which implies that the ranking structure of the goals has a significant effect on the model solutions. Comparing the solution with the rankings S1 and S2, we can observe that when the equity goal is placed in the last position, the efficiency and environment goals can nearly be achieved, but equity is still far away from the target value. However, comparing the solution of the S1 and S3 or S2 and S3, it is evident that the equity goal has been overachieved largely and simultaneously other goals are quite close to the targets, which is a more sustainable solution achieved by placing the equity goal into the leading position.
We now proceed to investigate the pattern of the optimal distance-based toll charge function. Figure 3 depicts the optimal chromosome outputs from three scenarios, which has 8 intervals and 9 boundary values. From Fig. 3, it is evident that the optimal distance-based toll charge function of each scenario is highly nonlinear. Additionally, when analyzing the results in Table 3, the toll charge function from S1 and S2 is slightly different from S3 as a result of the ranking of equity. The toll charges from the S1 and S2 both increase sharply as the distance traveled inside the pricing cordon is increased and the starting price is slightly higher when it is for short travel. In addition to short travel, the toll charge of S2 also increases distinctly when it is long travel. This kind of toll charge pattern can reduce the demand to help to improve the environment because a higher starting price and increase of tolls in long trips can stimulate road users forgoing the use of private cars and proceed to take public transport or make no trip. This can further alleviate total vehicular CO emissions. It proves that this toll charges scheme is more reasonable. Correspondingly, the toll charge pattern from S3 is opposite to S1 and S2. The toll charge with S3 increases mildly as the travel distance increases and is relatively close to the linear function because in S3 the leading goal is equity. It is prone to make public users accept this toll charge scheme.
Table 3 Computational profile of different scenarios to network C
Fig. 3 Optimal toll charge function for network C with three scenarios
The convergence results of the GA solution procedure are shown in Figs. 4 and 5. Figure 4 shows the convergence of the combined deviation of the three goals in the goal programming model. From Fig. 4, we can see that the combined deviations of S1 and S2 converge to a stable value in the 27th and 84th generations, respectively. S3 has a faster convergence rate compared with S1 and S2. Taking scenario 2 as example, Fig. 5 shows the effect of the user-specified priority structure in the GA. According to Fig. 5, the first and second goals are nearly achieved in the 83rd generation, while the third goal is largely not satisfied. The best goal obtained value in terms of the relative deviation for the third goal is 48.90% in the 18th generation. The first two goals (environment and efficiency) can be nearly satisfied, but the third goal (equity) is not fulfilled completely with a positive deviation of 48.90%. Moreover, when goals 1 and 2 approach to the target value simultaneously, the deviation value of goal 3 is initially decreased and then increased, which implies that when determining the multi-objective problem, the value of some goals may conflict with each other. Although the interval value in determining the nonlinear toll charge function is set to be constant in this work, different interval values can also have a great impact on the optimal distance-based toll charge function [7].
Fig. 4 Convergence curve of combined deviation
Fig. 5 Convergence curves of three goals in scenario 2
7 Conclusions
1) This work addresses the optimal distance-based toll charge design problem for the cordon-based congestion pricing scheme by considering three objectives. For the equity issue, Gini coefficient is adopted as the index of network equity level. A goal programming model is embedded into the bi-level model to convert the multi-objective problem into a single objective.
2) With the distance-based toll charge, a path-based DUE model with elastic demand is adopted for the users’ travel behavior. The distance-based toll charge function is allowed to be any positive and non-decreasing functional form, which makes the distance-based toll charge non-additive. Therefore, a path-based algorithm with k-shortest path is developed and a modified GA is designed to solve the multi-objective bi-level model. The methodology is verified by the numerical example. The output from the optimal distance-based toll charge function is distinctly nonlinear and it can fulfill the targets of the first and second goals provided by the decision-maker. The system deviation can be reduced to the minimum when the equity goal is placed in the first goal.
3) This work presents a multi-objective model for the optimal nonlinear distance tolls. Further works are needed to extend these methods to consider other practical issues such as dynamic traffic networks, heterogeneous or continuous values-of-time and multi-vehicle types.
References
[1] MAY A D, LIU R, SHEPHERD S P, SUMALEE A. The impact of cordon design on the performance of road pricing schemes [J]. Transport Policy, 2002, 9(3): 209-220.
[2] HO H W, Wong S C, Yang H, Loo B P Y. Cordon-based congestion pricing in a continuum traffic equilibrium system [J]. Transportation Research Part A: Policy and Practice, 2005, 39(7): 813-834.
[3] LIU Zhi-yuan, WANG Shuai-an, MENG Qiang. Toll pricing framework under logit-based stochastic user equilibrium constraints [J]. Journal of Advanced Transportation, 2013, 48(8): 1121-1137.
[4] LIU Zhi-yuan, WANG Shuai-an, MENG Qiang. Optimal joint distance and time toll for cordon-based congestion pricing [J]. Transportation Research Part B: Methodological, 2014, 69: 81-97.
[5] LIU Zhi-yuan, MENG Qiang, WANG Shuai-an. Speed-based toll design for cordon-based congestion pricing scheme [J]. Transportation Research Part C: Emerging Technologies, 2013, 31(2): 83-98.
[6] LIU Zhi-yuan, MENG Qiang. Bus-based park-and-ride system: a stochastic model on multimodal network with congestion pricing schemes [J]. International Journal of Systems Science, 2014, 45(5): 994-1006.
[7] MENG Qiang, LIU Zhi-yuan, WANG Shuai-an. Optimal distance tolls under congestion pricing and continuously distributed value of time [J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(5): 937-957.
[8] MAY A D, MILNE D S. Effects of alternative road pricing systems on network performance [J]. Transportation Research Part A: Policy and Practice, 2000, 34(6): 407-436.
[9] JOU R C, CHIOU Y C, CHEN K H, TAN H I. Freeway drivers’ willingness-to-pay for a distance-based toll rate [J]. Transportation Research Part A: Policy and Practice, 2012, 46(3): 549-559.
[10] LAWPHONGPANICH S, YIN Y. Nonlinear pricing on transportation networks [J]. Transportation Research Part C: Emerging Technologies, 2012, 20(1): 218-235.
[11] MENG Qiang, LIU Zhi-yuan. Impact analysis of cordon-based congestion pricing on mode-split for a bimodal transportation network [J]. Transportation Research Part C: Emerging Technologies, 2012, 21(1): 134-147.
[12] JOU R C, YEH Y C. Freeway passenger car drivers’ travel choice behaviour in a distance-based toll system [J]. Transport Policy, 2013, 27: 11-19.
[13] YANG Hai, HUANG Hai-jun. Mathematical and economic theory of road pricing [M]. Elsever, 2005.
[14] SANTOS G. The London congestion charging scheme [M]// Richardson H W, Bae C H C. Chapter 8: Road congestion pricing in Europe—implications for the United States. Edward Elgar Publishing, 2008: 159-175.
[15] MENG Qiang, YANG Hai. Benefit distribution and equity in road network design [J]. Transportation Research Part B: Methodological, 2002, 36(1): 19-35.
[16] YANG Hai, ZHANG Xiao-ning. Multiclass network toll design problem with social and spatial equity constraints [J]. Journal of Transportation Engineering, 2002, 128(5): 420-428.
[17] SUMALEE A, MAY T, SHEPHERD S. Comparison of judgmental and optimal road pricing cordons [J]. Transport Policy, 2005, 12(5): 384-390.
[18] MARUYAMA T, SUMALEE A. Efficiency and equity comparison of cordon and area-based road pricing schemes using a trip-chain equilibrium model [J]. Transportation Research Part A: Policy and Practice, 2007, 41(7): 655-671.
[19] YIN Y. Multiobjective bilevel optimization for transportation planning and management problems [J]. Journal of advanced transportation, 2002, 36(1): 93-105.
[20] CHEN A, SUBPRASOM K, JI Z. A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem [J]. Optimization and Engineering, 2006, 7(3): 225-247.
[21] SHARMA S, MATHEW T V. Multiobjective network design for emission and travel-time trade-off for a sustainable large urban transportation network [J]. Environment and Planning B: Planning and Design, 2011, 38(3): 520-538.
[22] CHEN A, XU X d. Goal programming approach to solve the stochastic multi-objective network design problem [M]. Network Reliability in Practice. New York: Springer, 2012: 151-170.
[23] YIN Y, LI Z C, LAM W H K, CHOI K. Sustainable toll pricing and capacity investment in a congested road network: A goal programming approach [J]. Journal of Transportation Engineering, 2014, 140(12): 04014062.
[24] WANG Shuai-an, MENG Qiang, YANG Hai. Global optimization methods for the discrete network design problem [J]. Transportation Research Part B: Methodological, 2013, 50(4): 42-60.
[25] SHEFFI Y. Urban transportation networks: equilibrium analysis with mathematical programming methods [M]. Prentice-Hall, 1985.
[26] JAYAKRISHNAN R, TSAI W T, PRASHKER J N, RAJADHYAKSHA S. A faster path-based algorithm for traffic assignment [J]. Transportation Research Reord, 1994, 1443: 75-83.
[27] CHEN A, JAYAKRISHNAN R. A path-based gradient projection algorithm: effects of equilibration with a restricted path set under two flow update policies [M]. Irvine: University of California, 1998.
[28] DIAL R B. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration [J]. Transportation Research Part B: Methodological, 2006, 40(10): 917-936.
[29] LO H K, CHEN A. Traffic equilibrium problem with route-specific costs: formulation and algorithms [J]. Transportation Research Part B: Methodological, 2000, 34(6): 493-513.
[30] CHEN A, ZHOU Z, XU X. A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem [J]. Computers & Operations Research, 2012, 39(2): 127-138.
[31] CHENG L, IIDA Y, UNO N, WANG W. Alternative quasi-newton methods for capacitated user equilibrium assignment [J]. Transportation Research Record, 2003, 1857: 109-116.
[32] SHARMA S, MISHRA S. Intelligent transportation systems-enabled optimal emission pricing models for reducing carbon footprints in a bimodal network [J]. Journal of Intelligent Transportation Systems, 2013, 17(1): 54-64.
[33] WALLACE C E, COURAGE K, REAVES D, SCHOENE G, EULER G. TRANSYT-7F user's manual [M]. Gainesville: University of Florida, 1984.
[34] SHEPHERD S, SUMALEE A. A genetic algorithm based approach to optimal toll level and location problems [J]. Networks and Spatial Economics, 2004, 4(2): 161-179.
[35] YANG Hai, ZHANG Xiao-ning, MENG Qiang. Modeling private highways in networks with entry–exit based toll charges [J]. Transportation Research Part B: Methodological, 2004, 38(3): 191-213.
(Edited by YANG Hua)
Foundation item: Projects(61304198, 61374195) supported by the National Natural Science Foundation of China; Projects(2013M530159, 2014T70351) supported by the China Postdoctoral Science Foundation
Received date: 2015-04-08; Accepted date: 2015-09-23
Corresponding author: BIE Yi-ming, Lecturer, PhD; Tel: +86-18345173755; E-mail: yimingbie@126.com