Consistent Route Choice Model Estimation Without Choice Set Sampling: a Dynamic Discrete Choice Approach
M Fosgerau, Centre for Transport Studies/DTU, SE/DK; E Frejinger, A Karlstrom, Centre for Transport Studies, SE
We propose a dynamic discrete choice approach for consistently estimating route choice model parameters using maximum likelihood. The approach is computationally efficient, does not require choice set sampling and is not based on the IIA assumption.
In this paper we propose a dynamic discrete choice approach for consistently estimating route choice model parameters based on path observations using maximum likelihood. The approach is computationally efficient, does not require choice set sampling and the resulting path probabilities do not exhibit the independence from irrelevant alternatives (IIA) property.
Discrete choice models where alternatives correspond to paths in the network are often used for estimating route choice model parameters. This is very difficult since the number of alternative paths is huge and the paths may share unobserved attributes. In order to obtain operational models it is common to define subsets of alternatives. Two different frameworks are presented in the literature: one aims at generating actual choice sets also known as consideration sets, and one samples alternatives from the set of all paths with the aim of obtaining unbiased parameter estimates (Frejinger et al., 2009). The latter is based on the IIA assumption and finding consistent estimates for a realistic correlation structure still remains difficult. Heuristics are used to generate consideration sets and this is not only time consuming, but the accuracy of the resulting choice sets is also difficult to evaluate since only chosen paths are observed. Moreover, in this context, the concept of consideration sets is in itself doubtful. Note also that, unlike the approach proposed in this paper, path based models cannot be extended to dynamic networks since the path concept is static per se.
A path is a sequence of links. We propose to use a dynamic discrete choice model and break down the utility maximizing choice of path into a sequence of link choices. At each stage the individual considers the utility associated with downstream link choices accumulated into a value function (expected maximum utility). If link attributes are deterministic and the link choice is modeled with a multinomial logit (MNL) model, we demonstrate that we can efficiently compute the destination specific value functions by solving a system of linear equations. Like in a path based MNL, the resulting path choice probabilities exhibit the IIA property which is undesirable in route choice. However, since the value functions can be efficiently computed we are able to relax the IIA property by using a random parameters model.
The idea of using a sequential link choice model has been around for quite some time in the context of traffic assignment. Dial (1971) limited the alternatives to "efficient links" but other contributions do not (Bell, 1995, Akamatsu, 1996, and Baillon and Cominetti, 2008) and are hence similar to the model we propose here. The numerical results in the former papers are limited to toy networks. Ziebart et al. (2008) pose the problem of estimation as "inverse reinforcement learning" and estimate a mix between a path and link based model on GPS data. They focus on prediction accuracy and do not discuss the consistency of their estimator. Our previous work (Fosgerau et al., 2009) focused on approximations of the value functions while the results of this paper indicate that such approximations are actually not necessary.
For the numerical results we use the Borlänge network and a related GPS dataset of observed path choices. For validation purposes we use a synthetic dataset generated with a postulated model for the same network. The size of the system of linear equations is 7288 and value functions, for a given destination, can be computed in less than 0.05 seconds (on a laptop). This is ongoing work and we are currently estimating the random parameters model.
Akamatsu, T. (1996). Cyclic flows, Markov process and stochastic traffic assignment, Transportation Research Part B 30(5):369-386.
Baillon, J.B, and Cominetti, R. (2008). Markovian traffic equilibrium, Mathematical Programming 111(1): 33-56.
Bell, M.G.H. (1995). Alternatives to Dial's logit assignment algorithm, Transportation Research Part B 29(4): 287-295.
Dial, R. (1971). A probabilistic multipath traffic assignment algorithm which obviates path enumeration, Transportation Research 5(2): 83-111.
Fosgerau, M., Frejinger, E., Karlström, A., (2009). Route choice modeling without route choice, Proceedings of the European Transport Conference, Leiden, Netherlands.
Frejinger, E., Bierlaire, M. and Ben-Akiva, M. (2009). Sampling of alternatives for route choice modeling, Transportation Research Part B 43(10): 984-994.
Ziebart B.D., Maas A., Bagnell J.A., Dey A.K (2008). Maximum Entropy Inverse Reinforcement Learning, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence.
Association for European Transport