Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
84,658 characters · 19 sections · 66 citation commands
Sensitivity analysis of the perturbed utility stochastic traffic equilibrium
\affil[a]{University of Copenhagen, Denmark} \affil[b]{Technical University of Denmark, Denmark} \affil[c]{Technion, Israel}
Keywords: Sensitivity analysis; perturbed utility; route choice; stochastic traffic equilibrium
This paper presents analytical results and computational algorithms for sensitivity analysis of the equilibrium assignment with the perturbed utility route choice (PURC) model. This allows estimation of the change in equilibrium flows that follows a change in network parameters, without having to resolve for equilibrium.
More specifically, we provide analytical expressions for the following.
To obtain these results, we have overcome some specific challenges presented by the PURC model. It is an important and attractive feature of the PURC model that it uses the whole network as choice set, but may predict that network links are inactive, having zero flow. This means we must deal with a flow conservation constraint at each network node as well as potential non-differentiability at points where some links change between being active and inactive.
With the analytical expressions for the Jacobians, we can approximate equilibrium outcomes in new scenarios without having to resolve for equilibrium. This is of value if we are able to compute the Jacobians faster than we can recompute the equilibrium. We provide algorithms for this purpose that exploit the sparsity that occurs when many network links in a large network are inactive.
These results have many potential applications. One is the economic appraisal of changes in network parameters. The perturbed utility framework implies a natural welfare measure, namely the maximized perturbed utility or, as it is often called, the value function. We demonstrate this is continuously differentiable as a function of link costs, with a gradient that is the link flow. This observation allows our sensitivity results to be applied directly for approximate cost-benefit analysis.
Perhaps the most important application of sensitivity analysis is to bilevel optimization problems, e.g., network design and pricing problems yang1997traffic,josefsson2007sensitivity, (hyper)parameter optimization and meta-learning franceschi2018bilevel,lorraine2020optimizing, as well as deep equilibrium and implicit models bai2019deep. Such problems are generally computationally intensive and require numerous model solutions. Our results may be used to speed up computation, thereby increasing the size of bilevel problems that can be addressed in practice.
We set up the PURC model and the perturbed utility stochastic traffic equilibrium model in Section (ref). Our theoretical results are presented in Section (ref). Section (ref) illustrates the use of our theoretical results in numerical examples using toy networks. We present a prediction of equilibrium link flow patterns following changes in network parameters, without needing to resolve for equilibrium. We also show how sensitivity results can assist in the uncertainty analysis of prediction outputs when there is uncertainty about network parameters. A particular finding, illustrated with examples, is that some pairs of paths can be complements in the PURC model. This contradicts a result in a previous paper in this journal. Although it is not a focus of this paper, we take the opportunity to point out and correct the error. Finally, Section (ref) applies our main results using a real-world network. Section (ref) concludes. The following section provides a literature review.
The perturbed utility route choice (PURC) model fosgerau_perturbed_2022, fosgerau_bikeability_2023 predicts the route choice behavior of an individual traveler as a link flow vector across a network that solves a convex minimization problem, defined in terms of link costs and a convex perturbation function of the link flow vector. The flow vector is constrained to satisfy flow conservation from origin to destination. Thus, the PURC model belongs to the general class of perturbed utility models fosgerau2012theory,allen2019identification, adapted to the route choice context. The perturbation function plays an important role for two reasons. First, it directly incorporates the network structure. This determines the substitution patterns of the PURC model, which therefore take the network structure into account, without the need to extend the model to explicitly account for "correlation". Second, the perturbation function is constructed to allow corner solutions, such that the model can predict travel only on a small active subnetwork, specific to each origin-destination pair.
The corresponding perturbed utility traffic equilibrium model is developed in yao_perturbed_2024, who develop a fast algorithm for computing the equilibrium assignment for large problems. The basis for this is a mathematical trick, due to beckmann1956studies, which formulates the equilibrium as the solution to a convex optimization problem involving a certain potential function. We employ the same potential function in this paper.
We now discuss sensitivity analysis for traffic equilibrium. This quantifies the rates of change in equilibrium traffic flows as a function of network parameters.
A key application of traffic equilibrium sensitivity is simply to estimate the change in equilibrium flow patterns that follows a change in network parameters without having to completely re-solve the traffic equilibrium problem tobin1988sensitivity, yang1997traffic, patriksson2003sensitivity. This, in turn, is important for the welfare analysis of transportation network interventions Small1992.
More broadly, sensitivity analysis is central in bilevel optimization problems luo1996mathematical, josefsson2007sensitivity, where a traffic equilibrium appears as the lower-level constraint. Two classic examples are capacity expansion and road pricing. In the capacity expansion problem yang1998models, gao2004continuous, sensitivity information points to the direction in which marginal investments have the largest impacts on equilibrium flows, guiding the design of efficient network investments. In the pricing problem yan1996optimal, wang2021optimal, sensitivity with respect to link costs enables the calculation of gradients for objectives such as social welfare or revenue, which is necessary for designing general pricing schemes beyond classic marginal pricing. Thus, an important motivation for sensitivity analysis is to make large-scale bilevel optimization tractable.
Existing methods for computing sensitivities often require solving auxiliary equilibrium problems patriksson_sensitivity_2004,josefsson2007sensitivity, lu2008sensitivity or inverting large dense matrices ying2005sensitivity, clark2006applications,yang2009sensitivity, both of which are computationally demanding and difficult to scale to real-size networks. This scalability issue motivates the analytical results and sparse algorithms that we develop in this paper.
The technical foundation for sensitivity analysis is the differentiability of the equilibrium solution with respect to network parameters. Classical results robinson1985implicit, robinson2006strong show that if the equilibrium conditions are continuously differentiable with an invertible Jacobian, sensitivities can be obtained via the implicit function theorem clarke1990optimization. Along these lines, tobin1988sensitivity, yan1996optimal, and cho2000reduction propose deriving equilibrium sensitivity on reduced networks using the implicit function theorem, under additional differentiability assumptions. However, differentiability is not always guaranteed patriksson_sensitivity_2004. In deterministic equilibrium models, for instance, flows may concentrate on a limited set of minimum-cost paths, so that small parameter changes can shift the set of active links in a non-smooth way patriksson2003sensitivity. Consequently, directional differentiation is required for equilibrium sensitivity analysis to network parameters patriksson_sensitivity_2004, josefsson2007sensitivity, and elastic demands lu2008sensitivity. Stochastic user equilibrium models based on additive random utility dial1971probabilistic,maher1997probit,bekhor2001stochastic, baillon2008markovian, kitthamkesorn2014unconstrained, oyama2022markovian avoid the issue of differentiability by assigning strictly positive flows to all links or paths, but at the cost of losing the ability to predict zero flows on long detour paths. The PURC model combines both features: it predicts equilibrium link flow patterns where travelers are predicted to use not only the minimum cost paths while still predicting zero flows on long detour paths fosgerau_perturbed_2022,fosgerau_bikeability_2023,yao_perturbed_2024. The possibility of zero flows raises the issue of differentiability. We establish that the equilibrium link flows in the PURC framework are differentiable almost everywhere, and derive analytical sensitivity expressions based on the projected first-order condition, which can be evaluated on the active subnetwork and thus supports efficient sparse computation. Our analytical sensitivity results are consistent with classic works such as tobin1988sensitivity, but our analysis and proof exploit specific properties of the PURC. We detail our analysis in the following sections.
The PURC model fosgerau_perturbed_2022, fosgerau_bikeability_2023 is defined for a network $(\mathcal{N},\mathcal{L})$, where $\mathcal{N}$ is the set of nodes with typical element $v$ and $\mathcal{L}$ is the set of directed links with typical element $ij$ for a link from node $i$ to node $j$. We assume at least one path exists between any two network nodes, i.e.,
The node-link incident matrix $A\in \mathbb{R}^{|\mathcal{N}| \times | \mathcal{L}|}$ has entries
The demand for a traveler is encoded as a unit demand vector $b\in \mathbb{R} ^{|\mathcal{N}|}$ with components
A network link flow vector $x\in \mathbb{R}_+^{|\mathcal{L}|}$ satisfies flow conservation if $Ax=b$. The network link lengths are summarized in the vector $l = \{l_{ij}\}_{ij \in \mathcal{L}}\in \mathbb{R}_{++}^{|\mathcal{L}|}$.
A traveler in the PURC model is associated with a demand vector $b$, a vector of non-negative link costs $c\in \mathbb{R}_{+}^{|\mathcal{L}|}$, and link-specific convex perturbation functions $\{F_{ij}\}_{ij \in \mathcal L}$, satisfying the following assumption.
For a flow vector $x\in \mathbb{R}_{+}^{|\mathcal{L}|}$, we define
for the sum across links of perturbations $F_{ij}(x_{ij})$. The link perturbations may incorporate link lengths $l_{ij}$ as in the examples below. Eq. (ref) generalizes fosgerau_perturbed_2022 by allowing perturbations $F_{ij}(x_{ij})$ to be link-specific.
Specific instances of the perturbation function for use in applications include, e.g., a specification based on entropy
and a quadratic specification
where $l_{ij}$ is the length of link $ij$.
The PURC model predicts an individual's routing decisions as a network flow vector $x^*$ that solves an individual-level cost minimization problem of the perturbed utility form
The constraint $Ax=b$ implies conservation of network flow.
Thus, the PURC model is a utility-maximizing model, which ensures that the model predictions conform to standard rationality requirements. The PURC model connects to data with the assumption that the optimal flow vector $x^*$ is the expectation of the vector $y$, which is observed path choice encoded as a vector of zeros and ones, with ones indicating which links are included in the observed path.
As a utility-maximizing model, the PURC model admits a natural welfare measure. Let $W$ denote the negative value function,
where $v=-c$. This is the optimal perturbed utility that a traveler obtains. Theorem (ref) below presents the gradient of the value function, and the use of this result for welfare analysis of marginal changes is discussed in Section (ref).
We now derive the optimal link flow vector $x^*$ for a given cost vector $c$ and demand $b$, which is the key ingredient to our sensitivity analysis of the PURC. We start with the Lagrangian for the individual traveler's perturbed cost minimization problem:
Let $B^* = \mathrm{diag} \left( 1_{\{x^*>0\}} \right)$ be the matrix with ones on the diagonal corresponding to positive optimal link flows $x^*_{ij}$. The first-order condition for the cost minimization problem can then be written as
where $\nabla F(x^*) = \{F_{ij}^{\prime }(x^*_{ij})\}_{ij\in \mathcal{L}}$ is the gradient of $F$.
Inspecting Eq. (ref), we see that it comprises dual variables $\eta^*$ corresponding to the flow-conservation constraints at each node in the network. We shall proceed to eliminate these. Let ${P^*}$ be the matrix
where $(A{B^*})^{+}$ is the Moore-Penrose inverse of $A B^*$. Lemma (ref) in the Appendix shows that $ P^*$ is the orthogonal projection onto the linear subspace
i.e. the intersection of the null space of $A$ and the subspace where the components corresponding to inactive links are zero. Pre-multiplying Eq. (ref) by ${P^*}$ yields (see again Lemma (ref)) the projected first-order condition
The perturbed utility stochastic traffic equilibrium model yao_perturbed_2024 extends PURC to the case where the collective routing decisions of individuals influence link costs. Specifically, the stochastic traffic equilibrium model formulates the equilibrium problem as an optimization problem:
where $\mathcal{W} = \{w\}$ is the set of traveler types, $x^w = (x_{ij}^w)_{{ij}\in\mathcal{L}}$ is the set of link flows for type $w$, $x= \sum_{w\in \mathcal{W}} q ^w x^w$ is the aggregate link flow vector, $\zeta_{ij}(\cdot)$ is the link cost function, $q^w \in \mathbb{R}_{++}$ is the total demand for each type $w$, $F^w$ is the perturbation function for type $w$, and $b^w$ is a unit demand vector that encodes the OD for type $w$. With these definitions, the term $q^w x_{ij}^w$ is the flow on link $ij$ of travelers of type $w$.
The equilibrium problem has a unique solution if link cost functions are monotone yao_perturbed_2024. Hence, we make the following assumption on link cost functions, which will be convenient for our sensitivity analysis presented in the next section.
Assumption (ref) implies that the link cost functions have inverses and hence that link flows corresponding to any cost $c_{ij}$ can be expressed in terms of the inverse cost function:
Therefore, we can write the equilibrium condition as
where $x^*_{ij}(c) = \sum_{w\in\mathcal{W}} q^w x_{ij}^{w*}(c)$ is the aggregate PURC optimal flow on link $ij$ given cost $c$. We will use this relationship to connect the sensitivity analysis of traffic equilibrium to the sensitivity analysis of the PURC optimal flows.
Our setup thus allows heterogeneous traveler types. To unburden the notation, we will not carry the potential heterogeneity of the perturbation function through the analysis. Hence, from this point, we will assume $F^w=F,w\in \mathcal{W}$.
We note that it is straightforward to allow heterogeneous link costs of an additively separable form, $\tilde \zeta_{ij}^w=c^w_{ij} + \zeta_{ij}$.
Differentiating the objective (ref) with respect to type-specific link flows $x_{ij}^w$, we obtain the type-specific perturbed link cost as
where the first term in the parenthesis reflects congestion due to collective routing decisions $x_{ij} = \sum_{w\in\mathcal{W}} q^w x_{ij}^w$, and the second term is the type-specific (marginal) perturbation cost $\nabla F_{ij}(x_{ij}^w)$, representing, for example, travelers' taste for variety.
The PURC model has the realistic feature that many links may have zero flow, i.e.\ they may be inactive. This implies that flow can change in a non-smooth way as links may change between being active and inactive as the cost vector changes. To help handle that issue, we define the activation boundary,
as the set of cost vectors $c$ where a marginal change in costs may cause the set of active links to change.
Using the projection matrix $ P^*$ defined in Eq. (ref), we now establish our first main result, showing that the optimal flow is equal to the gradient of the value function. Outside the activation boundary, we show the optimal flow is continuously differentiable, and we give an analytical expression for the Jacobian of the optimal flow vector differentiated with respect to the link cost vector. This Jacobian comprises all information about how demands respond to marginal cost changes.
Finally, we show that the activation boundary is small, of Lebesgue measure zero. For this result, we require a regularity assumption, namely that the perturbation function $F$ is definable van1998tame. Functions defined in terms of polynomials, exponentials and logarithms are definable, and hence the entropic (ref) and quadratic (ref) perturbation functions are examples of definable functions. We give a brief introduction to definability in Appendix (ref).
We provide now some remarks on Theorem (ref). Item 1 in the theorem is the analog of the Williams–Daly–Zachary Theorem for discrete choice additive random utility models (ARUM) mcfadden_econometric_1981,Sorensen2019, which states that the gradient of the expected maximum utility is equal to the choice probability vector. The ARUM has an equivalent representation as a perturbed utility maximization problem similar to (ref).
We note that the Jacobian $\nabla_c x^*(c)$ relates to all links in the network, including those with zero flow. Issues of non-differentiability occur only on the activation boundary where some links change between zero and positive flow. Using the convex conjugate of the perturbation function $F$, our theorem establishes continuous differentiability of the flow vector on the complement of the activation boundary. Moreover, we show that the activation boundary has Lebesgue measure zero, using again the properties of the convex conjugate.
An alternative approach to establishing sensitivity results for the PURC would have been to use tobin1988sensitivity as a starting point. We have not pursued this approach, but under the strict complementarity and linear independence constraint qualification conditions assumed there, the equilibrium would lie in the complement of the activation boundary $\mathcal{C}_0$. In that case, the equilibrium conditions reduce to a smooth system and would have led us to the same Jacobian as in item 2 of Theorem (ref). In this sense, our activation boundary condition plays a role closely analogous to strict complementarity or non-degeneracy in the classical literature.
Our analysis, however, differs primarily in its formulation: rather than working with primal–dual optimality conditions as in the classic works, our theorem builds on the projected first-order condition. This approach avoids the introduction of dual variables and allows differentiability to be characterized directly in terms of the predicted flow, an object of primary interest.
It is not a new insight that the set of points of non-differentiability is small. boyles2020transportation state (without proof) that there is a finite number of degenerate points in classical user equilibrium. Their argument is similar in spirit to our Lebesgue measure zero result, and our proof strategy could be applied in their case.
The dual variables $\eta^*$ (node potentials) can be recovered from the first-order condition (ref): for any active link $ij$ with $x^*_{ij} > 0$, we have $c_{ij} + F'_{ij}(x^*_{ij}) + \eta^*_j - \eta^*_i = 0$. Given the optimal flow $x^*$ and costs $c$, the dual variables are obtained by solving this linear system on the active subnetwork, after normalizing the potential at one node. The sensitivity of the (active) dual variables with respect to cost parameters then follows by differentiating (ref) with respect to $c$, using the Jacobian $\nabla_c x^*(c)$ from Theorem (ref).
In the next subsection, we will apply Theorem (ref) to sensitivity analysis of perturbed utility traffic equilibrium. Later, in Section (ref), we apply Theorem (ref) to analyze the substitution pattern of the PURC, showing in particular that complementarity may occur. Something which is ruled out by ARUM discrete choice models.
In the previous section, we presented analytical sensitivity results for the PURC model for the case where link costs are independent of link flows. We now extend the analysis to the case of perturbed utility stochastic traffic equilibrium, where link costs are flow-dependent.
We consider link cost functions parametrized by $\theta \in \Theta$ of arbitrary dimension, denoted as $\zeta_{ij}(x_{ij}; \theta_{ij})$. The equilibrium link flows are parameterized by type-specific demands $q=(q^w)_{w \in \mathcal{W}}$, and we consequently denote the equilibrium link flows as $x^*_{ij}(c_{ij}^*; q)$ and the inverse link cost functions as $\zeta^{-1}_{ij}(c_{ij}; \theta_{ij})$. With this notation, the equilibrium condition (ref) becomes
For notational ease, let $y = (\theta, q) \in \mathbb{R}^{|\mathcal{L}| + |\mathcal{W}|}$ denote the vector of parameters, with
and vector-valued function $G(y, c) = (G_{ij}(y, c))_{ij \in\mathcal{L}}$. We obtain the following result.
The proof of Theorem (ref) carries through even if the separability implicit in Assumption (ref) is relaxed. Indeed, we only need link cost functions to be strictly monotone in aggregate link flows in the sense that $\nabla_{x} c(x^*; \theta)$ must be positive definite, which also ensures the existence of the inverse function $\zeta^{-1}(c; \theta)$ and positive definiteness of $\nabla_c \zeta^{-1}(c^*; \theta)$.
Furthermore, Theorem (ref) implies that equilibrium link costs are functions of parameters $y$, that is $c^*(y)$. Hence, the aggregate equilibrium link flows are also implicit functions of the parameters $y$, i.e., $x^*(c^*(y); q) = \sum_{q\in\mathcal{W}} q^w x^{w*}(c^*(y))$. We can then compute the sensitivity of equilibrium link flows using the chain rule. We state this as a theorem for easy reference.
We note that, by exploiting the specific properties (strict convexity, separability, and differentiability, as detailed in Assumption (ref)) of the perturbation function, Eq. (ref)-(ref) provide closed-form expressions for the Jacobian of the equilibrium link flows for all parameters $y$ at once.
We now discuss the application of item 1 in Theorem (ref) to welfare analysis. We have in mind situations where it is desired to assess the welfare consequences of an intervention in the transport system, which is perhaps relatively minor, such that the effort required to recompute the model for the case after the intervention might seem disproportionately large. In that case, it might be useful to be able to approximate the welfare change without recomputing the model.
The value function (ref) measures the utility achieved by travelers of a certain type following a change in the link cost vector. Hence, the gradient of the value function in (ref) can be used to compute the approximate welfare change following a marginal change in link costs.
It is possible to apply a first-order Taylor approximation, whereby \[\Delta W(-c) \simeq x^*(c) \Delta c.\] This simply approximates the welfare change holding the flow vector constant.
The next step is to account also for the approximate change in the flow vector following a cost change. We can achieve this by a second-order Taylor approximation
This is reminiscent of the well-known rule-of-a half, commonly applied in benefit-cost analysis of transport system interventions fosgerau_rule---half_2021.
The individual traveler's value function (ref) depends only on the cost vector, regardless of whether it is flow-dependent or not. For the flow-dependent case of equilibrium described in Section (ref), we can use the chain rule, combining (ref) with (ref) in Theorem (ref), to estimate welfare changes due to changes in network parameters.
The primary challenge in computing the sensitivity of the optimal PURC link flows is evaluating the Jacobian in Eq. (ref). The naive approach, computing the pseudo-inverse of a matrix the size of the full network $|\mathcal{L}|\times |\mathcal{L}|$, is computationally prohibitive, with a complexity of $O(|\mathcal{L}|^3)$. We propose instead to exploit the inherent sparsity of the problem to find a much more efficient approach.
For any given traveler type $w$, the optimal flow vector $x^{w*}$ is typically sparse, as many links on irrelevant parts of the network have zero flow. The corresponding entries in the Jacobian matrix for these inactive links are simply zero. This allows us to restrict the expensive matrix operations to the much smaller active subnetwork where flows are strictly positive, $x_{ij}^{w*} > 0$.
The streamlined computational procedure is as follows. For each type $w \in \mathcal{W}$, we first identify the active subnetwork, which consists only of the set of active links $\mathcal{L}^{w*}$ and their incident nodes. We then construct a node-link incidence matrix for this active subnetwork and remove the row corresponding to the destination of $w$, denoting the resulting matrix as $\tilde{A}^{w*}$. This matrix has full row rank biggs1993algebraic, which makes the term $\left(\tilde{A}^{w*}\right)^\top \tilde{A}^{w*}$ invertible. We use $\sim$ to denote quantities related to the active subnetwork. The key algorithmic steps are then summarized in Algorithm (ref).
This approach has significant computational benefits. It dramatically reduces the computational complexity from $O(|\mathcal{L}|^3)$ to $O(|\tilde{\mathcal{L}}^{w*}|^3)$, where $|\tilde{\mathcal{L}}^{w*}|$ is typically far smaller than $|\mathcal{L}|$. This makes the sensitivity analysis scalable to very large, real-world networks, as will be shown in our large-scale experiment below.
The computations in Algorithm (ref) are carried out independently for each travel type $w \in \mathcal{W}$. This makes the algorithm embarrassingly parallelizable by traveler type, which allows for substantial speedups with multi-core processing units.
The sensitivity of the flow for each traveler type is an input for the computation of the sensitivity of traffic equilibrium, discussed in the next section.
The sensitivity analysis of traffic equilibrium requires evaluating the Jacobian from Eq. (ref), which involves inverting a large, network-sized matrix $\nabla_{c} \zeta^{-1}(c^*; \theta) - \nabla_c x^{*}(c^*; q)$, where the aggregate Jacobian $\nabla_c x^{*}(c^*; q)$ is assembled from the per-type Jacobians computed by Algorithm (ref), evaluated at the equilibrium costs $c^* $. Direct inversion of this matrix presents a significant computational bottleneck for large-scale networks. To overcome this, we propose an efficient two-step approach that exploits the inherent structure of the equilibrium problem. The core idea is to first reduce the problem's dimensionality by leveraging sparsity and then to solve the reduced problems using a numerically superior method.
First, we exploit again the fact that, in equilibrium, many links in the network are inactive, meaning they carry zero aggregate flows $x^*_{ij} = 0$. By partitioning the links into active $\tilde{\mathcal{L}^*} = \{ij| x^*_{ij} = \sum_{w\in\mathcal{W}}q^w x_{ij}^{w*}>0\}$ and inactive sets, we can reorder the matrix into a simpler block-diagonal structure. This isolates the computationally intensive part of the problem into two smaller sub-matrices:
where the upper-left block corresponds to the active subnetwork. $D_1$ is a diagonal matrix containing the inverse link cost functions, $\zeta_{ij}^{-1}(c^*_{ij}; \theta)$, for the active links $ij \in \tilde{\mathcal{L}^*}$. Similarly, $\nabla_{\tilde{c}} \tilde{x}^{*}(c)$ is the Jacobian of the active aggregated PURC flows with respect to the costs on the active links, that is $\nabla_{\tilde{c}} \tilde{x}^{*}(c) = \left(\sum_{w\in\mathcal{W}} q^w \nabla^\top_{\tilde{c}}{x}_{ij}^{w*}(c)\right)^\top_{ij\in\tilde{\mathcal{L}}^*}$ with $\tilde{c} = (c_{ij})_{ij \in \tilde{\mathcal{L}}^*}$. The bottom-right block corresponds to the inactive links. Since the Jacobian of PURC flows is zero for inactive links, this block simplifies to $D_2$, a diagonal matrix of the inverse link cost derivatives for inactive links, $ij \in \mathcal{L} \setminus \tilde{\mathcal{L}}^*$. Consequently, the inverse of the diagonal block $D_2$ is trivial. The only remaining challenge is to handle the smaller, dense block corresponding to the active subnetwork.
Second, we consider the inversion of the matrix $M \coloneqq D_1 - \nabla_{\tilde{c}} \tilde{x}^{*}(c)$ for the active subnetwork block. Computing the inverse $M^{-1}$ first is not the most efficient or stable method. Instead, we may observe that our goal is to compute $J \coloneqq M^{-1}\nabla_{\tilde{y}} \tilde{G}(y, c^*)$. We propose to employ an efficient and numerically stable computational routine golub2013matrix for that purpose: finding $J$ by solving the equivalent linear system of equations $MJ=\nabla_{\tilde{y}} \tilde{G}(y, c^*)$. This method allows leveraging highly optimized and numerically stable algorithms to find $J$ without ever needing to form the explicit inverse. For medium-size matrices (e.g., up to $10,000\times10,000$ on modern machines), direct solution routines like Cholesky or LDLT factorization golub2013matrix are highly efficient with time complexity of ${|\tilde{\mathcal{L}}^*|}^3/3 + O(|\tilde{\mathcal{L}}^*|^2)$, where $|\tilde{\mathcal{L}}^*|$ is the number of active links. For extremely large matrices, Krylov subspace methods like the conjugate gradient method golub2013matrix are well suited, whose complexity for large linear systems can be magnitudes smaller than direct methods saad2003iterative.
Combining these two steps, the block-diagonal transformation to reduce the problem's size and the solution of a linear system as the core computational step, we obtain an algorithm that is scalable, numerically stable, and practical for implementation in large, real-world networks.
The computational approach exploits sparsity at two distinct levels. At the first level, Algorithm (ref) computes the per-type Jacobians $\nabla_c x^{w*}(c^*)$ on each type's active subnetwork $\tilde{\mathcal{L}}^{w*}$, which is typically very small relative to the full network. This is where the most substantial computational savings occur. At the second level, the block-diagonal reduction in the equilibrium sensitivity computation exploits sparsity in the aggregate active subnetwork $\tilde{\mathcal{L}}^* = \{ij : \sum_w q^w x_{ij}^{w*} > 0\}$. When the number of OD pairs is large and traffic analysis zones are fine, most links may carry positive aggregate flow, limiting the compression at this second level. In such cases, the primary efficiency gain would come from Algorithm (ref) together with the fact that the equilibrium sensitivity is obtained by solving a linear system rather than recomputing the full equilibrium.
In this section, we show several applications of the sensitivity analysis of traffic equilibrium using an example network. Specifically, we will show how the sensitivity information can be used for estimating optimal solutions subject to a shift in the design parameters, something which is often required for bilevel optimization problems. We will show how sensitivity information can assist in identifying important design parameters, for which small changes will lead to large changes in network performance. We will apply the sensitivity-based uncertainty analysis to quantify the impacts of model parameter uncertainty on uncertainty in performance predictions. Lastly, we use sensitivity analysis of PURC to illustrate that the PURC model can capture complementarity between paths. The latter is a counterexample to Proposition 3 in Fosgerau2021, and we point out the error in their proof.
We consider the example network in Figure (ref), which has 5 nodes and 8 directional links, as well as two origin-destination (OD) pairs $(1, 4)$, $(1, 5)$ with demands of 15 and 20, respectively. We assume the link costs to follow BPR link cost-time functions
where $t_{0,ij}$ are free-flow travel times, $\alpha=0.15$, $\beta=4$, and $\kappa_{ij}$ are link capacities, with numerical values specified in Table (ref). Unless otherwise specified, the perturbation function in this section is the entropy-based Eq. (ref).
Table (ref) reports the equilibrium link flows at these parameters. The equilibrium is computed using the algorithm presented in yao_perturbed_2024.
Table (ref) shows the sensitivity of equilibrium link flows $x^*$ with respect to link capacities $\kappa$ and Table (ref) shows the same with respect to free-flow travel times $t_{0}$. Both tables are calculated using Theorem (ref). We first note that the signs in the Jacobian are immediately plausible given the network structure. We also observe as a check that, for any $\kappa_{ij}$, $\forall ij \in \mathcal{L}$ (and similarly for $t_{0,ij}$), $\partial x^*_{25}(\kappa)/\partial \kappa_{ij} + \partial x^*_{35}(\kappa)/\partial \kappa_{ij} = \partial x^*_{24}(\kappa)/\partial \kappa_{ij} + \partial x^*_{34}(\kappa)/\partial \kappa_{ij} = 0$, which implies, as expected, that flow conservation holds.
A classical application of sensitivity analysis is to estimate the new optimal solution after a shift in the design parameters. This is useful since it can be much faster to compute the approximate new solution than to solve the model exactly. Such computation efficiency is critical for bilevel optimization problems yang1997traffic,josefsson2007sensitivity,liu2022inducing.
For illustration, we consider two scenarios: i) increase the capacity on link $(1, 2)$ by $5\%$; ii) increase the free-flow travel time on link $(1, 2)$ by $5\%$. Our goal is to compare the optimal link flows computed exactly, rerunning the traffic equilibrium problem, and approximated using the first-order Taylor series approximation
where $x^{*}(\theta +\epsilon_{\theta})$ denotes the optimal link flows subject to a shift $\epsilon_{\theta}$ in parameters $\theta$, and $\nabla x^*(\theta)$ is computed using Eq. (ref). The results in Table (ref) show that the approximate solutions are close to the exact solutions after a 5% shift in the two model parameters.
When model parameters are estimated with uncertainty, model predictions will also be uncertain. Sensitivity-based uncertainty analysis concerns how uncertainty in model parameters propagates to model predictions in terms of link flow patterns at equilibrium and to determine the confidence level of the model predictions. We adopt the classic approach yang2013sensitivity, du2022sensitivity for uncertainty analysis. Specifically, let us suppose now that the model parameters are a random vector $\Theta$ with mean $\mu_{\Theta}$ and covariance matrix $K_{\Theta}$, the expectation and covariance of the equilibrium link flows $X^*=x^*(\Theta)$ are approximated by:
We can then derive the covariance and correlation between equilibrium link flow $X^*$ and model parameters $\Theta$ by the multivariate delta method:
where $\text{diag}(\sigma_{X^*}), \text{diag(}\sigma_{\Theta})$ are diagonal matrix whose diagonal elements are standard deviations of $X^*$ and $\Theta$, respectively. This covariance and correlation information will provide insights into the importance of model parameters on model predictions, such as for selecting critical parameters.
For demonstration, we consider a similar experiment as in yang2013sensitivity. We assume that link capacities are distributed with mean $\mu_{\kappa}$ as specified in Table (ref) and coefficient of variation (CV) of 0.20. Table (ref) reports i) the mean equilibrium link flows, computed using Eq. (ref), ii) the standard deviation, which is the square root of the diagonal entries of Eq. (ref), and iii) the coefficient of variation, computed using the estimated mean and standard deviation.
We observe in Table (ref) that the CV of most links is smaller than that of the link capacities (0.20), while uncertainties on links $(1, 3), (2, 5)$ are relatively larger, potentially due to their larger free-flow travel times that scales up the variations.
In addition, we can estimate the correlation between equilibrium link flows and link capacities using Eq. (ref). As shown in Table (ref), link capacities are mostly correlated with the corresponding equilibrium link flows, i.e., diagonal values are larger than off-diagonal values in each column. We also observe that the capacity on link $(1, 2)$ has strong correlations with equilibrium link flows, compared to link capacities on other links. This implies that $\kappa_{12}$ could have significant impacts on equilibrium link flow patterns in the network.
The PURC model does not have error terms in the way that a classical discrete choice model in its random utility representation has random utility components. Therefore, talking about correlation in the PURC model is not immediately meaningful. Instead, we discuss the model in terms of substitution and complementarity, which is what we are concerned about. Specifically, we say that substitution occurs when a cost increase for an alternative causes the demand to increase for another alternative. In contrast, complementarity occurs when a cost increase for an alternative causes the demand to decrease for some other alternative. As we will show in this section, the PURC model allows paths to be complements. This is in contrast to the ARUM discrete choice model, in which alternatives can only be substitutes Fosgerau2013y.
It is clear that both substitutability and complementarity are at work when considering route choice at the level of network links: a cost increase on a link tends to reduce flow on nearby upstream and downstream links, while flow tends to increase on links on alternative paths. The situation is different when we consider substitution over paths. The path alternatives are necessarily substitutes in a classical discrete choice model, an additive random utility discrete choice model over paths. This fact follows from the properties of general additive random utility models Fosgerau2013y. In this paper, by applying our sensitivity analysis results, we will show via an example that complementarity among paths is possible in the PURC model in general.
To illustrate the substitution pattern of PURC, we consider a simple example network (Figure (ref)) with equal link lengths of 1, (flow-independent) link costs equal to link lengths, and a single OD pair $(1, 3)$. Suppose a positive flow vector $x^*$ such that all links are active, and that the perturbation function $F(x)$ takes the form of Eq. (ref).
Applying Theorem (ref), the Jacobian of $x^*$ with respect to the cost vector can be found to be the following matrix.
\[ \nabla_c x^* =
\]
By construction, this example network contains 4 paths, where path flows are equal to the flows on links $(23)$, $(24)$, $(54)$, and $(53)$, respectively. Consider the entries marked in bold, corresponding to $\frac{\partial x_{54}}{\partial c_{23}} $ and by symmetry to $\frac{\partial x_{23}}{\partial c_{54}}$. This is negative, which shows that paths $1\rightarrow{}2\rightarrow{}3$ and $1\rightarrow{}5\rightarrow{}4\rightarrow{}3$ are complements and not substitutes: the flow on the latter route decreases when the cost on link $23$ on the first route increases.
We take this opportunity to point out that this contradicts Proposition 3 in fosgerau_perturbed_2022, which erroneously stated that paths are necessarily substitutes in PURC. In the proof of that proposition, we rewrote the perturbation function $F$ defined in terms of link flows as a function $G$ defined in terms of path probabilities. We then claimed that $G$ is strictly convex. However, that is not generally true, since the decomposition of a flow into path flows is not unique.
In this section, we demonstrate the application of flow-dependent sensitivity analysis of the PURC model in a large-scale case, covering the Copenhagen Metropolitan Area using a network containing 30,773 links and 12,876 nodes. Each link $a$ has a BPR cost-time function (ref), with specific parameters. In fosgerau_perturbed_2022, we utilized a GPS dataset with 1,234,289 observed route choices to estimate the PURC model. We apply their Model C, which includes pace parameters (min/km) specific to link-types, a parameter for a dummy if links lead into intersections (i.e. the number of outlinks excluding u-turns is at least two), and uses the entropy link perturbation function from Eq. (ref). The parameter estimates are shown in Table (ref).
We scale the demands of the 8,046 OD-relations used in fosgerau_perturbed_2022 (stemming from the GPS observations) to the overall demand level in the case study area. Using these demands, the estimated route-choice parameters, and the BPR-based link cost-time functions defined for each network link, we calculate the network equilibrium flows. This is done by the approach introduced in yao_perturbed_2024, obtaining the resulting link flow vector $x^*$ for each OD-relation. Using this, we compute the Jacobian of the equilibrium link flows as follows. First, the per-OD flow sensitivities with respect to equilibrium costs are computed using (ref). This involves evaluating 8046 matrices of size $30773\times{}30773$. Then, the sensitivities of equilibrium costs with respect to parameters are computed using (ref). Finally, we compute the sensitivity of aggregate equilibrium link flows with respect to parameters using the chain rule (ref)-(ref).
To illustrate the precision of sensitivity analysis carried out using Theorem (ref), we consider a slight change in the free-flow travel time $t_0$ of a network link, and thus calculate the Jacobian with respect to this parameter. Computing the Jacobian takes 134 seconds, and with that, we can easily approximate the network-wide impacts of any small change in the free-flow travel time on any network link in virtually no additional time. In the following, we consider a scenario in which the free-flow travel time is increased by 10% in the southbound direction of Langebro, one of the four bridges connecting Zealand (northwest) to the island of Amager (southeast). The location of the bridge can be seen in Figures (ref) and (ref). The resulting link flows are approximated using (ref), where $\nabla x^*(\theta)$ is computed using Eq. (ref)-(ref) and $\epsilon_{\theta}$ is $0.1\cdot{}t_0$ on the southbound link on Langebro and 0 elsewhere.
To evaluate the approximation, we also compute the exact equilibrium solution for the scenario. This computation takes 52.6 minutes, which is about 24 times longer than when using the Jacobian from Theorem (ref). Figure (ref) compares the approximate changes in link flows computed using the Jacobian to the exact changes in link flows computed using the exact equilibrium solution. We observe that predictions are very close to the 45$^\circ$ line.
Figures (ref) and (ref) compare the absolute and relative changes in link flows using the approximate and exact calculations. As also suggested by Figure (ref), the differences are very small. Furthermore, the patterns look plausible: when the cost on the southbound direction of the Langebro bridge increases, flows on this and the main corridors leading to and from it decrease, while flows increase on the main alternatives, including other bridges connecting Zealand to the island of Amager. The largest change in flow is on the southbound direction of Langebro, where flow reduces by 193.65 and 192.05 vehicles in the approximate and exact computations, respectively.
In Table (ref), we compute the welfare measure (ref) using both the approximation and the exact equilibrium solutions, as well as for the baseline. The welfare measure for the baseline is computed as,
and so is the scenario computation using the exact equilibrium solution. The approximate welfare measure for the scenario is computed using equation (ref) and adding the welfare of the baseline. The relative difference between the welfare measures of the approximate and the exact methods is very small ($2.6 \times 10^{-6}$).
This paper contributes to the literature on route choice and network equilibrium by developing a sensitivity analysis framework for the perturbed utility route choice (PURC) model. By deriving closed‐form expressions for the Jacobian of optimal PURC flows with respect to link cost parameters, our analysis is not only useful for improving computational efficiency but also provides deeper insights into the substitution and complementarity patterns inherent in PURC. In contrast to traditional additive random utility models that yield only substitution effects, our results reveal that complementarity among routes may emerge in the PURC model.
Furthermore, the extension to flow-dependent cases allows us to estimate the changes in equilibrium link flows when network parameters are shifted. The numerical examples demonstrate how sensitivity measures can be used to predict changes in equilibrium flows and corresponding changes in welfare without resolving the entire traffic equilibrium problem, as well as to quantify the uncertainty in model prediction outputs resulting from uncertainties in, e.g., estimated link cost parameters. As our large-scale case study clearly demonstrates, this is also feasible for very large networks.
In sum, our framework offers a versatile tool for analyzing the response of travelers' routing decisions in the network to parameter shifts, thereby bridging a critical gap between theoretical modeling and empirical application. In ongoing research, we are using Theorem (ref) to develop a regression-based estimator for the PURC model that is applicable to individual-level data. This will widen the scope for application of the PURC model considerably, as it then becomes unnecessary to aggregate trips into observed origin-destination flows as was done in fosgerau_perturbed_2022. Moreover, individual-level estimation allows individual-level information, such as income, to be incorporated. Future research could also apply the proposed approach to real-world network design and pricing problems.