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.
69,917 characters · 15 sections · 41 citation commands
A perturbed utility route choice model
Keywords: Route choice; perturbed utility; discrete choice; networks
Big data that traces individual vehicles through complex traffic networks is now widely available. This opens new possibilities for estimating route choice models that better reflect actual behavior. However, route choice models face the curse of dimensionality, as the number of potential routes through a realistically sized network is extremely large.
{\color{black} This paper formulates a route choice model as an instance of a perturbed utility model. In a general perturbed utility model, a consumer chooses a consumption vector $x$ from some budget set $B$ that solves a utility maximization problem of the form $\hat x= \operatorname*{arg\,max}_{x \in B}(a^\intercal x - F(x))$, i.e. where the utility function is a linear function “perturbed” by subtracting a convex function McFadden2012, Fudenberg2015,Allen2019. Perturbed utility models are firmly rooted in modern microeconomic theory and can be interpreted as representing a population of agents whose individual behavior is described by one of a wide range of models, where the additive random utility discrete choice model is an example.\footnote{The choice probability vector $p(v)=(p_1(v),\ldots,p_J(v))$ with $v=(v_1,\ldots,v_J)$ of an additive random utility model with utilities $u_j=v_j+\epsilon_j$ can be found as the solution to the perturbed utility maximization problem $p(v) \in \operatorname*{arg\,max} (v^\intercal p - F(p))$, where $F$ is the convex conjugate of the surplus function; this result holds for any joint distribution of random residuals $\epsilon_j$ Sorensen2019.} Alternatively, a perturbed utility model can be interpreted at face value to represent the behavior of individual agents who randomize across options Allen2019.
We utilize this framework to formulate a new kind of route choice model. We consider a traveler, represented as choosing their network flow vector $x$ to maximize a certain perturbed utility function. The linear component of utility is the sum across links $e$ of link utility times individual link flow $x_e$. The convex perturbation is specified as a link-length weighted sum across the network links of positive and increasing convex functions $F(x_e)$, each of these being a function of the individual link flow. The perturbation terms induces the traveler to avoid concentrating their flow on few links. The network structure is incorporated through the budget constraint, which requires that flow is conserved at each node in the network. A final important point of the model setup is that we require that $F(0)=F'(0)=0$ while link utilities are negative (representing travel cost with the sign reversed). This has the consequence that link flows will be zero in parts of the network where the flow conservation constraint is not active.
In this paper, we formulate the model, analyze its properties, derive an estimator, and then apply the model to simulated and real data. We will show that the new model has a range of desirable properties. In particular, it allows all physically possible network flows; it predicts that many links are unused by any traveler, while no choice set generation is required. Furthermore, we will show that it implies realistic substitution patterns while being very fast to estimate.}
We use the first-order conditions for the traveler's perturbed utility maximization problem to formulate a linear regression equation, which allows the parameters of the route choice model to be estimated from observed data. We then present a transformation that eliminates the flow conservation constraint such that ordinary least squares (OLS) estimation is applicable. This is a major step forward, as the simplicity of linear regression allows realistic networks to be handled at low computational cost.
We add to a long line of research into route choice models. Early route choice models have relied on maximum likelihood estimation of an additive random utility discrete choice model McFadden1981 for the choice between alternative routes. However, the number of possible routes in a large network is extremely large, comparable to the number of atoms in the universe, even if loops are ruled out. Therefore, the main problem for these models is that the number of potential routes is prohibitively large. Much attention has been given to the generation of choice sets with good coverage to avoid bias resulting from excluding relevant alternatives Prato2009. Similarly, much attention has been given to finding models that lead to realistic substitution patterns when alternatives routes overlap more or less.\footnote{Prato2009 provides a review. {\color{black} More recent overviews of the literature may be found in Oyama2020 and Duncan2020.}} The perturbed utility route choice model (PURC) operates at the network level and does not require a choice set as input. On the contrary, the PURC model predicts which links are active, and the set of routes using these links can be thought of as a consideration set.
Another issue with additive random utility discrete choice models of route choice is that error terms are generally assumed to have full support such that every alternative is chosen with positive probability. This is neither necessarily realistic nor desirable in assignment, as most feasible routes in a large network are quite nonsensical Watling2015,Rasmussen2017,Watling2018. {\color{black} The bounded choice model (BCM) Watling2018 assigns zero probability to alternatives with a random utility that exceeds an exogenously defined upper bound\footnote{Routes are assigned probabilities based on the distribution of the random utility difference to an “imaginary” reference alternative. Probabilities of the routes relate to the odds of choosing each route versus the ’imaginary’ reference alternative. Setting the reference alternative as the route with the minimum generalized cost (maximum systematic utility) is a special case of the BCM, causing routes to only receive non-zero probabilities if their costs are within the bound of the cheapest route. See supplementary material of Duncan2021 for further details.}. Unlike the PURC model, the BCM requires path enumeration, as the distinction between used and unused alternatives is based on path costs. For large-scale applications with realistic values of the bound on random utility, BCM thus requires the enumeration of very large choice sets.}
A stream of research has considered recursive models in which the traveler is seen as choosing a path link by link in a Markovian fashion. Earlier papers considered the assignment problem Dial1971, Bell1995, Shen1996a, Baillon2008. A recent series of papers has considered estimation by maximum likelihood of what they term the recursive logit model {\color{black} and generalizations building on the multivariate extreme value distribution Fosgerau2013e, Mai2015, Mai2015a, Mai2016}. In contrast, estimation of the PURC model does not require computationally demanding maximization of a likelihood function. Whereas the basic recursive logit model has the independence of irrelevant alternatives (IIA) property at the route choice level, the PURC model predicts realistic substitution patterns that derive directly from the network structure. {\color{black} Various route choice models have been proposed that account for substitution patterns across alternatives. The path-size logit (PSL) route choice model Ben-Akiva1999PSL adjusts the systematic utility of an alternative based on the overlap with other alternatives in the choice set. Some variations of the PSL model are reviewed in Duncan2020. The adaptive path-size logit (APSL) model, proposed by Duncan2020, is internally consistent in the sense that the adjustment factors for overlap are calculated based on route choice probabilities. Recently, the integration of path-size concepts, including the APSL, into the BCM have been explored by Duncan2021. The challenge of path enumeration, however, still remains in these models. }
Oyama2020 cast the assignment problem for the network generalized extreme value model as a concave maximization problem of the perturbed utility form, where the perturbation function is a generalized entropy that incorporates the network structure. This is an instance of the general result that any additive random utility {\color{black} discrete choice} model can be represented as a perturbed utility model Hofbauer2002. In contrast to Oyama2020, we here consider estimation of the model parameters. Furthermore, we use a perturbation function that allows corner solutions, which avoids assigning positive probability to all routes that are physically possible.
We set up the model in Section (ref) and derive a linear regression equation that can be estimated by OLS regression. We find that the model implies that routes are substitutes and more so the more they overlap. In Section (ref), we illustrate the model's predictions using first a toy network and then a large-scale network covering the Copenhagen metropolitan area. In Section (ref), we demonstrate that true parameters can be recovered from realistic simulated data from a large network. We go on in Section (ref) to estimate the model using a large dataset of GPS traces for trips in the Copenhagen network. We validate the model's predictions against our data. Section (ref) concludes the study.
A network $(\mathcal{V},\mathcal{E})$ is defined by an incidence matrix $A$, which has a row for each vertex (node) $v\in\mathcal{V}$ and a column for each edge (link) $e\in\mathcal{E}$. As we are considering traffic networks, we will talk about links and nodes. The entries of $A$ are $a_{ve}=-1$ if edge/link $e$ leads out of vertex/node $v$, $a_{ve}=1$ if link $e$ leads into node $v$, and $a_{ve}=0$ otherwise.
A traveler has unit demand given by the vector $b$, which is a column vector across nodes with $-1$ at the origin node, $1$ at the destination node, and zeros otherwise. There is a traveler for each demand vector $b$. We suppress the dependence on $b$ in the notation.
{\color{black} The traveler is viewed as solving the constrained utility maximization problem
where the constraint ensures that flow is conserved at each node in the network. This assumption may be interpreted as saying that if we observe many individual travelers with a given demand $b$, then their combined network flow vector $x$ is the solution to the problem (ref).
The utility function $U$ is specified using the perturbed utility form McFadden2012, Fudenberg2015,Allen2019, consisting of a linear term minus a convex perturbation term.\footnote{\color{black} Subtracting a convex function rather than adding a concave function follows the convention of convex analysis Rockafellar1970.} We specify the utility function as a weighted sum over links weighted by the length of each link as follows.
We will first explain the linear term $l^\intercal\left( u\circ x\right)$. The vector $u=(u_e)_{e\in \mathcal{E}}$ has a component for each link that expresses the utility rate --- that is, the utility per distance unit --- of using that link. We assume that all components of $u$ are negative. Vector $l=(l_e)_{e\in \mathcal{E}}$ comprises the link lengths. The vector $u \circ x = (u_e x_e)_{e\in \mathcal{E}}$ is the component-wise product of the vector of link utility rates and the flow vector. Hence, the term $l^\intercal\left( u\circ x\right)$ is the sum across links of the utility rate multiplied by link flow and by link length.
The second term, the perturbation, is the sum across links, weighted by link length, of the function $F$ applied component-wise to the flow vector, that is, $F(x)=(F(x_e))_{e\in \mathcal{E}}$. We make the following assumption concerning $F$.
The perturbation $F(x_e)$ corresponding to each link is zero and flat at zero flow, which, together with the condition that link utilities are negative, ensures that the optimal flow on any link is zero if the flow conservation constraint is not active there. The combined perturbation $l^\intercal F(x)$ is strictly convex, as it is a linear combination of strictly convex terms. The presence of the combined perturbation term makes the utility function (ref) strictly concave, which ensures a unique solution to the utility maximization problem.
The perturbation term becomes large and negative if much flow is concentrated on a link. This induces the traveler to distribute their flow across more links. In this way, the perturbation term works in much the same way as a congestion term would work, but with the crucial difference that the perturbation is part of the traveler's preferences and depends not on the behavior of other travelers but only on the individual flow vector $x$.
We also note that the utility function (ref) is a sum across links of independent terms. The flow conservation constraint creates dependencies whereby changes in utilities on some links induces substitution with flow on other links. }
All terms in utility function (ref) are weighted by link length, which makes the model invariant to link splitting. Consider a link $e$ with a contribution to the utility that is $l_e u_e x_e - l_e F( x_e)$, and split that link into two links $e_1,e_2$ with $l_e = l_{e_1}+l_{e_2}$, $x_e=x_{e_1}=x_{e_2}$, and $u_e=u_{e_1}=u_{e_2}$. Then, \[l_e u_e x_e - l_e F(x_e) = l_{e_1} u_{e_1} x_{e_1} - l_{e_1} F(x_{e_1} ) +l_{e_2} u_{e_2} x_{e_2} - l_{e_2} F(x_{e_2} ). \] In other words, the utility contribution of the whole link is equal to the sum of the contributions of the two parts. This is a desirable model feature, as it makes the predictions of the model invariant with respect to the introduction of dummy nodes.
The utility rate vector $u$ is specified as a linear function $u=z\beta$ of link characteristics organized in a matrix $z$ and parameters organized in a column vector $\beta$ to be estimated. {\color{black} Which link characteristics to include in $z$ depends on the specific application. In our empirical application in Section (ref), we use number of outlinks (divided by link length), travel time per kilometer (i.e., pace), and link type dummies.}
Even though the utility function (ref) does not comprise an explicit representation of heterogeneity, it may still be interpreted as representing an underlying heterogeneous population of travelers {\color{black} Allen2019, in the same way as the choice probabilities of some additive random utility discrete choice model represent an underlying population of agents with heterogeneous random utility residual terms. }
{\color{black} We solve the traveler's problem (ref) by setting up the corresponding Lagrangian
\[ \Lambda \left( x,\lambda \right) =l^{\intercal }\left( u\circ x\right) -l^{\intercal }F\left( x\right) +\lambda ^{\intercal }\left( Ax-b\right), \] } where $\lambda \in \mathbb{R}^{|\mathcal{V}|}$ is a vector of Lagrange multipliers, one for each node in the network, corresponding to the flow conservation constraints. For each link $e$, $x_{e}$ is either zero or the partial derivative of the Lagrangian with respect to $x_{e}$ is zero. Altogether, we have the first-order conditions
where hats denote the optimal values of $x$ and $\lambda$.
{\color{black} We can interpret the first-order conditions, noting that for each active link, the marginal utility rate equals the marginal perturbation, that is, $u_e=F'(\hat x_e)$}, except for the effect induced by the flow conservation constraint.
Let $B$ be a matrix that is an $|\mathcal{E}|$-dimensional identity matrix, except (at least) all rows corresponding to edges with zero flows are omitted. Pre-multiplying the first-order conditions by $B$, we can disregard links with zero flows (and possibly more), obtaining
{\color{black}
}
{\color{black} We allow that $B$ omits also rows corresponding to some positive flows. We mention this as it may be useful in future applications where there is concern over sampling noise owing to small vehicle counts on some links. We have not made use of this possibility in the results presented in this paper.}
Equation (ref) can be used to formulate a regression model. For each origin--destination (OD) pair, the corresponding traveler's problem leads to vectors $( \hat x,\hat \lambda)$, where the elements of {\color{black} $B (l \circ F'(\hat x))$ }can be used as dependent variables.
Noting that \[B(l\circ u) = B(l\circ z\beta) = B(l\circ z) \beta, \] the matrix $B(l\circ z)$ can act as independent variables with corresponding parameter vector $\beta$. The Lagrange multipliers $\hat \lambda$ can be treated as fixed effects, that can be corrected for in the regression. That is, however, computationally challenging, as the size of $\hat \lambda$ is equal to the number of nodes in the network and the vector is specific to each OD combination. The number of fixed effects may therefore become very large as the size of the network and the number of OD combinations increases. We will therefore seek an alternative regression equation that eliminates $\hat \lambda$ {\color{black} from (ref)}.
{\color{black} For eliminating $\hat \lambda$ from (ref), we have to take into account that the matrix $BA^{\intercal }$ is not invertible. Let }$C=\left( BA^{\intercal }\right) ^{\ast }$ be a Moore--Penrose inverse of $BA^{\intercal }$. We may then utilize that $BA^{\intercal }CBA^{\intercal }=BA^{\intercal }$. Multiplying the traveler's reduced first-order condition (ref) by $BA^{\intercal }C$, we find that {\color{black}
which leads to \[ BA^{\intercal }\lambda =BA^{\intercal }CB\left( l\circ \left( F'(\hat x) -u\right) \right). \]} Substituting this back into the reduced first-order condition (ref), we find that {\color{black}
which leads to
} We have thus managed to eliminate the Lagrange multipliers from the first-order condition.
Given a flow vector $\hat x$ corresponding to demand $b$, we now use (ref) to motivate the construction of a vector {\color{black} $y=( I-BA^{\intercal }C) B( l\circ F'(\hat x) )$} and a matrix $w =\left( I-BA^{\intercal }C\right) B\left( l\circ z\right)$ with the aim of estimating the parameters of the model by regression.
Doing this for each demand vector $b$, we construct pairs $(y_{bi},w_{bi})$, where $b\in\mathcal{B}$ indexes the set of demand vectors and $i$ indexes the elements of each vector $y_b$.
Adding mean zero noise terms $\epsilon_{bi}$, we see that parameters $\beta$ can be recovered from the regression
We assume the noise terms to be independent of the variables in $w_{bi}$, but allow them to be heteroscedastic, which leads us to use robust standard errors when running regressions.
The computational complexity of the regression is independent of the number of route choice observations constituting the flow vector $\hat{x}$ for each $b$, and only increases linearly with the size of the set of demand vectors $\mathcal{B}$, as the computationally most demanding task is obtaining the Moore-Penrose inverse $C$ for each $b$.\footnote{We used the IMqrginv function in Matlab Ataei2014, which required less than 0.06 seconds per OD combination. It is probably possible to utilize sparsity to speed this up.}
The perturbed utility route choice model is formulated in terms of links, which we have seen is useful for estimation and avoids the need to enumerate the set of available routes. Proposition (ref){, established in this section, }shows that the model can (in principle) equivalently be formulated in terms of routes. {\color{black} Formulating the model in terms of routes would be impossible in practice, as all routes would have to be enumerated. However, this} perspective allows some understanding to be gained of the model's properties.
The proposition shows that the equivalent model is a perturbed utility discrete choice model over the universal set of loop-free routes in which the routes are substitutes. An important driver of this result is that loops are ruled out by utility maximization.
{\color{black} Why is it important to note that routes are substitutes? Most discrete choice models used in transportation are additive random utility models McFadden1974a, McFadden1981. A feature of these models is that alternatives are always substitutes in the sense that increasing the utility of one alternative (weakly) decreases the probability that any other alternative is chosen. This property does not, however, hold in general for all discrete choice models and, in particular, it does not hold in general for perturbed utility discrete choice models Allen2019b. Depending on the specification of the convex perturbation function, these models can allow alternatives to be complements such that increasing the utility of one alternative increases the probability that another alternative is chosen. This is important in practice, as there are many situations in which alternatives are complements. In a supermarket, we may think of products that are often consumed together (such as salsa and nachos). In route choice, many complementarities occur at the level of links. It is therefore quite informative and important for the understanding of the present model to establish that it predicts that routes are substitutes.}
The proof of Proposition (ref) shows that the perturbed utility model has an equivalent formulation as a perturbed utility model (ref) for the choice among all loop-free routes connecting origin to destination. The convex perturbation $G$ is a length-weighted sum across links of terms that are the convex function $F$ applied to each link flow. The flow on link $e$ is the sum of route choice probabilities for routes using that link, $\tsum\limits_{\sigma \ni e}p_{\sigma }$. The presence of such sums in the utility function generates a tendency for substitutability. In fact, if there was only one such term $F\left(\tsum\limits_{\sigma \ni e}p_{\sigma }\right)$, then routes using link $e$ would be perfect substitutes. {\color{black} We explore the model's predicted substitution patterns in Section (ref) below.}
{ \color{black}
The shape of the perturbation function matters for the pattern of substitution across links with different flows. To see this, consider how the optimal flow vector is affected by a change in the utility of some active link. The first-order condition (ref) involves the derivatives $F'(\hat x_e)$, which are increasing in link flows. Hence, smaller changes in link flows are required to adjust the first-order condition on links where the flow is high than on links where the flow is low. The size of the difference is determined by the degree of convexity of the perturbation function.
To apply the perturbed utility model, we need to impose a specific form on the perturbation function while respecting Assumption (ref). Taking inspiration from the well-known connection between the multinomial logit (MNL) model and the Shannon entropy Hofbauer2002, we use the form of the entropy function, modified to satisfy the requirements of Assumption (ref), and define
where $F'(x) = \ln(1+x)$ and $F''(x)=(1+x)^{-1}$, such that $F'(0)=0$ and $F''(x)>0$ for $x>0$ as required. In our empirical application in Section (ref), we also tested a quadratic perturbation $F(x)=x^2$, but found that the entropy-like function (ref) led to a better fit. }
In this section, we investigate the behavior of the model by solving the traveler's problem, first on a small toy network and then on a large network for the Copenhagen metropolitan area.
Consider a toy network with six links and four loop-free routes from origin to destination; see Figure (ref). One route uses link 1 with length $l_1=2$, which goes straight from the origin to the destination. Two routes share link 2 with length $l_2=1$ and then split into links 3 and 4, each also with length $l_3=l_4=1$. The fourth route uses link 6 with length $l_6=2$ that also directly connects the origin to the destination. To test the ability of the perturbed utility model to handle {\color{black} the possibility of loops}, we add link 5 that is equal to link 2 but goes in the opposite direction, such that it is consistent with flow conservation to have flow looping on links 2 and 5. The unit link utility rate is $u_e=-1$ on all links except link 6, on which $u_6=-2$. This causes three of the four direct routes to have the same total disutility, and the alternative using link 6 to be twice as costly.
The base case utility maximizing flows for the PURC model are shown in Table (ref). We have also included flows for a corresponding MNL model McFadden1974a and a PSL model Ben-Akiva1999PSL.\footnote{ {\color{black} Parameters for the MNL and PSL models were calibrated against PURC flow. As link 6 was unused in the base network for the PURC, the calibration was performed on a slightly modified network with $u_6=-1.25$, causing link 6 to be used for all models. The direct utilities of alternative $n$ for the MNL and PSL models were defined as $V_n = \beta_u U_n$ and $V_n = \beta_u U_n + \beta_\text{PS} \ln S_n$, respectively, where $U_n = \sum\limits_{e \in n} l_e u_e$, and $S_n$ was defined as in Ben-Akiva1999PSL based on link lengths. In both cases, the probability of choosing an alternative $n$ within the choice set $\mathcal{C}$ was given by $P_n = \frac{e^{V_n}}{\sum\limits_{k \in \mathcal{C}} e^{V_k}}$. Setting $\beta_u=1$ for the PURC model and d}isallowing loops for the MNL and PSL models, the parameters found to reduce the sum of square errors across the link flows for the MNL and PSL models were $\beta_u = 2.0$ and $\beta_\text{PS} = 1.1$, respectively. } We note that the PURC model assigns zero flow on link 5; hence, utility maximization causes the loop to not occur even though it is (physically) possible in the model. In contrast, the MNL and PSL models rely on generated choice sets for which we omitted paths with loops. {\color{black} We note also that the PURC model assigns zero flow on the costly link 6, which demonstrates that the model is in fact able to assign zero flow.} In contrast, the MNL and PSL models both assign a positive flow because the route using link 6 is included in the choice set.
\footnotetext{Zero flow is purely a consequence of the choice set generation method.}
We consider two experiments. In the first, we increase the unit cost on link 4 by 0.1. In all three models, this leads to a decrease in the flow on the route using link 4. In the PURC model, the flow on the route using link 3 increases more in relative terms than the flow on link 1. Thus, the IIA property does not hold for the PURC model: the routes using links 3 and 4 are closer substitutes with each other than with the route using link 1. This is a desirable property, which occurs because the two close routes share link 2. In contrast, in the MNL and PSL models, the flow on the routes using links 1, 3, and 6 increase by the same proportion, in accordance with the IIA property.
In the second experiment, we reduce the lengths of links 2 and 5 by 0.5 and increase the lengths of links 3 and 4 by the same amount. This makes the routes using link 2 more dissimilar and hence attracts more flow to them in the PURC model. The limiting cases of this kind of change are as desired: the utility maximizing flows split evenly on the three routes if link 2 is reduced to zero length, and the utility maximizing flows split fifty-fifty if the length of link 2 is increased to 2. In other words, as the two routes overlap less, they function as more independent routes. In contrast, the change in link lengths leads to no change in flows in the MNL model. The PSL model reacts similarly to the PURC model in this case.
{\color{black} We summarize the points in the comparison of the PURC model to the MNL and PSL models in the following table. The comparison speaks clearly in favor of the PURC model.
}
We proceed to illustrate how the perturbed utility model behaves on a large network. We use a network, shown in Figure (ref), for the Copenhagen metropolitan area, comprising 30,773 links and 12,876 nodes Kjems2019.
Figure (ref) shows the model's prediction for a trip from the airport (located South-East on the figure) to the Technical University of Denmark (North). For the example, we specified the link utility as a parameter $\beta$ multiplied by {\color{black} pace (defined as travel time in minutes per kilometer)} and used different values of $\beta$. We solved the traveler's problem using MatLab MATLAB2010 with the fmincon command using an interior point algorithm Byrd1999,Waltz2006 approach for constrained optimization.
Note that most links in the network are inactive, having zero predicted flow. {\color{black} This is in line with Rasmussen2017, who also demonstrated many unused links, but using a model requiring path enumeration.} As in Proposition (ref), the active links and predicted flows can be translated into a set of active routes with corresponding route choice probabilities.
The model predicts two clear main alternatives. One is the Western motorway bypass across Kalvebod bridge (Kalvebodbroen), and the other is a cluster of alternatives going through the Copenhagen city center.
{\color{black} The optimal flow balances the incentive to reduce travel time, determined by the size of $\beta$, against the incentive to distribute flow across more links in the network, determined by the perturbation $F$. As Figure (ref) illustrates, the incentive to distribute flow matters relatively more; hence, the number of active routes is high when $\beta$ is numerically small. As $\beta$ increases numerically, the incentive to reduce travel time receives more weight and hence link usage approaches the shortest (fastest) path. In particular, the use of the cluster of alternatives through the city center is reduced when $\beta$ becomes numerically larger.}
Figure (ref) shows the change in predicted flows that follows an increase {\color{black} of two minutes in the travel time on Kalvebodbroen in the southern part of the map}. This change increases the cost on all routes that use Kalvebodbroen and consequently flow shifts toward alternative routes. Routes that share links with routes that use Kalvebodbroen are {\color{black} seen to be }closer substitutes, which confirms the theoretical expectation.
{\color{black} Before we proceed to estimate the PURC model on real data, it is useful to explore what precision and bias we might expect. In this section, we therefore test the ability of the estimator to recover a known true parameter from data simulated from the model using the Copenhagen metropolitan area network. We can then assess the quality of the parameter estimates, depending on the size of the dataset. }
We pre-select 22 nodes {\color{black} spread across the model area} that are used as origins/destinations. Sampling from these, we generate a number of datasets using a different number of OD combinations (1, 5, 20, and 100) and different values of a parameter for {\color{black} pace (minutes per kilometer) } ($\beta\in\{-3,-2.5,\ldots,-0.5\}$). For each OD and $\beta$, we solve the traveler's problem and sampled a number of {\color{black} trips }consistent with the predicted link flows. {\color{black} Each sampled trip is a random walk between the origin and destination nodes, with link selection probabilities at each node that are proportional to the predicted link flows.} This mimics actual data collection but in a case where the true model is known. We have created datasets sampling, respectively, 25, 100, 250, and 1000 {\color{black} trips }for each OD.
{\color{black} Figure (ref) shows cumulative distributions of some summary statistics of the flows underlying the simulation --- that is, the predicted flows found when using the true parameters. Panel (a) shows how the number of active links increases as the {\color{black} parameter $\beta$ for pace} approaches zero and the influence of travel time diminishes. Panel (b) shows that, as expected, a numerically smaller {\color{black} parameter for pace } increases the average predicted travel time.
}
Altogether, we have created $4\times 4 \times 6 = 96$ datasets. For each dataset, {\color{black} treating it as if it were a real dataset of observed route choices}, we have computed a flow vector $x$ for each origin-destination. We have then transformed the data as described in Section (ref) and estimated $\beta$ using ordinary least squares (OLS).
We have used all observations for all links with positive flow without applying any truncation. This might have led to bias as the function $\ln (1+x)$ that transforms the flows is nonlinear and the flows are estimated with considerable noise. As the results in Figure (ref) show, we find no visible bias when the number of origin-destinations and the number of route choices are sufficiently large. It seems plausible that the reason we do not find any noticeable bias is that the logarithm $\ln(1+x)$ is close to linear for small values of $x$.
Altogether, the results are encouraging. We find that it is possible to recover the true parameter from a sample of routes with good precision. The estimates seem to be biased toward zero, when the dataset is small, but the bias is negligible at moderate dataset sizes.
{\color{black} Our empirical application is based on GPS vehicle trajectory data for the Copenhagen metropolitan area. As described in Appendix (ref), we obtain an estimation dataset comprising 8,046 OD combinations and 1,337,096 trips. There are 166.2 trips per OD relation and 153.4 active links on average per OD relation, such that the transformed dataset corresponding to eq. (ref) has 1,234,289 observations. }
To explain the observed route choices, {\color{black} we specify the utility rate using average observed pace (in minutes per kilometer) for each link},\footnote{A total of 9,464,883 trips were used for determining the empirical average link {\color{black} paces}.} the number of outlinks, and dummies for road type. Table (ref) reports the estimation results for three different model specifications. Numbers in parentheses are robust standard errors. As can be seen, all parameters are very precisely estimated. {\color{black} This precision is reassuring, but unsurprising given the large number of observations entering the regression. }
{\color{black} Model A has the simplest specification of the utility rate, with just a term for pace. Comparison with the simulations in Figure (ref) suggests that the range is reasonable. }
In model B, we extend with a constant for each link having at least two outlinks. This penalizes links that lead into intersections. The {\color{black} pace} parameter is reduced in absolute value, as expected. {\color{black} The adjusted R-square increases by 0.006, indicating preference for model B over model A.}
In model C, we interact the {\color{black} pace} variable with link type dummies to estimate {\color{black} pace} parameters that are specific to each link type. The sign and relative sizes of these parameters make intuitive sense. {\color{black} The adjusted R-square increases now by 0.04 relative to model B, indicating preference for model C over model B. }
{\color{black} $R^2$ values around $0.4$ are quite satisfactory considering that we are dealing with cross-sectional data, transformed as described in Section (ref). We present further validation of model C in Section (ref) below. }
{\color{black} We have estimated the same models using $F(x)=x^2$ instead of the modified entropy formulation (ref). The fit was better with the modified entropy formulation in all three cases.
}
We go on to validate the prediction of model C against our data. For each OD combination in the data, we compute the predicted flow vector using the estimated parameters. We compare this prediction to the estimation dataset to ascertain the ability of the model to reproduce these data. The main text shows validation results using the full sample. We have a large dataset and a model with few parameters, so the results are not likely to be very vulnerable to over-fitting. However, we test out-of-sample predictions in Appendix (ref), where we have split the data at random by OD combination into two equal-sized datasets. We have estimated the model for each sample split and applied each set of estimated parameters to make predictions for the other half of the sample. The parameter estimates for the two sample splits found in Appendix (ref) are very similar and the out-of-sample prediction test did not reveal any issues.
Figure (ref) shows the main validation result, comparing observed link flows to the predicted flows. {\color{black} For each link, the observed link flow is the number of observed vehicles on that link in the observation dataset across all OD combinations, whereas the predicted link flows are found by multiplying the number of observed trips for each OD combination with the corresponding predicted link flow for a representative traveler for that particular OD combination before summing across all OD combinations. We observe that predictions are generally close to the $45^\circ$ line. A nonparametric fit with 95% confidence bands suggests some systematic deviations. The adjusted $R^2$ between the observed and predicted link flows is 0.9356.\footnote{Defined as $R^2_\text{adj}= 1 - \left( 1-\dfrac{\sum_{i=1}^N \left( \hat{x}_i - x_i \right)^2}{\sum_{i=1}^N\left(x_i - \bar{x}\right)^2} \right) \frac{1-N}{1-p-N}$, with $x_i, i = 1, 2, ..., N$ being the observed link flows, $\hat{x}_i, i = 1, 2, ..., N$ being the predicted link flows, $\bar{x}= \sum_{i=1}^N x_i$ being the mean of the $N = 30,772$ observed link flows, and $p=9$ being the number of estimated parameters.} We do find the fit to be very satisfactory, as we have employed no calibration: the predictions are driven solely by the nine estimated parameters in Table (ref). Our general conclusion is that the model is able to meaningfully predict the observed flows.}
Figures (ref) and (ref) visualize the comparison between predicted and observed flows on a map of the network. Blue links are well predicted, the model predicts too much traffic on red links and too little on green links compared with the observed flows. We observe that the main road network is generally blue on the figure, whereas red links tend to be minor roads. We find this result to be quite {\color{black} reasonable}, indicating {\color{black} again} that the estimated model is able to predict a large share of the variation in the observed link flows.
An issue that has troubled modeling approaches that rely on a predefined consideration set is that the observed routes may not be covered by the consideration set. In contrast, the perturbed utility route choice model takes all potential routes into account and predicts a set of active links. {\color{black} The model predicts 12,133 unused links with a total length of 4,253 km. The observed data comprises 12,063 unused links with a total length of 4,719 km. The overlap between the two sets of unused links is 79%, showing that the vast majority of the unused links is correctly predicted.}
{\color{black} In addition, we analyze how well the predicted sets of active links, one set for each OD combination, cover the chosen routes.} Figure (ref) shows the cumulative distribution of the proportion of utility of the chosen routes that is outside the predicted set of active links. Hence, a value of zero is perfect and small values are good. We find that about 85% of the observed trips are completely inside the predicted set of active links, and almost all observed trips have less than 20% of utility outside the predicted set of active links.
This paper has opened the door to a new way to model route choice. The perturbed utility route choice model can be estimated using just linear regression, {\color{black} it requires no choice set generation, }it is straightforward to use for assignment, and it produces reasonable substitution patterns. We have estimated and applied the model to a large dataset covering the Copenhagen metropolitan area and found that the model is able to predict much of the variation in observed flows, thereby demonstrating the feasibility of applying the model in practice.
We do not claim to have found the perfect model. However, we do hope to have convinced the readers that the perturbed utility route choice model is a worthwhile alternative to previous existing approaches. There are many ways to go forward from here.
We have ignored sampling error in the observation of flows. Our simulations suggest that this is not a problem when the number of observations is sufficiently large. Further work might incorporate weighting to reflect the number of observations used for estimating flows. It would also be of interest to be able to estimate the model with individual-level data, perhaps adapting the iteratively reweighted least squares algorithm of Nielsen2021. {\color{black} This might be relevant when using the perturbed utility route choice model with smaller datasets, where sampling error might be a more prominent issue.}
We have worked with a static and deterministic network. It might be possible to adapt the perturbed utility route choice model to more complex settings.
{\color{black} An interesting question is the shape of the perturbation function. There is considerable freedom within the requirement imposed on $F$, and there are many other options in addition to the two we have tested. The effect of using other perturbation functions remains an open issue.}
Another direction that could be explored is to add cross-link interactions as a means to control the substitution patterns of the model. One way to go might be along the lines of the nested recursive logit model Mai2015.
Finally, we note that our model seems to fit well into the equilibrium assignment in Oyama2020. This research direction also seems appealing.