Obsidian/Zotero/Liiklussageduse kaudne hindamine/05_Artiklid/zilltollchoicestochasticuser2019.md

---

category: literaturenote citekey: zilltollchoicestochasticuser2019 title: "Toll Choice and Stochastic User Equilibrium: Ticking All the Boxes" authors: "Zill, Jan C.; Camargo, Pedro; Daisy, Naznin Sultana; Veitch, Tim" year: 2019 date: "2019-04-01 April 1, 2019" doi: 10.1177/0361198119837496 publication: Transportation Research Record url: "https://doi.org/10.1177/0361198119837496" zotero_key: T8BK7MZ3 zotero_storage: DDBBP6FT collections: doktoritöö folder: Liiklussageduse kaudne hindamine/05_Artiklid firstAuthor: "Zill, Jan C."

status: converted

People

Transportation Research Record 2019, Vol. 2673(4) 930–940 - National Academy of Sciences: Transportation Research Board 2019 Article reuse guidelines: sagepub.com/journals-permissions DOI: 10.1177/0361198119837496 journals.sagepub.com/home/trr

Toll Choice and Stochastic User Equilibrium: Ticking All the Boxes

Jan C. Zill1 , Pedro Camargo1 , Naznin Sultana Daisy1 , and Tim Veitch1

Abstract

Stochastic user equilibrium is a behaviorally realistic framework for strategic demand modeling and forecasting in cities/ regions where there are multiple tolled facilities, especially when it comes to patronage forecasting for existing or planned tolled facilities. However, there is currently no algorithm available in the literature or in commercial software that provides a comprehensive approach for stochastic user equilibrium assignment that addresses the generation of route choice sets for tolled roads, path overlap, and high levels of convergence. This paper presents a novel choice set generation algorithm combined with the path-size logit model and the bi-conjugate Frank-Wolfe equilibrium assignment in a comprehensive algorithm for forecasting tolled road patronage, along with the results of its application to a real-life model in Brisbane, Australia.

Traffic assignment is the last stage of conventional transport models, usually within a user equilibrium framework, following Wardrop's first principle (1). Daganzo and Sheffi first proposed a stochastic variation of the equilibrium framework, stochastic user equilibrium (SUE) (2), and consolidated the approach by providing a mathematical proof for the SUE model (3). Although logit-based models are an option for network assignment within this framework, researchers have previously pointed to the theoretical shortcomings of not considering path overlap in some of the existing implementations of logit-based SUE models (2, 4, 5); namely, the violation of the assumption of independence of irrelevant alternatives, and results in higher traffic flows in routes that share a significant portion of links in the network.

To overcome the issue of path overlapping, a number of methods have been derived from generalized extreme value models (6–11), as well as some other approaches that attempt to utilize the advantages of probit models (12). However, it is important to note that most of these efforts have not been widely incorporated in strategic demand forecasting models, hence the lack of empirical data to compare such methods.

Furthermore, as pointed out by Cascetta et al. (6), choice set generation has also been a substantial research area and resulted in a variety of algorithms. Despite the number of publications and contributions on the subject area, most of the recent algorithms introduced are based on traditional link elimination and link penalty methods (11, 13), with two notable exceptions (14, 15). Moreover, even though choice set generation algorithms are mostly heuristic in nature, there is evidence that the generation of routes that are substantially different from each other and the sheer size of the choice set can significantly affect the results and estimation of a route choice algorithm and its application (16). Generating choice sets containing routes substantially different from each other is, however, a very time-consuming task that scales with the square of the number of origin–destination pairs in the network (11, 13–15), while still not specializing in generating routes for the toll choice problem, in which they are similar to the more traditional Dial approach (17).

In parallel, recent research (18) has shown that tighter convergence of user equilibrium algorithms is critical to obtaining robust and and stable traffic assignment results. This cannot be achieved without the use of more modern algorithms (19). Although convergence of traffic assignment has become an important matter, with several commercial software providers testing their algorithms for convergence speed (18, 20) and proportionality (20), the same is not true with regards to SUE assignment. For this reason, this paper presents a more detailed

Veitch Lister Consulting, Brisbane QLD, Australia

Corresponding Author:

Address correspondence to Pedro Camargo: pedro.camargo@veitchlister.com.au

discussion on the bi-conjugate Frank-Wolfe (BFW) algorithm in the context of SUE and multiple user classes.

In this setting, the contributions of this paper are three-fold:

• - We introduce a novel route choice set generation algorithm specialized in toll choice modeling, which has similar order of complexity as standard all-or-nothing (AoN) assignments.
• - We introduce a simple hierarchical route choice model and compare its outcomes with a traditional path-size logit (PSL) (9).
• - We demonstrate that applying the BFW method (19) in SUE when using sophisticated route choice models significantly improves the rate of convergence of such SUE instances.

It is important to highlight that the experiments conducted during this research consist of a real-world model with 4,797 traffic analysis zones, and a network with more than 110,800 directed links and 44,600 nodes. Furthermore, these SUE experiments consider multiclass road users including autos, light trucks, and heavy trucks, which have different values of time and are related to different sets of turning and access restrictions.

This paper is organized as follows. Section 3 discusses the BFW implications for multi-class assignment and how it was used for the SUE case. This is followed by a description of the VEhicle Inteligent Toll CHoice (VEITCH) algorithm of route choice set generation and the two route choice models utilized in this paper in Section 4. Results (Section 5) compares the performance of the proposed algorithms in run times, convergence, and equilibrated path flows. Finally, our concluding remarks in Section 6 also describe some of the experience of utilizing the proposed method in the context of Australian transportation planning practice.

Equilibrium Traffic Assignment

In this section we introduce the notation and mathematical equations for the multi-class user equilibrium (for further details, see e.g., Dafermos (21) and Florian and Hearn (22)). Assume a directed network of nodes n and links a 2 A, where A is the set of all one-way links; a vector of demand ~tod = (t od, t 2 od, ... , t m od) ^T for each origin–destination pair od in OD, with one component for each user class m 2 M, where M is the number of distinct classes and OD is the set of all origin– destination pairs. Paths are defined as pm od 2 P^m od, where Pm od is the set of all possible paths between origin o and destination d on the network for class m; and f ^m p

describes the flow for a given path p. With these definitions, the feasible regioncan be described as:

$$\sum{p \in P{od}^m} f_p^m = t_p^m, \qquad \forall m \in M, od \in OD$$ (1)

$$\begin{aligned} fp^m &\geqslant 0, & \forall m \in M, p \in P{od}^m \ va^m &= \sum{od \in OD} \sum{p \in P{od}^m} \delta_{ap} f_p^m, & \forall a \in A, m \in M, \end{aligned}$$

where dap is non-zero only when path p contains link a and v^{m a} is the flow (volume) of class m on link a. The first constraint guarantees conservation of flow (fixed demand), the second constraint guarantees non-negative path flows, and the third constraint converts between link flows and path flows. The total link flow va is not simply the sum of class link flows, but given by:

$$va = \sum{m \in M} \beta_a^m v_a^m, \tag{2}$$

where b^{m a} are the passenger car unit (PCU, also known as passenger car equivalent) conversion factors. Finding the user equilibrium for the problem as stated can be expressed as a variational inequality (see e.g., Florian and Hearn [22]), and numerically solved. However, for a certain sub-class of problems it is possible to formulate the user equilibrium problem as a convex optimization problem, subject to the linear constraints in Equation 1. The advantage lies in the computational supremacy of numerical solution methods for the latter.

Convex Optimization Formulation for Multiple User Classes

Dafermos (21) formulated the problem of multiple user classes on a shared super-network with each class living on an individual sub-network. The interaction between classes takes place via the link cost functions, which depend on the total flow on a super link. To be able to write the user equilibrium problem as a convex optimization problem, the Jacobian J of the cost function with respect to the link flows has to be symmetric (21). Note that when J is additionally positive definite, the userclass flows will be unique. This property is generally hard to prove. However, a numerical study, supplemented by some theoretical arguments (20), suggests that this property holds more generally.

Assuming that costs c^{m a} (va) are link-separable, J is block diagonal. This implies that the M 3 M matrices (recall that M is the set of all user classes):

$$\left(\frac{\partial c_a^m(v_a)}{\partial v_a^w}\right)^{M \times M} \qquad m, w \in M \tag{3}$$

must be symmetric for each link a. We assume the following general form for the link cost function:

$$ca^m = W{a,0}^m t(v_a) + \suml W{a,1}^m b_{a,l}^m,$$ (4)

where W^{m a}, ⁰ is a weight factor for the volume-dependent part t(va). The sum corresponds to l fixed cost contributions per link and class, with weights W^{m a}, ¹ and cost factors b^{m a} . As usual, the link travel time t(va) is determined by a strictly monotonic volume-delay function (VDF) r va ca , that is:

$$t_a(v) = t_a^{ff} r \left(\frac{v_a}{c_a}\right), \tag{5}$$

where ca is the capacity of the link and t ff ^a its free-flow travel time. Unfortunately, these properties mean that the link cost function as in Equation 4 does not have a symmetric Jacobian, Equation 3. However, there are two key observations to be made here: first, setting b^m constant per class, the PCU conversion factors can technically be considered as multipliers for demand matrices and factored out of the cost function. Second, as Lam and Huang noted (23), a simple re-scaling of the cost function for each class does not change what constitutes a minimum-cost path and therefore we can re-write Equation 4 as:

$$C_a^m = \frac{ca^m}{W{a,0}^m} = t(v_a) + \suml \frac{W{a,1}^m}{W{a,0}^m} b{a,l}^m \equiv t(v_a) + b_a^m, \quad (6)$$

where we defined the constant (per class and link) bias bm a for notational convenience. Taking all these assumptions into account, the Jacobian is now symmetric because:

$$\frac{\partial C_a^m(v_a)}{\partial v_a^w} = \frac{\partial}{\partial v_a^w} [t(v_a) + b_a^m] = \frac{\partial}{\partial v_a^w} t(v_a) = \frac{\partial t(v_a)}{\partial v_a} \frac{\partial v_a}{\partial v_a^w} = \frac{\partial t(v_a)}{\partial v_a}.$$ (7)

The user equilibrium can now be obtained as the solution to the convex optimization problem (21–23):

$$\min O(v) = \sum_{a \in A} \int_0^{v_a} ta(x) \, dx + \sum{a \in A} \sum_{m \in M} b_a^m v_a^m \qquad (8)$$

with va ^{= P m} v^{m a} and the linear constraints of Equation 1. The solution to this problem can be obtained by a linear approximation method and its general steps are as follows:

1. Calculate the shortest path for each origin– destination pair and each user class on the

• respective sub-network (on the first iteration this is our initial guess).
• 2. Allocate all demand on that path (AoN), which leads to link flows~y.
• 3. Calculate direction of descent ~d.
• 4. Calculate step size l.
• 5. Update link flows and costs ~v(n+1) = (1 l)~v + l~d.
• 6. Repeat (i.e., set n= n + 1) until converged.

For the method of successive averages (MSA), Step 4 at iteration n is achieved by setting l(n) = ¹ n. For Frank-Wolfe (FW) type algorithms, Step 4 is achieved by calculating the optimal step size according to:

$$\min O(\lambda) = \sum{a} \int{0}^{\nu_a + \lambda (d_a - \nu_a)} Ca(x) dx \Leftrightarrow \sum{a} C_a(\nu_a + \lambda (d_a - \nu_a))(d_a - \nu_a) = 0,$$ (9)

which can be solved quickly because it is a minimization with respect to one variable only. The various FW techniques differ in the way they calculate the descent direction ~d, as discussed in the following.

Step Direction for FW, CFW, and BFW

For the plain FW algorithm at iteration n, the step direction is ~d(n) FW =~y(n) , that is, at each iteration we take a step in the direction of the current linear approximation.

For Conjugate Frank-Wolfe (CFW) (19), the step direction is:

$$\vec{d}{CFW}^{(n)} = \alpha^{(n)} \vec{d}{CFW}^{(n-1)} + (1 - \alpha^{(n)}) \vec{y}^{(n)}, \tag{10}$$

where a 2 ½0, 1 is a parameter determined in such a way to make the previous step direction and the current direction conjugate to each other:

$$\alpha^{(n)} = \frac{(\vec{d}{CFW}^{(n-1)} - \vec{v}^{(n)})^T H^{(n)} (\vec{v}^{(n)} - \vec{v}^{(n)})}{(\vec{d}{CFW}^{(n-1)} - \vec{v}^{(n)})^T H^{(n)} (\vec{v}^{(n)} - \vec{d}_{CFW}^{(n-1)})},$$ (11)

where H(n) = H(~v(n) ) is the Hessian of the objective function at the current solution.

For BFW (19), the step direction is:

$$\vec{d}_{BFW}^{(n)} = \beta_0^{(n)} \vec{y}^{(n)} + \beta1^{(n)} \vec{d}{BFW}^{(n-1)} + \beta2^{(n)} \vec{d}{BFW}^{(n-2)},$$ (12)

where P b0, ¹, ² are real parameters with b^x ø 0 and ^x b^x = 1. These parameters are given by:

$$\beta_0^{(n)} = \frac{1}{1 + \mu^{(n)} + \nu^{(n)}}, \quad \beta_1^{(n)} = \nu^{(n)} \beta_0^{(n)}, \quad \beta_2^{(n)} = \mu^{(n)} \beta_0^{(n)},$$ (13)

where

$$\mu^{(n)} = \frac{(\lambda^{(n-1)} \vec{d}{BFW}^{(n-1)} + (1 - \lambda^{(n-1)}) \vec{d}{BFW}^{(n-2)} - \vec{v}^{(n)})^T H^{(n)} (\vec{v}^{(n)} - \vec{v}^{(n)})}{(\lambda^{(n-1)} \vec{d}{BFW}^{(n-1)} + (1 - \lambda^{(n-1)}) \vec{d}{BFW}^{(n-2)} - \vec{v}^{(n)})^T H^{(n)} (\vec{d}{BFW}^{(n-2)} - \vec{d}{BFW}^{(n-1)})}$$ (14)

$$\nu^{(n)} = \frac{(\vec{d}{BFW}^{(n-1)} - \vec{v}^{(n)})^T H^{(n)} (\vec{v}^{(n)} - \vec{v}^{(n)})}{(\vec{d}{BFW}^{(n-1)} - \vec{v}^{(n)})^T H^{(n)} (\vec{d}_{BFW}^{(n-1)} - \vec{v}^{(n)})} + \frac{\mu^{(n)} \lambda^{(n-1)}}{1 - \lambda^{(n-1)}},$$ (15)

and we used the same approximation as Mitradjieva and Lindberg (19) (see their Appendix A). Note that all terms in equations 11,14, and 15 are of the generic form ~xTH~y, where ~x,~y are generic real vectors with dimension equal to the number of links on the shared super-network. In the following we will use these generic parameters instead of the many different actual expressions for notational convenience. Recall that H is block diagonal because the supernetwork links a are independent. Super-network quantities are now vector quantities with components of the individual user classes, and the blocks of H for each link a are given by:

$$H{a} = \frac{\partial^{2} O(\vec{\mathbf{v}}{a})}{\partial \vec{\mathbf{v}}{a}^{2}} = \frac{\partial}{\partial \vec{\mathbf{v}}{a}} \left[ \frac{\partial O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{1}}, \dots, \frac{\partial O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{m}} \right]$$

$$= \begin{pmatrix} \frac{\partial^{2} O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{1} \partial \mathbf{v}{a}^{1}} & \dots & \frac{\partial^{2} O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{1} \partial \mathbf{v}{a}^{m}} \ \vdots & \ddots & \vdots \ \frac{\partial^{2} O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{m} \partial \mathbf{v}{a}^{1}} & \dots & \frac{\partial^{2} O(\vec{\mathbf{v}}{a})}{\partial \mathbf{v}{a}^{m} \partial \mathbf{v}{a}^{m}} \end{pmatrix}, \tag{16}$$

where v^{m a} is the flow component on link a corresponding to user class m. Using Equation 8 and some algebra, we obtain:

$$H_a = \frac{\partial t_a(v_a)}{v_a} U, \tag{17}$$

where U is the unity matrix with ones in every entry. For the terms of the form ~xTH~z for CFW and BFW this translates to:

$$\vec{x}^T H \vec{z} = \sum_a \frac{\partial t_a(v_a)}{\partial va} \left[ \sum{m,m'} x_a^m y_a^{m'} \right], \tag{18}$$

where t is defined in Equation 5. Note the double sum over user classes for each link. For the scenario study in the Experiments and Results section, we have three different modes (auto, light commercial vehicle [LCV], heavy commercial vehicle [HCV]) and therefore the computational cost is only slightly increased over the singleclass case and pales in comparison with the shortest-path build.

Replacing Step 2 in the above solution algorithm, as done in the section covering Route Choice Model, the optimality of the step direction is no longer guaranteed. It can be shown that including stochastic preferences in the cost (utility) functions of routes still leads to a convex optimization problem, but with Equation 8 above containing additional terms related to path entropies. We refrain from presenting a formal extension of the SUE formulation for the proposed mode choice model, as similar considerations made for the case of the generalized nested logit model in Bekhor and Prashker (24) could be made for the hierarchical logit model and the PSL, which are presented in the following.

Route Choice Model

As discussed in the introduction, route choice algorithms have been intensely researched since Dial (17), and a series of models (6–12) have been proposed to address the path overlapping problem. However, despite having the evidence (24) that these models can be applied in large-scale networks, commercially available software have not yet incorporated these more sophisticated choice models within their SUE assignment algorithms. Although we understand that there is a number of possible applications for SUE, and software providers aim to produce tools that can be deployed in a wide range of situations, this gap in research is crucial for the practice of transport forecasting in the presence of tolled roads, particularly for tolled road patronage studies.

Figure 1 shows the route choice algorithms used in our implementation of SUE, where the first three steps are the core of the choice set formation, VEITCH, and the final step is the proper route choice step:

Step 1: Based on the current state of the network, the untolled shortest routes R¹ from all origins o, in the set of origins O and destination d in the set of destinations D are computed using a standard shortest-path algorithm on a network that does not include any of the tolled sections.

Step 2: Also based on the current state of the network, shortest paths are computed between all o 2 O and all t 2 T, where T is the set of all the tolled points, and between all t 2 T and all other t 2 T and all d 2 D, which are stored in a set TP.

Step 3: This stage consists of building a number of tolled paths between each origin o 2 O and each destination d 2 D by combining individual paths in TP. This step, along with the first two steps are presented on a specific section on choice set formation, which presents the VEITCH algorithm in detail.

Step 4: The final step is the proper route choice model, considering the available choice set. For this step, we have considered two different approaches to evaluate the effect of path overlap on the patronage of tolled roads: a PSL model and a hierarchicalmultinomial logit model. These two choice models are presented in more detail in a specific subsection that follows the presentation of the VEITCH algorithm.

Naturally, separate tolled route choice sets are constructed for each of the road user classes included in the model, which are auto, LCV and HCV, which consider attributes such as value-of-time (VoT), speed, toll levels, and toll caps specific for each user class.

Choice Set Generation

In the case of a discrete choice model, enumeration of alternatives and the creation of a choice set are the first steps in a route choice model. Furthermore, as discussed earlier, several route choice set generation methods are available in the existing literature, which can be categorized broadly into four types: deterministic shortest pathbased methods, stochastic shortest path-based methods, constrained enumeration methods, and probabilistic methods. The deterministic shortest path-based method has a variety of submethods, including a labeling approach (25), link elimination (26), and link penalty (11, 13). The stochastic shortest path-based method includes simulation methods (27) and a doubly stochastic generation function (28). In 2006, Prato and Bekhor proposed a branch-and-bound-based constrained enumeration method of choice set generation (29). Cascetta and Papola (30), Frejinger et al. (14), and Dial (17) proposed probabilistic methods that can generate the probability of choice set membership based on their utilities.

Although all the aforementioned models have different features, there is one major drawback common to all such algorithms when it comes to toll choice forecasting. None of them specializes in identifying tolled vs. untolled routes, which lies at the center of the modeling requirements of all of Australia's major cities and in a growing number of cities around the world, as tolled urban expressways become more common. To fill the gap for a high-performing choice set formation method capable of properly modeling tolled roads within a SUE framework, we present a novel deterministic route choice set generation, VEITCH, which has been developed by Veitch Lister Consulting as part of its Zenith model.

Although identifying untolled routes can be done by simply eliminating all tolled sections from the network and performing a traditional shortest-path in the resulting network, the same technique cannot be applied in the case of tolled routes. Unlike what has been done in most of the literature already mentioned, the VEITCH algorithm does not attempt to generate routes between each origin and destination pair at a time, but rather focuses on each of the toll points in the network.

As previously described, the approach taken in the VEITCH algorithm to generate tolled routes between origins and destinations consists of two phases. The first

Figure 1. Route choice algorithm.

phase consists of computing the paths from all centroids to each toll point and from each of these toll points to all centroids. Though the trees to each toll point are the same trees computed for the untolled case, the paths from a toll point to all other nodes in the network can be found by simply computing a single shortest-path tree with origin in said point on a network that does not contain the other tolled facilities. As a consequence, the additional computational complexity added by this step is proportional to the number of toll points in the network, which is often orders of magnitude smaller than the number of centroids in the model.

The second phase of the tolled route construction algorithm, however, consists of combining the travel segments between origins and toll points, toll points and other toll points, and toll points and destinations in a truly combinatorial fashion, envisioning that between an origin and a destination, there would be an alternative path for each possible sequence of toll points along the path. However, considering all possible toll combinations is not necessary, and disregarding unreasonable paths has already been argued for in the literature (17, 29).

Although combinatorial, we have found that applying a domination criteria, where ''a tolled route is considered irrational and is removed from the set of tolled routes if there exists another route with a lower toll cost and a lower travel time,''(31) while going through the tree of possible path section combinations does not result in high computational times for all real-world instances tested (; 20 toll points).

In turn, the domination criteria are applied while sweeping the tree of toll point combinations, which allows for the exclusion of tree branches that violate said criteria. This reduction of the search space in a branchand-bound fashion results in a practical computation performance substantially different than its theoretical worst case, as tests in networks with over 4,750 centroids and 20 toll points resulted in computation time roughly 20% longer than the standard AoN shortest-path computation. Finally, these criteria also imply that the shortest-path route without toll (untolled route) will always be part of the choice set, as no route will have a lower monetary cost than this alternative.

Path-Size Logit (PSL)

In a nutshell, PSL (9, 32) is a factor that adds disutility to a route in the case of path overlap with other routes, in which the amount of overlap an alternative has with all other alternatives in the choice set is approximated by the path size (PS). It is formulated such that the probabilities of the choices are adjusted according to the degree of uniqueness of an alternative in comparison with other alternatives. For instance, if an alternative a is unique, its PS PSa will be 1. Whereas, if it overlaps partially with other alternatives in the choice set, then the PSa will be lower than 1, which means that the disutility of the alternative will increase as the amount of overlap increases. In other words, the relative attractiveness of the choice will decrease if the amount of overlap increases. Thus, an alternative with a unique route will have a higher probability compared with those with overlaps. The probability of an alternative route i to be chosen from the choice set Cn can be written as follows:

$$P(i|Cn) = \frac{\exp[\mu(V{in} + \ln PS{in})]}{\sum{j \in Cn} \exp[\mu(V{jn} + \ln PS_{jn})]},$$ (19)

where

0\P(ijCn) ł 1, and

Vin = representative utility of route i for user n,

Cn = set of all routes available for user n,

m = logit scale term, and

PSin = correction factor.

The PS of a cheap alternative that shares common route elements with other alternatives will be affected by all other alternatives in the choice set. However, it is assumed that the effect of such a particular overlap on the probabilities of route choices is equal for cheap and expensive routes. The PS factor utilized in this study was the exponential PS factor introduced by Ramming (9), but with generalized cost instead of link length to account for our link cost function (compare [cf.] Equation 4). This can be written as follows:

$$PS{in} = \sum{a \in \tau_i} \left(\frac{c_a}{Ci}\right) \frac{1}{\sum{j \in S_a} \left(\frac{C_i}{Cj}\right)^{\gamma}} \delta{aj}, \tag{20}$$

where

ca = generalized cost of link a,

Ci = generalized cost of path i,

daj = 1 if link a is in path j; 0 otherwise,

tⁱ = set of links of path i,

g = parameter to be calibrated,

Sn = set of all paths in the choice set, and

PSin = is the expanded path-size factor for alternative i for user n.

If the link a is unique and can be found only in alternative i, then, daj = 1 and daj =08j 6¼ i. Subsequently, if link a is uniquely utilized in alternative i, then:

$$\frac{1}{\sum{j \in S{ln}} \left(\frac{C_i}{Cj}\right)^{\gamma} \delta{aj}} = 1. \tag{21}$$

The PS factor of link a is equivalent to its proportional cost Ca Ci . Subsequently, if link a is found in another route, for instance in route j, then the PS contribution of link a to PSi is lower than Ca Ci . If g.0 and the cost of routes are not equal, then the PS contribution depends on the ratio Ca Ci . For instance, if g.0 and the cost of route i is more expensive than the cost of route j, then the contribution of link a to the overall PSi is greater than Ca 2Ci . However, the PSL formulation penalizes the expensive routes in favor of cheap routes if the value of g is more than 1. Thus, if the cost of the overlapping routes is not significantly different but more or less equal, then some authors (Ramming [9]; Hoogendoorn-Lanser [33]) suggest that g should be set to zero. Thus, in this study, we set g to zero with an assumption that significant variation of costs among the alternatives in the choice set does not exist.

Hierarchical-Multinominal Logit

To evaluate the impact of path overlaps in our empirical model, we also implemented a hierarchical logit that consists of two nests, one for the sole untolled route, and one for all the tolled routes in a multinomial fashion. This structure allows the implementation of different tests, such as different parameters for the utility functions within each nest to evaluate, for example, the impact of the higher VoT that toll users usually display, or other assumptions with regard to the split between the untolled and the tolled nest, for example, using maximum expected utility or the maximum utility for the split. For the effect of this paper, we have utilized the standard parameters of the Zenith models that consider a 100% higher VoT for toll users when compared with the entire population.

Experiments and Results

In this section, we present a case study on a real-world road network of South-East Queensland in Australia. First, we show that the convergence behavior of the equilibration methods for the route choice case with VEITCH and PSL are commensurate with those without route choice. We then turn our attention to the comparison of the route choice algorithm with and without taking path overlap into account. We will show that the solution in relation to link flows on tolled roads is very close for those two cases.

The network we considered consists of 110,877 directed links, 44,615 nodes, and 4,797 centroids. There are a total of 20 toll gantries in the study area, and all classes are permitted on all tolled roads. We did not model public transport explicitly, but took the average demand as given by free-flow conditions and the frequency of services into account by pre-loading the network with this demand. During the PM peak from 4– 6 p.m., which we chose as our example period, there was a total demand of 1,686,059 trips. This demand was split across three main modes: auto, LCV, and HCV. The auto mode was further split into three sub-classes with different behavior with respect to tolls: trips to/from the airport, private car trips excluding airport trips, and business car trips excluding airport trips. In the following, the input to the traffic assignment, that is, the demand per origin–destination pair for each mode and user class, is fixed. We can therefore directly compare all considered equilibration methods.

Convergence of Equilibration Methods for SUE

In this subsection, we investigate the convergence behavior of various assignment methods. Our convergence metric of choice is the commonly used relative gap rgap, defined as:

$$r{gap} = \frac{\sum{a \in A} \sum_{m \in M} v_a^m C_a^m(va^{(n)}) - \sum{a \in A} \sum_{m \in M} v_a^m C_a^m(va^{(n)})}{\sum{a \in A} \sum_{m \in M} v_a^m C_a^m(v_a^{(n)})},$$ (22)

where v(n) ^a is the link flow at the current iteration and y(n) a is the link flow for the current linear approximation. At the solution, the relative gap is exactly zero. Numerical studies suggest that a relative gap of 10⁴ is necessary to get relatively stable link flows and that 10⁵ is desirable, see for example, Slavin et al. (18) and references therein.

In our discussion of the link cost function in the Equilibrium Traffic Assigment section, we omitted the exact functional form of the VDF because it was not important for the derivation. However, for the empirical study of equilibration methods, the functional form matters because it influences the runtime of the algorithm. In our work, we use a generalization of the popular Bureau of Public Roads (BPR) VDF. This is given by cf. Equation 5:

$$r\left(\frac{v_a}{c_a}\right) = \left(\frac{1-\varepsilon}{1+\delta\left(\frac{v}{c}\right)+\alpha\left(\frac{v}{\beta c}\right)^{\gamma}} + \varepsilon\right)^{-1}, \quad (23)$$

where

ca = the capacity of link a,

va = the volume, and

a, b, g, d,e = model parameters.

Note that for d= e = 0, b = 1, this simplifies to the BPR form.

In Figure 2 we compare the convergence behavior of MSA, FW, and BFW for two cases. Figure 2a shows the relative gap as a function of the number of iterations for a traffic assignment run without route choice, in which tolls are simply included as part of the generalized cost of

Figure 2. Relative gap for iterative equilibration methods: (a) no route choice, that is, simple shortest-path and (b) with route choice.

a link, with costs being link-additive. This is the regular setting for traffic assignment algorithms, and the results are well-documented in the literature (see for example Slavin et al. [18], Florian and Hearn [22], and references therein). As can be seen in Figure 2a, MSA (blue line) converges more slowly than FW (dark gray line). FW reaches 10⁴ around iteration number 350, whereas MSA does not reach the same convergence level even after twice the number of iterations. BFW (orange line), on the other hand, reaches a relative gap of 10⁴ after around 100 iterations. Note that the actual runtime of all three algorithms is dominated by the shortest path at each iteration, and therefore the time per iteration is virtually identical for all three methods. Compared with the fastest commercially available multi-threaded multi-class BFW implementation, the runtime performance of our implementation is within 20% of reaching a relative gap of 10⁵, which provides some confidence in our implementation of the algorithm.

Figure 2b also shows the relative gap as a function of the iteration number, but this time for traffic assignment algorithms with route choice and overlap correction (VEITCH and PSL). As can be seen, the convergence behavior of all three methods is remarkably similar to that of the corresponding algorithms without route choice in Figure 2a. For BFW (orange line), the convergence behavior below 5 3 10⁵ shows stronger oscillations than for BFW without route choice. As discussed in the section in which we presented the BFW formulation, this is presumably because of the replacement of the AoN as the linear approximation at each iteration of assignment with the result of the route choice algorithm. It is an open question how the oscillations relate to the specific network and toll setup.

Nevertheless, on average, the relative gap still continues to reduce with the number of iterations. This can be better seen in Figure 3, in which we plot the relative gap on a double-logarithmic scale for both MSA and BFW, and for runs with and without route choice. For MSA, the route choice runs (blue line) show the same scaling behavior as for runs without route choice (dark gray line), although the latter converges slightly faster. For BFW, the route choice run (orange line) and the run without route choice (black line) show similar behavior initially, before the untolled run seems to converge faster from around 50 iterations onwards.

Having discussed the convergence behavior in relation to the relative gap, we now turn our attention to the flows on the network. Figure 4a shows a scatterplot of the flows on each link for MSA with route choice and rgap = 10⁴ (vertical axis), and for BFW with route choice and rgap = 10⁶ (horizontal axis). Figure 4b shows the same quantities as Figure 4a, but for small link flows. Some small variations between the two methods were visible and to quantify the difference, we estimated a linear regression model. The resulting slope was 1:000034, the intercept was 0:087314, the R² value was 0:999999, and the root mean square error was 0:671115. We therefore concluded that both methods had converged to equivalent solutions.

Comparison of Route Choice with and without Path Overlap

In the last section, we compared the simple shortest-path assignment with our route choice algorithm. As previously mentioned, the algorithm was developed to predict usage of urban tolled roads and applied to all major Australian cities. In Australia, there are currently only a few tolled roads in any given region. For example, the region we studied here, South-East Queensland, has 20 toll gantries. We here ask the question whether including the path overlap via PSL leads to noticeable link flow differences when compared with a hierarchical logit model, as described when we presented the PSL formulation chosen for this research. Figure 5a shows the link flows for route choice with PSL (horizontal axis), and without PSL (vertical axis). The equilibration method is BFW and the relative gap is 10⁶ in both cases. As can be seen, the two methods seem to give very close results over the entire flow range.

However, Figure 5b focuses on a flow range of 10,500 to 12,500, in which some flow values differ by around 1:5%. This noticeable difference can be explained by inspecting the inner-city area of Brisbane in more detail. As can be seen in Figure 6, Brisbane is divided by a river, and there exist only a few auto bridges in the inner-city area, two of which are tolled, and one tolled tunnel. Tolled river crossings are indicated by dashed circles in Figure 6, and the relative difference of flows on the network are color-coded, with green indicating larger flows

Figure 3. Relative gap for iterative equilibration methods with route choice.

Figure 4. Link flows for BFW (x-axis) and MSA (y-axis) for route choice algorithm. The convergence levels are rgap =10⁶ and rgap =104, respectively: (a) all link flows on the network; (b) small flows up to 200 vehicles.

Figure 5. Link flows for route choice algorithm with PSL (x-axis) and without (y-axis). The equilibration method is BFW with a convergence level of rgap =10⁶ in both cases: (a) all link flows on the network; (b) small flows up to 200 vehicles.

for the method with path overlap taken into account via PSL. The bridge in the east is the M1, which is a tolled road that avoids the inner city. It is the only river crossing in the eastern area. As such, paths crossing it do not have much overlap with any other paths that cross the river. The situation is reversed in the central inner-city area, where two tolled roads and two untolled roads directly compete with each other. Consequently, the overlapping paths through the central inner-city area artificially increase the attractiveness of the corresponding routes relative to the M1 in the east. Indeed, Figure 6 shows that PSL flows on the M1 are around 1:5% higher compared with the hierarchical logit model, and innercity cross-river flows are reduced correspondingly. This increase of flows on the M1 causes the difference of flows in Figure 5b. However, overall, modeling route choice with a straightforward hierarchical logit model leads to very similar results in link flows for our case study of Brisbane and avoids the computational burden of calculating path-overlap factors.

Conclusion

In this paper, we have presented one significant contribution to the SUE literature in the form of the VEITCH algorithm for route choice set generation, and have demonstrated its applicability in real-world instances. The numerical experiment we presented allowed us to reach a number of important results that can guide the development of future SUE models.

The first result was the first empirical evidence we have seen of how the BFW method (19) accelerates the convergence of sophisticated SUE algorithms, while allowing for stricter convergence. The second important result was that path overlap does have a measurable impact on the patronage of tolled facilities, especially when there is clear competition between facilities, and disregarding this effect cannot be done without close inspection of the network.

The third important result was that convergence of SUE is substantially more difficult than User Equilibrium at higher levels of convergence, especially beyond a relative gap of 10⁵, which indicates the need for future research on better convergence methods in the event of tighter convergence levels becoming a practical necessity.

The fourth and final result was that MSA does converge to the same link volumes as more sophisticated methods, although at a substantially slower rate. This final result indicates that MSA can be used in the SUE context, as long as a much higher number of iterations is used.

Finally, by combining a sophisticated choice set generation algorithm, an advanced route choice model and a state-of-the-art equilibration method, this paper

Figure 6. Difference in link flows for inner-city Brisbane. Green indicates larger link flows when taking path overlaps into account, whereas red indicates larger link flows for the hierarchical logit model. Tolled facilites are marked with dashed circles.

presents one of the most comprehensive approaches for traffic assignment in the presence of urban tolled facilities available in the literature. Further, by demonstrating a computational performance that is adequate for its application in practice, we believe we have presented an attractive alternative to the current methods utilized in tolled road patronage forecasting.

Future areas of research include using a coefficient for the overlap factor in the choice probabilities (cf. Equation 19), including more than one untolled path in the choice set, and evaluating the performance of the method on networks and tolled facilities with different features. It would also be interesting to better understand the oscillations in the relative gap in Figure 2 and potentially derive their relation to the network and toll structure.

Acknowledgments

The authors thank the Veitch Lister Consulting team for discussions and the opportunity to develop this research, especially Jamie Cook for code reviews and implementation support, and Ali Inayathusein for proofreading the manuscript.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: JZ, PC, TV; data collection: JZ, PC, TV; analysis and interpretation of results: JZ, PC, ND, TV; draft manuscript preparation: JZ, PC, ND. All authors reviewed the results and approved the final version of the manuscript.

References

• 1. Wardrop, J. G., and J. I. Whitehead. Correspondence. Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institution of Civil Engineers, Vol. 1, No. 5, 1952, pp. 767–768.
• 2. Daganzo, C. F., and Y. Sheffi. On Stochastic Models of Traffic Assignment. Transportation Science, Vol. 11, No. 3, 1977, pp. 253–274.
• 3. Fisk, C. Some Developments in Equilibrium Traffic Assignment. Transportation Research Part B: Methodological, Vol. 14, No. 3, 1980, pp. 243–255.
• 4. Florian, M., and B. Fox. On the Probabilistic Origin of Dial's Multipath Traffic Assignment Model. Transportation Research, Vol. 10, No. 5, 1976, pp. 339–341.
• 5. Sheffi, Y. Urban Transportation Networks, 1st ed. Prentice-Hall, Englewood Cliffs, NJ, 1985.
• 6. Cascetta, E., A. Nuzzolo, F. Russo, and A. Vitetta. A Modified Logit Route Choice Model Overcoming Path Overlapping Problems: Specification and Some Calibration Results for Interurban Networks. 1996. https://trid.trb.org/ view.aspx?id=481284.
• 7. Vovsha, P., and S. Bekhor. Link-Nested Logit Model of Route Choice: Overcoming Route Overlapping Problem. Transportation Research Record: Journal of the Transportation Research Board, 1998. 1645: 133–142.
• 8. Koppelman, F. S., and C.-H. Wen. The Paired Combinatorial Logit Model: Properties, Estimation and Application. Transportation Research Part B: Methodological, Vol. 34, No. 2, 2000, pp. 75–89.
• 1. Ramming, M. Network Knowledge and Route Choice. Ph.D. thesis. Massachusetts Institute of Technology, Cambridge, MA, 2002.
• 1. Papola, A. Some Developments on the Cross-Nested Logit Model. Transportation Research Part B: Methodological, Vol. 38, No. 9, 2004, pp. 833–851.
• 1. Camargo, P. ReMulAA A New Algorithm for the Route Choice Problem. PhD thesis. University of California Irvine, Irvine, CA, 2014.
• 1. Bekhor, S., M. E. Ben-Akiva, and M. S. Ramming. Adaptation of Logit Kernel to Route Choice Situation. Transportation Research Record: Journal of the Transportation Research Board, 2002. 1805: 78–85.
• 1. de la Barra, T., B. Perez, and J. Anez. Multidimensional Path Search and Assignment. Transportation Planning Methods; Proc., Seminar D Held at the PTRC, PTRC Education and Research Services, on Behalf of the Planning and Transport Research and Computation International Association, Machester, UK, 1993.
• 1. Frejinger, E., M. Bierlaire, and M. Ben-Akiva. Sampling of Alternatives for Route Choice Modeling. Transportation Research Part B: Methodological, Vol. 43, No. 10, 2009, pp. 984–994.
• 1. Flotterod, G., and M. Bierlaire. Metropolis–Hastings Sampling of Paths. Transportation Research Part B: Methodological, Vol. 48, 2013, pp. 53–66.
• 1. Prato, C. G., and S. Bekhor. Modeling Route Choice Behavior: How Relevant Is the Composition of Choice Set? Transportation Research Record: Journal of the Transportation Research Board, 2007. 2003: 64–73.
• 1. Dial, R. B. A Probabilistic Multipath Traffic Assignment Model Which Obviates Path Enumeration. Transportation Research, Vol. 5, No. 2, 1971, pp. 83–111.
• 1. Slavin, H., J. Lam, and K. Nanduri. Traffic Assignment and Feedback Research to Support Improved Travel Forecasting. Caliper Corporation, Newton, MA, 2015.
• 1. Mitradjieva, M., and P. O. Lindberg. The Stiff Is Moving – Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment. Transportation Science, Vol. 47, No. 2, 2013, pp. 280–293.
• 1. Florian, M., and C. D. Morosan. On Uniqueness and Proportionality in Multi-Class Equilibrium Assignment. Transportation Research Part B: Methodological, Vol. 70, 2014, pp. 173–185.
• 1. Dafermos, S. C. The Traffic Assignment Problem for Multiclass-User Transportation Networks. Transportation Science, Vol. 6, No. 1, 1972, pp. 73–87.
• 1. Florian, M., and D. Hearn. Network Equilibrium Models and Algorithms. In Handbooks in Operations Research and Management Science (M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds.), Elsevier, Amsterdam, the Netherlands, Vol. 8, 1995, pp. 485–550.
• 1. Lam, W. H., and H.-J. Huang. A Combined Trip Distribution and Assignment Model for Multiple User Classes. Transportation Research Part B: Methodological, Vol. 26, No. 4, 1992, pp. 275–287.
• 1. Bekhor, S., and J. N. Prashker. Stochastic User Equilibrium Formulation for Generalized Nested Logit Model. Transportation Research Record: Journal of the Transportation Research Board, 2001. 1752: 84–90.
• 1. Ben-Akiva, M., M. Bergman, A. Daly, and R. Ramaswamy. Modeling Inter-Urban Route Choice Behaviour. Proc., 9th International Symposium on Transportation and Traffic Theory, VNU Science Press Utrecht, the Netherlands, 1984.
• 1. Azevedo, J., M. E. O. Santos Costa, J. J. E. Silvestre Madeira, and E. Q. Vieira Martins. An Algorithm for the Ranking of Shortest Paths. European Journal of Operational Research, Vol. 69, No. 1, 1993, pp. 97–106.
• 1. Sheffi, Y., and W. Powell, An Algorithm for the Equilibrium Assignment Problem with Random Link Times. Networks, Vol. 12, 1982, pp. 191–207.
• 1. Nielsen, O. A Stochastic Transit Assignment Model Considering Differences in Passengers Utility Functions. Transportation Research Part B: Methodological, Vol. 34, 2000, pp. 377–402.
• 1. Prato, C., and S. Bekhor, Applying Branch and Bound Technique to Route Choice Set Generation. Transportation Research Record: Journal of the Transportation Research Board, 2003. 1985: 64–73.
• 1. Cascetta, E., and A. Papola. Random Utility Models with Implicit Availability Perception of Choice Travel for the Simulation of Travel Demand. Transportation Research Part C: Emerging Technologies, Vol. 9, 2001, pp. 249–263.
• 1. Veitch, T., and M. Jin. Zenith Technical Note: Static Traffic Assignment – Methodology. Internal report. Veitch Lister Consulting, 2012. https://veitchlister.com.au/wpcontent/uploads/2018/08/ZenithFramework_H_StaticTraf ficAssignment-1.pdf.
• 1. Ben-Akiva, M., and M. Bierlaire. Discrete Choice Methods and Their Applications to Short Term Travel Decisions. In Handbook of Transportation Science (R. W. Hall, ed.), Springer, Boston, MA, Vol. 23, 1999, pp. 5–33.
• 1. Hoogendoorn-Lanser, S. Modelling Travel Behaviour in Multi-Modal Networks. PhD thesis. Delft University of Technology, Delft, the Netherlands, 2005.

The Standing Committee on Transportation Network Modeling (ADB30) peer-reviewed this paper (19-05877).