03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

This article was downloaded by: [Monash University Library] On: 26 October 2014, At: 18:03 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UK

Transportmetrica

Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/ttra20

C-logit stochastic user equilibrium model: formulations and solution algorithm

Zhong Zhou , Anthony Chen & Shlomo Bekhor

a b a b c

Citilabs , 1040 Marina Village Parkway, Alameda, CA 94501, USA

Department of Civil and Environmental Engineering , Utah State University , Logan, UT 84322-4110, USA

c

Faculty of Civil and Environmental Engineering , Technion – Israel Institute of Technology , Haifa 32000, Israel Published online: 17 Nov 2010.

To cite this article: Zhong Zhou , Anthony Chen & Shlomo Bekhor (2012) C-logit stochastic user equilibrium model: formulations and solution algorithm, Transportmetrica, 8:1, 17-41, DOI: 10.1080/18128600903489629 To link to this article: http://dx.doi.org/10.1080/18128600903489629

PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms &

Conditions of access and use can be found at http://www.tandfonline.com/page/termsand-conditions

Downloaded by [Monash University Library] at 18:03 26 October 2014

Transportmetrica Vol. 8, No. 1, January 2012, 17–41

C-logit stochastic user equilibrium model: formulations and solution algorithm

Zhong Zhoua, Anthony Chenb* and Shlomo Bekhorc

a

Downloaded by [Monash University Library] at 18:03 26 October 2014

Citilabs, 1040 Marina Village Parkway, Alameda, CA 94501, USA; bDepartment of Civil and Environmental Engineering, Utah State University, Logan, UT 84322-4110, USA; cFaculty of Civil and Environmental Engineering, Technion – Israel Institute of Technology, Haifa 32000, Israel (Received 29 December 2008; final version received 14 November 2009)

This article considers the stochastic user equilibrium (SUE) problem with the route choice model based on the C-logit function. The C-logit model has a simple closed-form analytical probability expression and requires relatively lower calibration efforts and represents a more realistic route choice behaviour compared with the multinomial logit model. This article proposes two versions of the C-logit SUE model that captures the route similarity using different attributes in the commonality factors. The two versions differ with respect to the independence assumption between cost and flow. The corresponding stochastic traffic equilibrium models are called the length-based and congestion-based C-logit SUE models, respectively. To formulate the length-based C-logit SUE model, an equivalent mathematical programming formulation is proposed. For the congestion-based C-logit SUE model, we provide two equivalent variational inequality formulations. To solve the proposed formulations, a new self-adaptive gradient projection algorithm is developed. The proposed formulations and new solution algorithm are tested in two well-known networks. Numerical results demonstrate the validity of the formulations and solution algorithm. Keywords: stochastic user equilibrium; C-logit; mathematical program; variational inequality; gradient projection

1. Introduction Consider a strongly connected network [N, A], where N and A denote the sets of nodes and links, respectively. Let R and S denote the subsets of N for which nonnegative travel demand q rs is generated from origin r 2 R to destination s 2 S, fhrs denotes the flow on rs route h 2 H rs , where H rs is a set of routes from origin r to destination s, and D ? ?ha ? rs denotes the route-link incidence matrix, where ha ? 1 if route h from origin r to destination s uses link a, and 0, otherwise. Then, we have the following relationships: X q rs ? fhrs , 8r 2 R, s 2 S, ?1?

h2H rs

*Corresponding author. Email: achen@engineering.usu.edu

ISSN 1812–8602 print/ISSN 1944–0987 online ? 2012 Hong Kong Society for Transportation Studies Limited http://dx.doi.org/10.1080/18128600903489629 http://www.tandfonline.com

18 va ?

Z. Zhou et al. XX X

r2R s2S h2H rs rs fhrs ha ,

8a 2 A,

?2?

fhrs ! 0,

8h 2 H rs , r 2 R, s 2 S,

?3?

Downloaded by [Monash University Library] at 18:03 26 October 2014

where (1) is the travel demand conservation constraint; (2) is a definitional constraint that sums up all route flows that pass through a given link a, and va represents the corresponding flow on link a and (3) is a non-negativity constraint on the route rs denote the cost on route h between O-D pair (r, s), rs denote the minimal flows. Let ch rs , . . .?T . Thus, cost between O-D pair (r, s) and f denote a vector of route flows ?. . . , fh the deterministic user equilibrium (DUE) problem is to find a route-flow pattern, f ? , such that, for each route h 2 H rs between every O-D pair (r, s), the following conditions hold: ( ? 0 if ? fhrs ?? 4 0 rs ? rs ?4? ch ? f ? ? , 8h 2 H rs , r 2 R, s 2 S: ! 0 if ? fhrs ?? ? 0 These conditions represent Wardrop’s first principle: all of the used routes have equal and minimum travel cost, and all of the unused routes have equal or higher travel costs (Wardrop, 1952). The basic assumption of the DUE model is that each traveler has perfect knowledge of network conditions and accordingly chooses the route to minimise his or her travel cost. However, this assumption cannot always be assumed to hold even approximately in practise. To relax this assumption, Daganzo and Sheffi (1977) made a distinction between the travel cost that individuals perceive and the actual travel cost, and stated the stochastic user equilibrium (SUE) principle that no traveler can improve his or her perceived travel cost by unilaterally changing routes. The route choice process in this case is probabilistic rather than deterministic, and the route choice model is derived by assuming a random component associated with the travel cost:

rs rs rs ? ch ? h , Ch

8r 2 R, s 2 S, h 2 H rs ,

?5?

rs rs is the perceived travel cost on route h of O-D pair (r, s), h is a random term where Ch rs with E?h ? ? 0 that represents the traveler’s perception error. Using the perceived travel cost concept, the SUE conditions can be characterised by the following equation (e.g. Sheffi, 1985): rs rs ? q rs Ph , fh

8r 2 R, s 2 S, h 2 H rs ,

?6?

rs is the probability that route h between O-D pair (r, s) is chosen by travelers. where Ph In this case, the equilibrium model is dependent on not only the congestion effect but also the stochastic effect which accounts for the behavioural route choice model associated with the distribution of the random terms. An equivalent unconstrained optimisation formulation for the SUE problem was provided by Daganzo (1982) under a general distribution assumption of random terms. Among various route choice models proposed in the literature, the most popular models are the multinomial logit (MNL) model and the multinomial probit (MNP) model. Under the assumption that the random terms are independently and identically distributed (IID) Gumbel variates, the MNL SUE model

Transportmetrica gives a closed-form expression of route choice probabilities:

rs Ph ?P

19

fhrs

l2H rs

flrs

?P

e?ch , ?clrs l2H rs e

rs

8r 2 R, s 2 S, h 2 H rs ,

?7?

where is a positive parameter, which is inversely proportional to the perception variance and describes the degree of dispersion of the network. It allows efficient calibration procedure (e.g. Ben-Akiva and Lerman, 1985) and solution algorithms with implicit route enumeration (e.g. Dial 1971, 2001, Maher 1998). Furthermore, by assuming link separable property, Fisk (1980) showed that the model can be formulated as an equivalent mathematical programming formulation. This MNL SUE model has been adopted as a path flow estimator for estimating path flows (hence origin-destination flows) from traffic counts by various researchers (Bell and Shield 1995, Bell et al. 1997, Chen et al. 2005, 2009, Chootinan et al. 2005). However, serious deficiencies of the MNL model were observed by many researchers (Daganzo and Sheffi 1977, Sheffi 1985) due to its inherent independent of irrelevant alternative (IIA) property. That is, the MNL SUE model is unable to account for similarities among different alternatives, i.e. overlapping effects among different routes and gives unrealistic route choice probabilities. On the other hand, by introducing normally distributed random terms, the MNP SUE model (Daganzo and Sheffi, 1977) does not have such drawbacks, because it takes into account the route similarities by allowing the covariance between the random error terms for each pair of routes. The MNP SUE model has been adopted by Lam and Xu (1999) as a traffic flow simulator for assessing network reliability and also recently extended by Meng et al. (2008) to consider link capacity constraints. However, it should be noted that the MNP SUE model does not have a closed-form probability expression and straightforward behavioural interpretation. It also requires high calibration and specification efforts and is computationally burdensome when the choice set contains more than a handful of routes. To overcome the deficiencies of the MNL route choice model, some extensions have been proposed recently. One group of extensions is based on the generalised extreme value (GEV) theory (McFadden 1978), such as the cross-nested logit (CNL) model (Prashker and Bekhor 1998, Vovsha and Bekhor 1998, Papola 2004), the paired combinatorial logit (PCL) model (Bekhor and Prashker 1999, Gliebe et al. 1999, Prashker and Bekhor 1998, 2000, Chen et al. 2003, Pravinvongvuth and Chen 2005), and the generalised nested logit (GNL) model (Bekhor and Prashker 2001). The GEV-type models capture the similarity among routes through the error component of the utility function. The model structure is a two-level tree structure, which allows alternative (route) to belong to more than one nest (i.e. a nest here is a link in the CNL and GNL models or a route pair in the PCL model). The choice probability is calculated according to the two-level tree structure using the marginal and conditional probabilities. Equivalent mathematical programming formulations for all three models were given by Bekhor and Prashker (1999, 2001). Prashker and Bekhor (2004) provided an excellent review of these GEV-type route choice models used in the SUE problem. Another group of extensions that overcomes the overlapping problem is by modifying the deterministic (or systematic) part of the utility to account for the overlapping problem while still retaining the single-level tree structure of the MNL model. The models in this group include the C-logit model (Cascetta et al. 1996), the implicit availability/perception

Downloaded by [Monash University Library] at 18:03 26 October 2014

20

Z. Zhou et al.

(IAP) model (Cascetta et al. 2002) and the path-size logit (PSL) model (Ben-Akiva and Bierlaire 1999, Bekhor et al. 2002). All three models add a correction term to the deterministic part of the utility to adjust the choice probability; however, the interpretation of each model is different. The C-logit model uses the commonality factor to penalise the overlapping paths, while both the IAP and PSL models use a logarithmic correction term to modify the utility (hence, the choice probability). In the IAP model, the logarithmic correction term accounts for the awareness of paths. If travelers are unaware of that path or unable to use it, then the logarithm correction term would decrease the probability of choosing that path. On the other hand, the logarithmic correction term in the PSL model accounts for different path sizes determined by the length of links within a path and the relative lengths of paths that share a link. Among these extensions, the C-logit model has been adopted for many applications such as the path flow estimator for estimating O-D trip table from traffic counts (Bell 1998), microscopic traffic simulation (e.g. AIMSUM), and network design problem (Yin et al. 2005), due to its analytical closed-form probability expression, relatively lower calibration efforts and sound rational behaviour consistent with random utility theory. For solving the C-logit model, Russo and Vitetta (2003) proposed a D-C-logit algorithm using Dial’s STOCH algorithm structure for the implicit assignment of network flows. However, a special form of commonality factor has to be adopted in order to allow for summing up the common links. To our best knowledge, there exists no known equivalent mathematical formulation for the C-logit SUE model in the literature. Furthermore, although Cascetta et al. (1996) mentioned that the commonality factor could be assessed based on flow-independent (e.g. physical length) or flow-dependent (e.g. travel time) attributes, no study to date has been conducted to compare and discuss the different attributes used in the commonality factor to model C-logit SUE route choice problem. In this study, we consider the C-logit SUE model using two different attributes to evaluate the commonality factor: one is based on the flow-independent cost (e.g. physical length or free-flow travel time) and the other is based on the flow-dependent cost of the overlapping segments (i.e. congestion effect is explicitly considered). A mathematical programming (MP) formulation is proposed for the length-based C-logit SUE model, and two variational inequality (VI) formulations are proposed for congestion-based C-logit SUE model. Qualitative properties of the formulations are provided and a new self-adaptive gradient projection (NSAGP) algorithm is developed for solving the C-logit SUE formulations proposed in this article. The algorithm is tested on two well-known networks (i.e. Sioux Falls and Winnipeg). The numerical results show that there exist significant differences in terms of route flow allocations between the MNL SUE model and the two C-logit SUE models. The reminder of the article is organised as follows. In Section 2, a brief review of the general concept of C-logit route choice model is introduced and different attributes used in the commonality factor are discussed. Then, equivalent mathematical formulations, including MP and VI, are proposed for both cases. Some qualitative properties of the proposed formulations are also provided. For solving the proposed formulations, NSAGP algorithm is developed in Section 3. Numerical results based on two well-known networks are presented in Section 4 to illustrate the validity of the formulations and solution algorithm. Finally, conclusions are summarised and some future directions are suggested in Section 5.

Downloaded by [Monash University Library] at 18:03 26 October 2014

Transportmetrica 2. Alternative formulations of C-logit SUE models

21

To overcome the deficiencies of the MNL route choice model due to its IIA property, Cascetta et al. (1996) proposed the C-logit model to account for the similarities between overlapping routes by adding a commonality factor in the systematic part of the utility function, while keeping the analytical closed-form expression of route choice probabilities. The C-logit model is stated as follows:

rs rs Ph ?c ? ? P rs rs exp???ch ? cfh ?? , rs exp ?? ? c ? cflrs ?? l2H rs l

8r 2 R, s 2 S, h 2 H rs ,

?8?

Downloaded by [Monash University Library] at 18:03 26 October 2014

rs , 8r 2 R, s 2 S, h 2 H rs , is a commonality factor of route h between origin r and where cfh destination s. It has been shown by Cascetta et al. (2002) that the C-logit model can be interpreted as an implicit route alternative availability/perception choice model, where the commonality factor can be considered as a normalised measure of the availability/ perception of route h as an alternative for a generic traveler, which is directly proportional to the degree of similarities of route h with other routes in OD pair (r, s). In other words, the perception of route h as an alternative will increase due to its dependence with other routes for the same OD pair. Thus, the commonality factor reduces the utility of the overlapping routes and has the ability to alleviate the IIA effect. By incorporating the C-logit route choice model, more realistic SUE solutions can be generated than using the MNL model. Cascetta et al. (1996) proposed several functional forms for the commonality factor. In this article, we consider the following functional form: X Llh p??????p????? , 8r 2 R, s 2 S, h 2 H rs , cfhrs ? ln ?9? Lh Ll l2H rs

where Llh is the ‘length’ of links common to route l and h, Ll and Lh is the overall ‘lengths’ of routes l and h, respectively, and is a parameter. If this parameter is equal to zero, the C-logit collapses to the MNL route choice model. If the parameter is equal to 1, C-logit choice probabilities in the limiting case of N coincident paths tend to 1/N of those calculated with a MNL model applied considering the coincident paths as a single path (Cascetta 2001). In this article, we assume that is equal to 1 for all origin-destination pairs. The effect of the commonality factor in the route choice probability was exemplified in simple networks by several authors (see Cascetta et al. 1996, Prashker and Bekhor 1998, Prashker and Bekhor 2004, for illustrations). In particular, Prashker and Bekhor (2004) compared several route choice models, including the C-logit model. In all examples, constant values for the route lengths were assumed. Figure 1 illustrates the ‘loop-hole’ network (also known as the red-bus/blue-bus network) example presented in Cascetta et al. (1996). This network is composed of three equal-length routes: one independent path and two overlapping paths. Assuming ? ? 1, when the overlapping proportion p moves from 0 to 1, the probability of choosing the independent path vary from 0.33 (when p ? 0) to 0.5 (when p ? 1). In Equation (9), ‘lengths’ can be regarded as a nonadditive generalised cost. In the following, we consider two different attributes used to assess the commonality factor and their applications in the stochastic traffic equilibrium problem. In one case, the ‘lengths’ are based on the flow-independent cost (e.g. physical length or free-flow travel time), while in the other case, the ‘lengths’ are based on the flow-dependent cost (e.g. travel time) to

22

Probability of choosing independent path

Z. Zhou et al.

50% 48% 46% 44% 42%

MNL

A

1

B 1–p

40% 38% 36% 34% 32% 30% 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Overlapping proportion 0.8

C–Logit

p 1–p

Downloaded by [Monash University Library] at 18:03 26 October 2014

0.9

1

Figure 1. Loop-hole network and probability of choosing the independent route.

account for congestion of the overlapping segments. We name these two route choice models as length-based and congestion-based C-logit SUE models, respectively. It is easy to see that the congestion-based C-logit SUE model includes the length-based C-logit SUE model as a special case when the congestion effects are negligible. Note that the selection of appropriate attributes in the commonality factor depends on the specifics of the intended scenario. For example, for travelers who have better (but not exact) knowledge of the network conditions such as commuters or drivers equipped with traveler information (since the information obtained from the traveler information centre may not be always complete and perfect), it would be more appropriate to choose a congestion-based commonality factor. On the other hand, a length-based commonality factor would be more suitable for modelling route choice behaviours of travelers (e.g. visitors) who do not have much information of the network conditions. Based on the discussion above, we now consider two stochastic traffic equilibrium models, where the route choice behaviour of the travelers is described by the length-based and congestion-based C-logit models, respectively.

2.1. Formulation for the length-based C-logit model If the attribute used in the commonality factor is flow-independent (e.g. route similarities computed from link lengths), the length-based C-logit SUE model can be formulated as a mathematical programming (MP) problem as follows: X Z va 1 X X X rs rs CL-SUE-MP : min Z? f ? ? ta ?!?d! ? fh ln fh f 0 rs a2A r2S s2S h2H ?10? XX X ? fhrs cfhrs subject to ?1???3?,

r2R s2S h2H rs

where ta ?va ? represents the travel time on link a. It is easy to see that formulation [CL-SUE-MP] can be regarded as an extension of Fisk’s (1980) logit-based SUE formulation. Here, an additional flow-independent term (i.e. the third term) is introduced

Transportmetrica

23

in the objective function (10) to capture the similarities among the routes. Note that Z? f ? is rs strictly convex with respect to fh and the constraints are linear. Therefore, the formulation [CL-SUE-MP] has a unique solution and the first-order Karush–Kuhn–Tucker (KKT) conditions become the sufficient and necessary conditions of the optimal solution. Proposition 1: The proposed formulation [CL-SUE-MP] is equivalent to the SUE condition (6) of the length-based C-logit SUE model. Proof: The first-order KKT conditions of [CL-SUE-MP] are provided as follows: 1 rs fhrs ch ? ?1 ? ln fhrs ? ? cfhrs ? rs ? 0, 8r 2 R, s 2 S, h 2 H rs , ?11? X fhrs ? q rs ? 0, 8r 2 R, s 2 S, ?12?

h2H rs

Downloaded by [Monash University Library] at 18:03 26 October 2014

1 rs ch ? ?1 ? ln fhrs ? ? cfhrs ? rs ! 0, fhrs ! 0,

8r 2 R, s 2 S, h 2 H rs ,

?13? ?14?

8r 2 R, s 2 S, p 2 P rs , h 2 H rs ,

where rs is the dual variable of the demand conservation constraint (12). For every effective route h between O-D pair ?r, s?, there should be fhrs 4 0. This means 1 rs ? ?1 ? ln fhrs ? ? cfhrs ? rs ? 0: ch By re-arranging (15), we obtain

rs rs fhrs ? exp? rs ? 1? ? exp??ch ? cfh ?:

?15?

?16?

Combining (12) and (16), we have the C-logit probability expression: ? ? rs rs rs exp ??ch ? cfh ? fh rs ? ? , 8r 2 R, s 2 S, h 2 H rs : Ph ? rs ? P rs rs q rs exp ? ? c ? cf k2H k k ? This completes the proof. 2.2. Formulation for the congestion-based C-logit model

?17? ?

If the route similarities depend on both network topology and congestion, then the commonality factor in (9) is represented by a nonlinear flow-dependent function. Therefore, unlike the length-based commonality factor, the congestion-based C-logit SUE model cannot be formulated as a mathematical programming problem. Instead, we propose two formulations based on the theory of variational inequality problem. rs Let q ? ?. . . , q rs , . . .?T represent the vector of O-D demands, cf ? ?. . . , cfh , . . .?T denote the vector of congestion-based commonality factors, and be the feasible set of route flows defined by (1) and (3), a VI formulation of the congestion-based C-logit SUE model is to find a vector f ? 2 , such that: T 1 CL-SUE-VI-I : c? f ? ? ? ?1 ? ln f ? ? ? cf ? ? f ? f ? ? ! 0, 8 f 2 : ?18?

24

Z. Zhou et al.

Proposition 1: f ? is a solution of the congestion-based C-logit SUE model if and only if f ? is a solution of the VI problem [CL-SUE-VI-I] Proof: It is easy to see that f ? is a solution of the VI problem [CL-SUE-VI-I] if and only if it solves the following MP problem: min ? f ? ?T f,

f2

?19?

where ? f ? ? c? f ? ? ?1 ? ln f ?= ? cf is a mapping from toRn . By using the primal-dual optimality conditions, the sufficient and necessary conditions for f ? to be an optimal solution of (19) are: ? ?T ?20? ? f ? ? ? ?T ? f ? ? 0,

Downloaded by [Monash University Library] at 18:03 26 October 2014

? f ? ? ? ?T ? ! 0, ?f ? ? q ? 0, f ? ! 0,

?21? ?22? ?23?

where ? is the optimal dual solution and ? is the OD-path incidence matrix. Without loss of generality, for every effective route h between O-D pair (r, s), there rs should be fh 4 0. Thus, from condition (20), we have ?f ? ? ? ?T ? ? 0: ?24? It implies that the VI problem [CL-SUE-VI-I] is equivalent to the SUE condition (6), where route choice probabilities are represented by Equation (8) with the congestion-based commonality factor cf. This completes the proof. ? Proposition 2: Assume the route travel cost function c( f ) is continuous, then the VI problem [CL-SUE-VI-I] has at least one solution. Proof: According to the definition of commonality factor cf and the continuity of route travel cost function c( f ), the mapping ? f ? is also continuous. Furthermore, the set is nonempty, convex and compact. Thus, the VI problem [CL-SUE-VI-I] has at least one solution (e.g. Corollary 2.2.5, Facchinei and Pang 2003). ? Remark 1: In this case, the mapping ? f ? ? c? f ? ? ?1 ? ln f ?= ? cf can be regarded as a generalised route cost, which is nonadditive (i.e. the cost incurred on each route is not just a simple sum of the link costs on that route). Furthermore, from the proof of Proposition 1, we can see that the DUE condition (4) is satisfied naturally. Therefore, solving the VI problem [CL-SUE-VI-I] is equivalent to solving the DUE problem with the generalised nonadditive route cost ? f ?.

rs rs Let P ? ?. . . , Ph , . . .?T represent the vector of route choice probabilities, where Ph is rs defined by (8) with a flow-dependent commonality factor cfh . The congestion-based C-logit SUE model can be formulated as another VI problem, which is to find a vector f ? 2 , such that:

CL-SUE-VI-II : ? f ? f ? ?T ? f ? ? P?c? f ? ?? q? ! 0,

8 f 2 ,

?25?

where ‘’ is the Hadamard product, i.e. z ? x y , zi ? xi yi , I ? 1, 2, . . ., n.

Transportmetrica

25

Proposition 3: f ? is a solution of the congestion-based C-logit SUE model if and only if f ? is a solution of the VI problem [CL-SUE-VI-II]. Proof: Firstly, if f ? is a solution of the congestion-based C-logit SUE model, from the SUE condition (6), we can see (25) is satisfied naturally. Thus, any equilibrium solution of the congestion-based C-logit SUE model is a solution of the VI problem [CL-SUE-VI-II]. Secondly, suppose if f ? is a solution of the VI problem [CL-SUE-VI-II], without loss of generality, we fix a path h 2 H rs of OD pair (r, s) and construct a feasible flow f, rs rs? 6? fh . Upon substituting it into (25), such that flmn ? flmn? , ?l, m, n? 6? ?h, r, s? but fh rs rs? T rs? rs rs ? one obtains ? fh ? fh ? ? fh ? Ph ?c ? f ?? ? qrs ? ! 0. For every effective route h between rs rs? rs rs 4 0. Therefore, we have fh ? Ph ?c ? f ? ?? ? q rs ? 0 O-D pair (r, s), there should be fh (e.g. Corollary 1.3, Nagurney, 1993). Thus, the SUE condition (6) is satisfied, and the solution of VI problem [CL-SUE-VI-II] is the solution of congestion-based C-logit SUE problem. ? Remark 2: From the proof of proposition 3, we can see that the VI formulation [CL-SUE-VI-II] in fact states an equivalent complementary condition 0 f ? ? P?c? f ? ?? q ! 0 (e.g. Lo et al. 1999). That is, at the equilibrium solution, the SUE condition (6) is satisfied. Proposition 4: Assume the route travel cost function c(f) is continuous, then the VI formulation [CL-SUE-VI-II] has at least one solution. Proof: According to the assumption of continuity, it is easy to see that F? f ? ? f ? P?c? f ?? q is a continuous mapping from to Rn. Since is a nonempty, convex and compact set, the VI problem [CL-SUE-VI-II] has at least one solution (e.g. Corollary 2.2.5, Facchinei and Pang 2003). ? Remark 3: Both VI formulations for the congestion-based C-logit SUE model can be written as a general form: F? f ?T ? f ? f ? ? ! 0, 8 f 2 , ?26?

Downloaded by [Monash University Library] at 18:03 26 October 2014

where F??? is a general mapping from toRn . For the first VI formulation [CL-SUE-VI-I], the generalised nonadditive route cost function ??? can be regarded as F???. For the second VI formulation [CL-SUE-VI-II], the mapping ? f ? P?c? f ?? q? can be represented by F???. Furthermore, since the length-based C-logit SUE model is a special case of the congestion-based C-logit SUE model, the proposed VI formulations are also valid for the length-based model. Furthermore, it is easy to prove that the MP formulation [CL-SUE-MP] is equivalent to the VI formulations [CL-SUE-VI-I] and [CL-SUE-VI-II] when the commonality factor is flow-independent. This enables the solution algorithm developed in the next section to be described in a unified way for solving all three formulations of the length-based and congestion-based C-logit SUE problems. Remark 4: Note that the VI formulations [CL-SUE-VI-I] and [CL-SUE-VI-II] above belong to a broad category of nonadditive traffic equilibrium problems (Gabriel and Bernstein 1997, Lo and Chen 2000, Altman and Wynter 2004, Agdeppa et al. 2007), which has many important applications and is receiving more attention recently. The C-logit model, in general, is nonadditive because of the additional commonality factor in the systematic utility, which is a function of route attributes. Therefore, our formulation

26

Z. Zhou et al.

works for general cases, where the commonality factor could be any rational definition to minimise the IIA effects. In other words, the commonality factor needs not to be limited to a certain special form, such as the one adopted in the D-C-logit algorithm of Russo and Vitetta (2003) that requires summing up the common links in order to set up a link-based algorithm. Remark 5: It should also be noted that uniqueness of a solution to the VI formulations [CL-SUE-VI-I] and [CL-SUE-VI-II] depends on the property of mapping F???. That is, if F??? is strictly monotone, the VI formulations give one unique equilibrium solution (Nagurney 1993). According to the definition of the C-logit model and the commonality factor (i.e. Equations (8) and (9)), we can prove that the length-based C-logit model has a unique equilibrium solution. However, the uniqueness of the congestion-based C-logit model may not be guaranteed due to the nonadditive route cost structure and the nonseparable flow-dependent commonality factor.

Downloaded by [Monash University Library] at 18:03 26 October 2014

3. Solution algorithm Gradient projection (GP) algorithm has been shown as a successful route-based algorithm for solving the traditional traffic equilibrium problem (e.g. Jayakrishnan et al. 1994, Chen et al. 2002). A general iterative scheme of GP can be described as follows: given an initial solution, f0 2 , the algorithm generates a sequence f fk g according to the following recursive update equation: fk?1 ? P ? fk ? k F? fk ??, k ? 0, 1, . . . , ?27?

where P ? ? denotes a unique projection of a vector 2 RjHj on (here, jH j is the cardinality of the route set H ? [H rs , 8r 2 R, s 2 S ), and k ! 0 is a judiciously chosen positive stepsize. Under an ingenious approach that utilises the special structure of traffic equilibrium problem (e.g. Jayakrishnan et al. 1994, Chen et al. 2002), GP only needs to compute a simple projection on the nonnegative orthant. Therefore, the required computational effort is modest. Attracted by the efficiency and simplicity, the GP algorithm has been extended to solve the asymmetric traffic equilibrium problem (Zhou and Chen 2003), the nonadditive traffic equilibrium problem (Scott and Bernstein 1999, Zhou and Chen 2006), and the MNL SUE problem (Bekhor and Toledo 2005). To enhance the robustness and efficiency of the GP algorithm, one critical issue is how to choose an appropriate stepsize for the recursive update Equation (27). A large stepsize would lead to divergence, while a small stepsize would slow down the convergence. Previous results reported in the literature (e.g. Jayakrishnan et al. 1994, Scott and Bernstein 1999, Chen et al. 2002, Zhou and Chen 2003, 2006, Bekhor and Toledo 2005) demonstrated that the stepsize selection indeed plays a significant role in the efficiency and robustness of the algorithm. In these studies, several different stepsize strategies have been suggested to overcome the difficulty, such as embedding a predetermined stepsize sequence (Nagurney and Zhang 1996), adopting a generalised Armijo’s rule (Bertsekas 1976, Gafni and Bertsekas 1982) or imposing a positive definite symmetric scaling matrix (Bertsekas and Gafni 1982). However, the predetermined stepsize suffers from a sublinear convergence rate, the generalised Armijo’s rule requires gradient information and expensive function evaluations, and the numerical results reported on using a diagonal

Transportmetrica

27

approximation as the scaling matrix with a unity stepsize have difficulty either in obtaining a highly accurate solution (Jayakrishnan et al. 1994, Chen et al. 2002) or in converging to the correct solution under a highly nonlinear route cost function (Scott and Bernstein 1999, Bekhor and Toledo 2005). For more discussions on the different stepsize selection strategies embedded in the GP algorithm and their comparisons, we refer to Zhou and Chen (2007). Recently, an NSAGP algorithm has been proposed for solving the traffic equilibrium problems with asymmetric link costs (Zhou and Chen 2003) and with nonadditive route costs (Zhou and Chen 2006). The unique feature of the algorithm is its embedded self-adaptive scheme. The main idea of the scheme is to determine the stepsize automatically by using the information provided by previous iterations. The self-adaptive scheme is reminiscent to Bertsekas’ Armijo rule (1976). However, it is more practical and robust since we allow the stepsize sequence to be non-monotone (i.e. k can decrease as well as increase). Furthermore, the global convergence can be guaranteed under certain assumptions (He et al. 2002, Han and Sun 2004) such as the strongly monotonicity and Lipschitz continuity of the underlying mapping F???. The results reported in Zhou and Chen (2003) show that the self-adaptive scheme can significantly enhance the robustness and efficiency of the algorithm and perform much better than the strategies that use a fixed stepsize (e.g. determined empirically or by a ‘trial-and-error’ approach as suggested by Scott and Bernstein (1999)) or a predetermined stepsize sequence (Nagurney and Zhang 1996), such as the method of successive averages (MSA) scheme. Meanwhile, the NSAGP algorithm still maintains the elegant flow update strategy (e.g. Jayakrishnan et al. 1994, Chen et al. 2002), which only requires a simple projection on the nonnegative orthant by utilising the special structure of the DUE problem, thus avoiding the computational burden of solving quadratic programs. As mentioned in Remark 4, the C-logit model in general has a nonadditive route cost structure that cannot be decomposed into each individual link. Link-based algorithms, such as the D-C-logit procedure (Russo and Vitetta 2003), may not be applicable under this general circumstance. Thus, a route-based algorithm is needed to solve the nonadditive traffic equilibrium problem. Motivated by the good features of the NSAGP algorithm (i.e. the ingenious simple projection approach and the self-adaptive stepsize strategy), we adopted it for solving the C-logit SUE formulations proposed in this article. The underlying mapping F??? adopted here is based on the generic VI formulation (26) (i.e. F??? is different for each formulation). Thus, the algorithm has the ability to solve both length-based and congestion-based C-logit SUE models in a unified manner. The main steps of the algorithm are summarised as follows.

Downloaded by [Monash University Library] at 18:03 26 October 2014

3.1. New self-adaptive gradient projection algorithm Step 1: Initialisation . Set stepsize 0 4 0, max 4 0, stopping criteria " 4 0, parameters 2 ?0, 1?, u 2 [0.5, 1], and iteration counter k ? 0 . Set the initial route flow vector: f0 2 . Set the initial scaling parameter:
0 ? 1 . Compute the commonality factor cf0 and underlying mapping F0

28 Step 2: Termination

Z. Zhou et al.

. Compute the residual e? fk , k ? according to the predefined convergence rule . If e? fk , k ? ", then stop, Output the equilibrium route flow vector fk Otherwise, go to Step 3. Step 3: Self-adaptive scaling procedure . Determine an appropriate stepsize k?1 and obtain a new solution vector . Find the smallest nonnegative integer lk , such that k?1 ? ulk
k , h i ~rs ? max 0, f rs ? k?1 ?r,s " rs , r 2 R, s 2 S, f 8h 2 H rs , h 6? h h,k?1 h,k?1 k h,k?1 , h i "rs ? max 0, f rs ? k ?r,s , 8h 2 H rs , h 6? h " rs , r 2 R, s 2 S, f h,k?1 h,k k h,k satisfy ~k?1 ?T ??k ? ?k?1 ? ? 2 ?k ? ?k?1 2 ?2 ? ?k?1 ?f~k ? f k?1 & 2 ' ? 2 ~ 2 " ! max k?1 2 k kf ? f k , 0 , k k?1 k

T rs rs rs rs ~ " where ?k represents vector ?. . . , ?h " rs , k , fk and fk denote ,k , . . .? , ?h,k ? Fh,k ? Fh k T T rs rs " ~ the vectors ?. . . , fh,k , . . .? and ?. . . , fh,k , . . .? . Then, update the shortest route flows X rs rs rs rs fh ? q ? fh 8r 2 R, s 2 S: ,k?1 , ,k?1

k

Downloaded by [Monash University Library] at 18:03 26 October 2014

h2H rs " rs h6?h k

2 if 0:5k?1 ?f~k ? f~k?1 ?T ??k ? ?k?1 ? ? 2 k?1 ?k ? ?k?1 & 2 ' ? 2 ! max k?1 2 k k f~k ? f k?1 k2 , 0 , k ? ? then
k?1 ? min k?1 =u, max ; otherwise
k?1 ? k?1 : . Increment iteration counter K ? K ? 1 and go to Step 2. From the above solution procedure, it should be noted that only simple projections on the nonnegative orthant are required in each iteration (i.e. the demand conservation constraints are removed from the constraint set). The self-adaptive stepsize updating scheme is embedded in Step 3, where the stepsize k?1 is decided according to the information of the previous iterations (i.e. route flow vector fk and underlying mapping rs rs rs ?h " rs , k ). Note that the self-adaptive scaling procedure for searching the ,k ? Fh,k ? Fh

k

stepsize k?1 will terminate in finite steps. In other words, there is a positive real number, denoted by min , such that for all k 4 0, k?1 4 min 4 0 (Han and Sun 2004). In short, the self-adaptive scheme resolves the messy problem of finding an appropriate stepsize and the simple projection approach avoids the computational burden of solving convex

Transportmetrica

29

quadratic programs. These two key features make the NSAGP algorithm robust and efficient. For more details, we refer to Jayakrishnan et al. (1994) and Chen et al. (2002) for the strategy of redefining the feasible path flows in terms of nonnegative path flows so that only simple projections on the nonnegative orthant are required in each iteration, and to Zhou and Chen (2003, 2006) and Han and Sun (2004) for the self-adaptive stepsize updating scheme and the convergence properties of the NSAGP algorithm. One note of caution is that the convergence of the proposed method requires the strongly monotonicity and Lipschitz continuity of the underlying mapping, which may not be always satisfied. Therefore, the proposed algorithm should be regarded as a heuristic approach in that case. However, the numerical experiments conducted in Section 4 show that the algorithm works well in all three models for both networks.

Downloaded by [Monash University Library] at 18:03 26 October 2014

Remark 6: If the formulation [CL-SUE-VI-I] is adopted, special care should be taken in setting the initial route flow vector in Step 1 since zero flows cannot be admitted due to the characteristics of the natural logarithm function. A good initialisation procedure is to calculate the route costs and commonality factors based on the free-flow travel times (i.e. empty network). Then, the initial route flow vector f?0? is calculated according to the probability formula (8) and SUE condition (6). During the iteration process, a safeguard against the zero flow routes is to truncate the underlying mapping at an appropriate point. In other words, set F? f ?k?? ? c? ? ? ?1 ? ln ?= ? cf ? ? for f ?k? , where is a sufficiently small amount of flow. At the equilibrium solution, it will always be true that all feasible routes have positive flows. Remark 7: Note that the proposed algorithm has the ability to handle both length-based and congestion-based C-logit SUE formulations. The only difference during the algorithmic implementation is the calculation of the commonality factors. For the length-based case, the commonality factors only need to be computed once at the initialisation step. However, for the congestion-based case, the commonality factors have to be recomputed during the iteration process to reflect the congestion effect, which increases the computational efforts significantly.

4. Numerical results In this section, some numerical results are presented to examine the proposed formulations and solution algorithm. The NSAGP algorithm is implemented on a personal computer with Pentium IV 2.4GHz, 768mb RAM. In our implementation, we assume a set of working routes is available in advance to solve the C-logit SUE models. The advantage of using a working route set (i.e. generated from a choice set generation scheme) is that it provides a common basis for the comparison of various models. Behaviourally, it has the advantage of identifying routes that would likely to be used (Cascetta et al. 1997, Bekhor et al. 2006, 2008). However, the NSAGP algorithm can also work with a column generation procedure (e.g. Chen et al. 2001). Two well-known networks are adopted in our numerical experiments. Figure 2 shows the Sioux Falls network (Leblanc 1973). It consists of 24 nodes, 76 links and 528 OD pairs with positive demands. Figure 3 shows the Winnipeg car network from the EMME/2 software (INRO Consultants 1999), and it has 154 zones, 2535 links and 4345 OD pairs. The volume-delay function for both networks is based on the Bureau of Public Road

30

1 2 3 6 7 5 8 4

Z. Zhou et al.

3 1 11 5 9 13 35 10 31 25 33 12 11 36 32 27 10 29 51 49 30 34 40 28 43 53 41 37 38 42 23 72 73 74 13 39 24 75 76 66 21 64 69 65 68 62 20 14 44 71 70 22 63 59 61 15 45 57 19 17 58 59 60 52 9 24 26 48 16 50 22 47 55 18 23 21 8 20 18 54 12 16 19 17 7 15 6 4 2 14

Downloaded by [Monash University Library] at 18:03 26 October 2014

Figure 2. Sioux Falls network.

(BPR) formula with link-specific parameters. The network and demand data were constructed according to Leblanc’s (1973) PhD dissertation for the Sioux Falls and from the EMME/2 software (INRO Consultants, 1999) for the Winnipeg network. The working route sets of these two networks are from Bekhor et al. (2006, 2008), where the routes are generated by using a combination of the link elimination method (Azevedo et al. 1993) and the penalty method (De La Barra et al. 1993) for comparing the MNL and CNL SUE models. For the Sioux Falls network, the maximum number of routes generated for any OD pair is 13 and the average number of routes is 6.3 per OD pair. For the Winnipeg network, there are 174,491 unique routes with an average of 40.1 routes for each OD pair and the maximum number of routes generated for any OD pair is 50. The total demand of the Winnipeg matrix is 54,459 trips and deterministic assignment results show a moderate congestion on the network (average volume to capacity ratio less than 0.7). The total demand of the Sioux Falls matrix is 386.9 units and deterministic assignment results show

Transportmetrica

0 2 4 Kilometers 6

31

Downloaded by [Monash University Library] at 18:03 26 October 2014

0

2 4 Kilometers

6

Figure 3. Winnipeg network.

high congestion on the network with several links with volume-to-capacity ratio higher than 1.0. For the numerical experiments, we specify the initial stepsize 0 ? 1 and convergence error " ? 10?5 , where the residual e? f ?k?, k ? is defined as the root mean squared error (RMSE) of the route flows between two consecutive iterations: q ?????????????????????????????????????????????? e? f ?k?, k ? ? f?k? ? f?k ? 1?2 =jHj, ?28? where k?k2 is Euclidean norm and |H | is the number of routes. The first set of results shows the convergence characteristics of the NSAGP algorithm for solving the three logit-based SUE models (MNL, length-based C-logit and congestion-based C-logit). For simplicity, we use MNL, LC and CC to represent each model respectively in reporting the results. Figures 4–7 show the convergence in terms of the residual in logarithmic scale as a function of number of iterations and CPU times required for solving the three logit-based SUE models with the dispersion parameter ? 1:2 using the Sioux Falls and Winnipeg networks. From the figures, we can observe that the NSAGP algorithm has the ability to solve all three logit-based SUE models in a finite number of iterations with reasonable computational efforts. The convergence rate is approximately linear in both the number of iterations and CPU times for all three models. Similar findings were also observed in Zhou and Chen (2006) for solving the nonadditive traffic equilibrium problem. These results are very encouraging; they seem to show that the NSAGP algorithm is robust and has the ability to obtain optimal solution with a high degree of accuracy.

32

0 –1

Log10(residual error)

Z. Zhou et al.

MNL LC CC

–2 –3 –4 –5

Downloaded by [Monash University Library] at 18:03 26 October 2014

–6 0 20 40 60 80 # of iterations 100 120

Figure 4. Convergence of the NSAGP algorithm as a function of number of iterations required to solve three logit-based SUE models – Sioux Falls network.

0 –1 Log10(residual error) –2 –3 –4 –5 –6 MNL LC CC

0

0.5

1

1.5

2

2.5

3

3.5

4

CPU time (s)

Figure 5. Convergence of the NSAGP algorithm as a function of CPU times required to solve three logit-based SUE models – Sioux Falls network.

Note that, though it seems that a large number of iterations is needed to solve the Winnipeg network at a desired accuracy level, it does not necessarily mean high computational efforts. On the contrary, the simple projection (on nonnegative orthant) approach in the NSAGP algorithm greatly improves the efficiency and saves a lot of CPU times by avoiding the need to solve expensive quadratic problems as in the traditional projection methods. Therefore, more iterations are typically needed to achieve a higher efficiency in the NSAGP algorithm, but the overall CPU times are significantly reduced since it requires only simple nonnegative projections to be performed to determine the descent direction.

Transportmetrica

2 1

MNL LC CC

33

Log10(residual error)

0 –1 –2 –3 –4 –5

Downloaded by [Monash University Library] at 18:03 26 October 2014

–6 0 200 400 600 800 # of iterations 1000 1200 1400

Figure 6. Convergence of the NSAGP algorithm as a function of number of iterations required to solve three logit-based SUE models – Winnipeg network.

2 1 Log10(residual error) 0 –1 –2 –3 –4 –5 –6 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 CPU time (s)

MNL LC CC

Figure 7. Convergence of the NSAGP algorithm as a function of CPU times required to solve three logit-based SUE models – Winnipeg network.

Furthermore, we can observe that the number of iterations and CPU times for solving the MNL and LC models are quite similar. This is because the only difference between the algorithmic implementation is to compute an additional commonality factor for each route. Since the attribute used in the LC model is flow-independent, the commonality factors only need to be computed once in the initialisation step. However, for the CC model, the commonality factors need to be recomputed during the iteration process to reflect the flow-dependent travel times in the CC model. This requirement significantly increases the computational efforts per iteration required to solve the CC model, especially for the Winnipeg network, since the commonality factor calculation involves many route comparisons.

34

110 100 90

# of iterations

Z. Zhou et al.

MNL LC CC

80 70 60 50 40 30 0 0.2 0.4 0.6 0.8 1 θ 1.2 1.4 1.6 1.8 2

Downloaded by [Monash University Library] at 18:03 26 October 2014

Figure 8. Impact of the dispersion parameter on number of iterations required to solve three logit-based SUE models – Sioux Falls network.

4 3.5 CPU time (s) 3 2.5 2 1.5 1 0 0.2 0.4 0.6 0.8 1 θ 1.2 1.4 1.6 1.8 2

MNL LC CC

Figure 9. Impact of the dispersion parameter on CPU times required to solve three logit-based SUE models – Sioux Falls network.

The second set of results examines the impact of the dispersion parameter on the performance of the NSAGP algorithm. Figures 8–11 show the number of iterations and CPU times required for solving the three logit-based SUE models using the Sioux Falls and Winnipeg networks as a function of the dispersion parameter . For the Sioux Falls network, when the dispersion parameter is less than 0.6, there exists a clear trend that the required number of iterations and CPU times increase for all three models as increases. However, when is greater than 0.6, the number of iterations and CPU times are similar for all cases. This is because the dispersion parameter controls the contribution of the perception errors to the perceived route costs. This contribution is lessened as increases. On the other hand, for the Winnipeg network, this trend keeps increasing as increases. The reason for this is that the congestion level of the Winnipeg network is lower than that of the Sioux Falls network. Similar to the first set of results, the number of iterations required to solve all three models are about the same, CPU times required to solve the MNL and LC models are comparable, and higher computational efforts per iteration are required to solve the

Transportmetrica

2000 1800 1600

35

# of iterations

1400 1200 1000 800 600 400 200 0 0.2 0.4 0.6 0.8 1 θ 1.2 1.4 1.6

MNL LC CC

1.8

2

Downloaded by [Monash University Library] at 18:03 26 October 2014

Figure 10. Impact of the dispersion parameter on number of iterations required to solve three logit-based SUE models – Winnipeg network.

x 104 2.5 2

CPU time (s)

MNL LC CC

1.5 1 0.5 0 0 0.2 0.4 0.6 0.8 1 θ 1.2 1.4 1.6 1.8 2

Figure 11. Impact of the dispersion parameter on CPU times required to solve three logit-based SUE models – Winnipeg network.

CC model due to the need to update the flow-dependent commonality factors during the iteration process. Larger networks typically require a lot more CPU times due to large number of route manipulations as shown in Figures 9 and 11 between the Sioux Falls and Winnipeg networks. The third set of results compares the assignment results of the three logit-based SUE models as a function of the dispersion parameter for the Sioux Falls and Winnipeg networks in Figures 12 and 13, respectively. The difference of any two assignments results is measured by the RMSE as shown below: q???????????????????????????????????????????????????? ? ? ? =jH j, ? f ?29? RMSE ? fmodel model II 2 I

? ? where fmodel I and fmodel II are the equilibrium route flows of model 1 and model 2 ? ? ? ? ? ? , or fLC and fCC ), k?k2 is Euclidean norm, and jHj is the (e.g. fMNL and fLC , fMNL and fCC number of routes.

36

0.06 0.05 0.04 RMSE 0.03 0.02 0.01 0 0

Z. Zhou et al.

MNL-LC MNL-CC LC-CC

0.2

0.4

0.6

0.8

Downloaded by [Monash University Library] at 18:03 26 October 2014

1 θ

1.2

1.4

1.6

1.8

2

Figure 12. Impact of the dispersion parameter on the differences of equilibrium flows among three logit-based SUE models – Sioux Falls network.

0.14 0.12 0.1 RMSE 0.08 0.06 0.04 0.02 0 0 0.2 0.4 0.6 0.8 1 θ 1.2 1.4 1.6 1.8 2

MNL-LC MNL-CC LC-CC

Figure 13. Impact of the dispersion parameter on the differences of equilibrium flows among three logit-based SUE models – Winnipeg network.

The results indicate that the differences among the three logit-based SUE models are substantial, especially the difference between the MNL model and the two C-logit models. When tends to zero, the differences among the three logit-based SUE models are nil, as expected from the theory. This is because the route flow allocations tend to be equally distributed among all the available routes (i.e. the contribution of the perception errors dominates; all available routes are perceived equally). However, as the dispersion parameter increases, the differences increase. Although the difference between the LC and CC models is not as significant as compared to the differences with the MNL model, it demonstrates the variation of the equilibrium flows when congestion effects are taken into account for capturing the route similarities. The results indicate that LC and CC models produce much different equilibrium flow patterns compared to that of the MNL model. It should also be noted that when is very large, the stochastic effects (i.e. second term in Equation (10)) become negligible. Therefore, the MNL SUE model tends to the

Transportmetrica

70% 60% 50% 40% 30% 20% 10%

MNL LC CC

37

Downloaded by [Monash University Library] at 18:03 26 October 2014

Percentage of OD demand

0 0 5 10 15 20 25 30 35 Equilibirum route flows of different models

Figure 14. Route flow comparison for a specific OD pair among three logit-based SUE models – Winnipeg network.

DUE assignment. However, this is not the case for the two C-logit models. They still have significant differences with the MNL SUE results due to the consideration of route dependencies in the commonality factors. Figure 14 further illustrates the differences among the three logit-based SUE models at the disaggregate level, where the route flow patterns of a specified OD pair in the Winnipeg network are compared side-by-side with ? 1:2. From the above figure, we can observe that most of the travel demands are allocated to a limited number of routes (57), where the 5 highest route flows carry 74, 78 and 80% of the OD demand for the MNL, LC and CC models, respectively. This phenomenon is consistent with the discussions in Cascetta et al. (1997) and Bekhor et al. (2001), where they showed that only a limited number (4–7) of routes in the working set is sufficient to obtain a reasonable solution. However, the flow allocations to these routes can be quite different among the three logit-based SUE models. For instance, route 3, which carries the highest volume, occupies 40% of the OD demand under the MNL model, which is 32 and 36% lower than the flow allocations of the LC and CC models.

5. Conclusion and future research In this article, we studied the length-based and congestion-based C-logit SUE models using flow-independent and flow-dependent attributes in the evaluation of the commonality factors. Equivalent mathematical formulations (one MP formulation and two VI formulations) were proposed and the corresponding qualitative properties were presented. Furthermore, NSAGP algorithm was developed as a unified algorithm for solving all three C-logit SUE formulations. The numerical results showed that the algorithm is efficient and robust, which has the capability to be implemented on real-size networks in practice. It also demonstrated that both C-logit SUE models have the ability to overcome the

38

Z. Zhou et al.

Downloaded by [Monash University Library] at 18:03 26 October 2014

limitation of the MNL model and potentially give more realistic route choice probabilities. Moreover, the comparison of the three logit-based SUE models showed that the differences among the equilibrium route flows could be significant. In this study, we considered only one functional form of the commonality factor for evaluating the length-based and congestion-based C-logit SUE models. Further research is needed to compare different functional specifications of the commonality factor and to examine their effects on the equilibrium solutions. There are also some other important issues that may affect the performance of the solution algorithm and equilibrium flow patterns, such as various demand levels and different route set generation methods (a priori or column generation). The impacts induced by these issues are worth further investigation. The convergence properties, such as robustness and efficiency, of the NSAGP algorithm and other route-based algorithms for solving logit-based SUE problems can also be compared in future research. In addition, the route choice model considered in this article is a function of travel times only. The formulation of the problem can accommodate additional explanatory variables, similar to the ‘generalised cost’ variable in deterministic traffic assignment problems. The generalised cost is a linear transformation of the travel time and cost. More complex utility functions are yet to be implemented in traffic assignment models. The results presented in this article are based on several assumptions common to simple equilibrium models: static assignment, fixed demand, separable volume-delay function and single-user class. Additional research is needed to extend and verify the C-Logit SUE model for more general problems.

Acknowledgements

The work described in this article was supported by a CAREER grant from the National Science Foundation of the United States (CMS-0134161). Constructive comments and suggestions provided by two anonymous referees are highly appreciated.

References

Agdeppa, R.P., Yamashita, N., and Fukushima, M., 2007. The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation. Transportation Research Part B, 41, 862–874. Altman, E. and Wynter, L., 2004. Equilibrium, games and pricing in transportation and telecommunication networks. Networks and Spatial Economics, 4, 7–21. Azevedo, J.A., et al., 1993. An Algorithm for the ranking of shortest paths. European Journal of Operational Research, 69, 97–106. Bekhor, S., Ben-Akiva, M., and Ramming, S., 2001. Route choice: choice set generation and route choice models. Paper presented at the IV Tristan Conference, 13–19 June 2001, Azores, Portugal. Bekhor, S., Ben-Akiva, M., and Ramming, S., 2002. Adaptation of logit kernel to route choice situation. Transportation Research Record, 1805, 78–85. Bekhor, S. and Prashker, J.N., 1999. Formulations of extended logit stochastic user equilibrium assignments. In: Proceedings of the 14th international symposium on transportation and traffic theory, 20–23 July, Jerusalem, Israel. Elsevier, Pergaman, 351–372.

Transportmetrica

39

Bekhor, S. and Prashker, J.N., 2001. Stochastic user equilibrium formulation for generalized nested logit model. Transportation Research Record, 1752, 84–90. Bekhor, S. and Toledo, T., 2005. Investigating path-based solution algorithms to the stochastic user equilibrium problem. Transportation Research Part B, 39 (3), 279–295. Bekhor, S., Toledo, T., and Prashker, J.N., 2006. Implementation issues of route choice models in path-based algorithms. Paper presented at the 11th international conference on travel behaviour research, 13–19 August 2006, Kyoto, Japan. Bekhor, S., Toledo, T., and Prashker, J.N., 2008. Effects of choice set size and route choice models on path-based traffic assignment. Transportmetrica, 4 (2), 117–133. Bell, M.G.H., 1998. Unpublished lecture notes on transportation network analysis. Imperial College London, UK. Bell, M.G.H. and Shield, C.M., 1995. A log-linear model for path flow estimation. In: Proceedings of the 4th international conference on the applications of advanced technologies in transportation engineering, 27–30 June 1995, Carpi, Italy. ASCE, 695–699. Bell, M.G.H., et al., 1997. A stochastic user equilibrium path flow estimator. Transportation Research Part C, 5 (3/4), 197–210. Ben-Akiva, M. and Lerman, S.R., 1985. Discrete choice analysis: Theory and application to travel demand. Cambridge, MA: The MIT Press. Ben-Akiva, M. and Bierlaire, M., 1999. Discrete choice methods and their applications to short term travel decisions. In: R.W. Hall, ed. Handbook of transportation science. USA: Kluwer Publishers, 5–34. Bertsekas, D.R., 1976. On the Goldstein–Levitin–Polyak gradient projection method. IEEE Transactions on automatic control, 21 (2), 174–184. Bertsekas, D.P. and Gafni, E.M., 1982. Projection methods for variational inequalities with application to the traffic assignment problem. Mathematical Programming Study, 17, 139–159. Cascetta, E., 2001. Transportation systems engineering: theory and methods. The Netherlands: Kluwer Academic Publishers. Cascetta, E., et al., 1996. A modified logit route choice model overcoming path overlapping problems: specification and some calibration results for interurban networks. In: J.B. Lesort, ed. Proceedings of the international symposium on transportation and traffic theory, Lyon, France. Oxford: Pergman, 697–711. Cascetta, E., Russo, F., and Vitetta, A., 1997. Stochastic user equilibrium assignment with explicit path enumeration: comparison of models and algorithms. In: Proceedings of the international federation of automatic control: Transportation systems, Chania, Greece, 1078–1084. Cascetta, E., et al., 2002. A model of route perception in urban road networks. Transportation Research Part B, 36, 577–592. Chen, A., Chootinan, P., and Recker, W., 2005. Examining the quality of synthetic origindestination trip table estimated by path flow estimator. Journal of Transportation Engineering, 131 (7), 506–513. Chen, A., Chootinan, P., and Recker, W., 2009. Norm approximation method for handling traffic count inconsistencies in path flow estimator. Transportation Research Part B, 43 (8), 852–872. Chen, A., Kasikitwiwat, P., and Ji, Z., 2003. Solving the overlapping problem in route choice with paired combinatorial logit model. Transportation Research Record, 1857, 65–73. Chen, A., Lee, D.-H., and Jayakrishnan, R., 2002. Computational study of state-of-the-art path-based traffic assignment algorithms. Mathematics and Computers in Simulation, 59, 509–518. Chen, A., Lo, H.K., and Yang, H., 2001. A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs. European Journal of Operational Research, 135 (1), 27–41. Chootinan, P., Chen, A., and Recker, W., 2005. Improved path flow estimator for estimating origindestination trip tables. Transportation Research Record, 1923, 9–17.

Downloaded by [Monash University Library] at 18:03 26 October 2014

40

Z. Zhou et al.

Daganzo, C.F. and Sheffi, Y., 1977. On stochastic models of traffic assignment. Transportation Science, 11, 253–274. Daganzo, C.F., 1982. Unconstrained extremal formulation of some transportation equilibrium problems. Transportation Science, 16, 332–360. De La Barra, T., Perez, B., and Anez, J., 1993. Multidimensional path search and assignment. Proceedings of the 21st PTRC summer annual meeting, Manchester, England, 307–319. Dial, R.B., 1971. A probabilistic multipath traffic assignment algorithm which obviates path enumeration. Transportation Research, 5, 83–111. Dial, R.B., 2001. Equilibrium logit traffic assignment: elementary theory and algorithm. Paper presented at 80th transportation research oard annual meeting, 7–11 January 2001, Washington D.C., USA. Facchinei, F. and Pang, J.S., 2003. Finite-dimensional variational inequalities and complementarity problems. New York, NY: Springer-Verlag. Fisk, C., 1980. Some developments in equilibrium traffic assignment. Transportation Research Part B, 14, 243–255. Gabriel, S.A. and Bernstein, D., 1997. The traffic equilibrium problem with nonadditive path costs. Transportation Science, 31, 337–348. Gafni, E.M. and Bertsekas, D.P., 1982. Convergence of a gradient projection method. Laboratory for Information and Decision Systems Report P-1201 [online]. Available from http:// hdl.handle.net/1721.1/2803 [Accessed 30 November 2009]. Gliebe, J.P., Koppleman, F.S., and Ziliaskopoulos, A., 1999. Route choice using a paired combinatorial logit model. Paper presented at the 78th annual meeting of the transportation research board, 10–14 January 1999, Washington, D.C., USA. Han, D.R. and Sun, W.Y., 2004. A new modified Goldstein-Levitin-Polyak projection method for variational inequality problems. Computational Mathematics and Application, 47 (12), 1817–1825. He, B.S., et al., 2002. Modified Goldstein-Levitin-Polyak projection method for asymmetric strongly monotone variational inequalities. Journal of Optimization, Theory and Applications, 112, 129–143. ? al. INRO Consultants, 1999. Emme/2 User’s Manual: Release 9.2. Montre Jayakrishnan, R., et al., 1994. Faster path-based algorithm for traffic assignment. Transportation Research Record, 1443, 75–83. Lam, W.H.K. and Xu, G., 1999. A traffic flow simulator for network reliability assessment. Journal of Advanced Transportation, 33 (2), 159–182. Leblanc, L.J., 1973. Mathematical programming algorithms for large-scale network equilibrium and network design problems. PhD thesis, Northwestern University, Evanston, IL. Lo, H.K. and Chen, A., 2000. Traffic equilibrium problem with route-specific costs: formulation and algorithms. Transportation Research Part B, 34 (6), 493–513. Lo, H., Chen, A., and Yang, H., 1999. Travel time minimization in route guidance with elastic market penetration. Transportation Research Record, 1667, 25–32. Maher, M., 1998. Algorithms for logit-based stochastic user equilibrium assignment. Transportation Research Part B, 32, 539–549. McFadden, D., 1978. Modelling the choice of residential location. In: A. Karlquist, et al., eds. Spatial interaction theory and residential location, North-Holland, Amsterdam, 75–96. Meng, Q., Lam, W.H.K., and Yang, L., 2008. A general stochastic user equilibrium traffic assignment problems with link capacity constraints. Journal of Advanced Transportation, 42 (4), 429–465. Nagurney, A., 1993. Network economics: A variational inequality approach. Dordrecht, The Netherlands: Kluwer Academic Publishers. Nagurney, A. and Zhang, D., 1996. Projected dynamical systems and variational inequality with applications. Dordrecht/Boston, MA: Kluwer Academic Publishers.

Downloaded by [Monash University Library] at 18:03 26 October 2014

Transportmetrica

41

Downloaded by [Monash University Library] at 18:03 26 October 2014

Papola, A., 2004. Some developments on the cross-nested logit model. Transportation Research Part B, 38, 833–851. Prashker, J.N. and Bekhor, S., 1998. Investigation of stochastic network loading procedures. Transportation Research Record, 1645, 94–102. Prashker, J.N. and Bekhor, S., 2000. Congestion, stochastic and similarity effects in stochastic user equilibrium models. Transportation Research Record, 1733, 80–87. Prashker, J.N. and Bekhor, S., 2004. Route choice models used in the stochastic user equilibrium problem: a review. Transport Reviews, 24, 437–463. Pravinvongvuth, S. and Chen, A., 2005. Adaptation of the paired combinatorial logit model to the route choice problem. Transportmetrica, 1 (3), 223–240. Russo, F. and Vitetta, A., 2003. An assignment model with modified Logit, which obviates enumeration and overlapping problems. Transportation, 30, 177–201. Scott, K. and Bernstein, D., 1999. Solving a traffic equilibrium problem when path costs are nonadditive. Paper presented at the 78th annual meeting of the transportation research board, 10–14 January 1991. Sheffi, Y., 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall Incorporated, Englewood Cliffs, N.J. Vovsha, P. and Bekhor, S., 1998. The link nested logit model: overcoming the route overlapping problem. Transportation Research Record, 1645, 133–142. Wardrop, J., 1952. Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineering, Part II, 1, 325–378. Yin, Y., Madanat, S.M., and Lu, X.Y., 2005. Robust improvement schemes for road networks under demand uncertainty. Paper presented at the 85th annual meeting of the transportation board, Washington, D.C., USA. Zhou, Z. and Chen, A., 2003. A self-adaptive scaling technique embedded in the projection traffic assignment algorithm. Journal of Eastern Asia Society for Transportation Studies, 5, 1647–1662. Zhou, Z. and Chen, A., 2006. A self-adaptive gradient projection algorithm for solving the nonadditive traffic equilibrium problem. Paper presented at the 85th annual meeting of the transportation board, Washington, D.C., USA. Zhou, Z. and Chen, A., 2007. Strategies for selecting stepsize in the gradient projection traffic assignment algorithm. Working paper, Utah State University.

相关文章:

更多相关标签:

- An Algorithm for the Stochastic User Equilibrium Problem
- FY2012美国网件 简介(user)
- Stochastic Programming with Equilibrium Constraints A. Shapiro 1
- INDETERMINACY OF EQUILIBRIUM IN STOCHASTIC OLG MODELS
- Invertible and Non-Invertible Information Sets in Dynamic Stochastic General Equilibrium
- 光学第二次2012zhong
- ADAPT-PT_2012_User_Manual(中)
- 2012.5.1 学位论文答辩 Zhou revised