# A fresh look at symmetric traffic assignment and algorithm convergence

Priyadarshan N. Patila CONTACT Priyadarshan N. Patil. Email:
<EMAIL_ADDRESS>aGraduate Program in Operations Research and
Industrial Engineering, The University of Texas at Austin, 204 E. Dean Keeton
St., C2200, Austin, TX, USA.

###### Abstract

Extensions of the static traffic assignment problem with link interactions
were studied extensively in the past. Much of the network modeling community
has since shifted to dynamic traffic assignment incorporating these
interactions. We believe there are several reasons to re-examine static
assignment with link interactions. First, if link interactions can be captured
in a symmetric, monotone manner, equilibrium always exists and is unique, and
provably-correct algorithms exist. We show that several of the most efficient
algorithms for the separable traffic assignment problem can be readily applied
with symmetric interactions. We discuss how the (asymmetric) Daganzo merge
model can be approximated by symmetric linear cost functions. Second, we
present computational evidence suggesting that convergence to equilibrium is
_faster_ when symmetric, monotone link interactions are present. This is true
even when interactions are asymmetric, despite the lack of a provable
convergence result. Lastly, we present convergence behavior analysis for
commonly used network and link metrics. For these reasons, we think static
assignment with link interactions deserves additional attention in research
and practice.

###### keywords:

Traffic assignment; algorithm convergence; symmetric traffic assignment;
asymmetric traffic assignment; gradient projection

††articletype: ARTICLE TEMPLATE

##  1 Introduction

Traffic assignment is a cornerstone of the urban planning and forecasting
process, relating travel demand to a forecasted network loading, providing
metrics such as link flows and travel times. Many traffic assignment models
exist. The most common in practice is the static traffic assignment problem
(TAP) first formulated by Beckmann, McGuire, and Winsten (1956). Dynamic
traffic assignment has been researched for several decades, and is
increasingly used by practitioners. Both static and dynamic traffic assignment
are described at length in Boyles, Lownes, and Unnikrishnan (2020).
Equilibrium assignment is also now a feature of some microsimulation software.
Broadly speaking, there is a tension between the level of “realism” of a model
(used here to refer to the level of detail in capturing traffic physics) and
how “nice” the model is (in terms of mathematical analysis, computational
efficiency, provably correct algorithms, and properties such as equilibrium
existence, uniqueness, and stability). Dynamic link and node models are much
more descriptive of traffic flow than the volume-delay functions typical of
static assignment, a powerful argument in their favor. At the same time,
dynamic equilibrium need not exist (Boyles, Lownes, and Unnikrishnan 2020,
Section 11.3.1), or several may exist (Nie 2010); and precisely the same
features that make dynamic models more realistic may also make them more
sensitive to any errors in input data, complicating calibration and possibly
introducing more error than is saved by improving the traffic flow model
(Boyles and Ruiz Juri 2019). These are not merely theoretical concerns — if
dynamic equilibrium may not exist at all, or if multiple equilibria exist, it
is not at all clear how to use the results of such a model for alternatives
analysis; and if a model is highly sensitive to parameters which are hard to
estimate (such as a time-dependent OD matrix decades in the future) its
practical utility is heavily limited. More extended versions of these issues
are discussed in Bar-Gera (2010), Boyles and Ruiz Juri (2019), and Patil,
Ross, and Boyles (2021); in short, some applications demand the realism of a
dynamic model, while in other applications the advantages of static models
outweigh their drawbacks, and careful researchers and practitioners select
their tool based on the problem at hand.

This ongoing conversation serves as background for our investigation. Some
researchers have attempted to find unifying frameworks for static and dynamic
assignment; see Bliemer et al. (2012) and Bliemer and Raadsen (2019) for
examples. An alternative approach is to improve the traffic model in static
assignment. In the 1980s, there was an active line of research in the static
assignment problem with _interactions_ among links, rather than using
separable link performance functions. (This background material is described
at greater length in Section 3.) While research in this area has continued to
this day, much of the community’s attention shifted to dynamic assignment in
the 1990s, with the advent of reasonable link and node models, such as the
cell transmission model (Daganzo 1994, 1995). In recent decades, our knowledge
of good dynamic link and node models has advanced further still (Yperman 2007;
Tampère et al. 2011). Research has also advanced considerably in how the
separable TAP is solved, with the discovery of path- and bush-based algorithms
(Jayakrishnan et al. 1994; Bar-Gera 2002; Dial 2006; Bar-Gera 2010; Xie and
Xie 2014; Chen et al. 2020).

We believe there are several reasons to take a fresh look at the static
traffic assignment problem with symmetric link interactions, considering it at
least as an alternative to static assignment, if not dynamic. As is known,
with monotone cost functions, S-TAP retains most of the favorable properties
of TAP, including formulating the equilibrium problem as a convex program, and
the resulting features of solution existence, uniqueness, and algorithmic
tractability. In this study, we accomplish the following:

  1. 1.

As an example of how existing node models can be approximated by symmetric,
monotone link performance functions, we develop such a representation of the
Jin-Zhang merge model (Jin and Zhang 2003). (Section 4)

  2. 2.

We discuss solution algorithms for S-TAP, including classic convex
combinations methods, but focusing mainly on more recent algorithms based on
shifting flow between a pair of alternative segments. We show that the flow
shift formula for S-TAP takes a familiar and simple form, and therefore
existing algorithms for TAP can be easily adapted for S-TAP. (Section 5).

  3. 3.

We implement these algorithms on standard test networks, and show that in most
cases, S-TAP actually converges _faster_ than the separable TAP. Therefore,
S-TAP can be considered as a serious alternative to TAP in planning practice.
We also report preliminary results showing good performance of gradient
projection for asymmetric link interactions, even though there is no convex
objective function (and therefore no guarantees of convergence).

Section 8 summarizes our findings, and provides specific suggestions for
further investigations on the utility of S-TAP.

##  2 Model Formulation

Consider a network with node and link sets $N$ and $A$, respectively. Let $Z$
denote the subset of nodes where trips may start and end, and for each
$(r,s)\in Z^{2}$, let $d_{rs}$ denote the fixed travel demand from node $r$ to
node $s$, and $\Pi_{rs}$ the set of paths connecting $r$ to $s$. Let $h_{\pi}$
denote the number of travelers using path $\pi$. For each link $a\in A$, let
$x_{a}$ and $t_{a}$ denote its flow and travel time. If each $t_{a}$ is a
nonnegative, continuous, and increasing function of $x_{a}$ alone, then the
flows $\mathbf{x}$ solving the convex program

$\qquad\min_{\mathbf{x},\mathbf{h}}\sum_{a}\int_{0}^{x_{a}}t_{a}(x)~{}dx$ (1)

subject to:

$\displaystyle x_{a}$ $\displaystyle=\sum_{\pi\in\Pi:a\in\pi}h_{\pi}$
$\displaystyle\forall a\in A$ $\displaystyle\sum_{\pi\in\Pi_{rs}}h_{\pi}$
$\displaystyle=d_{rs}$ $\displaystyle\forall(r,s)\in Z^{2}$ $\displaystyle
h_{\pi}$ $\displaystyle\geq 0$ $\displaystyle\forall\pi\in\Pi$

are an equilibrium, with all used paths having equal and minimal travel time
(Beckmann, McGuire, and Winsten 1956). We will use $X$ to denote the set of
link flows corresponding to feasible solutions of TAP; this set is compact and
convex. We will also refer to this optimization problem as TAP. As the
objective is strictly convex, equilibrium exists and is unique in link flows.
There are many efficient algorithms for solving TAP, including convex
combinations algorithms (Powell and Sheffi 1982; Frank and Wolfe 1956; Chen,
Jayakrishnan, and Tsai 2002; Mitradjieva and Lindberg 2013), path-based
algorithms (Larsson and Patriksson 1992; Jayakrishnan et al. 1994; Lee, Nie,
and Chen 2003; Florian, Constantin, and Florian 2009; Kumar and Peeta 2010,
2014; Xie, Nie, and Liu 2018), and bush-based algorithms (Bar-Gera 2002; Dial
2006; Gentile 2014; Bar-Gera 2010; Nie 2012; Xie and Xie 2015). Many (but not
all) of the latter two algorithm types shift flow between pairs of path
segments as a key operation, aiming to equilibrate them using a line search.

Now instead assume that the link performance functions depend on multiple
links’ flow. For generality, we write $t_{a}(\mathbf{x})$ to express
dependence on (potentially) every other link flow, although in practice each
link’s travel time depends only on a few other links. If these functions are
differentiable, and the Jacobian of $\mathbf{t}$ with respect to $\mathbf{x}$
is symmetric, equilibrium flows correspond to stationary points of the
function

$\qquad\min_{\mathbf{x},\mathbf{h}}\oint_{0}^{\vec{x}}t_{i}(\vec{s})d\vec{s}$
(2)

relative to the same constraints as TAP, as can be seen by writing the
optimality conditions. We will refer to this optimization problem as S-TAP.
The symmetry requirement on the Jacobian is critical. Otherwise, the line
integral is path-dependent and the function as stated is not well-defined, and
the model would need to be formulated and solved using variational inequality
(VI) methods. Facchinei and Pang (2003) We will refer to the asymmetric case
as A-TAP.

If this Jacobian is additionally positive definite, then we say that the link
performance functions are _monotone_ (note that this is stronger than
requiring each $t_{a}$ to be monotone in each link flow separately). In such a
case, the objective (2) is a strictly convex function (its Hessian is the
Jacobian just described), and equilibrium again exists and is unique. If the
link performance functions are not monotone, the function (2) is not convex,
and multiple stationary points (and therefore equilibria) may exist, with the
minima corresponding to stable equilibria. For example, see Figure 1. There
are three equilibria corresponding to the flow vectors (0,10), (5,5), and
(10,0); the first and third of these are stable, and the second is unstable.
For derivations of the above results and more discussion, see the books by
Patriksson (2015) and Boyles, Lownes, and Unnikrishnan (2020).

##  3 Background

Historically, Prager (1954) first mentioned the need to model traffic
interactions on a two-way street. Dafermos (1971) and Dafermos (1972) were the
first to formulate S-TAP and A-TAP, showing equivalence with the multi-class
TAP, and presenting an iterative flow update algorithm to obtain user
equilibrium and system optimal flows. Sender and Netter (1970) used the fixed
point theorem to show the existence of an equilibrium solution in the
asymmetrically formulated multi-class TAP. Smith (1979) was the first to
formulate A-TAP as a VI, presenting a set of conditions for existence
(continuity of cost vectors) and uniqueness (strict monotonicity of cost
vectors for all supply feasible vectors) of the equilibrium solution. Dafermos
(1980) showed that these uniqueness conditions were equivalent to the Jacobian
being positive definite, and proved the existence of an equilibrium solution.
As checking positive definiteness can be cumbersome to test in practice,
Heydecker (1983) proposed an easier test, based on diagonal dominance. This is
a weaker condition than positive definiteness, thus showing that positive
definiteness of the Jacobian is a sufficient but not necessary condition.
Heydecker also discussed the existence of multiple (and unstable) equilibrium
solutions when said conditions are violated. The equivalent requirement of
positive definite Jacobian for the multi-class TAP solution existence was also
shown by Braess and Koch (1979).

The VI formulation allowed for a number of different solution approaches to be
proposed for A-TAP, including the non-linear Jacobi method (or diagonalization
method), projection methods, and column generation methods. Dafermos (1982)
proposed a relaxation method and proved its convergence. Fisk and Nguyen
(1982) analyzed this approach, the projection method, and three other solution
methods, concluding that the non-linear Jacobi method was most efficient.
Nagurney (1984, 1986) extended this comparison of the relaxation and
projection method for multi-modal problem with varying travel costs and A-TAP,
concluding that no one method was uniformly superior. Smith (1983) modeled
junction interactions using A-TAP, while proposing a new objective function
measuring deviation of traffic distribution from equilibrium. Smith also
provided a descent direction to monotonically reduce the new objective
function and a path enumeration based algorithm for A-TAP.

Florian and Spiess (1982) provided a sufficient condition for diagonalization
algorithm convergence. Nguyen and Dupuis (1984) proposed an iterative approach
for A-TAP post-optimizing a linear sub-problem at each iteration.
Lawphongpanich and Hearn (1984) used simplicial decomposition, constructing
the solution as a convex combination of all extreme points of the flow vector
space. They compared their approach to the Nguyen and Dupuis (1984) approach
on the networks proposed in Nguyen and Dupuis (1984) and Fisk and Nguyen
(1982), concluding that the simplicial approach is competitive with the
iterative approach while storing a small number of extreme flow patterns. In
the same vein, Gabriel and Bernstein (1997) and Bernstein and Gabriel (1997)
solved A-TAP with non-additive route costs using column generation for
nonlinear complementarity problem (NCP) gap minimization, equivalent to the VI
formulation. The NCP formulation is needed when route-level interactions are
modeled, such as non-additive route cost interactions. They also showed the
existence and uniqueness of the solution if the function is separable. Lo and
Chen (2000) also apply column generation to the reformulated NCP for route-
specific tolls.

Mahmassani and Mouskos (1988) tested the diagonalization approach on three
networks including the Texas highway network, and observed convergence of the
algorithm despite violation of sufficient conditions presented in Dafermos
(1982). Similar observations were made by Friesz, Harker, and Tobin (1984) and
Friesz (1985). Mahmassani and Mouskos also compared their implementations with
Sheffi’s streamlined implementation Sheffi (1985) with one FW iteration per
subproblem and concluded that there is no single best choice for the number of
FW iterations. Meneguzzer (1995) provided an overview of the advances in the
field of diagonalization for A-TAP and convergence for explicit modeling of
intersections. Marcotte and Guélat (1988) applied the modified Newton method
to A-TAP, comparing its performance with cutting plane methods and
diagonalization, observing their method performing better than other methods
for complex asymmetric interactions. Dupuis and Darveau (1986) assessed the
convergence conditions for A-TAP solutions using projection and
diagonalization methods.

Hearn, Lawphongpanich, and Nguyen (1984) drew a connection between convex
programming formulation of A-TAP and the VI formulation. Marcotte and Wynter
(2004) relaxed the monotonicity condition for interactions, proposing weaker
convergence conditions for A-TAP with multiple modes. Wong, Yang, and Lo
(2001) modeled A-TAP with simulation approach for the intersection delay.
Panicucci, Pappalardo, and Passacantando (2007) formulated the VI in terms of
path flows and propose a column generation scheme based on Khobotov’s method.
Yook and Heaslip (2016) discussed ways to accelerate the convergence of
double-projection method proposed by Panicucci et al. using the decomposable
path flow VI structure. De Grange and Muñoz (2009) presented a method to
equalize line integral paths for affine cost A-TAP. Chen, Zhou, and Ryu (2011)
modeled A-TAP interactions using side constraints. Sancho, Ibáñez Marí, and
Bugeda (2015) evaluated the performance of five projection methods for A-TAP
and observe that a variation of Khobotov’s method proposed by He, Liao, and
Wang (2012) shows the fastest convergence. Patriksson (2015) and Yook (2014)
provide good overviews of alternative solution approaches for A-TAP.

As suggested by the above review, there was significant focus on A-TAP
research in the 1980s and 1990s, but comparatively less since then. The broad
explanation for this is the emergence of DTA as a serious modeling tool (Peeta
and Ziliaskopoulos 2001; Chiu et al. 2011), with better grounding in traffic
science than link performance functions could ever hope to have, whether
separable or with interactions. Nevertheless, as suggested in the
introduction, there are other advantages TAP and its variants have, and both
tools are used today for different applications. Our aim in this paper is to
suggest that further work in S-TAP and A-TAP can be valuable, incorporating
insights from recent DTA research, adapting recent algorithms for the basic
TAP, and showing that S-TAP may be a reasonable alternative in places where
static assignment is still useful.

##  4 A symmetric, monotone merge model

While much research has been done on theoretical properties of traffic
assignment with interactions, we are not aware of specific guidance on exactly
_how_ interactions should be chosen to represent real-world scenarios. To
further motivate our investigation, we will give an illustration of how
symmetric, monotone link performance functions can be chosen to approximate a
node model used in dynamic traffic assignment. The method we describe here is
surely not the only way to do this, but a full study of how to develop such
approximations (and to assess their quality on full-sized, realistic networks)
is beyond the scope of this study. Our aim in this section is simply to
demonstrate that S-TAP is a plausible model for certain applications.

We take as our starting point a simple network loading model, a network of
point queues. In this model, the time required to travel each link is a fixed
free-flow time ($t^{0}$), plus time spent waiting in a queue at the downstream
end. Let $Q(\tau)$ denote the length of the queue at time $\tau$; these queues
are “point” queues in that they may grow arbitrarily long. Each link also has
a uniform saturation flow $u$, perhaps proportional to the number of lanes. We
will denote by $x(\tau)$ the _inflow_ rate at the link’s upstream end, and
$y(\tau)$ the _outflow_ rate at the link’s downstream end. If $x$ and $y$ are
time-invariant, we must have $x\geq y$, and the queue length at a given point
in time will be $Q(\tau)=\tau(x-y)$. The travel time experienced for a vehicle
entering the link at time $t$ will be $t^{0}+\tau(x/y-1)$. If we assume that
$x$ is constant over an interval of length $T$ (and zero otherwise), the
average delay experienced by a vehicle on the link will be
$t^{0}+\frac{T}{2}(x/y-1)$. If we choose units so that $T=2$, the formula
simplifies to $t^{0}+(x/y-1)$, which we will adopt for the remainder of the
section.

Consider now a merge node with two upstream links (indexed 1 and 2) and one
downstream link (indexed by 3). A “merge model” takes as input the demands
from each upstream link and the available supply from the downstream link, and
produces the flow rates out of each upstream link into the downstream link.
Several merge models have been proposed in the literature (Daganzo 1995;
Lebacque 1996; Jin and Zhang 2003).

We now show that the Jin-Zhang merge model (Jin and Zhang 2003) leads to a
symmetric, monotone delay function, if the demands are interpreted as the
inflows $x$.111This is an approximation to the actual dynamic model, since if
a queue forms, the demand will increase to the saturation flow $u$. Indeed,
one critique of the Jin-Zhang model is that it is unstable with respect to
this transition, a violation of the “invariance principle,” cf. Lebacque and
Khoshyaran (2005).  With this interpretation, the model takes the following
form. If $x_{1}+x_{2}\leq u_{3}$, there are no queues, and hence no delays:
$y_{1}=x_{1}$, $y_{2}=x_{2}$, so $t_{1}=t^{0}_{1}$ and $t_{2}=t^{0}_{2}$.
Otherwise, the Jin-Zhang model allocates flows proportionally to demands:
$y_{1}=u_{3}x_{1}/(x_{1}+x_{2})$, and hence
$t_{1}=t^{0}_{1}+[(x_{1}+x_{2})/u_{3}-1]$. Likewise,
$t_{2}=t^{0}_{2}+[(x_{1}+x_{2})/u_{3}-1]$. In either case, the Jacobian of
$\mathbf{t}$ with respect to $\mathbf{x}$ is symmetric and positive
semidefinite.

Alternative merge models, such as that of Daganzo (1995), do not directly lead
to symmetric and monotone performance functions. However, it may be possible
to create reasonable approximations to them that satisfy these conditions
(indeed the Jin-Zhang model may be seen as such an approximation), at least in
a region of demand and supply values the modeler believes to be likely at a
particular junction. For instance, the Daganzo merge violates symmetry only in
the exceptional case when a queue forms on one upstream link, not both. We
believe it plausible that similar procedures or approximations can apply to
other types of interactions between links, based either on node models from
dynamic traffic assignment, formulas from the Highway Capacity Manual (2010)
or similar literature, or regression from simulation, but we leave such
investigation to future study.

##  5 Algorithms and convergence

This section discusses solution algorithms for S-TAP with monotone cost
functions. To do so, it will be convenient to choose a specific integration
path for the line integral in (2). If we choose the path
$(0,0,0,\ldots,0)\rightarrow(x_{1},0,0,\ldots,0)\rightarrow(x_{1},x_{2},0,\ldots,0)\rightarrow\cdots\rightarrow(x_{1},x_{2},\ldots,x_{n})\,,$
the line integral decomposes into a sum of ordinary integrals as

$F(\mathbf{x})=\sum_{i=1}^{n}\int_{(x_{1},\ldots,x_{a-1},0,0,\ldots,0)}^{(x_{1},\ldots,x_{a-1},x_{a},0,\ldots,0)}t_{i}(x)~{}dx\,.$
(3)

Each link performance function is increasing for each independent flow
variable, so each integral is convex, as is the sum.

With this representation, the gradient and Hessian of $F$ take simple forms.
Using the Leibniz rule, the derivative of $F$ with respect to any link flow
$x_{a}$ is

$\frac{\partial F}{\partial
x_{a}}=t_{a}(x_{1},\ldots,x_{a},0,\ldots,0)+\sum_{i>a}\int_{(x_{1},\ldots,x_{i-1},0,\ldots,0)}^{(x_{1},\ldots,x_{i-1},x_{i},0,\ldots,0)}\frac{\partial
t_{i}}{\partial x_{a}}(x)~{}dx\,.$

But using the symmetry condition, $\partial t_{i}/\partial x_{a}=\partial
t_{a}/\partial x_{i}$, and so we ultimately have $\partial F/\partial
x_{a}=t_{a}$, from the fundamental theorem of calculus. That is, the gradient
of $F$ is simply the vector of link travel times, as it is in TAP (and indeed,
as it should be for the optimality conditions to express equilibrium). The
Hessian of $F$ is then just the Jacobian of the link performance functions,
that is, $(HF)_{ab}=\partial t_{a}/\partial x_{b}$.

###  5.1 Convex combinations algorithms

Convex combinations algorithms operate on the link flow vector $\mathbf{x}$,
iteratively combining a current feasible solution with a “target” solution
$\mathbf{x^{*}}$, with an update rule of the form
$\mathbf{x}\leftarrow(1-\lambda)\mathbf{x}+\lambda\mathbf{x^{*}}$. Typically
$\mathbf{x^{*}}$ is an “all-or-nothing” solution obtained by placing all
demand on shortest paths when the link costs are $\mathbf{t(x)}$. They are
relatively naïve, but amenable to parallelization, and they typically make
excellent progress in their initial iterations before the rate of convergence
slows sharply (ultimately, to a sublinear rate).

The simplest possible convex combinations algorithm is the method of
successive averages, where the step sizes $\lambda$ are chosen _a priori_ in a
divergent sequence (but with $\sum\lambda^{2}$ finite); a common example is
$\\{1/2,1/3,1/4,\ldots\\}$. Convergence of this method for S-TAP can be shown
using the following result:

######  Proposition 5.1.

_(Powell and Sheffi1982)_ Consider a twice-continuously differentiable convex
function $F(\mathbf{x})$, and a sequence
$\\{\mathbf{x_{0}},\mathbf{x_{1}},\ldots\\}$, where $\mathbf{x_{0}}\in X$ and
$\mathbf{x_{i}}=(1-\lambda_{i})\mathbf{x_{i-1}}+\lambda_{i}\mathbf{x^{*}_{i}}$
for $i\geq 1$, with $\mathbf{x^{*}_{i}}\in X$, $\lambda_{i}\in[0,1]$,
$\sum\lambda_{i}=\infty$, but $\sum\lambda_{i}^{2}<\infty$. This sequence
converges to a minimizer $\bar{\mathbf{x}}$ of $F$ if the following conditions
hold:

  1. 1.

The inner product $(\nabla
F(\mathbf{x_{i}}))^{T}(\mathbf{x^{*}_{i}}-\mathbf{x_{i}})$ is negative
whenever $F(\mathbf{x_{i}})>F(\bar{\mathbf{x}})$.

  2. 2.

The values of
$(\mathbf{x^{*}_{i}}-\mathbf{x_{i}})^{T}HF(\mathbf{x_{i}}+\psi\lambda_{i}(\mathbf{x^{*}_{i}}-\mathbf{x_{i}}))(\mathbf{x^{*}_{i}}-\mathbf{x_{i}})$
are bounded over all $i$ and $\psi\in[0,1]$.

Each condition can be checked easily. If $\mathbf{x^{*}_{i}}$ is an all-or-
nothing assignment to shortest paths, then
$\mathbf{t(\mathbf{x_{i}})}^{T}(\mathbf{x^{*}_{i}}-\mathbf{x_{i}})\leq 0$,
with equality only if $\mathbf{x_{i}}$ is an equilibrium. Since $\nabla
F(\mathbf{x})=\mathbf{t}$, and since equilibria correspond to minima of $F$,
the first condition is satisfied. Since $X$ is compact, continuity of the link
performance functions ensures that the elements of $HF$ and that the
magnitudes of $\mathbf{x^{*}_{i}-\mathbf{x}}$ are bounded, and the second
condition is satisfied as well.

As a convex program, monotone S-TAP can also be solved by the Frank-Wolfe
algorithm, which selects each $\lambda_{i}\in[0,1]$ to minimize the value of
the objective. A proof of convergence can be found in Section 2.2.2 of
Bertsekas (2016).

###  5.2 Algorithms equilibrating paths

In many path- and bush-based algorithms, the fundamental operation involves
equilibrating two paths: given a lower-cost path $\pi_{L}$ and a higher-cost
path $\pi_{U}$ connecting the same origin and destination, shifting flow from
$\pi_{U}$ to $\pi_{L}$ to either (approximately) equalize their costs, or to
shift all flow onto $\pi_{L}$. Examples of such algorithms are the gradient
projection (GP) method of Jayakrishnan et al. (1994), Algorithm B (Dial 2006),
and TAPAS (Bar-Gera 2010).222TAPAS actually performs such shifts for multiple
origin-destination pairs simultaneously, with alternative paths differing on
the same segments of links; this point does not affect the discussion here.

Given these paths, the question is how much flow $\Delta x$ to shift from
$\pi_{U}$ to $\pi_{L}$. For TAP, Newton’s method is commonly used to estimate
the value of $\Delta x$ that equalizes the path costs; this is also the value
of $\Delta x$ minimizing the Beckmann function. The same applies for S-TAP,
although the scaling factor in the denominator must change to reflect link
interactions, as we now show.

Let $\mathbf{x}(\Delta x)$ denote the link flows after $\Delta x$ has been
shifted away from $\pi_{U}$ onto $\pi_{L}$. The only links whose flows will
change are those in $\pi_{L}$ or $\pi_{U}$, but not both; let $A_{L}$ and
$A_{U}$ respectively denote the links only in $\pi_{L}$ and $\pi_{U}$. Then

$x_{a}(\Delta x)=\begin{cases}x_{a}+\Delta x&\mbox{if }a\in A_{L}\\\
x_{a}-\Delta x&\mbox{if }a\in A_{U}\\\ x_{a}&\mbox{otherwise}\end{cases}\,.$
(4)

To find the value of $\Delta x$ minimizing the S-TAP objective $F$, we find
where the derivative

$\frac{dF}{d\Delta x}=\sum_{a}\frac{\partial F}{\partial
x_{a}}\frac{dx_{a}}{d\Delta x}=\sum_{a\in A_{L}}t_{a}-\sum_{a\in A_{U}}t_{a}$
(5)

vanishes. As in the separable case, this is exactly when $\pi_{L}$ and
$\pi_{U}$ have equal cost.

To apply Newton’s method, we also need the second derivative of $F$ with
respect to $\Delta x$, in order to scale the step size properly. We calculate

$\frac{d^{2}F}{d(\Delta
x)^{2}}=\sum_{a}\sum_{a^{\prime}}\frac{\partial^{2}F}{\partial x_{a}\partial
x_{a^{\prime}}}\frac{dx_{a}}{d\Delta x}\frac{dx_{a^{\prime}}}{d\Delta x}\\\
=\sum_{a\in A_{L}}\sum_{a^{\prime}\in A_{L}}\frac{\partial t_{a}}{\partial
x_{a^{\prime}}}+\sum_{a\in A_{U}}\sum_{a^{\prime}\in A_{U}}\frac{\partial
t_{a}}{\partial x_{a^{\prime}}}-\sum_{a\in A_{L}}\sum_{a^{\prime}\in
A_{U}}\frac{\partial t_{a}}{\partial x_{a^{\prime}}}-\sum_{a\in
A_{U}}\sum_{a^{\prime}\in A_{L}}\frac{\partial t_{a}}{\partial
x_{a^{\prime}}}\,.$ (6)

Using the symmetry condition, this simplifies to

$\frac{d^{2}F}{d(\Delta
x)^{2}}=\sum_{a}\sum_{a^{\prime}}\frac{\partial^{2}F}{\partial x_{a}\partial
x_{a^{\prime}}}\frac{dx_{a}}{d\Delta x}\frac{dx_{a^{\prime}}}{d\Delta x}\\\
=\sum_{a\in A_{L}}\sum_{a^{\prime}\in A_{L}}\frac{\partial t_{a}}{\partial
x_{a^{\prime}}}+\sum_{a\in A_{U}}\sum_{a^{\prime}\in A_{U}}\frac{\partial
t_{a}}{\partial x_{a^{\prime}}}-2\sum_{a\in A_{L}}\sum_{a^{\prime}\in
A_{U}}\frac{\partial t_{a}}{\partial x_{a^{\prime}}}\,.$ (7)

If there are no interactions at all, this formula reduces to $\sum_{a\in
A_{L}\cup A_{U}}t^{\prime}_{a}$, as it must.

So, the Newton estimate for the flow shift equalizing path costs is the
quotient of equations (5) and (7). The denominator is strictly positive,
because $HF$ is positive definite by monotonicity, and this ratio is well-
defined. To preserve feasibility, the flow shift is truncated if any flow
would become negative. This corresponds to the case when the longer path
becomes unused after the shift.

This operation can be substituted for the flow shift step in gradient
projection, Algorithm B, or TAPAS.

##  6 Numerical results

This section describes tests of the algorithms described in the previous
section. The key questions concern the computation time needed when link
interactions are considered, compared to the separable case. We focus on this
issue since computational efficiency is one of the advantages static models
have over dynamic ones, and if S-TAP is to be useful in practice it should
maintain this advantage. This section also considers asymmetric instances as
well, using these algorithms as a heuristic.

We measure convergence using the relative gap, defined as the ratio between
the total system travel time, and the total travel time of an all-or-nothing
assignment to shortest paths (keeping the current link costs). Using
$\kappa_{rs}$ to reflect the shortest path cost between nodes $r$ and $s$, the
relative gap is calculated as

$RG=\frac{\sum_{a}t_{a}x_{a}-\sum_{(r,s)\in
Z^{2}}d_{rs}\kappa_{rs}}{\sum_{(r,s)\in Z^{2}}d_{rs}\kappa_{rs}}\,.$ (8)

Additional details on the relative gap, its relationship with other gap
measures, and with measures of effectiveness such as link flows and aggregate
travel times, are discussed in Patil, Ross, and Boyles (2021).

###  6.1 Motivation - Toy example

Consider the example network shown in Figure 2. We will use this network with
different cost functions to show the effects of symmetric vs. asymmetric
interactions, and the impact of how many other links affect the travel time of
a given link. Consider the five cases (and the corresponding link costs) shown
in Table 1.

The convergence results for the first few iterations of gradient projection
are given in Table 2. More iterations for this toy example are omitted for
brevity. The symmetric-full interaction scenario achieves a lower relative gap
for the same number of iterations, followed by asymmetric-full interaction,
symmetric-partial interaction, asymmetric-partial interaction, and lastly,
separable scenario.

This is due to two effects. First, a higher level of interaction leads to
faster convergence. We speculate that this occurs because each path flow
equilibration affects more links in the network than just those in $A_{L}$ and
$A_{U}$, and therefore moves more of the network towards equilibrium at each
step. Compare the symmetric-full and asymmetric-full scenarios to the
symmetric-partial and asymmetric-partial scenarios in Table 2. The full-
interaction cases perform better than partial interaction scenarios, which
still perform better than the separable TAP scenario.

Second, symmetric scenarios tend to achieve (somewhat) faster convergence
compared to asymmetric scenarios. This is attributed to the path equilibration
step having accurate information about the rest of the network (by symmetric
Jacobian effects) as opposed to approximate information in the asymmetric
case. Consider the symmetric-partial and asymmetric-partial cases, with very
minor link cost differences on links 2 and 3. The symmetric-partial relative
gap is almost half of the asymmetric-partial gap by iteration 5, a trend that
continues in additional iterations not shown in the detail.

These two effects can be quantified using the eigenvalues of the Hessian of
the cost matrix. For our problem, this is represented by the weight matrix for
linear cost functions, and approximated by it otherwise. For steepest descent
methods, the condition number (ratio of the largest eigenvalue to the smallest
eigenvalue) correlates to the rate of convergence (Bertsekas 2016). A large
condition number means the problem is ill-conditioned, i.e., the optimization
variables are not relatively scaled well, and convergence will be slow. A
small condition number (closer to 1) will have faster convergence behavior.
For example, the condition numbers for the symmetric and asymmetric toy
examples with full interaction in Table 1 are 3 and 3.154, respectively.

In our investigations, we observe that problem instances with differing
condition numbers follow this behavior, and the cost matrix can be useful for
predicting convergence behavior w.r.t. similar problem instances. For
instance, see Figure 3. We generated problem instances with slightly different
weight matrices (and therefore, condition numbers), and then allowed GP to
solve the instances for 20 iterations. We can see that the instances with
lower condition numbers generally show better convergence than instances with
higher condition numbers.

The next subsection details our experiment design on significantly larger
real-world networks to corroborate these observations, and our intuition about
convergence for the symmetric/asymmetric and no interaction/full interaction
cases.

###  6.2 Data and Experiment design

We test the method of successive averages (MSA), Frank-Wolfe (FW), and
gradient projection (GP) on five standard networks, chosen for their varying
size and congestion levels. The networks are obtained from the transportation
problems test repository (Stabler 2019). Our implementations of MSA, FW, and
GP for S-TAP and A-TAP, as well as the testing framework, can be found on the
first author’s Github repository (Patil 2021). Table 3 contains the network
size details and average link volume over capacity as a proxy for congestion.
These experiments used a relative gap of $10^{-6}$ as a convergence criterion.

We used the following procedure to generate cost functions with interactions
that attempt to preserve the level of congestion in the original networks. The
link performance functions in the original network are separable. In our
experiments, we replace each $x_{a}$ with a linear combination of the form
$\sum_{a^{\prime}\in A}w_{aa^{\prime}}x_{a^{\prime}}$, with
$\sum_{a^{\prime}}w_{aa^{\prime}}=1$ and each $w_{aa^{\prime}}\geq 0$. If the
weight matrix $\mathbf{W}$ is symmetric, then the interactions are
approximately symmetric (but not entirely so, since the link performance
functions are nonlinear). The separable case is represented with
$\mathbf{W}=\mathbf{I}$. We generate the weight matrices so that each link
depends on a given number of other links (the number of “degrees of
dependency,” denoted $N$), and with $\mathbf{W}$ diagonally dominant to avoid
cases with multiple equilibria.

The first set of experiments tested the convergence behavior of the three
algorithms for TAP, S-TAP, and A-TAP on all networks. The best performing
algorithm was then chosen for further convergence testing of S-TAP and A-TAP.
The second set of experiments studied the effect of topographical link
interactions. These experiments aim to understand impact the degree of
dependency has on the convergence rate. The third set of experiments analyzed
the effects of symmetry. We consider a smooth transition from asymmetry to
symmetry to starting with an asymmetric matrix W, and taking weighted averages
with the associated symmetric matrix $\frac{1}{2}(\mathbf{W}+\mathbf{W}^{T})$.
Specifically, these experiments consider the Jacobian matrices
$\lambda\textbf{W}+(1-\lambda)\frac{1}{2}(\mathbf{W}+\mathbf{W}^{T})$ for
$\lambda\in\\{0,0.2,0.4,0.6,0.8,1\\}$.

###  6.3 Results

Figures 4 and 5 present the compiled results for Sioux Falls. The first
observation from Figure 4(a) is the behavior of MSA and FW algorithms is
extremely similar for TAP, S-TAP, and A-TAP, while GP outperforms them. The
relative gap and number of iterations are linearly related on a logarithmic
axis, consistent with prior literature (Xie, Nie, and Liu 2018). Based on
these initial results, we use GP as the testing algorithm for further
experiments.

An important observation here is the independence from implementation details
and absolute computation time. Our experiments have been conducted on a basic
GP implementation. Therefore, any performance gains achieved by
parallelization or other implementation techniques are applicable to these
results, helping speed up convergence. For instance, Chen et al. (2020)
implement a parallel block coordinate descent algorithm based on GP algorithm,
and the absolute computation time gains would be applicable to our
observations for S-TAP and A-TAP. Therefore, we do not emphasize absolute
computation times, but focus on comparative behavior.

Figures 4(b) and 4(c) show the behavior of link cost dependency on link flows
within $N$ degrees of any given link for S-TAP and A-TAP, respectively. A
higher degree of dependence leads to earlier convergence, as was observed in
the motivating toy network. This is attributed to each flow equilibration step
having more implicit information about the network state. Also, S-TAP is seen
to converge marginally faster than A-TAP, as expected. The only exception is
the case $N=2$ case, though it still does not outperform $N=5$ or $N=6$ link
interaction instances. Along similar lines, Figure 5 shows convergence
behavior when the weight matrix proceeds from an asymmetric instance
($\lambda=1$) to the corresponding symmetric instance ($\lambda=0$). The
results indicate as the matrix tends toward the symmetric version, more
accurate information (about the remaining network) is available during each
flow equilibration, leading to marginally faster convergence.

Figures 6–9 show the results for Eastern Massachusetts, Chicago Sketch,
Barcelona, and Chicago Regional networks, respectively. The main observations
from the Sioux Falls networks are seen to hold for these larger networks. The
maximum $N$ for these four networks is 8, 31, 30, and 112, respectively. These
networks show no exception to these trends, unlike the Sioux Falls network.
Also, the test instances with lower $N$ values achieved better relative gap
levels for larger networks; the highest $N$ instances all reached a gap below
$10^{-12}$.

##  7 Convergence experiments

This subsection focuses on the convergence behavior for S-TAP. This is
particularly important for applications where TAP is solved multiple times as
a sub-problem. Some applications include network design problems (Yang 1997;
Patil, Walthall, and Boyles 2022; Gokalp, Patil, and Boyles 2021), sensitivity
analysis (Boyles 2012), trip table estimation (Yang 1995; Lundgren and
Peterson 2008), network pricing (Yang and Lam 1996), and other bilevel
optimization problems (Yin 2000; Astroza et al. 2017; Pandey and Patil 2022;
Boyles et al. 2018). Patil, Ross, and Boyles (2021) provide additional
background on convergence analysis for TAP.

Here, we primarily consider GP with two-link interactions. This limits the
scope of our experiments to the most common use case, i.e., two-way roads. The
networks studied in this paper are shown in Table 4, all obtained from the
Transportation Networks for Research repository (Stabler 2019). For ease of
reference, we categorize the networks roughly by size: Sioux Falls through
Anaheim are designated as small, Chicago Sketch through Terrassa are
designated as medium, and the remaining networks are designated as large. The
last column in this table shows the average equilibrium flow-to-capacity
ratios, excluding centroid connectors. We consider networks with ratios of
less than 0.5 to be uncongested, with ratios between 0.5 and 1.0 to be semi-
congested, and networks with ratios greater than 1.0 to be congested. The
Terrassa network is a clear outlier in this regard, assigning over 25 million
trips in a region whose current population is around 200,000, resulting in a
flow-to-capacity ratio of almost 6. While such a demand level may not be
realistic, we nevertheless include this network as a “stress test” to see
whether consistent trends can be seen even in extremely congested networks.
Lastly, we also conduct these experiments using Algorithm B (AlgB), a bush-
based algorithm which is often faster in practice.

Given a feasible solution $(\mathbf{x},\mathbf{h})$ to TAP, we select three
metrics for analysis. The _total system travel time_ (TSTT) expresses the sum
of each vehicle’s travel time in the network as

$TSTT(\mathbf{x})=\sum_{(i,j)\in A}t_{ij}x_{ij}\,.\\\ $ (9)

_Vehicle-miles traveled_ (VMT) expresses the total distance traveled by
vehicles in the network as

$VMT(\mathbf{x})=\sum_{(i,j)\in A}l_{ij}x_{ij}\,.\\\ $ (10)

To measure convergence of these metrics, we calculate the relative difference
between their values at the current solution $\mathbf{x}$ and the equilibrium
solution $\mathbf{x^{*}}$ as:

$\Delta
TSTT(\mathbf{x})=\frac{TSTT(\mathbf{x})-TSTT(\mathbf{x^{*}})}{TSTT(\mathbf{x^{*}})}$
(11)

$\Delta
VMT(\mathbf{x})=\frac{VMT(\mathbf{x})-VMT(\mathbf{x^{*}})}{VMT(\mathbf{x^{*}})}\,.$
(12)

Both TSTT and VMT are aggregate metrics. To represent convergence of the
specific link and path flows themselves, we measure the proportion of links
within a given relative threshold $\epsilon$ of their equilibrium values. Let
$A_{\epsilon}^{*}(\mathbf{x})$ denote the set of links with flows within this
threshold:

$A^{*}_{\epsilon}(\mathbf{x})=\left\\{(i,j)\in
A:\left|x_{ij}-x^{*}_{ij}\right|<\epsilon x^{*}_{ij}\right\\}\,.$ (13)

Using these sets, we define the _proportion of unconverged links (PUL)_ as

$PUL(\mathbf{x},\epsilon)=1-\frac{|A^{*}_{\epsilon}(\mathbf{x})|}{|A|}\,.$
(14)

These metrics — $\Delta TSTT$, $\Delta VMT$, $PUL$ — are directly related and
used in practical applications and planning, and converge to zero at the
equilibrium solution. We track these metrics against relative gap (defined in
Section 6), a convergence metric.

The full set of results can be found in the Appendix (Tables 1-3). The values
of the three main metrics for GP experiments are shown in Figures 10–12
(presented according to each metric). The thin lines represent the values of
each metric in one of the twelve networks tested, and the thick line
represents the average value. Both sets of figures use logarithmic axes for
the relative gap. All metrics converged at roughly similar rates, despite
significant differences in the size and congestion level of the networks
tested.

In all the networks, the aggregate metrics ($TSTT$ and $VMT$) are already very
near stabilization at a relative gap of $10^{-3}$. For the small and medium
networks, these values are within 1% of the equilibrium values when the
relative gap is $10^{-4}$, and for the large networks they are within 2%. Both
$\Delta TSTT$ and $\Delta VMT$ converge at roughly similar rates, but $\Delta
VMT$ is usually slightly lower at a particular gap level. This behavior is in
line with the metric behavior for TAP, as noted in Patil, Ross, and Boyles
(2021).

The proportion of unconverged links was the metric originally studied by
Boyce, Ralevic-Dekic, and Bar-Gera (2004) for the Philadelphia regional
network. They found that a gap of $10^{-4}$ was required to approach
convergence for freeway links, defining convergence as a $PUL$ of 1% or less.
To achieve this level of convergence for arterial links as well as freeway
links, a relative gap of $10^{-5}$ was needed. Our results show that this
latter conclusion generally holds across the other networks tested, and that
99% of link flows are accurate to within 1% of equilibrium values at this gap
level.

Next, we compare the GP convergence behavior to AlgB convergence behavior. The
full data from these results are shown in Tables 2 (raw data for Algorithm B)
and 3 (for a side-by-side comparison) in the Appendix. The trends are very
similar between the two algorithms, and the values of each metric are always
of the same order of magnitude, and almost always nearly identical
numerically. This finding is encouraging, suggesting that the conclusions of
the GP experiments are applicable to other algorithms, and that the relative
gap is a good universal measure of convergence, regardless of the specific
assignment algorithm. Again, these results are in line with prior results from
Patil, Ross, and Boyles (2021).

##  8 Conclusions

This study reconsiders the traffic assignment problems with interactions. We
showed that merge models from dynamic traffic assignment can be approximated
with symmetric, monotone cost functions; examined alternative algorithms,
deriving the Newton shift formula with interactions; and considered the
practical convergence rate of gradient projection and Algorithm B with such
functions. We found that instances with interactions actually converge faster
than separable instances of traffic assignment. All of this suggests that
problems currently studied with static traffic assignment may benefit from
considering interactions — there seems to be little computational difficulty
(in fact, convergence was almost always faster), and the valuable properties
of equilibrium existence and uniqueness are retained. Of course, there remain
other problems where dynamic assignment is preferred.

Further research would be valuable along several lines. Further investigation
of appropriate cost functions is needed, to derive them from other node
models, and to consider the impacts of these approximations on network-wide
flow. Additional research into algorithms for the non-monotone or non-
symmetric cases is also needed; we show that gradient projection still
functions as an acceptable heuristic, but comparisons with other algorithms
from the variational inequality literature are needed.

## Acknowledgments

This research was supported by the National Science Foundation under Grant
CMMI-1826320.

## Disclosure statement

The authors report there are no competing interests to declare.

## Data availability statement

The authors confirm that the data supporting the findings of this study are
available within the article and its supplementary materials.

## References

  * Astroza et al. (2017) Astroza, Sebastian, Priyadarshan N Patil, Katherine I Smith, and Chandra R Bhat. 2017. “Transportation planning to accommodate needs of wind energy projects.” _Transportation Research Record_ 2669 (1): 10–18.
  * Bar-Gera (2002) Bar-Gera, Hillel. 2002. “Origin-based algorithm for the traffic assignment problem.” _Transportation Science_ 36 (4): 398–417.
  * Bar-Gera (2010) Bar-Gera, Hillel. 2010. “Traffic assignment by paired alternative segments.” _Transportation Research Part B: Methodological_ 44 (8-9): 1022–1046.
  * Beckmann, McGuire, and Winsten (1956) Beckmann, Martin, Charles B McGuire, and Christopher B Winsten. 1956. _Studies in the Economics of Transportation_. Technical Report RM-1488-PR. RAND corporation.
  * Bernstein and Gabriel (1997) Bernstein, David, and Steven A Gabriel. 1997. “Solving the nonadditive traffic equilibrium problem.” In _Network optimization_ , 72–102. Springer.
  * Bertsekas (2016) Bertsekas, D. P. 2016. _Nonlinear Programming_. Cambridge, MA: Athena Scientific.
  * Bliemer et al. (2012) Bliemer, MCJ, L Brederode, Luc Johannes Josephus Wismans, and ES Smits. 2012. “Quasi-dynamic traffic assignment: static traffic assignment with queueing and spillback.” In _91st Transportation Research Board (TRB) Annual Meeting 2012_ , 1–24. Transportation Research Board (TRB).
  * Bliemer and Raadsen (2019) Bliemer, Michiel CJ, and Mark PH Raadsen. 2019. “Static traffic assignment with residual queues and spillback.” _Transportation Research Procedia_ 38: 647–667.
  * Boyce, Ralevic-Dekic, and Bar-Gera (2004) Boyce, David, Biljana Ralevic-Dekic, and Hillel Bar-Gera. 2004. “Convergence of traffic assignments: how much is enough?” _Journal of Transportation Engineering_ 130 (1): 49–55.
  * Boyles et al. (2018) Boyles, Stephen, Priyadarshan Patil, Venktesh Pandey, and Cesar Yahia. 2018. _Beyond Political Boundaries: Constructing Network Models for Megaregion Planning_. Technical Report CM2-11. The consortium of Cooperative Mobility for Competitive Megaregions (CM2).
  * Boyles (2012) Boyles, Stephen D. 2012. “Bush-based sensitivity analysis for approximating subnetwork diversion.” _Transportation Research Part B: Methodological_ 46 (1): 139–155.
  * Boyles, Lownes, and Unnikrishnan (2020) Boyles, Stephen D., Nicholas E. Lownes, and A. Unnikrishnan. 2020. _Transportation Network Analysis_. 0th ed., Vol. 1.
  * Boyles and Ruiz Juri (2019) Boyles, Stephen D, and Natalia Ruiz Juri. 2019. “Queue Spillback and Demand Uncertainty in Dynamic Network Loading.” _Transportation Research Record_ 2673 (2): 38–48.
  * Braess and Koch (1979) Braess, D, and G Koch. 1979. “On the existence of equilibria in asymmetrical multiclass-user transportation networks.” _Transportation Science_ 13 (1): 56–63.
  * Chen, Jayakrishnan, and Tsai (2002) Chen, Anthony, R Jayakrishnan, and Wei K Tsai. 2002. “Faster Frank-Wolfe traffic assignment with new flow update scheme.” _Journal of Transportation Engineering_ 128 (1): 31–39.
  * Chen, Zhou, and Ryu (2011) Chen, Anthony, Zhong Zhou, and Seungkyu Ryu. 2011. “Modeling physical and environmental side constraints in traffic equilibrium problem.” _International Journal of Sustainable Transportation_ 5 (3): 172–197.
  * Chen et al. (2020) Chen, Xinyuan, Zhiyuan Liu, Kai Zhang, and Zewen Wang. 2020. “A parallel computing approach to solve traffic assignment using path-based gradient projection algorithm.” _Transportation Research Part C: Emerging Technologies_ 120: 102809.
  * Chiu et al. (2011) Chiu, Yi-Chang, Jon Bottom, Michael Mahut, Alexander Paz, Ramachandran Balakrishna, Steven Waller, and Jim Hicks. 2011. “Dynamic traffic assignment: A primer (Transportation Research Circular E-C153).” .
  * Dafermos (1980) Dafermos, Stella. 1980. “Traffic equilibrium and variational inequalities.” _Transportation science_ 14 (1): 42–54.
  * Dafermos (1982) Dafermos, Stella. 1982. “Relaxation algorithms for the general asymmetric traffic equilibrium problem.” _Transportation Science_ 16 (2): 231–240.
  * Dafermos (1971) Dafermos, Stella C. 1971. “An extended traffic assignment model with applications to two-way traffic.” _Transportation Science_ 5 (4): 366–389.
  * Dafermos (1972) Dafermos, Stella C. 1972. “The traffic assignment problem for multiclass-user transportation networks.” _Transportation science_ 6 (1): 73–87.
  * Daganzo (1994) Daganzo, Carlos F. 1994. “The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory.” _Transportation Research Part B_ 28B (4): 269–287.
  * Daganzo (1995) Daganzo, Carlos F. 1995. “The cell transmission model, part II: network traffic.” _Transportation Research Part B_ 29B (2): 79–93.
  * De Grange and Muñoz (2009) De Grange, Louis, and Juan Carlos Muñoz. 2009. “An equivalent optimization formulation for the traffic assignment problem with asymmetric linear costs.” _Transportation planning and technology_ 32 (1): 1–25.
  * Dial (2006) Dial, Robert B. 2006. “A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration.” _Transportation Research Part B: Methodological_ 40 (10): 917–936.
  * Dupuis and Darveau (1986) Dupuis, Clermont, and Jean-Marc Darveau. 1986. “The convergence conditions of diagonalization and projection methods for fixed demand asymmetric network equilibrium problems.” _Operations Research Letters_ 5 (3): 149–155.
  * Facchinei and Pang (2003) Facchinei, F., and J. S. Pang. 2003. _Finite Dimensional Variational Inequalities and Complementarity Problems_. Springer Verlag.
  * Fisk and Nguyen (1982) Fisk, Caroline, and Sang Nguyen. 1982. “Solution algorithms for network equilibrium models with asymmetric user costs.” _Transportation Science_ 16 (3): 361–381.
  * Florian, Constantin, and Florian (2009) Florian, Michael, Isabelle Constantin, and Dan Florian. 2009. “A new look at projected gradient method for equilibrium assignment.” _Transportation Research Record_ 2090 (1): 10–16.
  * Florian and Spiess (1982) Florian, Michael, and Heinz Spiess. 1982. “The convergence of diagonalization algorithms for asymmetric network equilibrium problems.” _Transportation Research Part B: Methodological_ 16 (6): 477–483.
  * Frank and Wolfe (1956) Frank, Marguerite, and Philip Wolfe. 1956. “An algorithm for quadratic programming.” _Naval Research Logistics Quarterly_ 3 (1-2): 95–110.
  * Friesz (1985) Friesz, Terry L. 1985. “Transportation network equilibrium, design and aggregation: key developments and research opportunities.” _Transportation Research Part A: General_ 19 (5-6): 413–427.
  * Friesz, Harker, and Tobin (1984) Friesz, Terry L, Patrick T Harker, and Roger L Tobin. 1984. “Alternative algorithms for the general network spatial price equilibrium problem.” _Journal of Regional Science_ 24 (4): 475–507.
  * Gabriel and Bernstein (1997) Gabriel, Steven A, and David Bernstein. 1997. “The traffic equilibrium problem with nonadditive path costs.” _Transportation Science_ 31 (4): 337–348.
  * Gentile (2014) Gentile, Guido. 2014. “Local User Cost Equilibrium: a bush-based algorithm for traffic assignment.” _Transportmetrica A: Transport Science_ 10 (1): 15–54.
  * Gokalp, Patil, and Boyles (2021) Gokalp, Can, Priyadarshan N Patil, and Stephen D Boyles. 2021. “Post-disaster recovery sequencing strategy for road networks.” _Transportation research part B: methodological_ 153: 228–245.
  * He, Liao, and Wang (2012) He, Bingsheng, Li-Zhi Liao, and Xiang Wang. 2012. “Proximal-like contraction methods for monotone variational inequalities in a unified framework I: effective quadruplet and primary methods.” _Computational Optimization and Applications_ 51 (2): 649–679.
  * Hearn, Lawphongpanich, and Nguyen (1984) Hearn, Donald W, Siriphong Lawphongpanich, and Sang Nguyen. 1984. “Convex programming formulations of the asymmetric traffic assignment problem.” _Transportation Research Part B: Methodological_ 18 (4-5): 357–365.
  * Heydecker (1983) Heydecker, Benjamin G. 1983. “Some consequences of detailed junction modeling in road traffic assignment.” _Transportation Science_ 17 (3): 263–281.
  * Highway Capacity Manual (2010) Highway Capacity Manual. 2010. “HCM2010.” _Transportation Research Board, National Research Council, Washington, DC_ 1207\.
  * Jayakrishnan et al. (1994) Jayakrishnan, R, Wei T Tsai, Joseph N Prashker, and Subodh Rajadhyaksha. 1994. _A Faster Path-Based Algorithm for Traffic Assignment_. Technical Report. University of California Transportation Center.
  * Jin and Zhang (2003) Jin, WL, and H Michael Zhang. 2003. “On the distribution schemes for determining flows through a merge.” _Transportation Research Part B: Methodological_ 37 (6): 521–540.
  * Kumar and Peeta (2010) Kumar, Amit, and Srinivas Peeta. 2010. “Slope-based multipath flow update algorithm for static user equilibrium traffic assignment problem.” _Transportation research record_ 2196 (1): 1–10.
  * Kumar and Peeta (2014) Kumar, Amit, and Srinivas Peeta. 2014. “Slope-based path shift propensity algorithm for the static traffic assignment problem.” _International Journal for Traffic and Transport Engineering_ 4 (3): 297–319.
  * Larsson and Patriksson (1992) Larsson, Torbjörn, and Michael Patriksson. 1992. “Simplicial decomposition with disaggregated representation for the traffic assignment problem.” _Transportation Science_ 26 (1): 4–17.
  * Lawphongpanich and Hearn (1984) Lawphongpanich, Siriphong, and Donald W Hearn. 1984. “Simplical decomposition of the asymmetric traffic assignment problem.” _Transportation Research Part B: Methodological_ 18 (2): 123–133.
  * Lebacque (1996) Lebacque, J. P. 1996. “The Godunov scheme and what it means for first order traffic flow models.” In _Proceedings of the 13th International Symposium on Transportation and Traffic Theory_ , London, 647–678.
  * Lebacque and Khoshyaran (2005) Lebacque, J. P., and M. M. Khoshyaran. 2005. “First-order macroscopic traffic flow models: intersection modeling, network modeling.” In _Proceedings of the 16th International Symposium on Transportation and Traffic Theory_ , College Park, MD, 365–386.
  * Lee, Nie, and Chen (2003) Lee, Der-Horng, Yu Nie, and Anthony Chen. 2003. “A conjugate gradient projection algorithm for the traffic assignment problem.” _Mathematical and computer modelling_ 37 (7-8): 863–878.
  * Lo and Chen (2000) Lo, Hong K, and Anthony Chen. 2000. “Traffic equilibrium problem with route-specific costs: formulation and algorithms.” _Transportation Research Part B: Methodological_ 34 (6): 493–513.
  * Lundgren and Peterson (2008) Lundgren, Jan T, and Anders Peterson. 2008. “A heuristic for the bilevel origin–destination-matrix estimation problem.” _Transportation Research Part B: Methodological_ 42 (4): 339–354.
  * Mahmassani and Mouskos (1988) Mahmassani, Hani S, and Kyriacos C Mouskos. 1988. “Some numerical results on the diagonalization algorithm for network assignment with asymmetric interactions between cars and trucks.” _Transportation Research Part B: Methodological_ 22 (4): 275–290.
  * Marcotte and Guélat (1988) Marcotte, Patrice, and Jacques Guélat. 1988. “Adaptation of a modified Newton method for solving the asymmetric traffic equilibrium problem.” _Transportation Science_ 22 (2): 112–124.
  * Marcotte and Wynter (2004) Marcotte, Patrice, and Laura Wynter. 2004. “A new look at the multiclass network equilibrium problem.” _Transportation Science_ 38 (3): 282–292.
  * Meneguzzer (1995) Meneguzzer, Claudio. 1995. “An equilibrium route choice model with explicit treatment of the effect of intersections.” _Transportation Research Part B: Methodological_ 29 (5): 329–356.
  * Mitradjieva and Lindberg (2013) Mitradjieva, Maria, and Per Olov Lindberg. 2013. “The stiff is moving—conjugate direction Frank-Wolfe Methods with applications to traffic assignment.” _Transportation Science_ 47 (2): 280–293.
  * Nagurney (1986) Nagurney, Anna. 1986. “Computational comparisons of algorithms for general asymmetric traffic equilibrium problems with fixed and elastic demands.” _Transportation Research Part B: Methodological_ 20 (1): 78–84.
  * Nagurney (1984) Nagurney, Anna B. 1984. “Comparative tests of multimodal traffic equilibrium methods.” _Transportation Research Part B: Methodological_ 18 (6): 469–485.
  * Nguyen and Dupuis (1984) Nguyen, Sang, and Clermont Dupuis. 1984. “An efficient method for computing traffic equilibria in networks with asymmetric transportation costs.” _Transportation Science_ 18 (2): 185–202.
  * Nie (2012) Nie, Yu. 2012. “A note on Bar-Gera’s algorithm for the origin-based traffic assignment problem.” _Transportation Science_ 46 (1): 27–38.
  * Nie (2010) Nie, Yu (Marco). 2010. “Equilibrium analysis of macroscopic traffic oscillations.” _Transportation Research Part B_ 44: 62–72.
  * Pandey and Patil (2022) Pandey, Venktesh, and Priyadarshan N. Patil. 2022. “Computationally-Efficient Decomposition Heuristic for the Static Traffic Assignment Problem.” _arXiv preprint arXiv:2206.12496._ https://arxiv.org/abs/2206.12496.
  * Panicucci, Pappalardo, and Passacantando (2007) Panicucci, Barbara, Massimo Pappalardo, and Mauro Passacantando. 2007. “A path-based double projection method for solving the asymmetric traffic network equilibrium problem.” _Optimization Letters_ 1 (2): 171–185.
  * Patil, Walthall, and Boyles (2022) Patil, Priyadarshan, Rydell Walthall, and Stephen D Boyles. 2022. “Budget-Constrained Rail Electrification Modeling Using Symmetric Traffic Assignment: A North American Case Study.” _Journal of Infrastructure Systems_ 28 (2): 04022007.
  * Patil, Ross, and Boyles (2021) Patil, Priyadarshan N., Katherine C. Ross, and Stephen D. Boyles. 2021. “Convergence behavior for traffic assignment characterization metrics.” _Transportmetrica A: Transport Science_ 17 (4): 1244–1271. https://doi.org/10.1080/23249935.2020.1857883.
  * Patil (2021) Patil, Priyadarshan Nandkumar. 2021. “A-TAP implementation repository.” _https://github.com/PriyadarshanPatil/A-TAP-implementation_ Accessed: 2021-06-07.
  * Patriksson (2015) Patriksson, Michael. 2015. _The traffic assignment problem: models and methods_. Courier Dover Publications.
  * Peeta and Ziliaskopoulos (2001) Peeta, Srinivas, and Athanasios K. Ziliaskopoulos. 2001. “Foundations of dynamic traffic assignment: the past, the present, and the future.” _Networks and Spatial Economics_ 1: 233–265.
  * Powell and Sheffi (1982) Powell, Warren B, and Yosef Sheffi. 1982. “The convergence of equilibrium algorithms with predetermined step sizes.” _Transportation Science_ 16 (1): 45–55.
  * Prager (1954) Prager, William. 1954. “Problems of traffic and transportation.” _Proceeding of the Symposium on Operations Research in Business and Industry, Midwest Research Institute, Kansas City, Kansas, pp. 105—113._ .
  * Sancho, Ibáñez Marí, and Bugeda (2015) Sancho, Esteve Codina, Gemma Ibáñez Marí, and Jaume Barceló Bugeda. 2015. “Applying projection-based methods to the asymmetric traffic assignment problem.” _Computer-Aided Civil and Infrastructure Engineering_ 30 (2): 103–119.
  * Sender and Netter (1970) Sender, Jean Gerard, and Maurice Netter. 1970. _Equilibre offre-demande et tarification sur un réseau de transport, Modele ASTARTE (Application de systèmes tarifaires à un réseau de transport : trafics et tarifs d’équilibre)._ Technical Report. Institut de Recherche des Transports.
  * Sheffi (1985) Sheffi, Yosef. 1985. _Urban transportation networks_. Vol. 6. Prentice-Hall, Englewood Cliffs, NJ.
  * Smith (1979) Smith, Mike J. 1979. “The existence, uniqueness and stability of traffic equilibria.” _Transportation Research Part B: Methodological_ 13 (4): 295–304.
  * Smith (1983) Smith, Mike J. 1983. “The existence and calculation of traffic equilibria.” _Transportation Research Part B: Methodological_ 17 (4): 291–303.
  * Stabler (2019) Stabler, Ben. 2019. “Transportation Networks.” _https://github.com/bstabler/TransportationNetworks_ Accessed: 2019-05-25.
  * Tampère et al. (2011) Tampère, Chris M. J., Ruben Corthout, Dirk Cattrysse, and Lambertus H. Immers. 2011. “A generic class of first order node models for dynamic macroscopic simulation of traffic flows.” _Transportation Research Part B_ 45: 289–309.
  * Wong, Yang, and Lo (2001) Wong, Sze Chun, Chao Yang, and Hong K Lo. 2001. “A path-based traffic assignment algorithm based on the TRANSYT traffic model.” _Transportation Research Part B: Methodological_ 35 (2): 163–181.
  * Xie, Nie, and Liu (2018) Xie, Jun, Yu Nie, and Xiaobo Liu. 2018. “A greedy path-based algorithm for traffic assignment.” _Transportation Research Record_ 2672 (48): 36–44.
  * Xie and Xie (2014) Xie, Jun, and Chi Xie. 2014. “An improved TAPAS algorithm for the traffic assignment problem.” In _17th International IEEE Conference on Intelligent Transportation Systems (ITSC)_ , 2336–2341. IEEE.
  * Xie and Xie (2015) Xie, Jun, and Chi Xie. 2015. “Origin-based algorithms for traffic assignment: algorithmic structure, complexity analysis, and convergence performance.” _Transportation Research Record_ 2498 (1): 46–55.
  * Yang (1995) Yang, Hai. 1995. “Heuristic algorithms for the bilevel origin-destination matrix estimation problem.” _Transportation Research Part B: Methodological_ 29 (4): 231–242.
  * Yang (1997) Yang, Hai. 1997. “Sensitivity analysis for the elastic-demand network equilibrium problem with applications.” _Transportation Research Part B: Methodological_ 31 (1): 55–70.
  * Yang and Lam (1996) Yang, Hai, and William HK Lam. 1996. “Optimal road tolls under conditions of queueing and congestion.” _Transportation Research Part A: Policy and Practice_ 30 (5): 319–332.
  * Yin (2000) Yin, Yafeng. 2000. “Genetic-algorithms-based approach for bilevel programming models.” _Journal of transportation engineering_ 126 (2): 115–120.
  * Yook (2014) Yook, Donghyung. 2014. “Models and Solution Algorithms for Asymmetric Traffic and Transit Assignment Problems.” PhD diss., Utah State University.
  * Yook and Heaslip (2016) Yook, Donghyung, and Kevin Heaslip. 2016. “Acceleration of Double-Projection Method in Asymmetrically Formulated Traffic Assignment.” _Journal of Computing in Civil Engineering_ 30 (6): 04016025.
  * Yperman (2007) Yperman, I. 2007. “The Link Transmission Model for Dynamic Newtork Loading.” PhD diss., Katholieke Universiteit Leuven, Belgium.

##  Appendix A Raw Data

Table 1: Metric stabilization behavior data using Gradient Projection for S-TAP Sioux Falls |  | Berlin-Mitte-Prenzlauerberg-Friedrichshain-Center |  | Austin
---|---|---|---|---
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 2.13% | 1.48% | 5.26% |  | 1E-03 | 2.04% | 1.42% | 6.24% |  | 1E-03 | 2.39% | 2.18% | 9.55%
1E-04 | 0.89% | 0.65% | 2.63% |  | 1E-04 | 0.98% | 0.58% | 1.95% |  | 1E-04 | 1.59% | 1.09% | 5.38%
1E-05 | 0.35% | 0.18% | 1.31% |  | 1E-05 | 0.36% | 0.23% | 0.78% |  | 1E-05 | 0.85% | 0.59% | 0.90%
1E-06 | 0.07% | 0.03% | 0.00% |  | 1E-06 | 0.23% | 0.17% | 0.44% |  | 1E-06 | 0.58% | 0.39% | 0.72%
1E-07 | 0.02% | 0.01% | 0.00% |  | 1E-07 | 0.09% | 0.08% | 0.10% |  | 1E-07 | 0.19% | 0.19% | 0.19%
1E-08 | 0.00% | 0.00% | 0.00% |  | 1E-08 | 0.05% | 0.02% | 0.05% |  | 1E-08 | 0.05% | 0.03% | 0.08%
|  |  |  |  |  |  |  |  |  |  |  |  |
Eastern Massachusetts |  | Barcelona |  | Berlin Center
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 1.80% | 1.25% | 4.50% |  | 1E-03 | 1.78% | 1.65% | 5.52% |  | 1E-03 | 2.58% | 2.29% | 10.54%
1E-04 | 0.75% | 0.44% | 2.66% |  | 1E-04 | 0.94% | 0.93% | 2.54% |  | 1E-04 | 1.87% | 1.13% | 4.61%
1E-05 | 0.29% | 0.10% | 0.87% |  | 1E-05 | 0.45% | 0.43% | 0.91% |  | 1E-05 | 0.99% | 0.65% | 1.20%
1E-06 | 0.20% | 0.06% | 0.72% |  | 1E-06 | 0.23% | 0.31% | 0.67% |  | 1E-06 | 0.64% | 0.44% | 0.79%
1E-07 | 0.05% | 0.03% | 0.41% |  | 1E-07 | 0.12% | 0.11% | 0.29% |  | 1E-07 | 0.19% | 0.16% | 0.33%
1E-08 | 0.03% | 0.01% | 0.04% |  | 1E-08 | 0.02% | 0.03% | 0.08% |  | 1E-08 | 0.08% | 0.03% | 0.08%
|  |  |  |  |  |  |  |  |  |  |  |  |
Anaheim |  | Winnipeg |  | Chicago-Regional
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 2.47% | 1.41% | 4.77% |  | 1E-03 | 2.84% | 1.81% | 5.49% |  | 1E-03 | 2.24% | 1.51% | 11.58%
1E-04 | 0.77% | 0.57% | 2.58% |  | 1E-04 | 0.94% | 1.01% | 2.20% |  | 1E-04 | 1.24% | 0.84% | 5.07%
1E-05 | 0.41% | 0.31% | 0.72% |  | 1E-05 | 0.47% | 0.30% | 0.91% |  | 1E-05 | 0.61% | 0.43% | 0.94%
1E-06 | 0.25% | 0.18% | 0.24% |  | 1E-06 | 0.26% | 0.30% | 0.52% |  | 1E-06 | 0.46% | 0.34% | 0.77%
1E-07 | 0.10% | 0.08% | 0.04% |  | 1E-07 | 0.11% | 0.10% | 0.16% |  | 1E-07 | 0.18% | 0.08% | 0.27%
1E-08 | 0.05% | 0.01% | 0.02% |  | 1E-08 | 0.02% | 0.03% | 0.05% |  | 1E-08 | 0.04% | 0.02% | 0.04%
|  |  |  |  |  |  |  |  |  |  |  |  |
Chicago Sketch |  | Terrassa |  | Philadelphia
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 1.88% | 0.94% | 4.87% |  | 1E-03 | 2.55% | 2.16% | 6.51% |  | 1E-03 | 3.83% | 2.43% | 15.82%
1E-04 | 0.89% | 0.45% | 2.49% |  | 1E-04 | 0.98% | 0.96% | 2.77% |  | 1E-04 | 1.62% | 1.24% | 7.53%
1E-05 | 0.38% | 0.25% | 0.96% |  | 1E-05 | 0.52% | 0.36% | 0.98% |  | 1E-05 | 1.05% | 0.79% | 1.26%
1E-06 | 0.29% | 0.08% | 0.32% |  | 1E-06 | 0.29% | 0.37% | 0.48% |  | 1E-06 | 0.63% | 0.35% | 0.82%
1E-07 | 0.08% | 0.04% | 0.18% |  | 1E-07 | 0.13% | 0.08% | 0.20% |  | 1E-07 | 0.36% | 0.14% | 0.37%
1E-08 | 0.04% | 0.02% | 0.07% |  | 1E-08 | 0.02% | 0.03% | 0.08% |  | 1E-08 | 0.10% | 0.03% | 0.18%

Table 2: Metric stabilization behavior data using Algorithm B for S-TAP Sioux Falls |  | Berlin-Mitte-Prenzlauerberg-Friedrichshain-Center |  | Austin
---|---|---|---|---
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 2.00% | 1.44% | 5.26% |  | 1E-03 | 2.11% | 1.56% | 6.90% |  | 1E-03 | 2.87% | 2.47% | 11.24%
1E-04 | 0.80% | 0.59% | 2.63% |  | 1E-04 | 1.03% | 0.64% | 2.21% |  | 1E-04 | 1.91% | 1.24% | 5.90%
1E-05 | 0.20% | 0.15% | 1.31% |  | 1E-05 | 0.40% | 0.24% | 0.82% |  | 1E-05 | 1.02% | 0.66% | 1.11%
1E-06 | 0.10% | 0.07% | 0.00% |  | 1E-06 | 0.26% | 0.18% | 0.43% |  | 1E-06 | 0.61% | 0.49% | 0.79%
1E-07 | 0.05% | 0.04% | 0.00% |  | 1E-07 | 0.10% | 0.09% | 0.12% |  | 1E-07 | 0.20% | 0.20% | 0.20%
1E-08 | 0.04% | 0.03% | 0.00% |  | 1E-08 | 0.05% | 0.02% | 0.06% |  | 1E-08 | 0.05% | 0.04% | 0.08%
|  |  |  |  |  |  |  |  |  |  |  |  |
Eastern Massachusetts |  | Barcelona |  | Berlin Center
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 1.73% | 1.34% | 5.03% |  | 1E-03 | 2.02% | 1.74% | 6.10% |  | 1E-03 | 2.97% | 2.59% | 12.29%
1E-04 | 0.75% | 0.44% | 2.82% |  | 1E-04 | 1.00% | 1.03% | 2.88% |  | 1E-04 | 1.98% | 1.32% | 5.44%
1E-05 | 0.31% | 0.10% | 0.92% |  | 1E-05 | 0.52% | 0.46% | 1.02% |  | 1E-05 | 1.13% | 0.74% | 1.41%
1E-06 | 0.21% | 0.07% | 0.70% |  | 1E-06 | 0.24% | 0.36% | 0.73% |  | 1E-06 | 0.77% | 0.52% | 0.91%
1E-07 | 0.05% | 0.03% | 0.40% |  | 1E-07 | 0.13% | 0.11% | 0.32% |  | 1E-07 | 0.22% | 0.18% | 0.40%
1E-08 | 0.03% | 0.01% | 0.04% |  | 1E-08 | 0.02% | 0.03% | 0.08% |  | 1E-08 | 0.09% | 0.04% | 0.10%
|  |  |  |  |  |  |  |  |  |  |  |  |
Anaheim |  | Winnipeg |  | Chicago-Regional
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 2.56% | 1.45% | 4.93% |  | 1E-03 | 2.97% | 1.99% | 6.02% |  | 1E-03 | 2.61% | 2.38% | 13.07%
1E-04 | 0.80% | 0.60% | 2.55% |  | 1E-04 | 1.01% | 1.00% | 2.45% |  | 1E-04 | 1.59% | 1.10% | 5.97%
1E-05 | 0.40% | 0.30% | 0.77% |  | 1E-05 | 0.53% | 0.35% | 0.95% |  | 1E-05 | 0.92% | 0.61% | 1.00%
1E-06 | 0.26% | 0.19% | 0.23% |  | 1E-06 | 0.29% | 0.33% | 0.52% |  | 1E-06 | 0.76% | 0.54% | 0.79%
1E-07 | 0.10% | 0.08% | 0.04% |  | 1E-07 | 0.12% | 0.11% | 0.18% |  | 1E-07 | 0.50% | 0.23% | 0.00%
1E-08 | 0.05% | 0.01% | 0.02% |  | 1E-08 | 0.02% | 0.03% | 0.05% |  | 1E-08 | 0.15% | 0.10% | 0.00%
|  |  |  |  |  |  |  |  |  |  |  |  |
Chicago Sketch |  | Terrassa |  | Philadelphia
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
1E-03 | 2.03% | 1.02% | 5.55% |  | 1E-03 | 2.74% | 2.23% | 7.07% |  | 1E-03 | 3.95% | 2.80% | 17.88%
1E-04 | 0.99% | 0.50% | 2.85% |  | 1E-04 | 1.15% | 1.00% | 3.07% |  | 1E-04 | 1.89% | 1.50% | 7.91%
1E-05 | 0.37% | 0.25% | 0.99% |  | 1E-05 | 0.52% | 0.40% | 1.01% |  | 1E-05 | 1.48% | 1.26% | 1.49%
1E-06 | 0.29% | 0.09% | 0.34% |  | 1E-06 | 0.29% | 0.38% | 0.51% |  | 1E-06 | 1.01% | 0.76% | 0.89%
1E-07 | 0.08% | 0.04% | 0.20% |  | 1E-07 | 0.13% | 0.09% | 0.20% |  | 1E-07 | 0.64% | 0.45% | 0.49%
1E-08 | 0.04% | 0.02% | 0.08% |  | 1E-08 | 0.02% | 0.03% | 0.08% |  | 1E-08 | 0.30% | 0.05% | 0.20%

Table 3: Metric stabilization behavior comparison between Algorithm B and Gradient Projection Sioux Falls |  | Winnipeg
---|---|---
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
Alg-B | GP | Alg-B | GP | Alg-B | GP |  | Alg-B | GP | Alg-B | GP | Alg-B | GP
1E-03 | 2.00% | 2.13% | 1.44% | 1.48% | 5.26% | 5.26% |  | 1E-03 | 2.97% | 2.84% | 1.99% | 1.81% | 6.02% | 5.49%
1E-04 | 0.80% | 0.89% | 0.59% | 0.65% | 2.63% | 2.63% |  | 1E-04 | 1.01% | 0.94% | 1.00% | 1.01% | 2.45% | 2.20%
1E-05 | 0.20% | 0.35% | 0.15% | 0.18% | 1.31% | 1.31% |  | 1E-05 | 0.53% | 0.47% | 0.35% | 0.30% | 0.95% | 0.91%
1E-06 | 0.10% | 0.07% | 0.07% | 0.03% | 0.00% | 0.00% |  | 1E-06 | 0.29% | 0.26% | 0.33% | 0.30% | 0.52% | 0.52%
1E-07 | 0.05% | 0.02% | 0.04% | 0.01% | 0.00% | 0.00% |  | 1E-07 | 0.12% | 0.11% | 0.11% | 0.10% | 0.18% | 0.16%
1E-08 | 0.04% | 0.00% | 0.03% | 0.00% | 0.00% | 0.00% |  | 1E-08 | 0.02% | 0.02% | 0.03% | 0.03% | 0.05% | 0.05%
|  |  |  |  |  |  |  |  |  |  |  |  |  |
Anaheim |  | Austin
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
Alg-B | GP | Alg-B | GP | Alg-B | GP |  | Alg-B | GP | Alg-B | GP | Alg-B | GP
1E-03 | 2.56% | 2.47% | 1.45% | 1.41% | 4.93% | 4.77% |  | 1E-03 | 2.87% | 2.39% | 2.47% | 2.18% | 11.24% | 9.55%
1E-04 | 0.80% | 0.77% | 0.60% | 0.57% | 2.55% | 2.58% |  | 1E-04 | 1.91% | 1.59% | 1.24% | 1.09% | 5.90% | 5.38%
1E-05 | 0.40% | 0.41% | 0.30% | 0.31% | 0.77% | 0.72% |  | 1E-05 | 1.02% | 0.85% | 0.66% | 0.59% | 1.11% | 0.90%
1E-06 | 0.26% | 0.25% | 0.19% | 0.18% | 0.23% | 0.24% |  | 1E-06 | 0.61% | 0.58% | 0.49% | 0.39% | 0.79% | 0.72%
1E-07 | 0.10% | 0.10% | 0.08% | 0.08% | 0.04% | 0.04% |  | 1E-07 | 0.20% | 0.19% | 0.20% | 0.19% | 0.20% | 0.19%
1E-08 | 0.05% | 0.05% | 0.01% | 0.01% | 0.02% | 0.02% |  | 1E-08 | 0.05% | 0.05% | 0.04% | 0.03% | 0.08% | 0.08%
|  |  |  |  |  |  |  |  |  |  |  |  |  |
Chicago-Sketch |  | Philadelphia
Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL |  | Gap Level |  $\Delta$TSTT |  $\Delta$VMT | PUL
Alg-B | GP | Alg-B | GP | Alg-B | GP |  | Alg-B | GP | Alg-B | GP | Alg-B | GP
1E-03 | 2.03% | 1.88% | 1.02% | 0.94% | 5.55% | 4.87% |  | 1E-03 | 3.95% | 3.83% | 2.80% | 2.43% | 17.88% | 15.82%
1E-04 | 0.99% | 0.89% | 0.50% | 0.45% | 2.85% | 2.49% |  | 1E-04 | 1.89% | 1.62% | 1.50% | 1.24% | 7.91% | 7.53%
1E-05 | 0.37% | 0.38% | 0.25% | 0.25% | 0.99% | 0.96% |  | 1E-05 | 1.48% | 1.05% | 1.26% | 0.79% | 1.49% | 1.26%
1E-06 | 0.29% | 0.29% | 0.09% | 0.08% | 0.34% | 0.32% |  | 1E-06 | 1.01% | 0.63% | 0.76% | 0.35% | 0.89% | 0.82%
1E-07 | 0.08% | 0.08% | 0.04% | 0.04% | 0.20% | 0.18% |  | 1E-07 | 0.64% | 0.36% | 0.45% | 0.14% | 0.49% | 0.37%
1E-08 | 0.04% | 0.04% | 0.02% | 0.02% | 0.08% | 0.07% |  | 1E-08 | 0.30% | 0.10% | 0.05% | 0.03% | 0.20% | 0.18%

Table 1: Toy network costs for various scenarios | Separable | Symmetric-full | Symmetric-partial | Asymmetric-full | Asymmetric-partial
---|---|---|---|---|---
Link 1 | $15+x_{1}$ | $15+0.5x_{1}+0.167(x_{2}+x_{3}+x_{4})$ | $15+0.75x_{1}+0.25x_{2}$ | $15+0.5x_{1}+0.15x_{2}+0.167x_{3}+0.183x_{4}$ | $15+0.75x_{1}+0.25x_{2}$
Link 2 | $10+x_{2}$ | $10+0.5x_{2}+0.167(x_{1}+x_{3}+x_{4})$ | $10+0.75x_{2}+0.25x_{1}$ | $10+0.5x_{2}+0.167x_{1}+0.183x_{3}+0.15x_{4}$ | $10+0.75x_{2}+0.3x_{1}$
Link 3 | $10+x_{3}$ | $10+0.5x_{3}+0.167(x_{1}+x_{2}+x_{4})$ | $10+0.75x_{3}+0.25x_{4}$ | $10+0.5x_{3}+0.183x_{1}+0.167x_{2}+0.15x_{4}$ | $10+0.75x_{3}+0.3x_{4}$
Link 4 | $15+x_{4}$ | $15+0.5x_{4}+0.167(x_{1}+x_{2}+x_{3})$ | $15+0.75x_{4}+0.25x_{3}$ | $15+0.5x_{4}+0.15x_{1}+0.183x_{2}+0.167x_{3}$ | $15+0.75x_{4}+0.25x_{3}$
Table 2: Toy network convergence behavior | Relative gap
---|---
Iteration | Separable | Symmetric-full | Symmetric-partial | Asymmetric-full | Asymmetric-partial
1 | 6.0000 | 1.0000 | 4.5000 | 0.9048 | 4.5000
2 | 1.6670 | 0.2444 | 0.3542 | 0.3150 | 0.7500
3 | 1.1806 | 0.1531 | 0.3399 | 0.1537 | 0.3632
4 | 0.4289 | 0.0733 | 0.1482 | 0.0828 | 0.2465
5 | 0.6968 | 0.0384 | 0.0828 | 0.0396 | 0.1591
| Flows
Iteration | Separable | Symmetric-full | Symmetric-partial | Asymmetric-full | Asymmetric-partial
1 | [0.00,60.00,0.00,0.00] | [0.00,60.00,0.00,0.00] | [0.00,60.00,0.00,0.00] | [0.00,60.00,0.00,0.00] | [0.00,60.00,0.00,0.00]
2 | [0.00,30.00,30.00,0.00] | [0.00,40.00,20.00,0.00] | [0.00,30.00,30.00,0.00] | [0.00,41.00,19.00,0.00] | [0.00,40.00,20.00,0.00]
3 | [25.00,17.50,17.50,0.00] | [10.00,31.67,18.33,0.00] | [11.33,24.33,24.33,0.00] | [0.00,31.34,15.98,12.68] | [0.00,26.67,16.67,16.67]
4 | [12.50,11.25,11.25,25.00] | [6.67,26.11,17.22,10.00] | [5.67,18.48,20.37,15.48] | [9.78,25.73,15.19,9.30] | [15.55,21.11,13.33,10.00]
5 | [9.38,26.88,8.12,15.62] | [5.18,24.63,22.78,7.41] | [14.18,18.16,17.46,10.20] | [6.91,22.65,23.22,7.21] | [9.26,16.30,26.67,7.77]
Table 3: Description of networks used

Network name Zones Links Nodes Trips SiouxFalls 24 76 24 360,600 Eastern-
Massachusetts 74 258 74 65,576 Chicago-sketch 387 2950 933 1,260,907 Barcelona
110 2522 1020 184,679 Chicago-Regional 1790 39018 12982 1,360,427

Table 4: Description of networks used

Network name Zones Links Nodes Trips Average flow-to-capacity ratio SiouxFalls
24 76 24 360,600 1.612 Eastern-Massachusetts 74 258 74 65,576 0.163 Anaheim 38
914 416 104,694 0.297 Chicago-sketch 387 2950 933 1,260,907 0.257 Berlin-
Prenzlauerberg-Center 98 2184 975 23,648 0.121 Barcelona 110 2522 1020 184,679
1.137 Winnipeg 147 2836 1052 64,784 2.028 Terrassa 55 3264 1609 25,225,700
5.964 Austin 7388 18961 7388 739,351 0.875 Berlin-Center 865 28376 12981
168,222 0.092 Chicago-Regional 1790 39018 12982 1,360,427 0.522 Philadelphia
1525 40003 13389 18,503,872 0.949

(a) Example network

(b) Objective function visualization

Figure 1: S-TAP example with multiple extreme points

Figure 2: Toy network

Figure 3: Condition number behavior of Sioux Falls problem instances

(a) Asymmetric to symmetric weight matrix convergence

(b) Convergence for S-TAP GP with $N$-link cost dependency

(c) Convergence for A-TAP GP with $N$-link cost dependency

Figure 4: Experimental results for Sioux Falls network

Figure 5: Sioux Falls asymmetric to symmetric weight matrix convergence

(a) Convergence for S-TAP GP with $N$-link cost dependency

(b) Convergence for A-TAP GP with $N$-link cost dependency

(c) Asymmetric to symmetric weight matrix convergence

Figure 6: Experimental results for Eastern Massachusetts network

(a) Convergence for S-TAP GP with $N$-link cost dependency

(b) Convergence for A-TAP GP with $N$-link cost dependency

(c) Asymmetric to symmetric weight matrix convergence

Figure 7: Experimental results for Chicago-sketch network

(a) Convergence for S-TAP GP with $N$-link cost dependency

(b) Convergence for A-TAP GP with $N$-link cost dependency

(c) Asymmetric to symmetric weight matrix convergence

Figure 8: Experimental results for Barcelona network

(a) Convergence for S-TAP GP with $N$-link cost dependency

(b) Convergence for A-TAP GP with $N$-link cost dependency

(c) Asymmetric to symmetric weight matrix convergence

Figure 9: Experimental results for Chicago-regional network

Figure 10: $\Delta$TSTT trends for different gap levels

Figure 11: $\Delta$VMT trends for different gap levels

Figure 12: PUL trends for different gap levels

List of figure captions:

  * •

Figure 1. S-TAP example with multiple extreme points

  * •

Figure 2. Toy Network

  * •

Figure 3. Condition number behavior of Sioux Falls problem instances

  * •

Figure 4. Experimental results for Sioux Falls network

  * •

Figure 5. Sioux Falls asymmetric to symmetric weight matrix convergence

  * •

Figure 6. Experimental results for Eastern Massachusetts network

  * •

Figure 7. Experimental results for Chicago-sketch network

  * •

Figure 8. Experimental results for Barcelona network

  * •

Figure 9. Experimental results for Chicago-regional network

  * •

Figure 10. $\Delta$TSTT trends for different gap levels

  * •

Figure 11. $\Delta$VMT trends for different gap levels

  * •

Figure 12. PUL trends for different gap levels