Transportation Research Part B 38 (2004) 1–15 www.elsevier.com/locate/trb
The multi-class, multi-criteria traffic network equilibrium and systems optimum problem Hai Yang
a,*
, Hai-Jun Huang
b
a
b
Department of Civil Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong School of Management, Beijing University of Aeronautics and Astronautics, Beijing 100083, China Received 9 April 2002; received in revised form 4 October 2002; accepted 12 October 2002
Abstract It is well known that in the standard traffic network equilibrium model with a single value of time (VOT) for all users, a so-called marginal-cost toll can drive a user equilibrium flow pattern to a system optimum. This result holds when either cost (money) or time units are used in expressing the objective function of the system optimum and the criterion for user equilibrium. This paper examines the multi-criteria or the costversus-time network equilibrium and system optimum problem in a network with a discrete set of VOTs for several user classes. Specifically, the following questions are investigated: Are the user-optimal flows dependent upon the unit (time or money) used in measuring the travel disutility in the presence of road pricing? Are there any uniform link tolls across all individuals (link tolls that are identical for all user classes) that can support a multi-class user equilibrium flow pattern as a system optimum when the system objective function is measured by either money or time units? What are the general properties of the valid toll set? Ó 2003 Elsevier Ltd. All rights reserved. Keywords: Road pricing; Network equilibrium; System optimum; Value of time; User heterogeneity
1. Introduction In recent years there has been considerable interest in network-optimized toll pricing subject to user equilibrium. Traffic flow distribution in the tolled network is forecasted using bi-criterion traffic assignment models in which users select their routes according to two criteria: travel time and travel cost (toll charge). Value of time (VOT) plays a central role in the bi-criterion network
*
Corresponding author. Tel.: +852-2358-7178; fax: +852-2358-1534. E-mail addresses:
[email protected] (H. Yang),
[email protected] (H.-J. Huang).
0191-2615/$ - see front matter Ó 2003 Elsevier Ltd. All rights reserved. doi:10.1016/S0191-2615(02)00074-7
2
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
equilibrium model and network performance evaluation because it describes how users make tradeoffs between cost and time in response to toll charges. Conventionally, VOTs are assumed to be identical for all users (homogeneous users). In the case of homogeneous users, the first-best congestion pricing theory, namely, the theory of marginal cost pricing is well established in general traffic networks. In line with this theory, a toll that is equal to the difference between the marginal social cost and the marginal private cost is charged on each link, so as to achieve a system optimum flow pattern in the network (Beckmann, 1965; Dafermos and Sparrow, 1971). Investigations have been conducted on how this classical economic principle would work in a general congested road network with queuing (Yang and Huang, 1998) and in a congested network in a stochastic equilibrium (Yang, 1999). In spite of its perfect theoretical basis, the principle of marginal cost pricing can be difficult to apply in real situations. Apart from public and political resistance, a primary reason is due to the high extra cost spent on the equipment for toll collection over the entire network. This has motivated a number of researchers to consider various forms of second-best pricing schemes where only a subset of links is subjected to toll charges. A typical simple example of the second-best pricing involves two parallel routes where an untolled alternative exists. This problem has been investigated in both static and dynamic situations by, for example, Braid (1996), Verhoef et al. (1996), Liu and McDonald (1999), and De Palma and Lindsey (2000). Optimal determination of tolls for a subset of links in a general network with fixed demand was studied by Yang and Lam (1996), with link flow restrictions (Ferrari, 1995; Yang and Bell, 1997; Larsson and Patriksson, 1998), and in private highway modeling (Yang and Meng, 2000; Yang and Woo, 2000). Simplified formulations and solutions of the second-best toll design problem in general networks are presented by Chen et al. (1999) and Yang and Zhang (2002). Methodologies are developed to extract congestion toll sets such that the tolled user equilibrium is system optimal. Because the link tolls that support the tolled user equilibrium as a system optimum are not unique, various secondary objectives such as revenue minimization are defined and optimized with respect to the set of all feasible link tolls (Bergendorff et al., 1997; Hearn and Ramana, 1998; Hearn and Yildirim, 1999; Dial, 1999c, 2000). Various extensions of optimal congestion road pricing have been made to transportation networks with multi-class users. It should be clarified that the term of multi-class users refers to two distinct situations in the literature. The first situation is that the flows in a transportation network are divided into different classes of vehicles or modes, each of which has an individual cost-flow function, and at the same time contributes to its own and other classÕs cost functions in an individual way. A classification of vehicle types could distinguish trucks and buses from cars; heavy vehicles from light ones; private transport from public transit, etc. Netter (1971), Dafermos (1973) and Smith (1979) studied the user equilibrium and system optimum problems with different vehicle types (or with link flow interactions). In this situation, congestion charges can be differentiated across user classes on the basis of their observable differences, and the marginal cost pricing theory can be applied to determine the first-best differentiated toll charges. A detailed discussion of congestion pricing on this type of multi-class user transportation networks is presented in Patriksson (1994) and Nagurney (1999). The second situation is that all users or drivers are assumed to use the same type of vehicles and to behave identically when using road facility, but users differ from one another in other, unobservable ways such as the value they place on time. In this situation, users are observationally indistinguishable and then congestion charge must be anonymous or uniform (Arnott and Kraus,
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
3
1998). In transportation analysis with such heterogeneous users in terms of different VOTs, various network equilibrium models are developed by assuming either with a discrete set of VOTs for several distinct user classes or by a continuously distributed VOT across the whole population (Leurent, 1993, 1996, 1998; Marcotte and Zhu, 2000; Nagurney, 2000). The optimal pricing problems for users with discrete or continuous VOT distributions are investigated by Dial (1999a,b), Florian (1998), Yang et al. (2002) and Yang and Zhang (2002). Here, it should be particularly mentioned that Dial (1999a,b) establishes a model and algorithm for determining a system-wide optimal set of tolls that induce traffic that is simultaneously user- and system-optimal. The model permits the VOT to be continuously distributed for each origin–destination (O–D) pair. Assuming each trip uses a path that minimizes its own particular perception of generalized cost, Dial demonstrates what economists have always known: to minimize the total perceived cost of time, the best toll for a link is its expected value of the social component of its marginal cost. In addition, Arnott and Kraus (also refer to Lindsey and Verhoef, 2001) have shown that first-best pricing remains possible using anonymous tolls with heterogeneous user groups provided that the tolls can be varied freely over time and the system objective function is measured in conventional unit of dollars. The optimality of anonymous tolling derives from the fact that the appropriate tolls depend only on the marginal externality costs that drivers impose and the congestion externality is anonymous at any departure time. Recently, Mayet and Hansen (2000) investigate second-best congestion pricing with continuously distributed VOT for a highway with an unpriced substitute, different optimal tolls are found depending on whether the social welfare function is measured in money or in time, and whether toll revenue is or is not included as part of the benefit. This paper examines the multi-class multi-criteria or cost versus time network equilibrium and system optimum problem in a network with a discrete set of VOTs for several user classes. Note that Ômulti-classÕ hereinafter exclusively refers to the second case of users with different VOTs rather than different types of vehicles. Because different classes of drivers make tradeoffs between time and money with different VOTs, we are naturally interested in the following questions: Are the user-optimal flows on the network dependent upon the units (time unit or money unit) used to measure the travel disutility in the presence of road pricing? Is there any uniform (anonymous) link toll pattern (all classes traveling on a given link are charged the same toll) that can support a multi-class user equilibrium flow pattern as a system optimum when the systemÕs objective function is measured either in money or time units? If yes, does the marginal cost pricing provide an optimal uniform toll pattern? Answers to these questions are well known for the standard traffic network equilibrium model with a single VOT for all users. Namely, marginal-cost link tolls can drive a user equilibrium flow pattern to a system optimum and this optimal road pricing result holds for either monetary or time units used in expressing the system objective function and user equilibrium criterion. Nevertheless, once we move to the multi-class bi-criterion traffic equilibrium models, answers to these questions are not obvious and their pursuit makes for very interesting theoretical investigations.
2. The multi-class network equilibrium problem Let G ¼ ðN ; AÞ be a directed transportation network defined by a set N of nodes and a set A of directed links. Each link a 2 A has an associated flow-dependent travel time, ta ðva Þ, that denotes
4
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
the travel time per unit flow or average travel time on each link. The travel time function, ta ðva Þ, a 2 A, is assumed to be differentiable, convex, and monotonically increasing with the amount of flow, va . Let sa denote the toll charged on link a 2 A, W denote the set of O–D pairs and Rw the set of all routes between the O–D pair w 2 W . The demand for travel is subdivided in to M classes corresponding to groups of users with different socio-economic characteristics (for example, income level). Let bm ðbm > 0Þ be the average VOT for users of class m and dwm be the demand for travel of class m between O–D pair w 2 W . For simplicity and clarity, we suppose dwm is given and fixed so we are dealing with the fixed-demand multi-class traffic network equilibrium problem. w 2 W isPassociated with a travel time, twr , and Each feasible route, r 2 Rw , between P O–D pair w r r travel (dollar) cost, cw , where tw ¼ a2A ta ðva Þdar and crw ¼ a2A sa dwar . Herein, dwar equals 1 if route r between O–D pair w 2 W uses link a 2 A, and 0 otherwise. Each user of class m with a VOT of bm is assumed to choose a route that minimizes travel disutility, gwr ðbm Þ. In the literature, gwr ðbm Þ has been conventionally specified as the generalized travel time (money is transferred into equivalent travel time) or generalized travel cost (travel time is transferred into equivalent amount of money): crw X sa r r ¼ ta ðva Þ þ ð1Þ dwar ; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M; gw ðbm Þtime ¼ tw þ bm b m a2A X fbm ta ðva Þ þ sa gdwar ; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M: ð2Þ gwr ðbm Þcost ¼ bm twr þ crw ¼ a2A
Now we consider the following minimization problem for any exogenously given link toll, sa , a 2 A: M XX X Z va 1 m ta ðxÞ dx þ v sa ð3Þ min f b a 0 a2A a2A m¼1 m X m s:t: frw ¼ dwm ; w 2 W ; m ¼ 1; 2; . . . ; M; ð4Þ r2Rw m frw P 0;
r 2 Rw ;
m frw
w2W;
m ¼ 1; 2; . . . ; M;
is the flow of user class m on route r 2 Rw , w 2 W , f ¼ where defined as XX m w vma ¼ frw dar ; a 2 A; m ¼ 1; 2; . . . ; M;
ð5Þ m ð. . . ; frw ; . . .Þ,
and
vma
and va are ð6Þ
w2W r2Rw
va ¼
M X
vma ;
a 2 A:
ð7Þ
m¼1
Eq. (4) presents the O–D demand conservation conditions for all classes of travel between all O–D pairs, Eq. (5) is a non-negativity constraint of path flows, and Eqs. (6) and (7) are link flow expressions for all network links. From the necessary optimality conditions of the above convex optimization problem, we can easily establish the following equilibrium relations in terms of the minimization of travel disutility in time units:
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
X sa w d ¼ gw ðbm Þtime ; bm ar a2A a2A X X sa w ta ðva Þdwar þ d P gw ðbm Þtime ; bm ar a2A a2A X
ta ðva Þdwar þ
5
m if frw > 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M;
ð8Þ
m if frw ¼ 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M;
ð9Þ
where gw ðbm Þtime is the Lagrange multiplier associated with Eq. (4) and equals the minimum travel disutility in time units (inclusive of equivalent time of toll charge) between O–D pair w by users of class m. Multiplying both sides of Eqs. (8) and (9) by bm ðbm > 0Þ, we have X
bm ta ðva Þdwar þ
X
a2A
a2A
X
X
a2A
bm ta ðva Þdwar þ
sa dwar ¼ bm gw ðbm Þtime ;
m if frw > 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M;
ð10Þ sa dwar P bm gw ðbm Þtime ;
m if frw ¼ 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M:
a2A
ð11Þ Clearly, these are the multi-class network equilibrium conditions on the basis of generalized travel cost in monetary units. We thus conclude that: the optimization problem (3)–(7) leads to a multiclass network equilibrium in terms of either generalized travel time given by Eq. (1) or generalized travel cost given by Eq. (2). It should be particularly pointed out that the above equivalence of the time-based and the money-based equilibrium problems is true for the case when travelers of each class have a constant VOT or value of travel time changes linearly (but different VOTs for different traveler classes). When travelers of any classes have a nonlinear VOT or value of travel time changes nonlinearly, the time-based and the money-based equilibrium problem does not necessarily give the same equilibrium solution. This non-equivalence in the case of nonlinear VOTs has been demonstrated recently by Larsson et al. (2002). The conventional Frank–Wolf algorithm (Sheffi, 1985) can be easily applied to solve the above multi-class network equilibrium problem. It is worthwhile to point out that the flows by class, vma , m , because the objective function is not strictly convex are not unique, nor are the path flows, frw with respect to the two sets of variables, but the total link flows, va , are indeed unique. Also, note that the link travel time functions, ta ðva Þ, a 2 A, are relatively simple in our formulation, since they do not model asymmetric travel times due to different vehicle types. If more complex functions were used, the resulting multi-class model would be considerably more complex and would require the solution of a variational inequality (see Nagurney, 2000).
3. System optimum and optimal link toll For users with a single VOT, problem (3)–(7) collapses to the standard traffic network problem. It is well known that the marginal-cost link toll, sa ¼ bva ta0 ðva Þ, evaluated at the system optimum link flow, va , a 2 A, can support a system optimum (SO) as a user equilibrium (UE) flow pattern.
6
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
The SO here refers to the minimization of total travel disutility that can be measured in terms of either time or monetary units. We now seek optimal tolls for achieving a system optimum when allowing multiple classes of users with distinct VOT considered here. We are naturally interested in the following questions. Is there a uniform link toll pattern that can support a multi-class traffic network equilibrium as a system optimum? If yes, does such link toll pattern depend on the criterion or the unit (time or money) that defines the total travel disutility for the system optimum? 3.1. System optimum in cost units We now consider the SO in cost (monetary) units, allowing for multiple classes of users with distinct VOTs. The minimization of total system travel disutility measured in terms of monetary unit can be formulated as the following minimization problem: min f
M XX
bm ta ðva Þvma
ð12Þ
a2A m¼1
s:t:
ð4Þ–ð7Þ:
From the first-order optimality condition, the above minimization problem can be easily shown to lead to the following relationships: ) ( M X X k dta ðva Þ dwar ¼ gwso ðbm Þcost ; bm ta ðva Þ þ bk va dv a a2A k¼1 m > 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M if frw ) ( M X X dt ðv Þ a a dwar P gwso ðbm Þcost ; bm ta ðva Þ þ bk vka dv a a2A k¼1 m ¼ 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M if frw
ð13Þ
ð14Þ
Let sso a ¼
M X
bm vma
m¼1
dta ðva Þ ; dva
a 2 A:
Then, we have sso a ¼
! M X vma dta ðva Þ va b ; dva v m m¼1 a
a 2 A:
ð15Þ
Clearly, the optimality conditions (13) and (14) for the cost-based SO (12) can be regarded as the network equilibrium conditions in cost units and gwso ðbm Þcost is the corresponding minimum O–D travel cost. The only requirement for such an equilibrium is that, for each network link, each user of all classes m ðm ¼ 1; 2; . . . ; MÞ traversing link a 2 A should be charged a toll given by Eq. (15) in addition to his/her actual experienced, class-dependent travel time cost, bm ta ðva Þ (in monetary units).
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
7
Note that, in link toll (15), va dta ðva Þ=dva is the externality measured in time units which is the additional travel time that a marginal user imposes on others already traveling on link a 2 A. This travel time externality is identical for all classes of users. The resultant toll charge is uniform and equal to this common travel time externality multiplied by the average VOT of all users traversing the link: b^so a ¼
M X vma b ; v m m¼1 a
a 2 A:
ð16Þ
The mean VOT in Eq. (16) is link dependent and is the arithmetic mean of the VOTs of all users using link a 2 A. In summary, we find that: a cost-based SO in terms of total system travel disutility in monetary unit can be supported or decentralized as a multi-class network equilibrium by a uniform link toll pattern across all classes of users. The link toll is equal to the user externality of travel time multiplied by the arithmetic mean of the VOTs of all users traversing that link. Note that the link flow pattern, vma , a 2 A, m ¼ 1; 2; . . . ; M, used for determination of link tolls in Eq. (16) is the SO flow pattern in (12). Due to the non-uniqueness of link flows by class, the resulting externality-based uniform link tolls are not unique. Incidentally, the SO model (12) which has strictly convex objective function with linear constraints, can be solved using any algorithm used in solving network equilibrium problems with multiple user classes. The only modification is to use the link marginal-cost function instead of the link average-cost function. 3.2. System optimum in time units We next consider the following system optimum in time units and see how it leads to a different result: ( ) M X XX vma ta ðva Þ ¼ va ta ðva Þ ð17Þ min f
s:t:
a2A m¼1
a2A
ð4Þ–ð7Þ:
Problem (17) is strictly convex program under our prior assumptions on the link cost functions, the first-order necessary optimality conditions are given by X dta ðva Þ w m ta ðva Þ þ va > 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M; dar ¼ gwso ðbm Þtime ; if frw dv a a2A X a2A
ta ðva Þ þ va
dta ðva Þ w dar P gwso ðbm Þtime ; dva
ð18Þ m if frw ¼ 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M:
ð19Þ Similarly, the optimality conditions (18) and (19) for time-based SO (17) can be regarded as the network equilibrium conditions in time units, with gwso ðbm Þtime being the corresponding minimum O–D travel time. As seen from Eqs. (18) and (19), gwso ðbm Þtime is identical for all user classes
8
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
m ¼ 1; 2; . . . ; M travailing between the same O–D pair w 2 W . The requirement for such equilibrium is that each user should face a marginal social travel time consisting of a private or experienced travel time and a travel time externality common to all users when using each link in the network. As we can see, the above link travel time externality is anonymous, but can be internalized only when the toll charge for each link is differentiated according to each userÕs VOT: dta ðva Þ ; dva
sso a;m ¼ bm va
a 2 A; m ¼ 1; 2; . . . ; M:
ð20Þ
This discriminatory link toll pattern is of course unrealistic and difficult, if not impossible, to implement in reality because users differ from one another in an observationally indistinguishable way. Given the impossibility of introducing a discriminatory link toll pattern (20) for various user classes for achieving an exact time-based SO, we naturally wonder whether there exists an alternative uniform link toll pattern to support a multi-class network equilibrium as a time-based SO. We note that for the single class case as examined by Bergendorff et al. (1997) and Hearn and Yildirim (1999), the set of all link tolls to decentralize the conventional system optimum can be characterized by a non-empty polyhedron expressed in terms of a linear inequality and equality system and thus alternative toll patterns for a secondary optimization criterion can be easily found. Nevertheless, for the present multi-class user equilibrium problem, existence and selection of a uniform link toll pattern for supporting a multi-class UE as a SO in terms of total travel time minimization is not evident and straightforward. Let va , a 2 A be the link flow solution of the time-based SO (17), and ta ¼ ta ðva Þ, a 2 A be the corresponding link travel time at SO. Under our aforementioned assumption of increasing convex link cost functions, the time-based SO link flows va and hence link travel time ta , a 2 A, are uniquely given. We now begin to seek a uniform link toll pattern to decentralize this unique timebased SO as a multi-class bi-criteria UE. Consider the following linear programming (LP) problem: M XX bmta vma ð21Þ min f
s:t:
a2A m¼1 M X X X
m w frw dar ¼ va ;
a 2 A;
ð22Þ
m¼1 w2W r2Rw
X
m frw ¼ dwm ;
w 2 W ; m ¼ 1; 2; . . . ; M;
ð23Þ
r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M:
ð24Þ
r2Rw m frw P 0;
The dual formulation of the above LP problem is given by M XX X v a ka þ dwm lmw max k;l
s:t:
a2A
lmw þ
X a2A
ð25Þ
w2W m¼1
ka dwar 6
X a2A
bmta dwar ;
r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M;
ð26Þ
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
9
where the dual variables, k ¼ ð. . . ; ka ; . . .Þ and l ¼ . . . ; lmw ; . . . are associated with the equality constraints (22) and (23), respectively, and ka and lmw are unrestricted in sign. Note that the set of feasible solutions to the LP problem (21)–(24) is not empty, since the link flow solutions, va , a 2 A, of the time-based SO (17) are at least feasible to this LP problem. Hence, both original and dual problems have solutions. Let sa replace ðka Þ, a 2 A and rewrite Eq. (26) as o Xn bmta þ sa dwar P lmw ; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M: ð27Þ a2A
According to the duality theory, at the optimal points of the original and dual problems the following complementary slackness conditions hold: ( ) X m bmta þ sa dwar lmw frw ¼ 0; r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M; ð28Þ a2A
X ðbmta þ sa Þdwar lmw P 0;
r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M:
ð29Þ
a2A
The above conditions can be regarded as the multi-class user equilibrium conditions in cost units, with lmw being the corresponding minimum O–D travel cost. The dual variable, ka , can be interpreted as a shadow price, i.e., an additional cost implied by the need for consistency between the link flows generated by the time-based SO (17) and used in the LP problem (21)–(24). If sa is positive (or ka is negative), users traversing link a 2 A are charged by a toll equal to sa , and otherwise subsidized with sa . Therefore, we conclude that if the link travel cost perceived by the individual user is modified by charging or subsidizing an amount of money, sa , a 2 A, given by the solution of the dual problem (25) and (26), then a new network equilibrium is established. This new equilibrium is precisely a time-based SO in the sense that the same system optimal link flows, va , a 2 A, (and hence the same link travel times, ta ¼ ta ðva Þ, a 2 A) are reproduced. In summary, we have the following observation: A time-based SO of minimizing the system travel disutility measured in time unit, can be supported as a multi-class network equilibrium by a uniform link toll pattern across user classes. The toll is given as the solution of the dual LP problem (25) and (26) and can be positive (charge) or negative (subsidy) to link users. Note that the Lagrange multipliers sa (or ka ) and lw satisfying (28) and (29) may not be unique. The valid feasible set of sa , a 2 A and the corresponding O–D cost lw , w 2 W can be alternatively written as the following polyhedron consisting of a system of linear equality and inequalities: X a2A
X a2A
sava ¼
M XX
dwm lmw
w2W m¼1
sa dwar P lmw
X
M XX
bmta vma ;
ð30Þ
a2A m¼1
bmta dwar ;
r 2 Rw ; w 2 W ; m ¼ 1; 2; . . . ; M:
ð31Þ
a2A
Eq. (30) follows directly from the duality theory that the dual linear program has the same optimal objective value as the primal one, and Eq. (31) is simply an altered form of the dual feasibility constraint. Thus, Eqs. (30) and (31) are both necessary and sufficient to characterize the
10
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
dual optimal solutions. Note that the right-hand side of Eq. (30) is in fact the total revenue collected from toll charge. In reality, negative tolls or subsidies on road networks are difficult and seldom implemented by policy makers, and thus an optimal toll pattern with all link tolls being positive is more meaningful and acceptable to the policy makers. We note that the solution of a LP problem (including the dual problem) is not necessarily unique; this means that in certain cases, we are likely to obtain a uniform positive link toll pattern from the set of feasible solutions of the dual LP problem (25) and (26). This is indeed possible by modifying the primal LP problem (21)–(24) slightly. Consider a slightly modified version of the primal LP problem (21)–(24) with the equality constraints (22) replaced by the following inequality constraints: M X X X
m w frw dar 6 va ;
a 2 A:
ð32Þ
m¼1 w2W r2Rw
Because the constraints (32) are a simple relaxation of constraints (22) and other constraints remain unchanged, the feasible region of the new LP problem is expanded and hence nonempty. This means that the new LP problem and its dual problem have solutions. The dual formulation is given by (25) and (26) and the following additional constraints: ka 6 0;
a 2 A;
ð33Þ
where the dual variables ka , a 2 A are associated with the inequality constraints (32). Thus, Eq. (33) guarantees that the link tolls to be charged (i.e., sa ¼ ka , a 2 A) are always nonnegative. We still have to show that the modified LP also leads to a SO flow pattern at the optimum point. It suffices to prove that, at the optimum solution, constraints (32) are always binding or hold with strict equality for all a 2 A. Suppose there is a link b 2 A for which vb < vb , by monotonicity cost function we have tb ðvb Þ < tb ðvb Þ and hence tb ðvb Þvb < tb ðvb Þvb . We then P of the linkP have a2A ta ðva Þva < a2A ta ðva Þva . This can never occur since va , a 2 A is the unique optimum solution of the total travel time minimization problem (17) for given O–D demand dwm , w 2 W , m ¼ 1; 2; . . . ; M. Therefore, at the optimum of the modified LP problem, va ¼ va , a 2 A, is guaranteed.
4. A simple example Now we present a simple example to further elaborate the above conclusion. Fig. 1 shows a network consisting of four nodes and five directed links. The link cost functions are given by t1 ¼ 20 þ 2v1 ;
t2 ¼ v2 ;
t3 ¼ v3 ;
t4 ¼ 20 þ v4 ;
t5 ¼ 2v5 :
There are two classes of travelers with different values of time, class 1 consists of travelers with a lower value of time of 1.0 (HKD/min) (denoted by ‘‘C1’’) and class 2 consists of travelers with a higher value of time of 2.0 (HKD/min) (denoted by ‘‘C2’’). There are two O–D pairs for each class, one is from node 1 to node 4 (denoted by ‘‘a’’) and the other from node 2 to node 4 (denoted by ‘‘b’’). The demand for each traveler class between each O–D pair is daC1 ¼ 10, daC2 ¼ 10, dbC1 ¼ 20 and dbC2 ¼ 10. There are two paths connecting each O–D pair. For O–D pair a, path 1 (denoted
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
11
Fig. 1. An example to explain the multi-class, multi-criteria UE and SO problem.
by ‘‘1; a’’) includes link 1 only and path 2 (denoted by ‘‘2; a’’) includes links 2 and 3. For O–D pair b, path 1 (denoted by ‘‘1; b’’) includes links 3 and 4 and path 2 (denoted by ‘‘2; b’’) includes link 5 only. For system optimum in terms of minimization of total travel time, the optimal link flows are v1 ¼ 10, v2 ¼ 10, v3 ¼ 20, v4 ¼ 10, v5 ¼ 20, and the corresponding link travel times are t1 ¼ 40, t2 ¼ 10, t3 ¼ 20, t4 ¼ 30, t5 ¼ 40. The corresponding LP problem (21)–(24) is formulated as follows: min
C1 C2 C1 C2 C1 C1 C2 C2 C1 C2 40ðf1;a þ 2f1;a Þ þ 10ðf2;a þ 2f2;a Þ þ 20ðf2;a þ f1;b þ 2f2;a þ 2f1;b Þ þ 30ðf1;b þ 2f1;b Þ C1 C2 þ 2f2;b Þ þ 40ðf2;b
s:t:
C1 C2 þ f1;a ¼ 10 f1;a C1 C2 þ f2;a ¼ 10 f2;a C1 C2 C1 C2 þ f2;a þ f1;b þ f1;b ¼ 20 f2;a C1 C2 þ f1;b ¼ 10 f1;b C1 C2 þ f2;b ¼ 20 f2;b C1 C1 þ f2;a ¼ 10 f1;a C2 C2 þ f2;a ¼ 10 f1;a C1 C1 þ f2;b ¼ 20 f1;b C2 C2 þ f2;b ¼ 10 f1;b C1 C2 C1 C2 C1 C2 C1 C2 ; f1;a ; f2;a ; f2;a ; f1;b ; f1;b ; f2;b ; f2;b P 0: f1;a
C1 C2 C1 C2 C1 C2 C1 ¼ 10, f1;a ¼ 0, f2;a ¼ 0, f2;a ¼ 10, f1;b ¼ 10, f1;b ¼ 0, f2;b ¼ 10, The optimal solution is f1;a C2 f2;b ¼ 10. And the minimal value of the objective function is 2700.
12
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
The dual problem of the above linear program is formulated as follows: max
C2 C1 C2 10k1 þ 10k2 þ 20k3 þ 10k4 þ 20k5 þ 10lC1 a þ 10la þ 20lb þ 10lb
s:t:
lC1 a þ k1 6 40 lC1 a þ k2 þ k3 6 30 lC2 a þ k1 6 80 lC2 a þ k2 þ k3 6 60 lC1 b þ k3 þ k4 6 50 lC1 b þ k5 6 40 lC2 b þ k3 þ k4 6 100 lC2 b þ k5 6 80:
The maximal value of the objective function is 2700, which is equal to the minimal value of the objective function in the primal problem. But the solution of the variables is not unique, and the solution set is made up of the following equations: lC1 a þ k1 ¼ 40 lC1 a þ k2 þ k3 6 30 lC2 a þ k1 6 80 lC2 a þ k2 þ k3 ¼ 60 lC1 b þ k3 þ k4 ¼ 50 lC1 b þ k5 ¼ 40 lC2 b þ k3 þ k4 6 100 lC2 b þ k5 ¼ 80: After simplification by eliminating l and substituting k with s, the set of valid tolls supporting the multi-class, bi-criteria equilibrium as a system optimum is given below: 10 6 s2 þ s3 s1 6 20 s5 s3 s4 ¼ 10: To seek a set of positive link tolls supporting the multi-class, bi-criteria equilibrium as a system optimum, the first five equality constraints of the primal linear program are replaced by the following five inequalities: C1 C2 þ f1;a 6 10 f1;a C1 C2 f2;a þ f2;a 6 10 C1 C2 C1 C2 f2;a þ f2;a þ f1;b þ f1;b 6 20 C1 C2 f1;b þ f1;b 6 10 C1 C2 f2;b þ f2;b 6 20:
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
13
Correspondingly, an additional constraint is imposed in the dual problem as below: k1 ; k2 ; k3 ; k4 ; k5 6 0: Solving the revised primal problem, the same path flows for each class are obtained. And based on the revised dual problem, the set of positive valid link tolls is given by the linear equality and inequalities and nonnegative constraints: 10 6 s2 þ s3 s1 6 20 s5 s3 s4 ¼ 10; s1 ; s2 ; s3 ; s4 ; s5 P 0: 5. Conclusions This paper provides a preliminary theoretical investigation of the multi-criteria or cost-versustime network equilibrium and system optimum problem in a network with a discrete set of VOTs for several user classes. We conclude that, in the presence of road pricing, the same multi-class network equilibrium flow is obtained whenever the generalized travel cost is measured in cost or time units. There exists a uniform link toll pattern that supports a cost-based system optimum as a multi-class user equilibrium flow pattern. The link toll is equal to the user externality of travel time multiplied by the arithmetic mean of the VOTs of all users traversing that link. There also exits a uniform link toll pattern that supports a multi-class user equilibrium flow pattern as a timebased system optimum. However, the uniform link toll in this case is not based on the user externality, but can be determined from the solution of a linear dual problem and can be either a charge or a subsidy to link users. We further show that there exist positive uniform link tolls that can support a multi-class user equilibrium flow pattern as a time-based system optimum. Acknowledgements The authors thank Robin Lindsey of University of Alberta for his useful comment on an earlier version of the paper. Thanks also go to Xiaoning Zhang of the Hong Kong University of Science and Technology for his assistance in preparing the example. This study was supported by grants from the Research Grants Council of the Hong Kong Special Administrative Region (project no. HKUST6203/99E) and the National Natural Science Foundation of China (project no. 79825001). References Arnott, R., Kraus, M., 1998. When are anonymous congestion charges consistent with marginal cost pricing? Journal of Public Economics 67, 45–64. Beckmann, M.J., 1965. On optimal tolls for highways, tunnels and bridges. In: Vehicular Traffic Science. American Elsevier, New York, pp. 331–341. Bergendorff, P., Hearn, D.W., Ramana, M.V., 1997. Congestion toll pricing of traffic networks. In: Pardalos, P.M., Hearn, D.W., Hager, W.W. (Eds.), Network Optimization. Lecture Notes in Economics and Mathematical Systems (Springer-Verlag series), pp. 51–71.
14
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
Braid, R.M., 1996. Peak-load pricing of a transportation route with an unpriced substitute. Journal of Urban Economics 40, 179–197. Chen, M., Bernstein, D., Chien, S., Mouskos, K., 1999. Simplified formulation of the toll design problem. Transportation Research Record 1667, 88–95. Dafermos, S.C., 1973. The traffic assignment problem for multi-class user transportation networks. Transportation Science 6, 73–87. Dafermos, S.C., Sparrow, F.T., 1971. Optimal resource allocation and toll patterns in user-optimized transportation network. Journal of Transportation Economics and Policy 5, 198–200. De Palma, A., Lindsey, R., 2000. Private toll roads: competition under various ownership regimes. Annals of Regional Science 34, 13–35. Dial, R.B., 1999a. Network-optimized road pricing. Part 1: a parable and a model. Transportation Science 47, 54–64. Dial, R.B., 1999b. Network-optimized road pricing. Part 2: algorithms and examples. Transportation Science 47, 327–336. Dial, R.B., 1999c. Minimal-revenue congestion pricing. Part I: a fast algorithm for the single-origin case. Transportation Research 33B, 189–202. Dial, R.B., 2000. Minimal-revenue congestion pricing. Part II: an efficient algorithm for the general case. Transportation Research 34B, 645–665. Ferrari, P., 1995. Road pricing and network equilibrium. Transportation Research 29B, 357–372. Florian, M., 1998. Network equilibrium models for analyzing toll highways. In: Proceedings of the International Conference on Transportation into the Next Millenium. September 1998, Singapore. Hearn, D.W., Ramana, M.V., 1998. Solving congestion toll pricing models. In: Marcotte, P., Nguyen, S. (Eds.), Equilibrium and Advanced Transportation Modeling. Kluwer Academic Publishers, pp. 109–124. Hearn, D.W., Yildirim, M.B., 1999. A toll pricing framework for traffic assignment problem with elastic demand. In: Gendreau, M., Marcotte, P. (Eds.), Current Trends in Transportation and Network Analysis––Papers in Honour of Michael Florian (forthcoming). Kluwer Academic Publishers, Norwell, MA. Larsson, T., Lindeberg, P.O., Patriksson, M., Rydergren, C., 2002. On traffic equilibrium models with a nonlinear time/ money relation. In: Patriksson, M., Labbe, M. (Eds.), Transportation Planning: State of the Art. Kluwer Academic Publishers, pp. 19–31. Larsson, T., Patriksson, M., 1998. Side constrained traffic equilibrium models––traffic management through link tolls. In: Marcotte, P., Nguyen, S. (Eds.), Equilibrium and Advanced Transportation Modeling. Kluwer Academic Publishers, pp. 125–151. Leurent, F., 1993. Cost versus time equilibrium over a network. European Journal of Operational Research 71, 205–221. Leurent, F., 1996. The theory and practice of a dual criteria assignment model with a continuously distributed value-oftime. In: Lesort, J.B. (Ed.), Transportation and Traffic Theory. Pergamon, Exeter, pp. 455–477. Leurent, F., 1998. Sensitivity and error analysis of the dual criteria traffic assignment model. Transportation Research 32B, 189–204. Lindsey, R., Verhoef, E.T., 2001. Traffic congestion and congestion pricing. In: Button, K.J., Hensher, D.A. (Eds.), Handbook of Transport Systems and Traffic Control Button. Elsevier Science, Oxford, pp. 77–104. Liu, L.N., McDonald, F., 1999. Economic efficiency of second-best congestion pricing schemes in urban highway systems. Transportation Research 33B, 157–188. Mayet, J., Hansen, M., 2000. Congestion pricing with continuously distributed values of time. Journal of Transport Economics and Policy 34, 359–370. Marcotte, P., Zhu, D.L., 2000. Equilibria with infinitely many differentiated classes of customers. In: Ferris, M.C., Pang, J.S. (Eds.), Complementarity and Variational Problems––State of the Art. SIAM, Philadelphia, PA. Nagurney, A., 1999. Network Economics: A Variational Inequality Approach, second and revised edition Kluwer Academic, Dordrecht, The Netherlands. Nagurney, A., 2000. A multiclass, multicriteria traffic network equilibrium model. Mathematical and Computer Modeling 32, 393–411. Netter, M., 1971. Equilibrium and marginal cost pricing on a road network with several traffic flow types. Proceedings of the 5th International Symposium on Transportation and Traffic Theory, Berkeley.
H. Yang, H.-J. Huang / Transportation Research Part B 38 (2004) 1–15
15
Patriksson, M., 1994. The Traffic Assignment Problem: Models and Methods. VSP, Utrecht, The Netherlands. Sheffi, Y., 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Englewood Cliffs, NJ. Smith, M.J., 1979. The marginal cost taxation of a transportation network. Transportation Research 13B, 237–242. Verhoef, E.T., Nijkamp, P., Rietveld, P., 1996. Second-best congestion pricing: The case of an untolled alternative. Journal of Urban Economics 40, 279–302. Yang, H., 1999. System optimum, stochastic user equilibrium and optimal link tolls. Transportation Science 33, 354– 360. Yang, H., Bell, M.G.H., 1997. Traffic restraint, road pricing and network equilibrium. Transportation Research 31B, 303–314. Yang, H., Huang, H.J., 1998. Principle of marginal-cost pricing: How does it work in a general network? Transportation Research 32A, 45–54. Yang, H., Lam, W.H.K., 1996. Optimal road tolls under conditions of queuing and congestion. Transportation Research 30A, 319–332. Yang, H., Meng, Q., 2000. Highway pricing and capacity choice in a road network under a build-operate-transfer scheme. Transportation Research 34A, 207–222. Yang, H., Tang, W.H., Cheung, W.M., Meng, Q., 2002. Profitability and welfare gain of private toll roads with heterogeneous users. Transportation Research 36A, 537–554. Yang, H., Woo, K.K., 2000. Competition and equilibria of private toll roads in a traffic network. Transportation Research Record 1733, 15–22. Yang, H., Zhang, X., 2002. Multiclass network toll design problem with social and spatial equity constraints. Journal of Transportation Engineering 128, 420–428.
