•Model estimated and validated using bike GPS data on network of 40,000 links.•Quick computation of link flows without choice set generation.•Easy to compute accessibility measure with desirable ...properties.
Concerned by the nuisances of motorized travel on urban life, policy makers are faced with the challenge of making cycling a more attractive alternative for everyday transportation. Route choice models can help achieve this objective by gaining insights into the trade-offs cyclists make when choosing their routes and by allowing the effect of infrastructure improvements to be analyzed. We estimate a link-based bike route choice model from a sample of GPS observations in the city of Eugene on a network comprising over 40,000 links. The so-called recursive logit (RL) model (Fosgerau et al., 2013) does not require to sample any choice set of paths. We show the advantages of this approach in the context of prediction by focusing on two applications of the model: link flows and accessibility measures. Compared to the path-based approach which requires to generate choice sets, the RL model proves to make significant gains in computational time and to avoid paradoxical accessibility measure results discussed in previous works, e.g. Nassir et al. (2014).
We propose a Recursive Logit (STD-RL) model for routing policy choice in a stochastic time-dependent (STD) network, where a routing policy is a mapping from states to actions on which link to take ...next, and a state is defined by node, time and information. A routing policy encapsulates travelers’ adaptation to revealed traffic conditions when making route choices. The STD-RL model circumvents choice set generation, a procedure with known issues related to estimation and prediction. In a given state, travelers make their link choice maximizing the sum of the utility of the outgoing link and the expected maximum utility until the destination (a.k.a. value function that is a solution to a dynamic programming problem). Existing recursive route choice models and the corresponding solution approaches are based on the assumption that network attributes are deterministic. Hence, they cannot be applied to stochastic networks which are the focus of this paper.
We propose an efficient algorithm for solving the value function and its gradient, critical for parameter estimation. It is based on partitioning the state space and decomposing costly matrix operations into a series of simpler ones. We present numerical results using a synthetic network and a network in Stockholm, Sweden. The estimation running time has a 20-30 times speed-up due to matrix decomposition. The estimated model parameters have realistic interpretations. Specifically, travelers are more likely to be adaptive to realized travel times during a longer trip, and more sensitive to travel time when travel time variability is higher. The STD-RL model performs better in predicting route choices than the RL model in a corresponding static and deterministic network.
•A recursive logit (STD-RL) model for routing policy choice in stochastic networks.•A decomposition scheme to tackle a non-linear system with a large state space.•Potential biases due to ignored stochasticity identified by synthetic data analysis.•STD-RL achieves better prediction than a deterministic model in a Stockholm case study.
This paper deals with route choice models capturing travelers’ strategic behavior when adapting to revealed traffic conditions
en route in a stochastic network. The strategic adaptive behavior is ...conceptualized as a routing policy, defined as a decision rule that maps from all possible revealed traffic conditions to the choices of next link out of decision nodes, given information access assumptions. In this paper, we use a specialized example where a variable message sign provides information about congestion status on outgoing links. We view the problem as choice under risk and present a routing policy choice model based on the cumulative prospect theory (CPT), where utility functions are nonlinear in probabilities and thus flexible attitudes toward risk can be captured.
In order to illustrate the differences between routing policy and non-adaptive path choice models as well as differences between models based on expected utility (EU) theory and CPT, we estimate models based on synthetic data and compare them in terms of prediction results. There are large differences in path share predictions and the results demonstrate the flexibility of the CPT model to represent varying degrees of risk aversion and risk seeking depending on the outcome probabilities.
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.
Fosgerau et al. (2013) recently proposed the recursive logit (RL) model for route choice problems, that can be consistently estimated and easily used for prediction without any sampling of choice ...sets. Its estimation however requires solving many large-scale systems of linear equations, which can be computationally costly for real data sets. We design a decomposition (DeC) method in order to reduce the number of linear systems to be solved, opening the possibility to estimate more complex RL based models, for instance mixed RL models. We test the performance of the DeC method by estimating the RL model on two networks of more than 7000 and 40,000 links, and we show that the DeC method significantly reduces the estimation time. We also use the DeC method to estimate two mixed RL specifications, one using random coefficients and one incorporating error components associated with subnetworks (Frejinger and Bierlaire 2007). The models are estimated on a real network and a cross-validation study is performed. The results suggest that the mixed RL models can be estimated in a reasonable time with the DeC method. These models yield sensible parameter estimates and the in-sample and out-of sample fits are significantly better than the RL model.
•Model constraints can be learned from observations of executed plans.•Learned representation of constraints can be stored in common structure.•Trained learning models reflect relationships between ...variables in constraints.
When embedded in software-based decision support systems, optimization models can greatly improve organizational planning. In many industries, there are classical models that capture the fundamentals of general planning decisions (e.g., designing a delivery route). However, these models are generic and often require customization to truly reflect the realities of specific operational settings. Yet, such customization can be an expensive and time-consuming process. At the same time, popular cloud computing software platforms such as Software as a Service (SaaS) are not amenable to customized software applications. We present a framework that has the potential to autonomously customize optimization models by learning mathematical representations of customer-specific business rules from historical data derived from model solutions and implemented plans. Because of the wide-spread use in practice of mixed integer linear programs (MILP) and the power of MILP solvers, the framework is designed for MILP models. It uses a common mathematical representation for different optimization models and business rules, which it encodes in a standard data structure. As a result, a software provider employing this framework can develop and maintain a single code-base while meeting the needs of different customers. We assess the effectiveness of this framework on multiple classical MILPs used in the planning of logistics and supply chain operations and with different business rules that must be observed by implementable plans. Computational experiments based on synthetic data indicate that solutions to the customized optimization models produced by the framework are regularly of high-quality.
This paper focuses on the comparison of the random regret minimization (RRM) and mother logit models for analyzing the choice between alternatives having deterministic attributes. The mother logit ...model allows utilities of a given alternative to depend on attributes of other alternatives. It was designed to relax the independence from irrelevant alternatives (IIA) property while keeping the random terms independently and identically distributed extreme value distributed (McFadden et al., 1978).
We adapt and extend the RRM model proposed by Chorus (2014) to the case of recursive logit (RL) route choice models (Fosgerau et al., 2013). We argue that these RRM models can be cast as mother logit models and we define such models that are equivalent to the RRM ones considered in this paper. The results show that one of the RRM models and its mother logit equivalent has the best out-of-sample fit indicating that utility functions based on attribute differences best explains the choices in our application.
•Link-based route choice models (no path choice set generation).•We formulate random regret-based recursive logit models.•Two new specifications of the random regret functions.•New mother logit models that are equivalent to the regret-based models.•Estimation and cross-validation results using real data.
•A model for the choice of route in network.•Link size attribute: a deterministic correction for correlation.•No choice set generation needed.•A dynamic specification of sequential link choices is ...equivalent to a static logit model.•Estimation on synthetic and real GPS data in network of 7000 links.
This paper considers the path choice problem, formulating and discussing an econometric random utility model for the choice of path in a network with no restriction on the choice set. Starting from a dynamic specification of link choices we show that it is equivalent to a static model of the multinomial logit form but with infinitely many alternatives. The model can be consistently estimated and used for prediction in a computationally efficient way. Similarly to the path size logit model, we propose an attribute called link size that corrects utilities of overlapping paths but that is link additive. The model is applied to data recording path choices in a network with more than 3000 nodes and 7000 links.
•The IIA property is relaxed and random terms are correlated.•Link-based model: no choice sets of paths are required.•Efficient estimation and prediction.•Estimation and cross-validation results ...using real data.
We propose a route choice model that relaxes the independence from irrelevant alternatives property of the logit model by allowing scale parameters to be link specific. Similar to the recursive logit (RL) model proposed by Fosgerau et al. (2013), the choice of path is modeled as a sequence of link choices and the model does not require any sampling of choice sets. Furthermore, the model can be consistently estimated and efficiently used for prediction.
A key challenge lies in the computation of the value functions, i.e. the expected maximum utility from any position in the network to a destination. The value functions are the solution to a system of non-linear equations. We propose an iterative method with dynamic accuracy that allows to efficiently solve these systems.
We report estimation results and a cross-validation study for a real network. The results show that the NRL model yields sensible parameter estimates and the fit is significantly better than the RL model. Moreover, the NRL model outperforms the RL model in terms of prediction.