A dynamic programming approach for quickly estimating large network-based MEV models

TY - JOUR

T1 - A dynamic programming approach for quickly estimating large network-based MEV models

AU - Mai, Tien

AU - Frejinger, Emma

AU - Fosgerau, Mogens

AU - Bastin, Fabian

PY - 2017/4/1

Y1 - 2017/4/1

N2 - We propose a way to estimate a family of static Multivariate Extreme Value (MEV) models with large choice sets in short computational time. The resulting model is also straightforward and fast to use for prediction. Following Daly and Bierlaire (2006), the correlation structure is defined by a rooted, directed graph where each node without successor is an alternative. We formulate a family of MEV models as dynamic discrete choice models on graphs of correlation structures and show that the dynamic models are consistent with MEV theory and generalize the network MEV model (Daly and Bierlaire, 2006). Moreover, we show that these models can be estimated quickly using the concept of network flows and the nested fixed point algorithm (Rust, 1987). The main reason for the short computational time is that the new formulation allows to benefit from existing efficient solution algorithms for sparse linear systems of equations. We present numerical results based on simulated data with varying number of alternatives and nesting structures. We estimate large models, for example, a cross-nested model with 200 nests and 500,000 alternatives and 210 parameters that needs between 100–200 iterations to converge (4.3 h on an Intel(R) 3.2 GHz machine using a non-parallelized code). We also show that our approach allows to estimate a cross-nested logit model of 111 nests with a real data set of more than 100,000 observations in 14 h.

AB - We propose a way to estimate a family of static Multivariate Extreme Value (MEV) models with large choice sets in short computational time. The resulting model is also straightforward and fast to use for prediction. Following Daly and Bierlaire (2006), the correlation structure is defined by a rooted, directed graph where each node without successor is an alternative. We formulate a family of MEV models as dynamic discrete choice models on graphs of correlation structures and show that the dynamic models are consistent with MEV theory and generalize the network MEV model (Daly and Bierlaire, 2006). Moreover, we show that these models can be estimated quickly using the concept of network flows and the nested fixed point algorithm (Rust, 1987). The main reason for the short computational time is that the new formulation allows to benefit from existing efficient solution algorithms for sparse linear systems of equations. We present numerical results based on simulated data with varying number of alternatives and nesting structures. We estimate large models, for example, a cross-nested model with 200 nests and 500,000 alternatives and 210 parameters that needs between 100–200 iterations to converge (4.3 h on an Intel(R) 3.2 GHz machine using a non-parallelized code). We also show that our approach allows to estimate a cross-nested logit model of 111 nests with a real data set of more than 100,000 observations in 14 h.

KW - Discrete choice

KW - Dynamic programming

KW - Maximum likelihood estimation

KW - Multivariate extreme value models

KW - Nested fixed point algorithm

KW - Value iteration

U2 - 10.1016/j.trb.2016.12.017

DO - 10.1016/j.trb.2016.12.017

M3 - Journal article

AN - SCOPUS:85008395758

SN - 0191-2615

VL - 98

SP - 179

EP - 197

JO - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

ER -