A tutorial on recursive models for analyzing and predicting path choice behavior

Zimmermann, Maëlle; Frejinger, Emma Article A tutorial on recursive models for analyzing and predicting path choice behavior EURO Journal on Transportation and Logistics (EJTL) Provided in Cooperation with: Association of European Operational Research Societies (EURO), Fribourg Suggested Citation: Zimmermann, Maëlle; Frejinger, Emma (2020) : A tutorial on recursive models for analyzing and predicting path choice behavior, EURO Journal on Transportation and Logistics (EJTL), ISSN 2192-4384, Elsevier, Amsterdam, Vol. 9, Iss. 2, pp. 1-12, https://doi.org/10.1016/j.ejtl.2020.100004 This Version is available at: https://hdl.handle.net/10419/325131 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc-nd/4.0/ A tutorial on recursive models for analyzing and predicting path choice behavior Ma€ elle Zimmermann * , Emma Frejinger Department of Computer Science and Operations Research, Universit e de Montr eal, QC, Canada ARTICLE INFO Keywords: Path choice models Recursive discrete choice models Inverse optimization Inverse reinforcement learning ABSTRACT The problem at the heart of this tutorial consists in modeling the path choice behavior of network users. This problem has been extensively studied in transportation science, where it is known as the route choice problem. In this literature, individuals’choice of paths are typically predicted using discrete choice models. This article is a tutorial on a specific category of discrete choice models called recursive, and it makes three main contributions: First, for the purpose of assisting future research on route choice, we provide a comprehensive background on the problem, linking it to different fields including inverse optimization and inverse reinforcement learning. Second, we formally introduce the problem and the recursive modeling idea along with an overview of existing models, their properties and applications. Third, we extensively analyze illustrative examples from different angles so that a novice reader can gain intuition on the problem and the advantages provided by recursive models in comparison to path-based ones. 1. Introduction Road traffic, while essential to the proper functioning of a city, generates a number of nuisances, including pollution, noise, delays and accidents. It is the role of city managers, network administrators and urban planners to attempt to mitigate the negative impact of transportation by planning adequate infrastructure and policies. Most of the trafficis generated by individual travelers who seek to minimize their own travel costs without guidance from a system maximizing the overall welfare. It is thus a necessity to understand how users of the transportation system behave and choose their path in the network in order to provide planners with decision-aid tools to manage it. This is the main motivation for the introduction of what is known in the transport demand modeling literature as the route choice problem, which seeks to predict and explain travelers’path choices in a network. The path choice models we attend to are based on the assumption that individuals behave rationally by minimizing a certain cost function or, equivalently, maximizing a certain utility function. This function can depend on network attributes and possibly socio-economic characteristics of the travelers. The models’aim is to identify this cost function from a set of observed trajectories (revealed preferences data), which allows to predict chosen paths for all origin-destination (OD) pairs. All models in this tutorial are based on the assumption that network attributes are deterministic (static or dynamic). We refer the reader to, e.g., Gao et al. (2010) for the case of stochastic attributes. Path choice predictions are rarely useful on their own. Rather, path choice models are used in combination with information about aggregate demand given by an OD matrix. The latter states the number of travelers who wish to travel between each OD pair in a given time interval. The problem of computing trafficflows given an OD matrix, constant travel times and a path choice model is called stochastic traffic assignment. In fact, the key idea behind recursive path choice models –avoiding explicit path enumeration –originates from the traffic assignment model in Dial (1971). In turn, the resulting trafficflows are a central component in a number of problems with broad applicability. A prominent example is the computation of equilibrium flows when travel times are given as a function of flow (see, e.g., Bell, 1995;Huang and Bell, 1998;Akamatsu, 1996;Baillon and Cominetti, 2008, for recursive formulations). Traffic flows are also crucial to network design problems (Magnanti and Wong, 1984) and bilevel optimization formulations thereof (e.g., Brotcorne et al., 2008;Gilbert et al., 2015). The literature on each of these problems is rich, and a detailed description is out of the scope of this tutorial that is entirely devoted to disaggregate recursive path choice models. With the aforementioned problems in mind, it is desirable that path choice models satisfy several properties, such as (i) scaling with the size of large urban networks in order to be efficiently used for real networks, * Corresponding author. E-mail address: [email protected] (M. Zimmermann). Contents lists available at ScienceDirect EURO Journal on Transportation and Logistics journal homepage: www.journals.elsevier.com/euro-journal-on-transportation-and-logistics https://doi.org/10.1016/j.ejtl.2020.100004 2192-4376/©2020 Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). EURO Journal on Transportation and Logistics 9 (2020) 100004 i An update to this article is included at the end (ii) lending themselves well to behavioral interpretation, in order to, e.g., assess travelers’value of time, and (iii) yielding accurate predictions under different network scenarios. In the transportation demand literature, the most common methodology is a probabilistic approach known as discrete choice modeling, which finds its origin in econometrics. It views path choice as a particular demand modeling problem, where the alternatives of the decision maker are the paths in the network. The principal issue with this modeling approach stems from the fact that the set of feasible paths in a real network cannot be enumerated, and we do not observe which paths are actually considered by individuals. As a result, discrete choice models based on paths currently used in the transportation literature may suffer from biased estimates and inaccurate predictions, as well as potentially long computational times. This work is a tutorial on a modeling framework which in comparison meets the previously enumerated expectations. Recursive route choice models draw their efficiency from modeling the path choice problem as a parametric Markov decision process (MDP) and resorting to dynamic programming to solve its embedded shortest path problem. This tutorial is addressed to both transportation demand researchers who are unfamiliar with recursive models as well as researchers and practitioners who wish to gain understanding of the route choice problem and how it can be modelled. For this reason, we do not assume from the reader knowledge in discrete choice modeling and instead provide a new and comprehensive background on the route choice problem (which for generality purposes we denote path choice from here on). Rather than presenting recursive models in their entirety, we aim at deepening their conceptual understanding, in particular i) their link to inverse shortest path and inverse reinforcement learning problems, ii) their advantages over the most well-known approach in the transportation demand literature, i.e., discrete choice models based on paths, iii) guidance related to their applicability to large-scale problems. This tutorial is essentially divided into three parts. The first gives an extensive background on the problem it addresses and makes important connections to other fields in Section 2. We contextualize discrete choice models as a probabilistic approach for what is in fact an inverse shortest path problem with noisy data. The second part, in Section 3, formally introduces path-based and recursive route choice models and provides a review of the different recursive model types with references to technical papers. It also provides a review of existing applications supplied by guidance on scaling the models to larger networks. The third part consists of illustrative examples for educational purposes: Section 4provides a comparison of two simple recursive and path-based discrete choice models on toy networks for the illustration of basic concepts and properties for the uninitiated reader. Section 5discusses in depth the issues related to estimation and prediction and demonstrates the advantages of recursive models through practical examples and discussions. Finally, Section 6provides an outlook and concludes. 2. Context: from shortest paths problems to path choice models In this section, we frame the path choice problem as that of unveiling an unknown cost function from noisy shortest paths observations, which is an inverse optimization problem where the forward (inner) problem is a shortest path. We give some background on the literature on inverse optimization and we situate the problem this tutorial addresses within this context. We illustrate that there is a close connection between stochastic shortest path problems and the inverse problem with noisy data we are interested in. For the sake of clarity we start this section by introducing deterministic and stochastic shortest path problems before describing the related inverse problems. 2.1. Shortest path problems Throughout this section, we consider a simple oriented graph Gwith a set of nodes Vand a set of arcs A¼fði;jÞji;j2Vg. We denote vthe nodes in Vand athe arcs in A, which are characterized by a source node iaand a tail node ja. Arcs ði;jÞhave an associated cost cij given by a function c:A→R. A path is a sequence of arcs such that the head node of each arc is the tail node of the next. 2.1.1. The deterministic shortest path problem The deterministic shortest path problem (DSP) in the graph Gis concerned with finding the path with minimum cost between an origin node and a destination node, where the cost of a path is defined by the sum of its arc costs. More often, methods developed in the literature are designed to solve the shortest path problem between a given origin and all possible destinations, or a given destination and all possible origins. This combinatorial optimization problem has been amply studied in the literature. Its chief difficulty is the existence of a very large number of feasible paths between each node pair, which precludes proceeding by naive enumeration. The problem could be formulated and solved as a linear program, however more efficient algorithms have been developed, relying on dynamic programming (DP). In general, DP is a methodology to solve optimization problems in dynamic (often discrete time) systems, where a decision (denoted action or control) must be taken in each state in order to minimize future additive costs over a certain time horizon (finite or infinite). The shortest path problem in the graph Gcan be formulated as a DP problem by considering nodes as states and an arc choice as an action taken in a given state. The Bellman principle of optimality at the core of deterministic problems states that for an optimal sequence of choices (in this case, arcs along the shortest path), each subsequence is also be optimal. This allows to decompose the problem and formulate a recursive expression for the optimal arc choice at node ias well as the cost CðiÞof the shortest path from ito destination node d, CðiÞ¼(0;i¼d min j2Vþ icij þCðjÞ;8i6¼ d;i2V(1) where Vþ i¼fj2Vjði;jÞ2Ag. Solving (1) is however not straightforward in cyclic graphs. In this case, note that the problem is well-defined only when there are no negative cost cycles, otherwise there would be paths of cost ∞. Under this assumption, the shortest path in Gcontains at most jVj1 arcs. Bellman (1958) shows how to solve the shortest path problem by backwards induction as a deterministic finite state finite horizon optimal control problem. The DP algorithm is (CNðiÞ¼cid;8i2V d CnðiÞ¼ min j2Vþ icij þCnþ1ðjÞ;8i2V;n¼1;…;N1(2) where V i¼fh2Vjðh;iÞ2Ag, and N¼jVj1 is the length of the horizon. The value CnðiÞrepresents the cost of the shortest path from ito dusing at most Nnþ1 arcs, and in this sense is an upper bound on the cost of the shortest path. The cost of the shortest path from icorresponds to C1ðiÞ. Note that the value of the shortest paths can also be found by label correction algorithms (see, e.g., Dijkstra, 1959;Floyd, 1962). 2.1.2. The stochastic shortest path problem The stochastic shortest path problem (SSP), as defined by Bertsekas and Tsitsiklis (1991), is an extension of the previous problem which considers a discrete time dynamic system where a decision must be taken in each state and causes the system to move stochastically to a new state according to a transition probability distribution. This problem can be analyzed using the framework of Markovian Decision Processes (MDP), formally defined as: –A set of states Sand a set of available actions AðsÞfor each state s2S. –The cost cs;a;s’incurred by taking action ain state sand moving to next state s’. –pðs’js;aÞthe transition probability from sto s’when taking action a. M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 2 An MDP models problems where an action must be taken in each state, with the aim to minimize expected future discounted costs over a certain horizon. The SSP is a special case of MDP with infinite horizon, no discounting and a cost-free absorbing state d, where pðdjd;aÞ¼18a. The SSP is an infinite horizon problem since there is no upper limit on the number of arcs traversed. However, by assumption the absorbing state can be reached with probability 1 in finite time. The optimal solution of the SSP is not a path but a policy, which consists in a probability distribution over all possible actions in each state. When the optimal policy is followed, the path which is actually travelled is random but has minimum expected cost. This stochastic problem can be solved with DP and the recursion which defines the optimal expected cost VðsÞfrom any given state sis given by the Bellman equation VðsÞ¼ min a2AðsÞ"cs;aþX s’ pðs’js;aÞVðs’Þ#;(3) where cs;a¼P s’ pðs’js;aÞcs;a;s’.VðsÞis also known as the value function. Note that the DSP is a particular degenerate case of the SSP where states sare nodes iof the graph G, action costs are arc costs cij and state transition probabilities are deterministic, since the next state is always equal to the chosen successor node. Therefore, it is in fact a deterministic MDP. This definition of SSPs provided by Bertsekas and Tsitsiklis (1991) is very general. It also encompasses variants of shortest paths problems on random graphs (see, e.g., Polychronopoulos and Tsitsiklis, 1996), where arc costs are modelled as random variables ~ cij ¼cij þ ε ij, with cij the average arc cost and ε ij a random error term. Arguably the most interesting variation of the problem is the one where the realization of the arc costs is learned at each intersection as the graph is traversed. Below, we make the additional assumption that ε ij are i.i.d. variables. In this case, by defining an action aas an arc ði;jÞand a state sas a network node iand a vector eiof learned realizations eij of the error term for all outgoing arcs from i, (3) becomes Vði;eiÞ¼ min j2Vþ icij þeij þZVj;ejfdej;(4) where transitions between states are entirely contained by the density fðejÞ. This specific SSP will be of importance in Section 3.2. 2.2. Inverse shortest path problems In shortest path problems it is assumed that the modeler has complete knowledge of the cost function cor its distribution in the previous case, as well as state transitions p. In contrast, inverse shortest path problems study the case where the cost function is unknown and must be inferred with the help of an additional source of information at disposal, in the form of observed optimal paths between some origin-destination (OD) pairs. This class of problems broadly belongs to inverse optimization, an extensively studied problem (see e.g. Ahuja and Orlin, 2001) where the modeler seeks to infer the objective function (and sometimes the constraints) of a forward (inner) optimization problem based on a sample of optimal solutions. Motivation for studying inverse problems can be drawn from several types of applications. Burton and Toint (1992) cites possible motivations to examine inverse shortest path problems, one of which is precisely the subject of this tutorial. One may view the underlying optimization problem as a model for rational human decision making and assume that the cost function represents the preferences of users traveling in a network (possibly a parametrized function of certain arc features). In this context, recovering the cost function allows to analyze why individuals choose the observed routes and to gain understanding of network users’ behavior. Using the recovered cost function, the inner shortest path problem can be solved and in this sense yield predictions of path choices for unobserved OD pairs. Related to inverse shortest path problems is the literature on inverse reinforcement learning (IRL) or imitation learning (Ng and Russell, 2000; Abbeel and Ng, 2004). The IRL problem is more general than the inverse shortest path, since it considers an underlying optimization problem generally formulated as a infinite horizon MDP. In this context, observations consist of optimal sequences of actions. Nevertheless, models for IRL have also been applied to the problem of recovering the cost function of network users (e.g. Ziebart et al., 2008). Such applications consider specific MDPs where an action is a choice of arc in a network, and the destination is an absorbing state, as in Section 2.1.2. Most applications of IRL on path choice however consider a deterministic MDP (state transitions probabilities are degenerate) in contrast to the more general formulation in Section 2.1.2. Inverse problems are in general under-determined and may not possess a unique solution. In the inverse shortest path problem and in IRL, there may be an infinite number of ways to define the cost function such that observations form optimal solutions. Different modeling paradigms propose to solve this issue. They may be separated in two categories depending on the assumptions made on the presence of noise in the data, which distinguishes between deterministic and stochastic problems. The former consider that demonstrated behavior is optimal, while the latter make the hypothesis that observed trajectories deviate from deterministic shortest paths. The second case is often studied when the data collecting process may have induced measurement errors or when the data is generated by a decision maker who exhibits seemingly inconsistent behavior. In the following sections, we review existing models for the above mentioned inverse problems. 2.2.1. Deterministic problems Burton and Toint (1992) introduced the original deterministic inverse shortest path problem where observed trajectories are assumed to correspond to deterministic shortest paths. They do not assume that the cost function is parametrized by arc features and simply seek the value cij associated to each arc ði;jÞ. They propose to provide uniqueness to the inverse problem by seeking the arc costs cthat are closest to a given estimation bcof costs based on a certain measure of distance, thus minimizing an objective of the form jjcbcjj. This implies that the modeler has an a priori knowledge of costs, which is reasonable in some applications. Burton and Toint (1992) provide seismic tomography as an example. Seismic waves are known to propagate according to the shortest path along the Earth’s crust, but the geological structure of the zone of study is typically not entirely known, although modelers have an estimate. Given measurements of earthquakes’arrival times at different points in the “network”, the goal is then to predict movements of future earthquakes by recovering the actual transmission times of seismic waves. Variants of this problem have been studied by Burton and Toint (1994);Burton et al. (1997), for instance considering the case where arcs costs may be correlated or their values belong to a certain range. In Burton and Toint (1992) and following works, the l2norm is selected as a distance measure between initial and modified costs, and yields a quadratic programming formulation. In Zhang et al. (1995), the l1norm is assumed so that the problem can be modelled as a linear program and solved using column generation. In all the studies above, the inverse shortest past problem is modelled as a constrained optimization problem, with an exponential number of linear constraints to ensure that each observed path is shortest under the chosen cost function. B€ armann et al. (2017) provide another example of approach for inverse optimization with an application to learning the travel costs of network users, in particular subject to budget constraints. More precisely, they consider an inverse resource-constrained shortest path problem. Their approach does not recover an exact cost function, but provides a sequence of cost functions ðc1;…;cTÞcorresponding to each observation t¼1;…;T, which allows to replicate demonstrated behavior. Their M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 3 framework explicitly assumes the optimality of observations in order to infer the objective functions ct. The deterministic problem has also notably been studied under the guise of inverse reinforcement learning in Ratliff et al. (2006), with an application to robot path planning. The objective of their work is to learn a cost function in order to teach a robot to imitate observed trajectories, which are assumed optimal. In contrast to the aforementioned works, no hypothesis is made regarding preliminary arc costs. However, the environment is considered to be described by features, such as elevation, slope or presence of vegetation, and the model seeks to obtain a mapping from features to costs by learning the weights associated to each feature. To obtain uniqueness of the solution, they cast the problem as one of maximum margin planning, i.e. choosing the parameters of the cost function that makes observed trajectories better by a certain margin than any other path, while minimizing the norm of weights. This notion of distance between solutions is defined by a loss function to be determined by the modeler. Under the l2norm, this also results in a quadratic programming formulation with a number of constraints that depend on the number of state-action pairs, which consist of node-arc pairs in this context. 2.2.2. Stochastic problems Inverse optimization problems with noisy data have been studied in, e.g., Aswani et al. (2018) or Chan et al. (2018). In addition to non-uniqueness, the problem which typically arises in this situation is that there may not be any non trivial value of arc costs which makes the demonstrated paths optimal solutions of a DSP. If solutions do exist, they may be uninformative, such as the zero cost function. To solve this issue, the previous framework is extended by letting solutions be approximately optimal and measuring the amount of error. Thus accommodating noise requires to estimate a model for the choice of path which “fits”as closely as possible the observed data with various methods for measuring the fit, or loss, drawing from statistics. The chosen measure for the fit should uniquely define the solution. Different points of views exist on achieving a good fit in the literature. Approaches grounded in machine learning make no assumptions on the underlying process that generated the data and merely focus on obtaining good predictive power with the simplest possible model while considering a large family of potential functions. In contrast, the statistical inference perspective on the problem considers that there exists an underlying true cost function with a known parametric form. The aim is to obtain parameter estimates that asymptotically converge to the real values, a property known as consistency. Several loss functions are conceivable to formulate a minimization problem, and often the choice of loss is directly related to assumptions made on the underlying model. Examples for the former are the work of Keshavarz et al. (2011), who estimate cost functions in a flow network assuming an affine parametric shape, and the work of Bertsimas et al. (2015), who seek to infer cost functions in a network subject to congestion at equilibrium. The specificity of the latter is that the cost functions are endogenous, i.e., the cost of paths include congestion costs. This makes it an inverse variational inequality problem with noisy data. In both works the proposed method is a heuristic and treats the process that generates the data as a black box. For example, in Bertsimas et al. (2015), nonparametric cost functions are considered and the problem is formulated as a constraint programming model which balances the objective of minimizing the norm of the cost function with that of maximizing the fit of the data. They follow the approach of measuring the loss of the model by the amount of slack required to accommodate equilibrium constraints, i.e., making observed solutions “ ε -optimal”. In contrast, the latter category of models assume that observed behavior deviates randomly from optimality according to a certain known probability distribution. This leads to a different modeling paradigm, in which a random term is added to the true cost function of the inner optimization problem, with the interpretation that each observation corresponds to an instantiation of the cost. This framework, described in, e.g., Nielsen and Jensen (2004) for general inverse problems, has received limited attention in the literature on inverse shortest path problems. One notable exception consists in path choice models based on the discrete choice modeling framework. In the next section, we review the literature surrounding this probabilistic modeling framework, which is at the heart of this tutorial. 3. Probabilistic models for path choice Individuals traveling in real networks is a typical situation where the assumption that a cost function can account for all observed behavior is rarely valid. Probabilistic models for this inverse problem with noisy data assume that observed path choices randomly deviate from deterministic shortest paths. In particular, discrete choice models are a particular type of probabilistic models grounded in econometrics, which provides the theoretical basis for behavioral interpretation. One of the interpretations of the distributional assumption on the data is that travelers act rationally but observe additional factors impacting their path choice which vary among individuals and are unknown to the modeler. These factors are encompassed in a random term ε added to the cost function. Discrete choice models are based on the assumption that the cost function is a parametrized function of attributes. The only option available to the modeler, who knows the family of distributions for ε but does not observe the realization of random terms for a given individual, is to infer the probability that a given path is optimal from data. The problem becomes akin to density estimation, i.e., recovering the parameters of a probability distribution over a set of paths. In this context, statistical consistency of the estimator is a desirable property. Yet there are several ways to define a probability distribution over paths, well-known in the discrete choice literature, which do not necessarily yield a consistent estimator. In the following sections, we elaborate on the above statement and describe two distinct categories of discrete choice models for path choice. Note that discrete choice models employ the terminology of utilities instead of costs and that we uphold this convention in the remainder of this tutorial. This implies a trivial change of the above formulations from minimization to maximization problems and the definition of a utility function v¼c. 3.1. Path-based models Discrete choice models based on paths are the methodology embraced by most works on the topic (e.g., Prato, 2009;Frejinger, 2008). They assume that the utility of a path iis a random variable ui¼viþ με i, where ε iis a random error term, μ is its scale, and the deterministic utility viis parametrized by attributes of the network, such as travel time. Often the parametrization consists of a linear-in-parameters formulation vi¼βTxi, where βis a vector of parameters and xiis a vector of attribute variables of the path i. The parameter values are inferred from observed path choices f σ ngn¼1;…;Nthrough maximum likelihood estimation, as we further detail below. A key difficulty in specifying the probability of a given path is to identify the set of paths over which this probability should be defined. Since the very large number of feasible paths in a real network precludes enumeration, the immediate solution consists in choosing a subset of reasonable paths, assuming that all other paths have a null choice probability. This implies a two-step modeling framework (Manski, 1977): the probability of choosing path σ nis Pð σ nÞ¼ P Cn2Gn Pð σ njCnÞPðCnjGnÞwhere Cnis a choice set of paths and Gnis the set of all non-empty subsets of the set of all feasible paths. This expression hence involves an exponential sum that is impossible to evaluate in a path choice context as there is already an exponential number of feasible paths. Therefore, most path-based models ignore the sum and consider M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 4 one unique subset of path Cnfor each n, i.e., assuming that Pð σ nÞ¼ Pð σ njCnÞ. The models are defined and estimated in the following manner: 1 Plausible paths are generated between the origin and destination of each observation nby solving versions of the DSP, forming the choice set Cn(a vast array of methods exist and we refer to Bekhor et al. (2006) for an overview); 2. Parameters bβthat maximize the probability Pð σ njCn;βÞof observed paths within the choice set previously defined are estimated via maximum likelihood, i.e., by maximizing LLðβÞdefined as LLðβÞ¼log X N n¼1 Pð σ njCn;βÞ:(5) The distribution chosen for ε ileads to different types of discrete choice models. The most well-known is the multinomial logit formulation, resulting from the assumption of i.i.d. Extreme value type I distributed error terms, also known as the softmax in the machine learning community Pð σ njCn;βÞ¼ e1 μ v σ nðβÞ Pj2Cne1 μ vjnðβÞ:(6) Many other models exist, such as the link-nested logit, mixed logit and probit models (Vovsha and Bekhor, 1998;Yai et al., 1997;Frejinger and Bierlaire, 2007). The first step in the two-step approach may be viewed as deterministic or stochastic sampling of alternatives, depending on the algorithm. Problematically, the costs used for the DSP do in general not correspond to the utilities which are ultimately sought. This discrepancy is what prevents the consistency of the resulting estimates. However, if the utilities are adequately corrected to account for the sampling protocol, then the estimator is still consistent (McFadden, 1978). Frejinger et al. (2009) propose this idea for path choice modeling and delineate a method that corrects the path choice probabilities for the probability PðCnj σ nÞthat the given choice set was selected conditionally on the observed choice. The method proposed by Frejinger et al. (2009) can be understood as assuming that the true distribution is based on the set consisting of all feasible paths, while resorting to sampling paths in order to estimate the parameters of the distribution in practice. While the sampling correction allows to consistently estimate path-based models, it is still unclear how to use them for prediction. Designing a sampling correction in this context is an open problem. We further discuss this issue in Section 5.2. Arguably, since these issues arise from the exponential number of feasible paths, one may expect that DP could provide a solution for the inverse problem as well. The literature on IRL supplies such an example with Ziebart et al. (2008), who model the path choice problem as a MDP and estimate a probabilistic model which normalizes over the global set of feasible paths. This is achieved without enumeration nor sampling by viewing the path choice process as a sequence of action choices depending on a current state as in Section 2.1.2. In fact, this methodology is similar to recursive discrete choice models, which have been proposed independently and in parallel in the transportation research community. We introduce this modeling framework in the following section, which provides a method to consistently estimate parameters of the utility function without resorting to the two-step modeling approach with choice sets of paths. 3.2. Recursive models In this section, we introduce recursive models for the problem of path choice within the discrete choice modeling framework. We first present the initial model proposed by Fosgerau et al. (2013), before reviewing its subsequent extensions. We also discuss the link to the IRL model by Ziebart et al. (2008). 3.2.1. Path choice as a deterministic MDP Contrary to the previous section in which the problem is formulated in the high dimensional space of paths, recursive models consider arcbased variables. Their formulation is based on the framework of MDP used to solve shortest path problems in Section 2.1. In recursive models, network arcs correspond to states, while outgoing links at the head node of the current arc assume the role of available actions. For this purpose, we subsequently denote arcs as either kor adepending on whether they play the role of states or actions. Note that it would also be possible to select nodes as states, however, the arcbased formulation allows the deterministic utility vðajkÞof an actionstate pair to depend on turn angles between two subsequent arcs kand a. The destination is represented by a dummy link dwhich is an absorbing state of the MDP, where no additional utility is gained. Finally, utilities are undiscounted and the action-state transition function is assumed to be degenerate, since the new state is simply the chosen arc. A path under this framework is a sequence of states fk0;k1;…;kTg, starting from an origin state k0and leading to the absorbing state kTrepresenting the destination d. 3.2.2. Estimation of the parametric MDP Under this perspective, the inverse problem of recovering the utility function is a problem of parametric estimation of MDPs, as first described by Rust (1994). As in the previous section, the noise in the data is accounted for by assuming the presence of a random error term ε a, added to the utility vðajkÞ. The utility becomes a random variable uðajkÞ¼ vðajkÞþ με a, where μ is the scale of the error term. It is assumed that the individual observes the realizations of the random variables at each step of the process and chooses the best action accordingly. From the point of view of the modeler, the individual’s behavior hence consists in solving a stochastic shortest path problem similarly to Section 2.1.2. In this context, the Bellman equation gives the optimal value function when the state consists of an arc kand realizations ea2AðkÞof ε a2AðkÞ, Vdðk;eaÞ¼(0;k¼d; max a2AðkÞvðajkÞþ μ eaþZVdða;ea’Þfðdea’Þ;8k2A; (7) which is very similar to (4). We may however simplify this equation by taking the expectation with respect to ε aof (7) and defining the expected value function VdðkÞ¼RVdðk;eaÞfðdeaÞof a state k, which gives VdðkÞ¼0;k¼d; E ε max a2AðkÞvðajkÞþ με aþVdðaÞ;8k2A:(8) For simplicity and consistency with terminology in other works (e.g., Fosgerau et al., 2013;Mai et al., 2015), we nevertheless refer to (8) as the value function in this work. The modeler does not observe the realized utilities and can only compute the probability that each given action is optimal. According to the modeler, the observed behavior of individuals follows a probability distribution over the set of actions which maximizes the expected utility in (8). As in Section 3.1, choice probabilities may take several forms depending on the distributional assumption for the error terms ε a. When the modeler assumes that they are i.i.d. Extreme value type I, the model is known as the recursive logit (RL) model (Fosgerau et al., 2013). In Section 3.2.3, we provide an overview of existing models that relax the i.i.d. assumption. Under the RL model, the probability of an individual choosing a certain action aconditional on the state kand the destination dis given by the familiar multinomial logit formula: Pdðajk;βÞ¼ e1 μ vðajk;βÞþVdðajβÞ Pa’2AðkÞe1 μ vða’jk;βÞþVdða’jβÞ:(9) Given observations of sequences of actions (i.e., paths), the model can M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 5 be estimated by maximum likelihood. This requires to define the probability of choosing an observed path, which can be expressed as the product of the corresponding action choice probabilities using (9). For an observed path σ n¼fk0;k1;…;kTg, the path choice probability is given by P σ njβÞ¼Y T1 j¼0 Pdkjþ1kj;β!;(10) where dis the link kT, which can more simply be expressed as Pð σ njβÞ¼e1 μ vð σ njβÞ e1 μ Vðk0jβÞ(11) where vð σ njβÞis the sum of the link utilities of the path σ n. As a result, the likelihood of a set of Npath observations f σ ngn¼1;…;Nis defined as LðβÞ¼ Y N n¼1 P σ njβÞ¼ Y N n¼1Y Tn1 i¼0 Pdkn iþ1kn i;β!:(12) The expression in (12) does not depend on choice sets, in contrast to (5). However, the value function which appears in (9) must be computed in order to evaluate the likelihood. This suggests resorting to a two-step likelihood maximization algorithm, in which an inner loop solves the SSP and obtains the value function in (8) for the current value of parameters β, while an outer loop searches over the parameter space. Rust (1994) propose such a method, denoted the nested fixed point (NFXP) algorithm. The resulting parameter estimates are consistent. We note that alternative estimators to the nested fixed point algorithm exist, but have not yet been used in the context of path choice modeling (see, e.g., Aguirregabiria and Mira, 2010;Su and Judd, 2012). The model for IRL proposed in Ziebart et al. (2008) bears another name but is equivalent to the RL model, since they assume a maximum entropy (exponential family) distribution. The difference lies in the method for estimating the model, as Ziebart et al. (2008) approximate the value function in (8), whereas Fosgerau et al. (2013);Mai et al. (2016) show that they can be conveniently solved as a system of linear equations without approximation. We provide an illustration of the latter on small examples in Section 4. 3.2.3. Existing recursive models and their applications Path choice modelling entails two key challenges. First, the definition of the choice sets, or more precisely, the support for the choice probability distribution. Second, given the network structure, paths likely share unobserved attributes which lead to correlated random terms. It has been shown that accounting for this correlation is crucial to achieve accurate predictions and interpretation of parameter estimates. The RL model addresses the first challenge but not the second as the random terms are assumed to be i.i.d. This section is devoted to recursive models that have been designed to relax this assumption and hence address also the second challenge. We provide an overview of their properties and related applications. For a more in-depth description of each model, we refer to the corresponding articles. In the context of recursive models it is important to note that changing the distributional assumption of the random terms ε a, changes the expression of the value functions (8). When one relaxes the i.i.d. Extreme Value Type I assumption, the value functions are solutions to non-linear systems instead of linear ones, which are harder to solve. As the computation of the value functions constitutes the inner loop of the nested fixed point algorithm, even a slight increase in the computing time might lead to an important increase in the overall computing time associated with estimating the model parameters. The estimation also depends on the outer non-linear optimization algorithm. There are many possible algorithms that can be used for this purpose. As the estimation typically is done offline (i.e., the models are not re-estimated during prediction) high computing times may be acceptable, of course, within reasonable limits. Nevertheless, computing the value functions as fast as possible to a good accuracy is also crucial for prediction. We report in Table 1 a list of existing models. For each model we provide a reference to the article where it is introduced, we state whether the choice probabilities have a closed form (CF) or not, and if the model allows utilities to be correlated (Corr) or not. Moreover, we report in the second last column how the value functions were computed and the nonlinear optimization algorithm that was used in each of the articles. A key point is the ability to model correlated utilities. In this regard, more modeling flexibility results in higher computational time as a trade-off. The cross-nested (RCNL) model is more flexible than the nested (NRL) but the computation of the value functions is more complex. The mixed RL (MRL) can, in theory, approximate any correlation structure but requires a computationally intensive simulation approach. Some methods are available to reduce the computational burden associated with more complex models. For example, the time required to estimate the MRL is reduced by a decomposition method (DeC, introduced in Mai et al., 2016) and the use of common random numbers. The DeC method allows to solve one system of linear equations for all destinations in the case of RL, which results in an important speed up. In order to solve value functions which are solutions to non-linear systems, it is necessary to resort to value iteration methods that are widely applicable but can be slow to converge. This is why several works use a warm start (an initialisation using a RL solution computed by solving systems of linear equations) and dynamic accuracy. The latter means that the solutions are only computed with a high accuracy close to the maximum likelihood estimates. Next we turn our attention to the applications of these models on real networks, in order to show how the computation time increases for larger network sizes and to present the available methods to deal with largescale challenges. In Table 2 we summarize a number of articles reporting the type of application, the number of links in the graph (i.e., number of states of the MDP), the model, the number of estimated parameters as well as the reported computing times. We note that one has to be careful when analyzing these computing times as they depend on the data (in particular size of the dataset), choice of algorithms, their implementation as well as hardware. We report them to give an indication on the orders of magnitude. Arguably, it would have been more informative to present Table 1 Information on existing recursive route choice models. Model Reference CF a Corr b Value functions Opt c Recursive logit (RL) Fosgerau et al. (2013) Y N Linear system of equations (decomposition) BFGS Maximum entropy IRL Ziebart et al. (2008) YN VI d inspired algorithm NR f Nested recursive logit (NRL) Mai et al. (2015) Y Y Warm-started VI d and dynamic accuracy BFGS Mixed recursive logit (MRL) Mai et al. (2016) N Y Decomposition, common random numbers BFGS Recursive crossnested logit (RCNL) Mai (2016) Y Y Warm-started VI d and dynamic accuracy BFGS Random regretbased recursive logit (RRM-RL) Mai et al. (2017) Y Y Linear system of equations IP e Discounted recursive logit (DRL) Oyama and Hato (2017) YN VI d NR f a Closed-form probability. b Correlated utilities. c Precision on non-linear optimization algorithm. d Value iteration (method of successive approximations). e Interior point method. f Not reported in the article. M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 6 the computing time at the level of value functions (averages and the distribution over the destinations for each network). These values are however not reported across the different studies and there are even studies not mentioning computing times at all. The reported figures show clearly that the computing times are considerably longer for models that account for correlated utilities (compare for example, for the same data, the RL and NRL in the bike route choice application by Zimmermann et al., 2017). On the other hand when the utilities are discounted (Oyama and Hato, 2017), the utility interpretation changes but the model has nice properties as the value iteration converges faster and to a unique solution (contraction mapping). Computing times depend not only on the type of model being applied, but also on the type of graph and estimation method. Acyclic graphs, such as time-expanded networks, are advantageous for the computation of value functions, as they can be solved quickly by backwards induction (a process we illustrate in Section 4), resulting in gains of time for both estimation and prediction. In terms of estimation method, sampling of alternatives represents a possible substitute when the nested fixed point algorithm is too costly. Although this method was initially designed for path-based models in Frejinger et al. (2009), it can also be applied to some recursive models and possesses several additional advantages in this case. Compared to the NFXP, sampling of alternative obtains large gains in estimation time, but importantly, it remains possible to predict path choices using the estimated link choice probabilities without generating choice sets. Zimmermann et al. (2018a) provide an example of the application of sampling of alternatives to estimate the parameters of a MRL model on the largest graph in terms of size in Table 2. Note that sampling of alternatives yields unbiased estimates when used in conjunction with RL and MRL models, however these results have not yet been extended to more complex recursive models. Another aspect to consider in order to use recursive models in practice are requirements in terms of utility specification. Recursive models need link-additive utilities, which can be challenging to specify when inherently non-additive attributes, such as the slope of a road, are likely to have an impact on path choice. We note that Zimmermann et al. (2017) deals with such challenges in the context of a bike route choice application. In some applications, it may also be desirable to include socio-economic characteristics of individuals in the utility specification, as in Zimmermann et al. (2018b). It is important to note that in this case, value functions need to be solved not only for each destination, but also for each category of individuals defined in the utilities. 4. Illustrative examples Section 3presented two families of discrete choice models for the problem of estimating the utility function of travelers in a network: pathbased models and recursive models. Although the former is extensively used in practice, the latter is superior because of its consistent estimator and accurate predictions without choice set generation. This section is addressed to readers who are new to the topic and provides small illustrative examples on toy networks with two purposes in mind. First, we provide an intuitive understanding of the value function in recursive models. Second, we compare path probabilities obtained with both model formulations in order to highlight a key property of recursive models, namely, that the recursive logit model is equivalent to a path-based logit over the complete set of possible paths. Although both models can take several forms depending on distributional assumptions on the error terms, the focus of these illustrative examples is on the logit model. In the following, we refer to the recursive logit as the RL model and the path-based logit as the PL model. Note that the MATLAB code used for these numerical examples is available online, as well as a tutorial detailing how to use it. 1 4.1. An acyclic network The motivation for this example is to show that it is possible to obtain with the recursive formulation in (9) the same choice probabilities on paths as with the PL model in (6). For this illustrative purpose, it is meaningful to consider a given specification of the utility function. Hence we assume that path utilities are specified by an additive function of arc length La, such that for each path iwe have vi¼Li, where Liis the sum of the lengths of arcs contained in path i. The OD pair considered for the toy network displayed in Fig. 1 is ð1;4Þ. The two dashed arcs represent dummy origin and destination links. There exists 4 possible paths from node 1 to node 4, of respective length 2, 3, 4 and 6. Under the logit model, it is easy to compute the choice probability of the shortest path for this OD pair, which goes directly from node 1 to node 4 with length 2. Assuming that the scale μ of the random term for this example is 1, we obtain at the denominator of the logit function in (6) the term e2, and at the numerator the term e2þ e3þe4þe6, therefore the choice probability is equal to 0.6572. Table 3 displays similarly the choice probability of all other paths. Let us now suppose that instead of choosing between the possible Table 2 Overview of applications of recursive route choice models. Reference Application Acyclic Nb links Model Nb param. Est. time [h] Ziebart et al. (2008) Taxi route choice N 300,000 IRL NR a NR a Zimmermann et al. (2017) Bike route choice N 42,384 RL 14 1 NRL 15 336 de Freitas et al. (2019) Multimodal route choice N 127,873 RL 12 96 Zimmermann et al. (2018b) Activity choice Y millions MRL 48 3 Nassir et al. (2018) Transit route choice N NR a RL 7 NR a Oyama and Hato (2017) Car route choice N 2724 DRL 3 0.08 Mai et al. (2015) Car route choice N 7459 NRL 7 30 Mai (2016) Car route choice N 7459 RCNL 8 72 Mai et al. (2016) Car route choice N 7459 MRL 5–10 72–120 a Not reported in the article. Fig. 1. Small network. 1 http://intermodal.iro.umontreal.ca/software.html. M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 7 paths connecting origin and destination, the traveler builds the chosen path along the way through a series of consecutive link choices, as in the RL formulation. In each link choice situation, the alternatives to choose from are the outgoing links at the current node. We denote vðajkÞ¼La the utility of links a2AðkÞoriginating from link k. The choice probability of a path under the RL model is then equal to the product of each link choice probability in (9). In order to compute link choice probabilities, we need to compute the value function in (7). This equation can be rewritten as the logsum when ε ais assumed to be i.i.d. Extreme value type I distributed as in the logit model: VdðkÞ¼8 > > < > > : μ ln X a2AðkÞ e1 μ ðvðajkÞþVdðaÞÞ ;8k2A 0;k¼d: (13) Since the specified utility of a link does not depend on the incoming arc, the value function is identical for all links with the same end node. It is thus more convenient to compute the value function at each of the 4 nodes (the value function at a link is then equivalent to the value function at the end node of that link). Below, we show how to compute the value function in this network and display the value for each node. In this case, since the network is acyclic, it is possible to compute the value function by backwards induction. At the destination node 4, given that there is no utility to be gained, the value function Vð4Þis zero. Working our way backwards, we compute at node 3 the value function Vð3Þ¼lne1:5¼1:5. At node 2, we have Vð2Þ¼lnðe2þe3Þ¼ 1:6867. Finally, at node 1 we obtain Vð1Þ¼lnðe6þe2þe1:6867Þ¼ 1:5803. The values for all nodes are summarized in Table 4. Having computed the value function for this network, we may apply (9) to this example and we obtain the path probabilities in the last column of Table 3. We notice that they are identical to choice probabilities under the PL model. This is due to the property of the RL model of being formally equivalent to a discrete choice model over the full choice set of paths (Fosgerau et al., 2013). Therefore, the PL and the RL models are two strictly equivalent approaches when the set of all possible paths in the network can be enumerated. 4.2. A cyclic network Let us now consider a very similar network in Fig. 2, with an added link between nodes 3 and 1. This network is no longer acyclic, and as a result there is in theory an infinite number of paths between nodes 1 and 4, when accounting for paths with loops. The first consequence of dealing with a cyclic network is that the value function can no longer be computed by backwards induction starting from destination, since the network admits no topological order. However, the value function is still well defined as the solution of the fixed point problem (7) and can be solved either by value iteration or, in the case of the recursive logit, as the solution of a system of linear equations. For the latter, notice that by taking the exponential of (13) and raising to the power 1 μ , we obtain e1 μ VdðkÞ¼8 > > < > > :X a2AðkÞ δðajkÞe1 μ ðvðajkÞþVdðaÞÞ8k2A 1k¼d: (14) This is a linear system of equations if we solve for variable z¼e1 μ V. Doing so, we obtain the value function in Table 5. As in the previous example, having solved the value function, we can trivially compute the choice probabilities for different paths in this network as product of link choice probabilities. As can be observed, the probabilities of the four paths used in the acyclic example do not sum to 1 anymore (rather to 0.9698), and neither do the probabilities of the additional paths displayed in Table 6, which sum to 0.9965. This is because a cyclic network contains an infinite number of possible paths, and the RL model attributes a positive choice probability to each outgoing arc at an intersection. Hence, even paths with multiple cycles have a small probability of being chosen. We notice however that choosing a path with two or more cycles is extremely unlikely, with a probability of 0.0009 according to the model. This example illustrates that the RL model offers a convenient mathematical formulation for the choice of path in a cyclic network. In comparison, using the PL model for this network raise a well-known Table 3 Path choice probabilities under both models. Path Length Path probability (PL) Product of link probabilities (RL) 14 2 0.6572 0.6572 14 6 0.0120 0.0120 124 3 0.2418 0:3307 0:7311 ¼0:2418 123 4 4 0.0889 0:3307 0:2689 ¼0:0889 Table 4 Value function at each node. Node Value function 40 31:5000 21:6867 11:5803 Fig. 2. Small cyclic network. Table 5 Value function at each node. Node Value function 40 31:1998 21:5968 11:5496 Table 6 Recursive logit path choice probabilities. Path Length Product of link choice probabilities 14 2 0.6374 14 6 0.0117 12430:3509 0:6682 ¼0:2345 123440:3509 0:3318 0:7407 ¼0:0863 12314 5.5 0:3509 0:3318 0:2593 0:6374 ¼0:0192 12314 9.5 0:3509 0:3318 0:2593 0:0117 ¼0:0004 12312 4 6.5 0:3509 0:3318 0:2593 0:3509 0:6682 ¼ 0:0071 M. Zimmermann, E. Frejinger EURO Journal on Transportation and Logistics 9 (2020) 100004 8