# Modeling and estimating the capacity of urban transportation network with rapid transit.

Introduction

The concept of capacity is used as an important measure to evaluate the maximum throughput of the given road network. It will be helpful to quantify and to estimate the network capacity in order to prevent the congestion of the road system when the efficient land-use policies and traffic growth strategies are established. Furthermore, as the urban road network (the main trip mode of comprehensive transportation system) is getting saturated, the rapid transit will be considered as an alternative way to transfer the excess traffic demand, by which the capacity of the entire transportation system is expected to be expanded. Therefore, it is also meaningful to detect the capacity of the comprehensive transportation system with multimode travel demand. The results would be an important reference to help make transportation planning schemes, especially to help with the impact evaluation, the siting of the station and the fare pricing of the rapid transit lines.

The most well-recognized network capacity model which demonstrates the changes of the traffic demand along with the regional development was presented by Yang et al. (2000) for the urban road network. It considers that the increasing of the Origin and Destination (O-D) demand pattern is variable both in level and distribution. Thereby, the Equilibrium Trip Distribution and Assignment model with Variable Destination Costs (ETDA-VDC, Oppenheim 1993) is employed to capture this characteristic when the road network capacity is estimated. Utilizing this model, Kasikitwiwat and Chen (2005) proposed the concept and model of the practical network capacity. Furthermore, Chen and Kasikitwiwat (2011) used the practical network capacity model to describe the limited flexibility of the given transportation system.

In the field of multimode equilibrium, being based on the combined distribution and assignment problems, Florian (1977) and Florian and Nguyen (1978) first extended the model to two modes, which is to say the automobile and bus. The former considers that the two types of flow share the capacity of the roads, so their travel times are related; while the latter assumes that the two modes are independent, so that the problem is able to be solved by utilizing the straightforward convex combination algorithm. Then, Lam and Huang (1992) presented a multiclass combined model including modes of automobile, truck and franchised bus. In this model, the generalized formulations are used into the travel cost functions but the modal choice is specified. Further, Boyce and Bar-Gera (2001, 2004) allowed the conversion among various modes, and implemented a large-scale and detailed model for the Chicago region. By their independent assumption on the generalized performance functions, the travel costs on the distinct links in different modes are separable or symmetric. However, the independent or symmetric assumption of the link travel cost may not be realistic. To address this weakness, Oppenheim (1995) utilized the multinomial logit model in a hierarchical structure which integrates the steps of trip generation, distribution, modal split, and route choice into a sequential process. Later, Florian et al. (2002) formulated the multiclass multimode equilibrium model as a variational inequality problem. Recently, Zhou et al. (2009) has presented an alternative formulation of the combined travel demand model, in which both the hierarchical logit model and random utility theory are used. Other literature reviews on the combined travel demand model can be referred to Boyce and Bar-Gera (2004).

In this paper, for the purpose of estimating the capacity of the urban transportation network with rapid transit lines, the road network capacity model (Yang et al. 2000) is extended to a two-mode transportation system including the automobile and rapid transit. The features of the original capacity models are preserved. The current traffic flows are assumed to be maintained in the distribution which only allows changing the travel modes and routes, while the new generated demands are free to decide the destinations, shift modes, and change routes. This growth pattern is modeled by using the hierarchical logit demand function. Based on this, the object of our capacity model is to estimate the maximum demand that can be accommodated by the given comprehensive transportation system.

The capacity model proposed by Yang et al. (2000) is utilized to estimate the urban transportation network capacity and the level of service problem for the road network with single automobile mode. It regards that the traffic demand in transportation system consists of two parts:

--the existing flows currently running in the network;

--the additional demand generated along with the development of the population, economy and land use.

Such growth pattern helps to relate the traffic demand variation to site selection and layout, and takes the influences of the current traffic demand pattern into consideration as well.

This model is formulated as a bi-level programming problem, which aims to maximize the total trip productions subject to the physical constraints of road capacity and production/attraction limitations in each zone. In addition, the behavioral constraints are presented in the lower level where the ETDA-VDC model is employed to demonstrate the growth of the traffic demand. The bi-level network capacity problem is formulated as follows (Yang et al. 2000) (U--upper level problem; L--lower level problem):

(U) max [summation over i] [o.sub.i], (1)

s.t. [v.sub.a] (o) [less than or equal to] [C.sub.a], [for all]a ; (2)

[o.sub.i] = [summation over j] [q.sub.ij] (o) [less than or equal to] [o.sup.max.sub.i] - [[bar.o].sub.i], [for all]i; (3)

[d.sub.j] = [summation over (j)] [q.sub.ij] (o) [less than or equal to]

[d.sup.max.sub.j] [d.sup.max.sub.j] - [[bar.d].sub.j], [for all]j ; (4)

[o.sub.i] [greater than or equal to] 0, [for all]i, (5)

where: [q.sub.ij] (o) and [v.sub.a] (o) are obtained by solving the lower level ETDA-VDC problem.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

s.t. [summation over (j)] [q.sub.ij] = [o.sub.i], [for all]i ; (7)

[summation over r][f.sup.ij.sub.r] = [q.sub.ij], [for all]i,j ; (8)

[summation over r][h.sup.ij.sub.r] = [[bar.q].sub.ij], [for all]i,j ; (9)

[v.sub.a] = [summation over i] [summation over (j)] [summation over (r)]([f.sup.ij.sub.r] + [h.sup.ij.sub.r]) [[delta].sup.ij.sub.a,r], [for all]a ; (10)

[f.sup.ij.sub.r] [greater than or equal to] 0, [h.sup.ij.sub.r] [f.sup.ij.sub.r] 0, [q.sub.ij] [f.sup.ij.sub.r] 0, [for all]i, j,r , (11)

where: the upper level objective function of (1) maximizes the summation of the zonal trip production [o.sub.i] at each origin i, i [member of] I. Constraint (2) indicates that the traffic flow [v.sub.a] on each link a, a [member of] A , should not exceed the capacity of link a, [C.sub.a]. Besides, the numbers of the trip generations and attractions should be limited by some upper bounds, namely [o.sup.max.sub.i] and [d.sup.max.sub.j], respectively. Notation j is the index of the destinations, j [member of] J. Here, the trips generated at each origin include both the existing production [[bar.o].sub.i] and the additional production [o.sub.i]; the trips arriving at each destination consists of the existing and additional attractions, denoted by [[bar.d].sub.i] and [d.sub.i], respectively. These physical limitations originated from the development potential and employment opportunities at each developing zone, are represented by constraints (3) and (4). The zonal trip productions should be non-negative which are shown as constraint (5).

To keep it simple, the variables of the traffic demand and flow are represented in passenger car unit. The vector form of the variables is written in bold, e.g. o = {...,[o.sub.i],...}, which is the same in the remaining part of the paper.

2. Transportation Network Capacity Joint with Rapid Transit

2.1. Network Representation

According to Sheffi (1985) the joint travel choice model can be represented by a modified network presentation, which is known as supernetworks. In the supernetworks, the different choice dimensions are clearly described by using the dummy links added to the original network. Thus, our two-mode transportation network can be illustrated by the supernetwork as Fig. 1.

[FIGURE 1 OMITTED]

The variables of the trip demand in the supernetwork are defined as follows:

--[[bar.q].sub.ij]--existing O-D demand from i to j by automobile;

--[[bar.p].sub.ij]--existing O-D demand from i to j by rapid transit;

--[[bar.T].sub.ij]--total existing O-D demand from i to j, [[bar.T].sub.ij] = [[bar.q].sub.ij] + [[bar.p].sub.ij];

--[q.sub.ij]--additional O-D demand from i to j by automobile;

--[p.sub.ij]--additional O-D demand from i to j by rapid transit;

--[T.sub.ij] --total additional O-D demand from i to j, [T.sub.ij] = [[bar.q].sub.ij] + [p.sub.ij].

This supernetwork includes three types of dummy links. First, each origin node i [member of] I (e.g. 1, 2, ...) is set to be associated with one dummy destination node i' (e.g. 1', 2', ...). The destinations j [member of] J (e.g. 3, 4, ...) are connected to the dummy destinations by dummy links (j,i'). The flow on the dummy link (j,i') is equal to the total additional O-D demand [T.sub.ij] from i to j, which indicates the trip distribution of the newly increasing travel demand.

Besides, the transit mode is represented by dummy links directly connecting the origins and destinations. Each O-D pair is joined by a pair of parallel dummy links associated with the existing transit demand and additional transit demand respectively. The flows on the pair of parallel transit links indicate the current and future traffic demand which is shared by the rapid transit mode. For instance, the existing transit demand from node 1 to 3 should travel through the transit link associated to the existing demand [[bar.p].sub.13], while the additional transit demand between O-D 1-3 should travel along the additional transit link and dummy link (3,1') .

2.2. Combined Travel Demand Model

Like the road network capacity model in Section 1 the total additional O-D demand is not fixed but given by the logit-based trip distribution model:

[T.sub.ij] = [o.sub.i] exp(-[theta]([[tau].sub.ij] + [c.sub.j] (*)))/[summation over (k)] exp(-[theta]([[tau].sub.ik] + [c.sub.k] (*))), [for all]i, j, (12)

where: [[tau].sub.ij] represents the minimum travel cost from i to j by the automobile. The destination cost function [c.sub.j] (*) is in terms of the total destination attractions [D.sub.j], where [D.sub.j] = [[SIGMA].sub.i] ([[bar.T].sub.ij] + [T.sub.ij]). The other notations have the same definitions as in the previous sections.

The rapid transit network is assumed to be independent of the automobile network, and the travel times on it does not depend on the flows. Considering that the fares on the transit network are fixed for any given O-D pair, the generalized transit O-D travel costs (also including the waiting time at station and walking time out of vehicle, etc.) are also assumed to be fixed. The logit-based demand function is employed to decide the modal split in the entire network (Sheffi 1985). Thus, at equilibrium the current automobile flow [[bar.q].sub.ij] from i to j can be given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (13)

where: [gamma] reflects the sensitivity of the travelers to the mode choice, and its value is determined by the standard deviation of the random utility of the mode choice. [[tau].sub.ij] denotes the travel cost by the transit lines from i to j. The constant [[rho].sub.ij] captures the effects of the travel cost differences on the modal split. [[rho].sub.ij] > 0 implies that the share of the automobile trips is greater than the share of the transit when [[tau].sub.ij] =[[pi].sub.ij] for O-D pair i-j; or vice versa. The values of the parameters [gamma] and [[rho].sub.ij] can refer to Sheffi (1985). The existing transit flow is given by [[bar.p].sub.ij] = [[bar.T].sub.ij] - [[bar.q].sub.ij].

Similarly, let [[tau].sub.ij] + [c.sub.j] (*) denote the disutility from origin i to destination j for the additional automobile demand; and [[pi].sub.ij] + [c.sub.j] (*) represents the disutility between O-D i-j for the additional transit demand. Since the terms of destination costs [c.sub.j] (*) are the same for both travel modes, the future automobile O-D flow [q.sub.ij] is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (14)

and the additional transit flow is given by [p.sub.ij] = [T.sub.ij] - [q.sub.ij].

Corresponding to the modified network representation in Section 2.1, the equivalent performance functions on each type of dummy links are derived as follows:

[t.sub.ij] ([T.sub.ij]) = [[tau].sub.ij] = 1/[theta] ln([q.sub.ij] + [p.sub.ij] - [c.sub.j] (*), [for all]i, j; (15)

[[bar.t].sub.ij] = [[bar.p].sub.ij]) = [1/[gamma]] ln [[bar.p].sub.ij]/[[bar.T].sub.ij] - [[bar.p].sub.ij] + [[pi].sub.ij] + [[rho].sub.ij], [for all]i,j ; (16)

[t.sub.ij] = [p.sub.ij]) = [1/[gamma]] ln [p.sub.ij]/[q.sub.ij] + [[pi].sub.ij] + [[rho].sub.ij], [for all]i,j , (17)

where: [t.sub.ji'] (*) is the equivalent travel cost on dummy link (j,i'). [t.sub.ij] (*) and [t.sub.ij] (*) are the travel costs on the transit links associated with the existing and additional transit demand respectively. The flows travelling through the parallel transit links are independent and given by the logit-based share model of (13) and (14). Furthermore, the existing and additional demands are supposed to have the same sensitivity, [gamma], of mode choices between the automobile and transit costs. Therefore, the hierarchical logit structures of the destination/mode choices associated with the existing and additional demands can be illustrated as Fig. 2.

[FIGURE 2 OMITTED]

Synthesizing all the features above, the trip distribution/assignment joint with two-mode choices can be formulated as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (18)

s.t. [v.sub.a] = [summation over i][summation over j][summation over r]([f.sup.ij.sub.r] +[h.sup.ij.sub.r])[[delta].sup.ij.sub.a,r], [for all]i, j,a ; (19)

[[bar.T].sub.ij] = [phi] [summation over r][h.sup.ij.sub.r] +[[bar.p].sub.ij], [for all]i,j; (20)

[q.sub.ij] = [phi][summation over r] [f.sup.ij.sub.r], [for all]i, j ; (21)

[o.sub.i] = [summation over j] ([q.sub.ij] + [p.sub.ij]), [for all]i; (22)

0 < [[bar.p].sub.ij] < [[bar.T].sub.ij], [p.sub.ij] > 0, [q.sub.ij] [for all]i, j, (23)

where the parameter [phi] is the conversion factor that transfers the trip demand to the traffic flow into equivalent passenger car, and it could be equal to the average occupancy rate of passenger car (Boyce, Bar-Gera 2003).

In this model the traffic equilibrium assignment is indicated by the first term of objective function (18) with the link-flow/ route-flow relationship by (19). The distribution rule of the additional automobile and transit demand is indicated by the second term of (18). The last two terms of (18) mean the choice behavior of both travel modes. As constraint (20) shows, the distribution of the existing demand is fixed since [[bar.T].sub.ij] is constant. The trips of the additional demand are free to choose the travel destinations, which is indicated by (21) and (22). For all trips travelers are allowed to choose their trip modes for minimizing the travel costs.

This combined travel demand problem is formulated in terms of the existing transit demand [bar.p], the additional transit demand p and the additional automobile demand q. Equations (19)-(22) are the flow conservation constraints which are also shown in Fig. 2. The traffic flow variables, v, f, and h, are defined in the unit of equivalent passenger car, while the trip demand variables, [bar.p] [bar.p], p, q, [bar.T], T, o , are denoted in personal trips. Constraint (23) ensures the positive of the solutions and the valid of the values of the dummy link cost functions. This optimization problem has a unique solution under the following conditions:

--C1. The link cost [t.sub.a] (v) , a function of the link flows v, is once continuously differentiable and strictly increasing in v. The destination cost [c.sub.j] ([D.sub.j)] is a function of the total trip attractions [D.sub.j] at destination j, and is also once continuously differentiable and strictly increasing.

--C2. [theta] and [gamma] are greater than zero, and [gamma] > [theta], which is referred to the property of the nested logit model (Daganzo, Kusnic 1993).

Based on the above two assumptions, the strict convexity of the objective function of (18) can be shown as the followings:

Proposition 1. The combined modal split/distribution/assignment model in (18)-(23) is strictly convex and its minimum is unique.

Proof. It suffices to show that the Hessian of the objective function is positive definite. The Hessian matrix is calculated as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (24)

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Here, diag(*) denotes the diagonal matrix. Y is the destination/O-D incidence matrix. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is positive definite because [t.sub.a] (v) is strictly increasing in v. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a positive diagonal matrix, and is positive definite obviously. It is evident that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (denoted as [nabla] [c.sub.j]) is because of the formulation of the destination cost function. As [gamma] > [theta] from C2 it can be easily proved that the bottom-right block of the Hessian is positive definite by being transformed to a lower triangle matrix:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the diagonal elements are all positive.

Consequently, the Hessian matrix (24) is positive definite, because all of the diagonal blocks are positive definite. Thus the minimum of this model is unique.

From the above analysis we can also find that the formulation of the proposed combined model is not straightforward. It is because that the equivalent performance function of the dummy transit links (associated with the additional transit demand p, given by (17)) includes the additional automobile O-D demand q, which is also a variable in the performance function of the distribution-related dummy link by (15). Therefore, the link independence cannot be satisfied, and the interaction is not symmetric neither. In order to address this problem the diagonalization method is employed (Florian, Spiess 1982), which formulates the subproblem by fixing the effects of 'foreign flows' on the travel costs of each (dummy) link at every iteration. By using the diagonalization algorithm, the computational procedure for solving the proposed combined travel demand model can be implemented as follows:

Step 0: Determine a set of initial values [v.sup.k.sub.a] and [T.sup.k.sub.ij], and to set k = 0 ([T.sup.0.sub.ij] can be calculated by using the logit-based distribution model by setting [c.sub.j] = 0).

Step 1: Calculate the road link costs [t.sup.k.sub.a] and the destination costs [c.sup.k.sub.j].

Step 2: Find the direction:

1. Find the minimum travel-time route from each origin i to all the destinations by [t.sup.k.sub.a]. Let [[tau].sup.k.sub.ij] denote the minimum travel time from the origin i to the destination j.

2. Determine the auxiliary additional O-D demands by the logit-based distribution model:

[T'.sub.ij] = [o.sup.k.sub.i] [exp (-[theta][[tau].sup.k.sub.ij] + [c.sup.k.sub.j]))/ [summation over j] exp (-[theta][[tau].sup.k.sub.ij] + [c.sup.k.sub.j]))], [for all]i, j.

3. Determine the auxiliary automobile O-D demands by the logit-based modal choice model:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, the auxiliary transit O-D demands are given by [[bar.p]'.sub.ij] = [[bar.T].sup.k.sub.ij] and [[bar.q]'.sub.ij] = [[bar.T]'.sub.ij] - [q'.sub.ij].

4. Assign the auxiliary automobile O-D demands, [q'.sub.ij] and [[bar.q]'.sub.ij], to the minimum travel-time route between the O-D pair i-j, for yielding the route flows [f.sup.ij'.sub.r] and [h.sup.ij'.sub.r]. The O-D demands are converted to the average passenger cars.

Step 3: Set [v'.sub.a] = [summation over i][summation over j][summation over r] [f.sup.ij'.sub.r] + [h.sup.ij'.sub.r] [delta].sup.ij.sub.a,r], [for all]a,

where: the symbol indicates the corresponding auxiliary variables.

Step 4: Determine the step size [lambda] by minimizing the function:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 5: Update the link flows and O-D demands. Set:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Step 6: Convergence criterion. If [summation over (a)][[v.sup.k+1.sub.a] - [v.sup.k.sub.a]]/[v.sup.k.sub.a] [less than or equal to] [epsilon] is achieved, terminate the computation, and the solutions are [v.sup.k+1.sub.a], [[bar.p].sup.k+1.sub.ij], [p.sup.k+1.sub.ij], and [q.sup.k+1.sub.ij], otherwise, set k = k +1 and go to Step 1.

2.3. Network Capacity Model with the Combined Travel Choices

Based on the growing manner of the travel demand demonstrated by the combined travel demand model in (18)-(23), it is interesting to find that the maximum trip demand can be accommodated by the given transportation network which consists of the automobile network and the rapid transit lines.

Similar to the road network capacity problem, the physical limitations applied to our multi-mode transportation system should include the link capacity of both the roadway and transit, and should also be preset with the upper bounds for the zonal trip productions and attractions. The behavioral constraints are given by the combined model of (18)-(23) which has been discussed in the previous sections. Thus, our transportation network capacity model joint with the rapid transit is formulated as follows:

max [summation over (i)] [o.sub.i] (25)

s.t. [v.sub.a] (o) [less than or equal to] [C.sub.a], [for all]a; (26)

[s.sub.b] (o) [less than or equal to] [C.sub.b], [for all]b; (27)

[o.sub.i] = [summation over (j)] [T.sub.ij] (o) [less than or equal to] [o.sup.max.sub.j] - [[bar.o].sub.i], [for all]i; (28)

[d.sub.j] = [summation over (i)] [T.sub.ij] (o) [less than or equal to] [d.sup.max.sub.j] - [[bar.d].sub.j], [for all]j; (29)

[o.sub.i] [greater than or equal to] 0, [for all]i, (30)

where: [T.sub.ij] (o), [v.sub.a] (o) and [s.sub.b] (o) are the implicit functions of the additional zonal trip productions, o, and can be obtained by solving the combined travel demand problem in the lower level given by (18)-(23).

In this model, b is used to represent the transit link index, b [member of] B. [s.sub.b] is the trip demand on the transit link b; and [C.sub.b] is the capacity of b. It is supposed that each O-D pair is served by one transit route, and the transit link flows s is given by s = [GAMMA] ([bar.p] + p), where G is the link/O-D incidence matrix for the rapid transit mode. The constraint (26) and (27) means that the flows on each (transit) link should not exceed its capacity. Furthermore, the number of trips newly generated at each residential area and the trips attracted at each destination should be limited by some upper bounds, namely [o.sup.max.sub.i] and [d.sup.max.sub.j] respectively, and they are represented by the constraint (28) and (29). For further purposes, other physical constraints could be introduced, such as the fuel consumption and emission limits, or the expectation of the level of service.

The intention of this model is to maximize the summation of the trips generated at each origin zone under the constraints from both the travel behavior and physical infrastructures. Travelers are supposed to change the travel modes freely. The maximum total trip productions can be used to represent the capacity of the given transportation system.

3. Sensitivity Analysis Based Solution Algorithm

Because of the efficiency and capability of the Sensitivity Analysis Based (SAB) algorithm (Friesz et al. 1990), the proposed bi-level programming of the two-mode transportation network capacity problem could be solved. The derivatives of the equilibrium link flows and O-D demands are used to reflect the variations of the zonal trip productions. With the derivative information the nonlinear capacity constraints in the upper level of the bi-level problem can be linearly approximated by Taylor expansion as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (31)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (32)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (33)

where: the derivatives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (denoted as [[nabla].sub.o] v, [[nabla].sub.o] s and [[nabla].sub.o] T in vector form respectively) are obtained by:

[[nabla].sub.o]v = [DELTA] ([[nabla].sub.o]f + [[nabla].sub.o]h) ; (34)

[[nabla].sub.o]s = [GAMMA]([[nabla].sub.o] [bar.p] + [[nabla].sub.o]p) ; (35)

[[nabla].sub.o]T = [[nabla].sub.o]p + [[nabla].sub.o]q, (36)

where [DELTA] is the link/route incidence matrix for the automobile mode. The derivatives [[nabla].sub.o]f, [[nabla].sub.o]h, [[nabla].sub.o][bar.p], [[nabla].sub.o]p, and [[nabla].sub.o]q are given by the sensitivity analysis of the combined travel demand model.

Let y = [{f, h, [bar.p], p, q, u, [mu], [lambda]}.sup.T] denote the vector composed of the solution x = [{f, h, [bar.p], p, q}.sup.T] of the combined travel choice model, and the Lagrange multipliers [{u, [mu], [lambda]}.sup.T] be associated with the constraints of (20)-(23).

Based on the implicit function theorem, the derivatives of the lower level model solution x with respect to the upper level decision variable o are produced by:

[[nabla].sub.o]y = [[[J.sub.y]].sup.-1][[-J.sub.o]], (37)

where: the Jacobian matrices [J.sub.y] and [J.sub.o] are obtained from the restriction approach for the sensitivity analysis by Tobin and Friesz (1988). This approach has been corrected (Yang, Bell 2007) and employed for the sensitivity analysis of ETDA-VDC model (Du et al. 2012) which is used as the lower level problem in the network capacity model for the automobile traffic. Based on these literatures, we directly present the expressions of [J.sub.y] which is invertible in the restricted problem, and [J.sub.o] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The notations used in the restricted problem are defined as follows:

--[[DELTA].sub.h]--link/route incidence matrix associated with the existing automobile demand;

--[[LAMBDA].sub.f]--O-D/route incidence matrix associated with the additional automobile demand;

--[[LAMBDA].sub.H]--O-D/route incidence matrix associated with the existing automobile demand;

--[PHI]--origin/O-D incidence matrix associated with the additional demand.

The reduced automobile routes in the above restricted problem are chosen corresponding to the basic variables in the following system of equations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the superscript '0' indicates that these notations are associated with the original problem before the reduction; '+' denotes that the variables should be strictly positive; '*' means the model solutions.

The Jacobian Jy can be proved to be invertible in the similar way as Du et al. (2012), when the combined model in (18)-(23) is strictly convex as Proposition 1.

Thus, the derivatives of the model solutions are derived from Equation (37). Furthermore, we can obtain the derivative information from Equations (34)-(36), which is used to locally approximate the nonlinear constraints in the upper lower problem.

The mechanism of the sensitivity based heuristic algorithm is an iterative process between the upper level and lower level problems. Initially, the trip productions from the origins o are fixed to o*. Then the traffic flow pattern, namely the equilibrium link flows v and the O-D flows for each mode [bar.q], [bar.p], q, p, is given by solving the combined travel demand model. Utilizing the sensitivity analysis method, the first-order approximation is derived to have the upper-level problem linearized. With the constant flow pattern for o in the neighborhood of o* , the bi-level problem can be regarded as a single level differentiable constrained optimization, which can be solved by the appropriate decent algorithms, such as the simplex method. The solution of the approximate problem will give a better and feasible point to the original bi-level problem, and it will be used in a new round of iteration. Thus, the procedure of the SAB algorithm can be summarized as below:

Step 0: Determine an initial value of the trip production pattern o(0). To set n = 0.

Step 1: Solve the lower-level combined modal split/distribution/assignment model for the given [o.sub.(n)] by using the diagonalization algorithm. Thus, the equilibrium link flows [v.sub.(n)] and O-D demand [[bar.q].sub.(n)], [[bar.p].sub.(n)], [q.sub.(n)], and [p.sub.(n)] can be obtained.

Step 2: Calculate the partial derivatives, [partial derivative][v.sub.a]/ [partial derivative][o.sub.i], [partial derivative][s.sub.b]/ [partial derivative][o.sub.i] and [partial derivative][T.sub.ij]/[partial derivative][o.sub.k] by using the sensitivity method for the combined model.

Step 3: Formulate the local linear approximations of the upper-level capacity constraints by using the derivative information, and solve the approximate linear programming problem in order to produce a new trip production [o.sup.(n+1)]. Set n = n +1.

Step 4: If [absolute value of[o.sup.(n+1).sub.i] - [o.sup.(n).sub.i]] [less than or equal to] [KAPPA] for all i [member of] I, stop. Here, [KAPPA] is a predetermined tolerance. Otherwise return to Step 1.

Because of the advantages of the SAB algorithm, the computation can be completed in a few iterations. However, due to the non-convexity of the bi-level problem, the heuristic algorithm might converge to a local optimal point. So it is still meaningful to apply the probabilistic optimization techniques, like the simulated annealing or genetic algorithm.

4. Example

In order to study the impacts of the transit lines to the capacity of the comprehensive transportation system, a numerical example is given in this study. The proposed combined network capacity model is utilized to demonstrate this problem, and it is solved by the SAB algorithm given in the previous section.

[FIGURE 3 OMITTED]

The network example shown in Fig. 3 consists of the basic road network and the rapid transit lines. The realistic network includes five nodes (from node 1 to 5), seven automobile links (from link 1 to 7), and two transit lines [L.sub.1] and [L.sub.2]. Node 1 is the origin node, and node 4 and 5 are the destination nodes. Link 8 and 9 are two dummy links leading from the realistic destination 4 and 5 to dummy destination 1', and they are associated with the two possible choices of trip distributions from origin 1.

For our computational demonstration the function expressions and the value of the parameters in the two-mode combined model are given as follows. The link cost function employs the Bureau of Public Roads (BPR) function (Highway Capacity Manual 2010):

[t.sub.a] ([v.sub.a]) = [t.sup.free.sub.a] (1 + [alpha][([v.sub.a]/[c.sub.a]).sup.[beta]]), (38)

where: [t.sup.free.sub.a] is the free flow time on link a. The values of the parameters [alpha] and [beta] are assumed to be 0.15 and 4 in this case. Table 1 shows the input characteristics of the automobile and transit links. The transit line [L.sub.1] and [L.sub.2] are independent, of which the capacities are 40 and 30 separately. The travel costs for the two transit lines are [[pi].sub.14] = 10 , [[pi].sub.15] = 11, and [[rho].sub.14] = [[rho].sub.15] = 0 . The formulation of the destination cost function and the value of the parameters is defined according to Chen and Kasikitwiwat (2011) as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (39)

where: [k.sub.j] is a scaling factor between the demand and the service cost; [[omega].sub.y] is a dimensionless parameter related to the severity of the congestion; and [m.sub.j] represents a fixed attraction at destination j. For destination 3, [k.sub.3] = 0.15, [[omega].sub.3] = 0.25 and [m.sub.3] = 1.20; for destination 4, [k.sub.4] = 0.10, [[omega].sub.4] = 0.25 and [m.sub.4] = 1.50.

Besides, the impendence parameters of the trip distribution and modal split, [theta] and [gamma], are assumed to be 0.5 and 0.8, separately. The average occupancy rate of the equivalent passenger car is assumed to be 1.6, [phi] = 1.6. The existing traffic O-D demands are given by [[bar.T].sub.14] = 15 and [[bar.T].sub.15] = 20. The upper bound of the trip production is [o.sup.max.sub.1] = 120, and the attraction limits are [d.sup.max.sub.4] = 60 and [d.sup.max.sub.5] = 60.

Based on the parameters given above, now we compute the capacity of this two-mode transportation system by using the SAB algorithm which is described in Section 3. In this numerical experiment all the coding was carried out in Matlab 2010b. In practice, the C programming language is more appropriate because of the large-scale computation for the realistic transportation network. The computation results are shown in Table 2. The network capacity is the summation of the existing and additional trip demand on the network.

For this example network, a comparison is made between the network traffic states before and after the rapid transit lines are built. Before the construction of the two transit lines, the network included the roadways only. In such case the road network capacity model in Section 1 is used to formulate the capacity problem. Thus, we can get the traffic flow pattern at the maximum state, which is shown in Table 3. From the comparison of Table 2 and Table 3 we can find that the total traffic flow pattern on the road network will not be changed much after the transit lines are built. However, a significant portion of the existing automobile flows will be transferred to the transit mode after the transit lines are introduced. Furthermore, the O-D distribution of the trip demand could be much different. Destination 4 will attract more trip demand than destination 5, because the travel cost on the transit line [L.sub.1] is much closer to the minimum cost of the O-D pair that it serves to, thus the average cost of this O-D pair is significantly reduced. Being benefited from the new transit lines, the network capacity is expanded from 67.1 to 111.7 in this example. This expansion depends on the travel costs on each transit route, which is impacted by the location, the fare, the operation of the transit lines and etc. This 'before and after comparison' can work as the important basis in the transportation planning. The results can help the traffic engineers to make decision on whether it is necessary or not to set up the rapid transit system for the development of the city or region in the future.

Conclusions

This paper presents the combined travel choice model in order to formulate the transportation network capacity problem regarding to the two travel modes, the automobile transit and the rapid transit. The traveler's choices of destinations and travel modes are formulated by using the hierarchical logit-based structure. Being based on this, the capacity model of the two-mode network was proposed along with the sensitivity based heuristic method for its solution. At last, a simple network was employed for the model demonstration and computational test. The results show the usefulness of the proposed model. In addition, the effect of the rapid transit lines on the capacity of the transportation system as well as the traffic flow pattern has also been shown.

The capacity model of the transportation network with the rapid transit could be used to help make decisions for the transportation planning projects, such as the scheme evaluation, the fare pricing, or the siting of the station of the rapid transit. Furthermore, a set of objectives or constraints could be integrated into the proposed capacity model, for example, to minimize the transit operating costs, or to determine the pricing range limits. Considering the complexity of the bi-level model, the new solution methods might be needed for the global optimum in large-scale problems.

Caption: Fig. 1. Supernetwork for the combined distribution/ assignment model with two modes

Caption: Fig. 2. Hierarchical logit structures for destination and mode choice

Caption: Fig. 3. Supernetwork for the test example

Acknowledgements

This research is supported by the Natural Science Foundation of China No. 51078085 and No. 51178110.

References

Boyce, D. E.; Bar-Gera, H. 2001. Network equilibrium models of travel choices with multiple classes, in Lahr, M. L.; Miller, R. E. (Eds.) Regional Science Perspectives in Economic Analysis: a Festschrift in Memory of Benjamin H. Stevens, 85-98.

Boyce, D.; Bar-Gera, H. 2003. Validation of multiclass urban travel forecasting models combining origin-destination, mode, and route choices, Journal of Regional Science 43(3): 517-540. http://dx.doi.org/10.1111/1467-9787.00309

Boyce, D.; Bar-Gera, H. 2004. Multiclass combined models for urban travel forecasting, Networks and Spatial Economics 4(1): 115-124. http://dx.doi.org/10.1023/B:NETS.0000015659.39216.83

Chen, A.; Kasikitwiwat, P. 2011. Modeling capacity flexibility of transportation networks, Transportation Research Part A: Policy and Practice 45(2): 105-117. http://dx.doi.org/10.1016/j.tra.2010.11.003

Daganzo, C. F.; Kusnic, M. 1993. Technical note--Two properties of the nested logit model, Transportation Science 27(4): 395-400. http://dx.doi.org/10.1287/trsc.27.4.395

Du, M.; Cheng, L.; Rakha, H. 2012. Sensitivity analysis of combined distribution-assignment model with applications, Transportation Research Record 2284: 10-20. http://dx.doi.org/10.3141/2284-02

Florian, M. 1977. A traffic equilibrium model of travel by car and public transit modes, Transportation Science 11(2): 166-179. http://dx.doi.org/10.1287/trsc.11.2.166

Florian, M.; Nguyen, S. 1978. A combined trip distribution modal split and trip assignment model, Transportation Research 12(4): 241-246. http://dx.doi.org/10.1016/0041-1647(78)90065-5

Florian, M.; Spiess, H. 1982. The convergence of diagonalization algorithms for asymmetric network equilibrium problems, Transportation Research Part B: Methodological 16(6): 477-483. http://dx.doi.org/10.1016/0191-2615(82)90007-8

Florian, M.; Wu, J. H.; He, S. 2002. A multi-class multi-mode variable demand network equilibrium model with hierarchical logit structures, in Gendreau, M.; Marcotte, P. (Eds.) Transportation and Network Analysis: Current Trends, 119133. http://dx.doi.org/10.1007/978-1-4757-6871-8_8

Friesz, T. L.; Tobin, R. L.; Cho, H.-J.; Mehta, N. J. 1990. Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints, Mathematical Programming 48(1-3): 265-284. http://dx.doi.org/10.1007/BF01582259

Highway Capacity Manual. 2010. Transportation Research Board. 5th edition. 1650 p.

Kasikitwiwat, P.; Chen, A. 2005. Analysis of transportation network capacity related to different system capacity concepts, Journal of the Eastern Asia Society of Transportation Studies 6: 1439-1454.

Lam, W. H. K.; Huang, H.-J. 1992. A combined trip distribution and assignment model for multiple user classes, Transportation Research Part B: Methodological 26(4): 275-287. http://dx.doi.org/10.1016/0191-2615(92)90038-X

Oppenheim, N. 1993. Equilibrium trip distribution/assignment with variable destination costs, Transportation Research Part B: Methodological 27(3): 207-217. http://dx.doi.org/10.1016/0191-2615(93)90030-E

Oppenheim, N. 1995. Urban Travel Demand Modeling: From Individual Choices to General Equilibrium. 1st edition. Wiley-Interscience. 480 p.

Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall. 416 p.

Tobin, R. L.; Friesz, T. L. 1988. Sensitivity analysis for equilibrium network flow, Transportation Science 22(4): 242-250. http://dx.doi.org/10.1287/trsc.22.4.242

Yang, H.; Bell, M. G. H. 2007. Sensitivity analysis of network traffic equilibria revisited: the corrected approach, in Mathematics in Transport: Selected Proceedings of the 4th IMA International Conference on Mathematics in Transport in Honour of Richard Allsop, 7-9 September, 2005, London, United Kingdom, 373-395.

Yang, H.; Bell, M. G. H.; Meng, Q. 2000. Modeling the capacity and level of service of urban transportation networks, Transportation Research Part B: Methodological 34(4): 255275. http://dx.doi.org/10.1016/S0191-2615(99)00024-7

Zhou, Z.; Chen, A.; Wong, S. C. 2009. Alternative formulations of a combined trip generation, trip distribution, modal split, and trip assignment model, European Journal of Operational Research 198(1): 129-138. http://dx.doi.org/10.1016/j.ejor.2008.07.041

Lin Cheng (1), Muqing Du (2), Xiaowei Jiang (1), Hesham Rakha (3)

(1) Southeast University, China

(2) Hohai University, China

(3) Virginia Tech Transportation Institute, USA

Submitted 22 November 2012; resubmitted 7 February 2013; accepted 26 April 2013

Corresponding author: Muqing Du

E-mail: dumuqing@gmail.com
```Table 1. Link characteristics

Link                 1     2    3    4    5    6    7

[t.sup.free.sub.a]   4    5.2   1    5    5    4    4
[C.sub.a]            25   25    15   15   15   15   15

Table 2. Computation results

Origin   Trip production                   O-D   Demand pattern

1        56         55.7         120       1-4   24         32
1-5   32         23.7

Automobile

1-4   13.3       17.8
1-5   22.4       16.5

Transit

1-4   10.7       14.2
1-5   9.6        7.2

Network capacity        111.7

pattern *

1        1:(1, 3)   25.0        1.00
2:(1, 5)   21.5        0.86
3:(2, 4)   2.7         0.18
4:(2, 5)   9.9         0.66
5:(5, 6)   12.4        0.82
6:(6, 3)   10.7        0.71
7:(6, 4)   13.5        0.90

Notes: * Link low is denoted in the passenger car units; ** V/C is
the ratio of the traffic volume (V) against the capacity (C) of

Table 3. Traffic flow pattern before the building of the transit
lines

Origin   Trip production                   O-D

1        56         11.1         120       1-4
1-5

Network capacity        67.1

Origin   Demand pattern          Link       Flow        V/C **

1        24         8.5          3)         25.0        1.00
32         9.3          2:(1, 5)   21.0        0.84
3:(2, 4)   2.7         0.18
4:(2, 5)   9.8         0.65
5:(5, 6)   12.4        0.83
6:(6, 3)   10.5        0.70
7:(6, 4)   13.3        0.89

Notes: * Link flow is denoted in the passenger car units;
** V/C is the ratio of the traffic volume (V) against the