Complementarity Formulation and Solution Algorithm for Auto-Transit Assignment Problem

Abstract

In this paper, a combined model of auto-transit assignment is introduced based on two complementarity formulations in the literature. The model accounts for interactions between the auto and transit modes through non-separable asymmetric demand and cost functions. A path-based solution algorithm is presented based on the three ideas of decomposition, column generation, and linearization, which have proved to be effective in tackling large-size networks. Numerical results over the Chicago sketch network suggest that the algorithm converges quickly within the first iterations, but is less effective as the solution gets closer to the neighborhood of the equilibrium solution. The sluggish convergence behavior is attributed to the difficulty of searching the space of strategy-based transit assignment model.

Traffic assignment (TA) seeks to estimate the distribution of travel demand in a transportation network and the resulting link and path travel-times. Such information supports important urban planning functions such as evaluating and selecting infrastructure projects, and making policies related to travel demand management and control. Given its importance, TA models and their solution algorithms have been a recurrent theme in transportation research.

In urban travel forecasting, it is well known that TA is the fourth and the last step of the so-called four-step model, which also includes trip generation, trip distribution, and modal split ( 1 ). While the four-step model remains the state-of-the-practice in transportation planning, its shortcomings have been known and criticized for decades ( 2 , 3 ). A widely cited flaw is the inconsistency caused by the inability of a sequential procedure to capture the inherent interdependence between the steps. Consequently, many have attempted to integrate all or part of the four steps into various “combined” models ( 4 – 7 ). The state-of-the-art on these models has evolved to include various features to improve the realism of the model representation, such as user heterogeneity ( 4 ), composite mode choice ( 8 ), non-separable/asymmetric cost functions ( 5 , 7 ), and demand-side uncertainty ( 6 , 9 ). However, large-scale applications of these combined models are rare in the literature, mainly because the computational tools for transit assignment are relatively underdeveloped ( 4 , 5 ).

Mathematically, combined TA models can be formulated as one of the following: a nonlinear program, a variational inequality problem (VIP), a fixed point (FP) problem, and a nonlinear complementarity problem (NCP) ( 10 ). Of these approaches, nonlinear programming is probably the most widely used, but it is also more restrictive than the other approaches in that it requires symmetric cost functions ( 6 ). Therefore, most advanced models are formulated as VIP, FP, or NCP models, among which NCP models have been studied to a lesser extent (see [ 4 ] or [ 6 ] for examples).

Among combined TA models with two or more modes of transportation, namely “multi-modal” TA models, early studies often treated the transit mode as a dedicated service with a fixed cost between origin-destination (O-D) pairs. More sophisticated models have been proposed, however, to treat the transit mode through a “frequency-based” assignment ( 11 – 14 ). At the core of a frequency-based assignment model is the assumption that transit passengers use “strategy” to navigate through transit networks, which captures, with reasonable behavioral realism, how the passengers make choices at a transit stop where multiple lines are available.

The solution of the multi-modal TA problem has been mostly based on the diagonalization algorithm ( 15 ), the method of successive averages ( 16 ), and sensitivity-analysis based methods ( 17 ). Application of these methods on large-scale congested networks, to the best of the authors’ knowledge, has been rather limited, and hence their performance in real-world applications is largely unknown.

In recent studies, it has been recognized that the structure of the NCP model lends itself well to many efficient solution methods in large-scale problems. As a result, NCP assignment models of auto or transit mode have received more attention in various applications, for example, O-D demand estimation ( 18 ), network design problems ( 19 – 21 ), facility location problems ( 22 , 23 ), and congestion toll pricing ( 24 ). In spite of these efforts, however, there is still a gap in the literature on extending the NCP model to a multi-modal setting with a transit mode. This study aims to fill this gap by presenting a new NCP model which integrates TA and mode choice between auto and transit modes. Our study will leverage on the previous works by Aashtiani ( 25 ), which developed an NCP formulation for auto user equilibrium assignment, and by Babazadeh and Aashtiani ( 26 ), which developed an NCP formulation for frequency-based transit assignment in a congested network. This paper contributes to the literature in the following directions:

A joint NCP formulation of auto-transit assignment is introduced by integrating two previous formulations. The new formulation allows for non-separable asymmetric cost and demand functions.

Based on Aashtiani’s algorithm ( 25 ), a solution algorithm, capable of tackling large-size problems, is presented.

The performance measures of the solution algorithm are examined and reported in large-scale (although the convergence is not proven).

Complementarity Formulations for TA

A TA formulation is described here as “path-based” if it is written in relation to path-flow variables. Two separate path-based NCP models can be distinguished in the literature for auto and transit modes. These models are briefly introduced in next two sub-sections followed by a general description of their solution.

Path-Based Auto Assignment Model

The assignment of auto users is based on the concept of user equilibrium. In transportation literature, such equilibrium is often stated as Wardrop’s first principle which is “at equilibrium, for each O-D pair the travel-times on all the routes actually used are equal and less than the travel-times on non-used routes” ( 25 ). Under some mild assumptions, for example, links between volume and delay functions being continuous and non-decreasing, Aashtiani ( 25 ) proved that the user equilibrium problem with elastic demand functions can be stated as a path-based NCP model. Given that, Aashtiani’s model can be stated as:

(\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u^{A})) u_{rs}^{A} = 0 \forall r \in R, s \in S .

(1)

\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u^{A}) \geq 0 \forall r \in R, s \in S .

(2)

u_{rs}^{A} \geq 0 \forall r \in R, s \in S .

(3)

(t_{k}^{A} (f^{A}) - u_{rs}^{A}) f_{k}^{A} = 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(4)

t_{k}^{A} (f^{A}) - u_{rs}^{A} \geq 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(5)

f_{k}^{A} \geq 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(6)

where

R: set of trip origins.

S: set of trip destinations.

$δ_{lk}$ : a binary variable which is 1 if a link l lies on a path k and 0 otherwise.

$L^{A}$ : set of auto links in the network.

$K_{rs}^{A}$ : set of directed paths from r to s for auto mode, r∈R, s∈S.

$u_{rs}^{A}$ : minimum travel-time for auto mode from r to s, r∈R, s∈S.

$u^{A}$ : vector of minimum travel-times for auto mode.

$f_{k}^{A}$ : passenger flow on path k for auto mode, k∈ $K_{rs}^{A}$ , r∈R, s∈S.

$f^{A}$ : vector of path-flows for auto mode.

$x_{l}^{A}$ : auto passenger flow at link l, l∈ $L^{A}$ .

$x^{A}$ : vector of link flows for auto mode.

$t_{l}^{A}$ (.): volume-delay function for auto mode on link l, l∈ $L^{A}$ .

$t_{k}^{A}$ (.): travel-time of auto mode on path k, k∈ $K_{rs}^{A}$ , r∈R, s∈S.

$D_{rs}^{A}$ (.): demand function of auto mode from r to s, r∈R, s∈S.

and

t_{k}^{A} (f^{A}) = \sum_{l \in L^{A}} t_{l}^{A} (x^{A}) δ_{l, k} \forall k \in K_{rs}^{A}, r \in R, s \in S .

(7)

x_{l}^{A} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{A}} f_{k}^{A} δ_{l, k} \forall l \in L^{A} .

(8)

In the above model, Equations 1 to 3 state the flow conservation in a complementarity form and Equations 4 to 6 are those commonly used to describe Wardrop’s first principle in auto assignment ( 27 ).

Aashtiani ( 25 ) suggested that the volume-delay function of the above model can take a general form and need not depend only on its own traffic flow. As a result, more sophisticated volume-delay functions, as in two-way streets or intersections, may be incorporated into the model. He further extended the model for multiple modes of transportation while considering the demand as a function of all modes. This model has been recognized as the first model in the literature allowing for non-separable volume-delay and performance-demand functions ( 5 ). However, its representation of transit mode is still quite simplistic in the sense that it does not account for features like optimal strategies later developed in the literature.

Path-Based Transit Assignment Model

The behavior of transit users is more complex than that of auto users and is often modeled using the concept of “optimal strategy.” A “strategy,” first introduced by Spiess ( 11 ), is a set of rules that allows a transit user to navigate through a transit network ( 28 ). In most recent transit assignment models, it is assumed that transit users seek to minimize their “expected” travel-times through finding the optimal strategies ( 26 ).

The optimal strategy assignment with fixed travel-times was formulated by Spiess and Florian ( 12 ) as a linear programming problem in the space of link-flow variables. Later Babazadeh ( 14 ) proved that the optimal strategy assignment problem can be alternatively expressed in the space of path-flow variables. To formulate this problem, the following NCP model was proposed ( 26 ):

(\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T}) u_{rs}^{T} = 0 \forall r \in R, s \in S .

(9)

\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T} \geq 0 \forall r \in R, s \in S .

(10)

u_{rs}^{T} \geq 0 \forall r \in R, s \in S .

(11)

(t_{k}^{T} (f^{T}) - u_{rs}^{T}) f_{k}^{T} = 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(12)

t_{k}^{T} (f^{T}) - u_{rs}^{T} \geq 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(13)

f_{k}^{T} \geq 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(14)

(1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, s}^{T}) w_{i, s}^{T} = 0 \forall i \in, s \in S .

(15)

1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, s}^{T} \geq 0 \forall i \in, s \in S .

(16)

w_{i, s}^{T} \geq 0 \forall i \in, s \in S .

(17)

(F_{l}^{T} w_{i, s}^{T} - x_{l, s}^{T}) λ_{l, s}^{T} = 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(18)

F_{l}^{T} w_{i, s}^{T} - x_{l, s}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(19)

λ_{l, s}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(20)

where

$L^{T}$ : set of transit links in the network.

$K_{rs}^{T}$ : set of directed paths from r to s for transit mode, r∈R, s∈S.

$u_{rs}^{T}$ : minimum expected travel-time for transit mode from r to s, r∈R, s∈S.

$u^{T}$ :vector of minimum expected travel-times for transit mode.

$f_{k}^{T}$ : passenger flow on path k for transit mode, k∈ $K_{rs}^{T}$ , r∈R, s∈S.

$f^{T}$ : vector of path-flows for transit mode.

$x_{l}^{T}$ : transit passenger flow at link l, l∈ $L^{T}$ .

$x^{T}$ : vector of link flows for transit mode.

$t_{l}^{T}$ (.): volume-delay function for transit mode on link l, l∈ $L^{T}$ .

$t_{k}^{T}$ (.): expected travel-time of transit mode on path k, k∈ $K_{rs}^{T}$ , r∈R, s∈S.

$D_{rs}^{T}$ (.): demand function of transit mode from r to s, r∈R, s∈S.

$I_{b}^{T}$ : set of boarding stops for transit mode.

$L_{b, i}^{T}$ : set of boarding links (i.e., movements) to transit lines at stop i, i∈ $I_{b}^{T}$ .

$L_{b}^{T}$ : set of all boarding links to transit lines.

$F_{l}^{T}$ : frequency of arriving transit vehicles corresponding to the boarding link l, l∈ $L_{b}^{T}$ .

$w_{i, s}^{T}$ : total waiting time of transit passengers traveling to destination s at stop i, i∈ $I_{b}^{T}$ , s∈S.

$λ_{l, s}^{T} :$ an auxiliary variable used for transit passengers of destination s at the boarding link l, l∈ $L_{b}^{T}$ , s∈S.

$x_{l, s}^{T}$ : transit passenger flow to the destination s at the boarding link l, l∈ $L_{b}^{T}$ , s∈S.

and

t_{k}^{T} (f^{T}) = \sum_{l \in L^{T}} t_{l}^{T} (x^{T}) δ_{l, k} + \sum_{l \in L_{b}^{T}} λ_{l, s}^{T} δ_{l, k} \forall k \in K_{rs}^{T}, r \in R, s \in S .

(21)

x_{l}^{T} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{T}} f_{k}^{T} δ_{l, k} \forall l \in L^{T} .

(22)

x_{l, s}^{T} = \sum_{r \in R} \sum_{k \in K_{rs}^{T}} f_{k}^{T} δ_{l, k} \forall l \in L^{T}, s \in S .

(23)

The first six equations of the above model are adopted from Aashtiani’s model. Equations 9 to 11, again, stand for the flow conservation. Babazadeh ( 14 ) also proved that, using auxiliary variables $λ_{l, s}^{T}$ , Equations 12 to 20 implicitly state the strategy-based flow distribution ( 18 ). To this end, he first transformed the problem of strategy-based equilibrium transit assignment to an equivalent system of linear equations. He then showed that, under mild assumptions, the problem can be stated in relation to link flows rather than strategy flows. The link-based problem is then reformulated in the space of path-flow variables, which yields the above formulation. The reader is referred to Babazadeh ( 14 ) for more details.

A few remarks are in order here. Equations 9 to 20 may be regarded as an extension of the optimal strategy assignment proposed by Spiess and Florian ( 12 ) in a complementarity form. To the best of the authors’ knowledge, Babazadeh ( 14 ) and Babazadeh and Aashtiani ( 26 ), while accounting for congestion effects, are the only studies in the literature that report large-scale applications of asymmetric strategy-based transit assignment. Note that, similar to Aashtiani’s model, an elastic demand function, i.e., $D_{rs}^{T}$ = $D_{rs}^{T}$ ( $u^{T}$ ), ∀r∈R, s∈S, can be incorporated into Equations 9 to 20.

Solution of Complementarity Assignment Models

To solve the complementarity assignment model 1 to 6, an algorithm based on decomposition, column generation, and linearization was proposed by Aashtiani ( 25 ). A similar algorithm was later developed to the transit model by Babazadeh ( 14 ). According to the authors’ knowledge, no official proof has been reported for the convergence of the algorithm in a general case. However, the convergence has been supported by empirical studies on various examples in the literature ( 25 , 26 ). Aashitiani’s solution algorithm is briefly described below ( 25 ).

The complementarity assignment model typically has intractable numbers of solution variables and constraints. In the decomposition technique, this problem is broken into smaller sub-problems each corresponding to a single O-D pair. While solving each sub-problem, the variables corresponding to other O-D pairs are fixed. Accordingly, rather than solving the problem simultaneously for all O-D pairs, the algorithm iteratively solves the sub-problems and updates the resulting variables in the network.

Even with decomposition, enumerating all paths for a single O-D pair is still prohibitively expensive. To bypass a full enumeration of paths, the column generation technique is used, which only generates and keeps a small number of “working paths” as needed. Working paths for each O-D pair are those actually used by travelers and can typically be found by path-finding algorithms.

Finally, a Newton-type linearization technique is applied to tackle the non-linearity arising in the problem. Given that the complementarity assignment model has a general form as

Ψ (Y) . Y = 0;

(24)

Ψ (Y) \geq 0;

(25)

Y \geq 0,

(26)

the problem, in a given solution $\bar{Y}$ , can be linearized as follows:

[Ψ (\bar{Y}) + (Y - \bar{Y}) . \nabla Ψ (\bar{Y})] . Y = 0;

(27)

[Ψ (\bar{Y}) + (Y - \bar{Y}) . \nabla Ψ (\bar{Y})] \geq 0;

(28)

Y \geq 0 .

(29)

The original Equations 24 to 26 are then solved by successive linearizations as Equations 27 to 29 and the current solution $\bar{Y}$ is replaced by the new solution Y until the consistency is met.

The Joint Formulation for Auto-Transit Assignment

The two previous path-based formulations can be integrated into a single NCP, in which demand and travel-time functions are expressed in relation to f, x, and u, as the vectors of path-flows, link flows, and minimum O-D travel-times for both modes. Specifically, f = ( $f^{A}$ , $f^{T}$ ), x = ( $x^{A}$ , $x^{T}$ ), and u = ( $u^{A}$ , $u^{T}$ ). Note that, although Equations 36 to 41 for transit mode are similar to Equations 30 to 35 for auto mode, they are written separately for clarity of exposition.

The problem P (joint formulation)

(\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u)) u_{rs}^{A} = 0 \forall r \in R, s \in S .

(30)

\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u) \geq 0 \forall r \in R, s \in S .

(31)

u_{rs}^{A} \geq 0 \forall r \in R, s \in S .

(32)

(t_{k}^{A} (f) - u_{rs}^{A}) f_{k}^{A} = 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(33)

t_{k}^{A} (f) - u_{rs}^{A} \geq 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(34)

f_{k}^{A} \geq 0 \forall k \in K_{rs}^{A}, r \in R, s \in S .

(35)

(\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T} (u)) u_{rs}^{T} = 0 \forall r \in R, s \in S .

(36)

\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T} (u) \geq 0 \forall r \in R, s \in S .

(37)

u_{rs}^{T} \geq 0 \forall r \in R, s \in S .

(38)

(t_{k}^{T} (f) - u_{rs}^{T}) f_{k}^{T} = 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(39)

t_{k}^{T} (f) - u_{rs}^{T} \geq 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(40)

f_{k}^{T} \geq 0 \forall k \in K_{rs}^{T}, r \in R, s \in S .

(41)

(1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, s}^{T}) w_{i, s}^{T} = 0 \forall i \in I_{b}^{T}, s \in S .

(42)

1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, s}^{T} \geq 0 \forall i \in I_{b}^{T}, s \in S .

(43)

w_{i, s}^{T} \geq 0 \forall i \in I_{b}^{T}, s \in S .

(44)

(F_{l}^{T} w_{i, s}^{T} - x_{l, s}^{T}) λ_{l, s}^{T} = 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(45)

F_{l}^{T} w_{i, s}^{T} - x_{l, s}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(46)

λ_{l, s}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T}, s \in S .

(47)

where

t_{k}^{A} (f) = \sum_{l \in L^{A}} t_{l}^{A} (x) δ_{l, k} \forall k \in K_{rs}^{A}, r \in R, s \in S .

(48)

t_{k}^{T} (f) = \sum_{l \in L^{T}} t_{l}^{T} (x) δ_{l, k} + \sum_{l \in L_{b}^{T}} λ_{l, s}^{T} δ_{l, k} \forall k \in K_{rs}^{T}, r \in R, s \in S .

(49)

x_{l}^{A} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{A}} f_{k}^{A} δ_{l, k} \forall l \in L^{A} .

(50)

x_{l}^{T} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{T}} f_{k}^{T} δ_{l, k} \forall l \in L^{T} .

(51)

x_{l, s}^{T} = \sum_{r \in R} \sum_{k \in K_{rs}^{T}} f_{k}^{T} δ_{a, k} \forall l \in L^{T}, s \in S .

(52)

Application of vectors of travel-times and flows, that is, u and f, in the formulation of Problem P, enables the model to express users’ equilibrium in a very general framework, for example, allowing for non-separable asymmetric demand/cost functions, or variable total demand. The above formulation is set up in a similar way as in Aashtiani’s multi-modal NCP ( 25 ). The main difference is that the equilibrium for the transit mode is based on the concept of optimal strategy rather than Wardrop’s first principle. In general, the formulation allows for the multi-modal equilibrium conditions as follows:

Auto equilibrium based on Wardrop’s first principle, through Equations 30 to 35 ( 25 ),

Transit equilibrium based on optimal strategy, through Equations 36 to 47 ( 26 ), and

Interaction/trade-off between the two modes in cost/demand functions, by considering $D_{rs}^{A}$ , $D_{rs}^{T}$ , $t_{k}^{A}$ , and $t_{k}^{T}$ , respectively, as $D_{rs}^{A}$ ( $u^{A}$ , $u^{T}$ ) for r∈R, s∈S, $D_{rs}^{T}$ ( $u^{A}$ , $u^{T}$ ) for r∈R, s∈S, $t_{k}^{A} (f^{A}$ , $f^{T})$ for k∈ $K_{rs}^{A}$ , r∈R, s∈S, and $t_{k}^{T}$ = $t_{k}^{T} (f^{A}$ , $f^{T})$ for k∈, r∈R, s∈S.

It is worth mentioning that, while only two modes are considered in the formulation, extending the model to include multiple auto and transit modes is straightforward.

Solution Method

The model of this paper is a complementarity problem with a similar structure to the previous models introduced earlier. Therefore, the same three techniques of decomposition, path generation (column generation), and linearization are adopted to solve this problem.

Decomposition

First the problem is decomposed into sub-problems corresponding to each O-D pair and each of them is solved iteratively. The sub-problem corresponding to (r,s), that is, the decomposed version of the problem P for a single O-D pair (r,s), can be written as follows:

The sub-problem SP(r,s), for r∈R, s∈S:

(\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u)) u_{rs}^{A} = 0 .

(53)

\sum_{k \in K_{rs}^{A}} f_{k}^{A} - D_{rs}^{A} (u) \geq 0 .

(54)

u_{rs}^{A} \geq 0 .

(55)

(t_{k}^{A} (f) - u_{rs}^{A}) f_{k}^{A} = 0 \forall k \in K_{rs}^{A} .

(56)

t_{k}^{A} (f) - u_{rs}^{A} \geq 0 \forall k \in K_{rs}^{A} .

(57)

f_{k}^{A} \geq 0 \forall k \in K_{rs}^{A} .

(58)

(\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T} (u)) u_{rs}^{T} = 0 .

(59)

\sum_{k \in K_{rs}^{T}} f_{k}^{T} - D_{rs}^{T} (u) \geq 0 .

(60)

u_{rs}^{T} \geq 0 .

(61)

(t_{k}^{T} (f) - u_{rs}^{T}) f_{k}^{T} = 0 \forall k \in K_{rs}^{T} .

(62)

t_{k}^{T} (f) - u_{rs}^{T} \geq 0 \forall k \in K_{rs}^{T} .

(63)

f_{k}^{T} \geq 0 \forall k \in K_{rs}^{T} .

(64)

(1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, rs}^{T}) w_{i, rs}^{T} = 0 \forall i \in I_{b}^{T} .

(65)

1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, rs}^{T} \geq 0 \forall i \in I_{b}^{T} .

(66)

w_{i, rs}^{T} \geq 0 \forall i \in I_{b}^{T} .

(67)

(F_{l}^{T} w_{i, rs}^{T} - x_{l, rs}^{T}) λ_{l, rs}^{T} = 0 \forall l = (i, j) \in L_{b}^{T} .

(68)

F_{l}^{T} w_{i, rs}^{T} - x_{l, rs}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T} .

(69)

λ_{l, rs}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T} .

(70)

In the above single O-D formulation for (r,s), r∈R, s∈S, the new notations applied are

$x_{l, rs}^{T}$ : transit passenger flow from r to s at link l, l∈ $L^{T}$ .

$w_{i, rs}^{T}$ : total waiting time of transit passengers traveling from r to s at stop i, i∈ $I_{b}^{T}$ . $λ_{l, rs}^{T}$ : an auxiliary variable used for transit passengers from r to s at the boarding link l, $l$ ∈ $L_{b}^{T}$ .

Furthermore, $x_{l, rs}^{T}$ and $t_{k}^{T} (f)$ are redefined, accordingly, as:

x_{l, rs}^{T} = \sum_{k \in K_{rs}^{T}} f_{k}^{T} δ_{l, k} \forall l \in L^{T} .

(71)

t_{k}^{T} (f) = \sum_{l \in L^{T}} t_{l}^{T} (x) δ_{l, k} + \sum_{l \in L_{b}^{T}} λ_{l, rs}^{T} δ_{l, k} \forall k \in K_{rs}^{T} .

(72)

While solving the sub-problem SP(r,s), the variables associated with the O-D pairs other than (r,s) are considered to be fixed. The obtained $f_{k}^{A}$ and $f_{k}^{T}$ values are used after solving each sub-problem to update the link-/path-flows of the original problem. As suggested by Babazadeh and Aashtiani ( 26 ), however, after all the sub-problems corresponding to a destination are solved, auxiliary variables (i.e., $λ_{l, s}^{T}$ ∀l=( $i, j$ )∈ $L_{b}^{T}$ , s∈S) are updated as follows:

λ_{l, s}^{T} = \frac{\sum_{r \in R} λ_{l, rs}^{T}}{\sum_{l' \in L_{b}^{T}} \sum_{r \in R} F_{l'}^{T} λ_{l', rs}^{T}} \forall l \in L_{b}^{T}, s \in S .

(73)

Path Generation

In each iteration, path generation involves determining the single shortest path between O-D pairs for each mode. As the algorithm proceeds, new shortest paths generated for an O-D pair are introduced to the model. These paths, denominated as “working” or “active” paths, are stored for each O-D pair throughout the iterations of the algorithm.

Following the notations used by Babazadeh and Aashtiani ( 26 ), let us define:

$K_{rs}^{A, w}$ : set of working paths of auto mode, from r to s, $K_{rs}^{A, w}$ ⊆ $K_{rs}^{A}$ .

$L^{A}$ ( $K_{rs}^{A, w}$ ): set of auto links lying on paths of $K_{rs}^{A, w}$ .

$K_{rs}^{T, w}$ : set of working paths of transit mode, from r to s, $K_{rs}^{T, w}$ ⊆ $K_{rs}^{T}$ .

$I_{b}^{T}$ ( $K_{rs}^{T, w}$ ): set of boarding stops of transit mode, lying on $K_{rs}^{T, w}$ paths.

$L_{b}^{T}$ ( $K_{rs}^{T, w}$ ): set of boarding links of transit mode, lying on $K_{rs}^{T, w}$ paths.

$L^{T}$ ( $K_{rs}^{T, w}$ ): set of transit links lying on paths of $K_{rs}^{T, w}$ .

In the path generation phase, the above notations are considered in SP(r,s) instead of $K_{rs}^{A}$ , $L^{A}$ , $K_{rs}^{T}$ , $I_{b}^{T}$ , $L_{b}^{T}$ , and $L^{T}$ , respectively, implying that only working paths are taken into account while dealing with sub-problems. The resulting formulation is denominated as $S P^{w}$ (r,s) in this paper.

Linearization

As mentioned earlier, the idea of linearization is to start with an initial feasible solution, $\bar{Y}$ , and iteratively estimate the nonlinear terms of the model, such as Ψ(Y), by their linear approximations, i.e., Ψ( $\bar{Y}$ ) + (Y- $\bar{Y}$ ).∇Ψ( $\bar{Y}$ ). Given that $D_{rs}^{A}$ (u), $D_{rs}^{T}$ (u), $T_{k}^{A}$ (f), and $T_{k}^{T}$ (f) are the nonlinear terms arising in $S P^{w}$ (r,s), the corresponding linear approximations are:

D_{rs}^{A} (u) \approx D_{rs}^{A} (\bar{u}) + (u_{rs}^{A} - {\bar{u}}_{rs}^{A}) \frac{\partial D_{rs}^{A} (\bar{u})}{\partial u_{rs}^{A}} + (u_{rs}^{T} - {\bar{u}}_{rs}^{T}) \frac{\partial D_{rs}^{A} (\bar{u})}{\partial u_{rs}^{T}} .

(74)

D_{rs}^{T} (u) \approx D_{rs}^{T} (\bar{u}) + (u_{rs}^{A} - {\bar{u}}_{rs}^{A}) \frac{\partial D_{rs}^{T} (\bar{u})}{\partial u_{rs}^{A}} + (u_{rs}^{T} - {\bar{u}}_{rs}^{T}) \frac{\partial D_{rs}^{T} (\bar{u})}{\partial u_{rs}^{T}} .

(75)

\begin{matrix} t_{k}^{A} (f) & \approx t_{k}^{A} (\bar{f}) + \sum_{k' \in K_{rs}^{A, w}} (f_{k'}^{A} - {\bar{f}}_{k'}^{A}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k'}^{A}} \\ + \sum_{k' \in K_{rs}^{T, w}} (f_{k'}^{T} - {\bar{f}}_{k'}^{T}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k'}^{T}} . \end{matrix}

(76)

\begin{matrix} t_{k}^{T} (f) & \approx t_{k}^{T} (\bar{f}) + \sum_{k' \in K_{rs}^{A, w}} (f_{k'}^{A} - {\bar{f}}_{k'}^{A}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{A}} \\ + \sum_{k' \in K_{rs}^{T, w}} (f_{k'}^{T} - {\bar{f}}_{k'}^{T}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{T}} . \end{matrix}

(77)

Details on how to calculate partial derivatives are omitted here for brevity. Based on the approximations in Equations 74 to 77, the linearized version of $S P^{w}$ (r,s), denominated by $LS P^{w}$ (r,s), can be formulated as follows.

The linearized sub-problem $LS P^{w}$ (r,s), for r∈R, s∈S:

(\sum_{k \in K_{r s}^{A, w}} f_{k}^{A} - [D_{r s}^{A} (\bar{u}) + (u_{r s}^{A} - {\bar{u}}_{r s}^{A}) \frac{\partial D_{r s}^{A} (\bar{u})}{\partial u_{r s}^{A}} + (u_{r s}^{T} - {\bar{u}}_{r s}^{T}) \frac{\partial D_{r s}^{A} (\bar{u})}{\partial u_{r s}^{T}}]) u_{r s}^{A} = 0 .

(78)

\begin{matrix} \sum_{k \in K_{rs}^{A, w}} f_{k}^{A} - [D_{rs}^{A} (\bar{u}) + (u_{rs}^{A} - {\bar{u}}_{rs}^{A}) \frac{\partial D_{rs}^{A} (\bar{u})}{\partial u_{rs}^{A}} \\ + (u_{rs}^{T} - {\bar{u}}_{rs}^{T}) \frac{\partial D_{rs}^{A} (\bar{u})}{\partial u_{rs}^{T}}] \geq 0 . \end{matrix}

(79)

u_{rs}^{A} \geq 0

(80)

\begin{array}{l} [t_{k}^{A} (\bar{f}) + \sum_{k^{'} \in K_{r s}^{A, w}} (f_{k^{'}}^{A} - {\bar{f}}_{k^{'}}^{A}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k^{'}}^{A}} + \sum_{k^{'} \in K_{r s}^{T, w}} (f_{k^{'}}^{T} - {\bar{f}}_{k^{'}}^{T}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k^{'}}^{T}}] \\ - u_{r s}^{A}) f_{k}^{A} = 0 \forall k \in K_{r s}^{A, w} . \end{array}

(81)

\begin{matrix} [t_{k}^{A} (\bar{f}) + \sum_{k' \in K_{rs}^{A, w}} (f_{k'}^{A} - {\bar{f}}_{k'}^{A}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k'}^{A}} + \sum_{k' \in K_{rs}^{T, w}} (f_{k'}^{T} - {\bar{f}}_{k'}^{T}) \frac{\partial t_{k}^{A} (\bar{f})}{\partial f_{k'}^{T}}] \\ - u_{rs}^{A} \geq 0 \geq 0 \forall k \in K_{rs}^{A, w} . \end{matrix}

(82)

f_{k}^{A} \geq 0 \forall k \in K_{rs}^{A, w} .

(83)

(\sum_{k \in K_{r s}^{T, w}} f_{k}^{T} - [D_{r s}^{T} (\bar{u}) + (u_{r s}^{A} - {\bar{u}}_{r s}^{A}) \frac{\partial D_{r s}^{T} (\bar{u})}{\partial u_{r s}^{A}} + (u_{r s}^{T} - {\bar{u}}_{r s}^{T}) \frac{\partial D_{r s}^{T} (\bar{u})}{\partial u_{r s}^{T}}]) u_{r s}^{T} = 0 .

(84)

\begin{matrix} \sum_{k \in K_{rs}^{T, w}} f_{k}^{T} - [D_{rs}^{T} (\bar{u}) + (u_{rs}^{A} - {\bar{u}}_{rs}^{A}) \frac{\partial D_{rs}^{T} (\bar{u})}{\partial u_{rs}^{A}} + (u_{rs}^{T} - {\bar{u}}_{rs}^{T}) \frac{\partial D_{rs}^{T} (\bar{u})}{\partial u_{rs}^{T}}] \geq 0 . \end{matrix}

(85)

u_{rs}^{T} \geq 0 .

(86)

\begin{matrix} ([t_{k}^{T} (\bar{f}) + \sum_{k' \in K_{rs}^{A, w}} (f_{k'}^{A} - {\bar{f}}_{k'}^{A}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{A}} + \sum_{k' \in K_{rs}^{T, w}} (f_{k'}^{T} - {\bar{f}}_{k'}^{T}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{T}}] - u_{rs}^{T}) \\ f_{k}^{T} = 0 \forall k \in K_{rs}^{T, w} . \end{matrix}

(87)

\begin{matrix} [t_{k}^{T} (\bar{f}) + \sum_{k' \in K_{rs}^{A, w}} (f_{k'}^{A} - {\bar{f}}_{k'}^{A}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{A}} + \sum_{k' \in K_{rs}^{T, w}} (f_{k'}^{T} - {\bar{f}}_{k'}^{T}) \frac{\partial t_{k}^{T} (\bar{f})}{\partial f_{k'}^{T}}] \\ - u_{rs}^{T} \geq 0 \forall k \in K_{rs}^{T, w} . \end{matrix}

(88)

f_{k}^{T} \geq 0 \forall k \in K_{rs}^{T, w} .

(89)

(1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, rs}^{T}) w_{i, rs}^{T} = 0 \forall i \in I_{b}^{T} (K_{rs}^{T, w}) .

(90)

1 - \sum_{l \in L_{b, i}^{T}} F_{l}^{T} λ_{l, rs}^{T} \geq 0 \forall i \in I_{b}^{T} (K_{rs}^{T, w}) .

(91)

w_{i, rs}^{T} \geq 0 \forall i \in I_{b}^{T} (K_{rs}^{T, w}) .

(92)

(F_{l}^{T} w_{i, rs}^{T} - x_{l, rs}^{T}) λ_{l, rs}^{T} = 0 \forall l = (i, j) \in L_{b}^{T} (K_{rs}^{T, w}) .

(93)

F_{l}^{T} w_{i, rs}^{T} - x_{l, rs}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T} (K_{rs}^{T, w}) .

(94)

λ_{l, rs}^{T} \geq 0 \forall l = (i, j) \in L_{b}^{T} (K_{rs}^{T, w}) .

(95)

To start the linearization process in solving the above problem, a good initial solution may be shortest paths. For the transit mode, the shortest path further depends on auxiliary variables $λ_{l, s}^{T}$ (see Equation 21). Babazadeh and Aashtiani ( 26 ) proposed to consider initially $λ_{l, s}^{T}$ = $1 / \sum_{l' \in L_{b, i}^{T}} F_{l'}^{T}$ for all l=(i,j)∈ $L_{b}^{T}$ .

Termination Criteria

To check the convergence of the assignment algorithm, the well-known relative gap and a measure of demand error are applied. In the following, these measures are introduced.

Relative Gap

Relative gap is a common stopping criterion in the literature of TA algorithms ( 8 , 20 ). It is used to measure how far away the current solution is from the true equilibrium. For the auto mode, the relative gap can be defined as:

R G^{A} = \frac{TT T^{A} - {TTT}_{\min}^{A}}{TT T^{A}}

(96)

where

TT T^{A} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{A}} f_{k}^{A} t_{k}^{A} (f),

(97)

{TTT}_{\min}^{A} = \sum_{r \in R} \sum_{s \in S} d_{rs}^{A} u_{rs}^{A},

(98)

d_{rs}^{A} = \sum_{k \in K_{rs}^{A}} f_{k}^{A} .

(99)

Based on the notations introduced earlier, the following definition of the relative gap can also be applied to the path-based transit assignment:

R G^{T} = \frac{TT T^{T} - {TTT}_{\min}^{T}}{TT T^{T}}

(100)

where

TT T^{T} = \sum_{r \in R} \sum_{s \in S} \sum_{k \in K_{rs}^{T}} f_{k}^{T} t_{k}^{T} (f),

(101)

{TTT}_{\min}^{T} = \sum_{r \in R} \sum_{s \in S} d_{rs}^{T} u_{rs}^{T},

(102)

d_{rs}^{T} = \sum_{k \in K_{rs}^{T}} f_{k}^{T} .

(103)

To integrate both auto and transit relative gaps into a single measure, the following relative gap is adopted in this paper:

RG = \frac{TTT - TT T_{\min}}{TTT}

(104)

where

TTT = \sum_{r \in R} \sum_{s \in S} (\sum_{k \in K_{rs}^{A}} f_{k}^{A} t_{k}^{A} (f) + \sum_{k \in K_{rs}^{T}} f_{k}^{T} t_{k}^{T} (f)),

(105)

TT T_{\min} = \sum_{r \in R} \sum_{s \in S} (d_{rs}^{A} u_{rs}^{A} + d_{rs}^{T} u_{rs}^{T}) .

(106)

Similar to Equation 104, but at the scale of a single O-D pair, another relative gap is used here in the linearization process where $S P^{w}$ (r,s) is solved. This relative gap is defined, for each (r,s), r∈R, s∈S, as:

R G_{rs} = \frac{TT T_{rs} - TT T_{\min, rs}}{TT T_{rs}}

(107)

where

TT T_{rs} = \sum_{k \in K_{rs}^{A}} f_{k}^{A} t_{k}^{A} (f) + \sum_{k \in K_{rs}^{T}} f_{k}^{T} t_{k}^{T} (f),

(108)

TT T_{\min, rs} = d_{rs}^{A} u_{rs}^{A} + d_{rs}^{T} u_{rs}^{T} .

(109)

Demand Error

Another issue that may appear in multi-modal assignments is the amount of misplaced O-D flow for each mode ( 29 ). Following Aashtiani ( 25 ), this issue is addressed in this paper by using a “demand error” criterion that indicates how much the amount of flow for one mode is compatible with the performance-demand function of that mode. For auto and transit modes, the demand error is defined as Equations 110 and 111, respectively:

D E^{A} = \frac{\sum_{r \in R} \sum_{s \in S} | d_{rs}^{A} - D_{rs}^{A} (u) |}{\sum_{r \in R} \sum_{s \in S} d_{rs}^{A}} .

(110)

D E^{T} = \frac{\sum_{r \in R} \sum_{s \in S} | d_{rs}^{T} - D_{rs}^{T} (u) |}{\sum_{r \in R} \sum_{s \in S} d_{rs}^{T}} .

(111)

The two measures of demand error are integrated as:

DE = \frac{\sum_{r \in R} \sum_{s \in S} (| d_{rs}^{A} - D_{rs}^{A} (u) | + | d_{rs}^{T} - D_{rs}^{T} (u) |)}{\sum_{r \in R} \sum_{s \in S} (d_{rs}^{A} + d_{rs}^{T})} .

(112)

Also, for each O-D pair (r,s), r∈R, s∈S:

D E_{rs} = \frac{| d_{rs}^{A} - D_{rs}^{A} (u) | + | d_{rs}^{T} - D_{rs}^{T} (u) |}{d_{rs}^{A} + d_{rs}^{T}} .

(113)

Solution Precision

To specify the precision of the assignment solution, two values of $e^{RG}$ and $e^{DE}$ can be considered:

RG \leq e^{RG},

(114)

DE \leq e^{DE} .

(115)

While solving the sub-problem $S P^{w}$ (r,s), r∈R, s∈S, the following termination criteria may also be checked:

R G_{rs} \leq e_{rs}^{RG},

(116)

D E_{rs} \leq e_{rs}^{DE} .

(117)

Solution Algorithm

Based on the main features of the solution, presented in previous sub-sections, Figure 1 provides a detailed description of the solution algorithm. The algorithm starts by generating an initial solution (i.e., single shortest paths) for both modes and initially setting the corresponding variables (lines 1–12). Prior to performing the main iterations including decomposition, path generation, and linearization, the algorithm checks whether or not the stopping criteria are already met (lines 13–16).

Figure 1.

Solution algorithm for the auto-transit complementarity assignment model.

Within the main iterations of the algorithm (lines 16–44), the problem is decomposed into O-D pairs. The decomposition has two phases, one over destinations (line 17) and the other over origins (line 29). The selection of destinations or origins in the decomposition process may be done in a random way or any predefined order. As discussed earlier, new shortest paths need to be generated and introduced to the model when solving the decomposed sub-problems SP(r,s). But calculating a shortest path from a single origin to a single destination, in a worst case analysis, is computationally equal to calculating the shortest path tree. Since calculation of shortest paths can put a heavy computational burden on the algorithm, it is not performed separately for all O-D pairs. Instead, for both auto and transit modes, shortest path trees are generated at the same time from all origins to a single destination (lines 18–22 for auto and 23–27 for transit) and the sets of auto and transit working paths are updated (lines 21 and 26, respectively). This is carried out in this paper using the Dijkstra algorithm.

By decomposition of the problem into a single O-D pair for (r,s) with updated sets of working paths (already available from lines 21 and 26) and updated minimum travel-times (lines 30 and 31), the problem $S P^{w}$ (r,s) is iteratively linearized and solved (lines 34–37) to satisfy the termination criteria for a single O-D pair (line 33). Lemke’s pivot algorithm is used here to solve linear complementarity problems ( 30 ). Variables $σ_{l}^{T}$ are temporarily used to calculate $\sum_{r \in R} λ_{l, rs}^{T}$ in Equation 88 (line 39). These values are applied in updating $λ_{l, s}^{T}$ (line 43), and in turn, the transit working paths (line 23). At the end of solving each sub-problem, the sets of auto and transit working paths are updated by removing redundant paths having zero flows (lines 40 and 41).

After each single round of solving all decomposed sub-problems and updating the variables (lines 17–44), the two measures RG and DE are recalculated (lines 45–47). The algorithm proceeds through the iterations until the stopping criteria are ultimately satisfied (line 16).

Numerical Results

To explore the performance of the solution algorithm, the Chicago sketch transportation network is considered in this section. The Chicago sketch network is a rather large representation of the Chicago city transportation network, consisting of 387 trip zones, 933 nodes, 2950 links, and 93,513 O-D pairs with non-zero traveling demand. For illustrative purposes, 55 artificial transit lines are considered, each with a nominal frequency of 0.25 (vehicles/minutes), and it is assumed that auto and transit modes have a shared right-of-way throughout the network. Figure 2 shows the configuration of this network along with the transit lines. All details about transit lines and the Chicago sketch network (including link travel-times, capacities, and travel demands) may be found in Zarrinmehr et al. ( 20 ) and Bar-Gera ( 31 ).

Figure 2.

Topology of the Chicago sketch network and the transit lines ( 20 ).

The following implementation details and modeling assumptions are adopted in reporting the results in this section:

1) To capture various movements of transit users, a super-network is considered with a base layer corresponding to the auto mode ( 12 , 32 ). Transit movements are illustrated in relation to walking, boarding, alighting, and in-vehicle links, in a simple example in Figure 3 with transit lines L1 and L2 passing through stops 4, 5, 6 and 2, 5, 8 (denoted by 4(1)–5(1)–6(1) and 2(2)–5(2)–8(2)) respectively.

2) Given that:

- $t_{0, l}^{A}$ is the auto free-flow travel-time on link l (minutes), l∈ $L^{A}$ ,

- $C_{l}^{A}$ is the practical capacity of link l for auto mode (passengers/hour), l∈ $L^{A}$ , and

- $x_{l (0)}^{T}$ is the total amount of transit passenger flow passing through the auto link l (i.e., the base link l(0)), l∈ $L^{A}$ ),

Figure 3.

Example of super-network configuration.

an asymmetric auto travel-time, for the purposes of illustration, is adapted as follows:

t_{l}^{A} (x) = t_{0, l}^{A} (1 + 0.15 {(\frac{x_{l}^{A} + 0.2 x_{l (0)}^{T}}{C_{l}^{A}})}^{4}) \forall l \in L^{A} .

(118)

3) For transit mode, the in-vehicle travel-time is considered to be 30% more than the auto travel-time on the same link, implying that the transit traffic stream moves slightly slower than the auto. Besides, there are boarding/alighting delays at transit stops, referred to as dwell-times. To formulate the dwell-time function, it is assumed that:

- the in-vehicle link l∈ $L_{in - veh}^{T}$ ends with alighting link la and boarding link lb (e.g., in Figure 3, l = 4(1)–5(1), la = 5(1)–5(0), lb = 5(0)–5(2)),

- τ is the period of time in minutes in which the travel demand values are expressed (i.e., demand values are expressed in relation to passengers per hour, then τ = 60 minutes),

- $F_{lb}^{T}$ is the frequency of transit vehicles arriving at link lb, lb∈ $L_{b}^{T}$ ,

- $c_{l}^{T}$ is the average capacity of transit vehicles passing through the link l, l∈ $L_{in - veh}^{T}$ . In this paper, this capacity is considered to be 70 passengers over all transit vehicles, and

- $c_{l}^{T}$ is the capacity of the transit line at link l, in passengers/hour, l∈ $L_{in - veh}^{T}$ . The line capacity can be expressed in relation to vehicle capacities, as in Equation 119:

C_{l}^{T} = τ F_{lb}^{T} c_{l}^{T} \forall l \in L_{in - veh}^{T} .

(119)

Based on the above definitions, the dwell-time is modeled empirically using the following asymmetric formulation ( 26 ):

\begin{matrix} {dwt}_{l}^{T} (x^{T}) = {dwt}_{l}^{T} (x_{l}^{T}, x_{la}^{T}, x_{lb}^{T}) = 0.2 \\ + (\frac{1.26 x_{la}^{T} + 2.1 x_{lb}^{T}}{60 τ F_{lb}^{T}}) [1 + 2 {(\frac{x_{l}^{T}}{C_{l}^{T}})}^{2}] \forall l \in L_{in - veh}^{T} . \end{matrix}

(120)

All in all, the travel-time function for a transit link can be stated as:

t_{l}^{T} (x) = {\begin{matrix} 1.3 t_{0, l}^{A} (1 + 0.15 {(\frac{x_{l}^{A} + 0.2 x_{l (0)}^{T}}{C_{l}^{A}})}^{4}) + 0.2 + (\frac{1.26 x_{la}^{T} + 2.1 x_{lb}^{T}}{60 τ F_{lb}^{T}}) [1 + {(\frac{x_{l}^{T}}{C_{l}^{T}})}^{2}] l \in L_{in - veh}^{T} \\ 0 l \in L^{T} \ L_{in - veh}^{T} . \end{matrix}

(121)

4) For an O-D pair (r,s), the total amount of travel demand, $D_{rs}$ , is assumed to be fixed, but the demand share of each mode is variable using the following logit function ( 21 ).

\begin{matrix} D_{rs}^{A} (u) & = D_{rs}^{A} (u_{rs}^{A}, u_{rs}^{T}) \\ = D_{rs} \frac{e^{- 0.02 u_{rs}^{A} + 0.10}}{e^{- 0.02 u_{rs}^{A} + 0.10} + e^{- 0.02 u_{rs}^{T}}} \forall r \in R, s \in S . \end{matrix}

(122)

\begin{matrix} D_{rs}^{T} (u) & = D_{rs}^{T} (u_{rs}^{A}, u_{rs}^{T}) \\ = D_{rs} \frac{e^{- 0.02 u_{rs}^{T}}}{e^{- 0.02 u_{rs}^{A} + 0.10} + e^{- 0.02 u_{rs}^{T}}} \forall r \in R, s \in S . \end{matrix}

(123)

5) Walking is treated as a transit mode with infinite frequency at layer-0 (base network) of the super-network ( 12 ). The walking speed is considered to be 270 feet/minutes on average ( 33 ).

Based on the above assumptions, the algorithm was coded in Java programming language and executed on a server with an operating system of Red Hat Enterprise Linux Server release 5.4, a CPU of type Intel(R) Xeon(R) E5420 @ 2.50GHz, and 10 GB available RAM memory. The measures are reported during the successive iterations of the algorithm, which may offer a better insight about the performance of the algorithm. As a result, no pre-determined values are used for $e^{RG}$ and $e^{DE}$ as the termination criteria (line 16 of algorithm). At the stage of solving decomposed sub-problems, $S P^{w}$ (r,s), r∈R, s∈S (lines 33–38 of the algorithm), however, the values of $e_{rs}^{RG}$ and $e_{rs}^{DE}$ need to be determined. Experimentally, both of these values are considered to be 0.001 for the first three iterations and 0.00005 for the rest of iterations. Therefore, each separate sub-problem $S P^{w}$ (r,s), r∈R, s∈S, is solved to get $R G_{rs}$ ≤0.001 and $D E_{rs}$ ≤0.001 for iterations 1 to 3, and $R G_{rs}$ ≤0.00005 and $D E_{rs}$ ≤0.00005 beyond iteration 3.

The results of running the program through 500 iterations are reported in Table 1. Note that calculations of performance measures are carried out only to monitor the performance of the algorithm. Therefore, the run-times associated with calculating these measures (i.e., lines 13–15 and 45–47) are not included in the last column in Table 1. The RG and DE measures, during the first 20 iterations of the algorithm (8.3 minutes of running the program), are also illustrated separately in Figure 4.

Table 1.

Performance Measures of the Solution Algorithm for the Chicago Sketch Network

Iteration	Demand share (%)		Relative gap			Demand error			RunTime
Number	Auto	Transit	Auto	Transit	Integrated	Auto	Transit	Integrated	(sec)	(min)
1	84.38	15.62	0.5428	0.2526	0.4612	0.1468	0.5980	0.2373	46	0.8
2	77.61	22.39	0.0179	0.0774	0.0500	0.0274	0.0949	0.0425	76	1.3
3	78.48	21.52	0.0025	0.0265	0.0143	0.0167	0.0609	0.0262	99	1.7
4	78.09	21.91	0.0006	0.0152	0.0079	0.0075	0.0268	0.0117	123	2.0
5	78.09	21.91	0.0002	0.0110	0.0056	0.0054	0.0194	0.0085	147	2.4
6	78.02	21.98	0.0000	0.0082	0.0041	0.0041	0.0147	0.0065	172	2.9
7	77.99	22.01	0.0000	0.0075	0.0038	0.0036	0.0128	0.0056	197	3.3
8	77.96	22.04	0.0000	0.0065	0.0033	0.0031	0.0110	0.0048	220	3.7
9	77.94	22.06	0.0000	0.0054	0.0027	0.0027	0.0095	0.0042	244	4.1
10	77.93	22.07	0.0000	0.0051	0.0026	0.0023	0.0083	0.0037	268	4.5
15	77.90	22.10	0.0000	0.0039	0.0020	0.0016	0.0058	0.0025	383	6.4
20	77.89	22.11	0.0000	0.0034	0.0017	0.0013	0.0047	0.0021	498	8.3
50	77.88	22.12	0.0000	0.0020	0.0010	0.0007	0.0024	0.0011	1193	19.9
100	77.88	22.12	0.0000	0.0019	0.0010	0.0006	0.0023	0.0010	2429	40.5
200	77.88	22.12	0.0000	0.0016	0.0008	0.0005	0.0018	0.0008	4886	81.4
500	77.89	22.11	0.0000	0.0014	0.0007	0.0004	0.0015	0.0007	12155	202.6

Figure 4.

Performance measures for the Chicago sketch network: (a) relative gap and (b) demand error.

The results shown in Table 1 indicate that the auto relative gap converges quickly in the first few iterations of the algorithm. For the transit relative gap the convergence trend is also in line with the study of Babazadeh and Aashtiani ( 26 ) in the sense that the relative gap reduces sharply within the first iterations of the algorithm, but bears a low reduction, and then almost remains unchanged as the algorithm proceeds to further iterations. The table shows, for example, that the reduction of transit relative gap is only 0.0010–0.0007 = 0.0003, at the expense of 400 iterations beyond iteration 100 (i.e., iterations 101–500).

Similar to the relative gap measure, the values of demand error for both auto and transit modes in Table 1 suggest a rapid convergence within the first iterations, but remain almost unchanged beyond iteration 100. This observation can be justified, in part, with respect to the relative gap values of transit mode which are comparatively larger than those of auto mode. These gaps (errors), that is, the differences between the travel-times of existing transit paths and the minimum travel-times, are transmitted in both auto and transit demand errors through $u_{rs}^{T}$ values in Equations 122 and 123.

Summing up, the results suggest that the algorithm converges effectively in the first iterations, but reveals a sluggish convergence behavior in a local region around the final equilibrium solution (e.g., beyond iteration 10).

Finally, Table 2 presents the number of O-D pairs with N working paths for all values of N for both auto and transit modes. The results correspond to the solution obtained by performing 500 iterations of the algorithm. The total number of transit working paths, calculated from the results of Table 2, is 166,253. This number is by far (almost 76%) more than the number of auto working paths which is 94,458. The table also shows that there are no O-D pairs with more than four working paths for auto mode, whereas many O-D pairs have more than 10 working paths for transit mode. Such large numbers of working paths in the transit super-network explains why converging to highly precise solutions is more difficult for the transit mode than for the auto mode.

Table 2.

Numbers of Auto and Transit Working Paths in the Final Solution

N	Number of O-D pairswith N working paths
N	Auto	Transit
1	91,888	47,691
2	1176	20,475
3	66	7499
4	5	5721
5	0	4010
6	0	2705
7	0	1949
8	0	1208
9	0	781
10	0	352
11	0	208
12	0	202
13	0	68
14	0	72
15	0	42
16	0	80
17	0	20
18	0	13
19	0	6
20	0	6
21	0	8
22	0	6
23	0	4
24	0	3
25+	0	0

Concluding Remarks

In this study, a joint NCP formulation, allowing for non-separable asymmetric cost/demand functions, was proposed for the combined auto-transit TA. The solution algorithm was built upon decomposition, path generation, and linearization, and performance measures were reported in relation to relative gaps and demand errors in the Chicago sketch network with 55 transit lines and more than 93,000 O-D pairs. Both measures were observed to converge rapidly in the first iterations of the algorithm, but remained relatively flat for the subsequent iterations. Also, in comparison with the relative gap, the demand error was found to be more resistant to convergence. After 100 iterations of the algorithm in the Chicago sketch network, the value of 0.0010 was obtained for both integrated relative gap and demand error.

Since not much work has been directed towards path-based multi-modal assignments, several directions may be identified for future research:

1- It was observed in both Babazadeh and Aashtiani ( 26 ) and this study that, as the algorithm proceeds to many iterations, the transit relative gap (and then the demand error in this study) would fail to achieve higher levels of accuracy (e.g., in the order of $10^{- 4}$ ). Studying probable improvements to this issue could be an important topic in future.

2- Implementation of the solution algorithm may be extended to incorporate multiple auto/transit modes, or further modes other than auto and transit.

3- Pure auto and transit modes were considered in this study. Another research direction would be to extend the model to address composite modes of transportation, as well.

4- In many time-consuming decision making problems, application of paths information in assignment sub-models has been observed to notably speed up the solution algorithms ( 19 , 20 ). The proposed assignment tool, therefore, may be used as a sub-model to tackle advanced decision making problems such as multi-modal network design or pricing problems.

5- To report the results, several assumptions were made in this paper for illustrative purposes. The equilibrium and convergence behavior of the algorithm can be analyzed over these assumptions. For example, bus rapid transit systems (with exclusive transit lanes), various speed and frequency over transit lines, and different modal split functions may be considered in future research.

6- The performance of the solution algorithm may be compared with other multi-modal assignment algorithms in the literature, including those introduced to solve FP or VIP formulations. This comparison can be reported on speed, accuracy, or applicability as a sub-model in bi-level problems.

Footnotes

Acknowledgements

The authors are grateful to the three anonymous reviewers for their valuable insights and comments on this paper. The third author’s work was partially funded by U.S. National Science Foundation under the award number CMMI-1402911.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and model development: HZA, HA; code implementation: AZ; analysis and interpretation of results: HZA, YMN, AZ; draft manuscript preparation: AZ, YMN, HZA; All authors reviewed the results and approved the final version of the manuscript.

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

References

Ortuzar

J. D.

Willumsen

L. G.

Modelling Transport. John Wiley & Sons, New York, 2001.

Safwat

K. N. A.

Magnanti

A Combined Trip Generation, Trip Distribution, Modal Split, and Trip Assignment Model. Transportation Science, Vol. 22, 1988, pp. 14–30.

Boyce

Is the Sequential Travel Forecasting Procedure Counterproductive?

Journal of Urban Planning and Development, Vol. 128, 2002, pp. 169–183.

Boyce

Bar-Gera

Multiclass Combined Models for Urban Travel Forecasting. Networks and Spatial Economics, Vol. 4, 2004, pp. 115–124.

De Cea

Fernández

J. E.

Dekock

Soto

Solving Network Equilibrium Problems on Multimodal Urban Transportation Networks with Multiple User Classes. Transport Reviews, Vol. 25, 2005, pp. 293–317.

Cantarella

G. E.

De Luca

Di Gangi

Di Pace

Stochastic Equilibrium Assignment with Variable Demand: Literature Review, Comparisons and Research Needs. Urban Transport XIX, Vol. 130, 2013, pp. 349–364.

Cantarella

G. E.

Cartenì

De Luca

Stochastic Equilibrium Assignment with Variable Demand: Theoretical and Implementation Issues. European Journal of Operational Research, Vol. 241, 2015, pp. 330–347.

Garcıä

Marın

Network Equilibrium with Combined Modes: Models and Solution Algorithms. Transportation Research Part B, Vol. 39, 2005, pp. 223–254.

Clark

S. D.

Watling

D. P.

Modelling Network Travel Time Reliability under Stochastic Demand. Transportation Research Part B, Vol. 39, 2005, pp. 119–140.

10.

Magnanti

T. L.

Models and Algorithms for Predicting Urban Traffic Equilibria. Elsevier Science, Amsterdam, 1984.

11.

Spiess

Contributions à la théorie et aux outils de planification des reseaux de transport urbain. PhD dissertation. Département d’informatique et de recherche opérationelle, Université de Montréal, Canada, 1984.

12.

Spiess

Florian

Optimal Strategies: A New Assignment Model for Transit Networks. Transportation Research Part B, Vol. 23, 1989, pp. 83–102.

13.

Cominetti

Correa

Common-Lines and Passenger Assignment in Congested Transit Networks. Transportation Science, Vol. 35, 2001, pp. 250–267.

14.

Babazadeh

Equilibrium Transit Assignment Problem in Congested Networks: Formulation and Solution Algorithm. PhD dissertation. Sharif University of Technology, Tehran, Iran, 2005.

15.

Miandoabchi

Zanjirani Farahani

Dullaert

Szeto

W. Y.

Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks. Networks and Spatial Economics, Vol. 12, 2012, pp. 441–480.

16.

Z. X.

Lam

W. H. K.

Chan

K. S.

Multimodal Network Design: Selection of Pedestrianisation Location. Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, 2005, pp. 2275–2290.

17.

Uchida

Sumalee

Watling

Connors

A Study on Network Design Problems for Multi-Modal Networks by Probit-Based Stochastic User Equilibrium. Networks and Spatial Economics, Vol. 7, 2007, pp. 213–240.

18.

Babazadeh

Khodakarami

Aashtiani

H. Z.

Passenger Origin-destination Matrix Estimation Employing the Path-based Formulation of Transit Assignment Problem. Presented at 89th Annual Meeting of the Transportation Research Board of the National Academies, Washington, D.C., 2010.

19.

Izadpanah

Aashtiani

H. Z.

Application of Paths Information in Network Design Problem. Journal of Transportation Engineering, Vol. 138, 2011, pp. 863–870.

20.

Zarrinmehr

Saffarzadeh

Seyedabrishami

Nie

Y. M.

A Path-Based Greedy Algorithm for Multi-Objective Transit Routes Design with Elastic Demand. Public Transport, Vol. 8, 2016, pp. 261–293.

21.

Zarrinmehr

Saffarzadeh

Seyedabrishami

A Local Search Algorithm for Finding Optimal Transit Routes Configuration with Elastic Demand. International Transactions in Operational Research, Vol. 25, 2018, pp. 1491–1514.

22.

Miralinaghi

Lou

Keskin

B. B.

Zarrinmehr

Shabanpour

Refueling Station Location Problem with Traffic Deviation Considering Route Choice and Demand Uncertainty. International Journal of Hydrogen Energy, Vol. 42, 2017, pp. 3335–3351.

23.

Zarrinmehr

Meshkani

Seyedabrishami

Surveillance Camera Location Problem for Route-flow Observation in Urban Transportation Networks: Bi-level Formulation and Solution Algorithm. International Journal of Systems Science: Operations & Logistics, Vol. 5, No. 4, 2017, pp. 327–338.

24.

Shirazi

Aashtiani

H. Z.

Solving the Minimum Toll Revenue Problem in Real Transportation Networks. Optimization Letters, Vol. 9, 2015, pp. 1187–1197.

25.

Aashtiani

H. Z.

The Multi-modal Traffic Assignment Problem. PhD dissertation. Massachusetts Institute of Technology, Cambridge, Mass., 1979.

26.

Babazadeh

Aashtiani

H. Z.

Algorithm for Equilibrium Transit Assignment Problem. Transportation Research Record: Journal of the Transportation Research Board, 2005. 1923: 227–235.

27.

Patriksson

The Traffic Assignment Problem: Models and Methods. VSP Publishers, Utrecht, 1994.

28.

J. H.

Florian

Marcotte

Transit Equilibrium Assignment: A Model and Solution Algorithms. Transportation Science, Vol. 28, No. 3, 1994, pp. 193–203.

29.

Bar-Gera

Boyce

Origin-based Algorithms for Combined Travel Forecasting Models. Transportation Research Part B, Vol. 37, 2003, pp. 405–422.

30.

Murty

K. G.

Linear Complementarity, Linear and Nonlinear Programming. Heldermann, West Berlin, 1988.

31.

Bar-Gera

Transportation Test Problems. http://www.bgu.ac.il/∼bargera/tntp/. Accessed Apr. 15, 2014.

32.

Nagurney

Dong

Supernetworks: Decision-making for the Information Age. Edward Elgar, Cheltenham, England, 2002.

33.

Fruin

J. J.

Pedestrian Planning and Design. Elevator World, New York, 1971.