A theoretical analysis of the cross-nested logit model. (English) Zbl 1159.90307
Summary: The emergence of Intelligent Transportation Systems and the associated technologies has increased the need for complex models and algorithms. Namely, real-time information systems, directly influencing transportation demand, must be supported by detailed behavioral models capturing travel and driving decisions. Discrete choice models methodology provide an appropriate framework to capture such behavior. Recently, the Cross-Nested Logit (CNL) model has received quite a bit of attention in the literature to capture decisions such as mode choice, departure time choice and route choice. The CNL model is an extension of the Nested Logit model, providing more flexibility at the cost of some complexity in the model formulation. In this paper, we develop on the general formulation of the Cross Nested Logit model proposed by Ben-Akiva and Bierlaire (1999) and based on the Generalized Extreme Value (GEV) model. We show that it is equivalent to the formulations by Papola (2004) and Wen and Koppelman (2001). We also show that the formulations by Small (1987) and Vovsha (1997) are special cases of this formulation. We formally prove that the Cross-Nested Logit model is indeed a member of the GEV models family. In doing so, we clearly distinguish between conditions that are necessary to prove consistency with the GEV theory, from normalization conditions. Finally, we propose to estimate the model with non-linear programming algorithms, instead of heuristics proposed in the literature. In order to make it operational, we provide the first derivatives of the log-likelihood function, which are necessary to such optimization procedures.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | Abbé, E. (2003). ”Behavioral Modeling: Generalized Extreme Value for Choice Models.” Diploma Thesis. Institute of Mathematics, Ecole Polytechnique Fédérale de Lausanne, Switzerland. |
| [2] | Abbé, E., M. Bierlaire, and T. Toledo. (2005). ”Normalization and Correlation of Generalized Extreme Value Models.” Technical Report, Ecole Polytechnique Fédérale de Lausanne (EPFL). |
| [3] | Ben-Akiva, M. and M. Bierlaire. (1999). ”Discrete Choice Methods and their Applications to Short-Term Travel Decisions.” In R. Hall (ed.), Handbook of Transportation Science, Kluwer, pp. 5–34. |
| [4] | Ben-Akiva, M. and M. Bierlaire. (2003). ”Discrete Choice Models with Applications to Departure Time and Route Choice.” In R. Hall (ed.), Handbook of Transportation Science, 2nd edn., Kluwer, pp. 7–37. |
| [5] | Ben-Akiva, M., M. Bierlaire, D. Burton, H.N. Koutsopoulos, and R. Mishalani. (2001). ”Network State Estimation and Prediction for Real-Time Transportation Management Applications.” Networks and Spatial Economics 1(3/4), 293–318. · doi:10.1023/A:1012883811652 |
| [6] | Bertsekas, D.P. (1999). Nonlinear Programming, 2nd edn., Athena Scientific, Belmont. · Zbl 1015.90077 |
| [7] | Bhat, C. (1995). ”A Heteroscedastic Extreme Value Model of Intercity Travel Mode Choice.” Transportation Research B 29, 471–483. · doi:10.1016/0191-2615(95)00015-6 |
| [8] | Bierlaire, M. (1995). ”A Robust Algorithm for the Simultaneous Estimation of Hierarchical Logit Models.” GRT Report 95/3, Department of Mathematics, FUNDP. |
| [9] | Bierlaire, M. (2003). ”BIOGEME: A Free Package for the Estimation of Discrete Choice Models.” Proceedings of the 3rd Swiss Transportation Research Conference, Ascona, Switzerland. |
| [10] | Bierlaire, M., K. Axhausen, and G. Abbay. (2001). ”Acceptance of Model Innovation: The Case of the Swissmetro.” Proceedings of the 1st Swiss Transport Research Conference. |
| [11] | Bierlaire, M., T. Lotan, and P.L. Toint. (1997). ”On the Overspecification of Multinomial and Nested Logit Models Due to Alternative Specific Constants.” Transportation Science, 31(4), 363–371. · Zbl 0920.90055 · doi:10.1287/trsc.31.4.363 |
| [12] | Bierlaire, M., R. Mishalani, and M. Ben-Akiva. (2000). ”General Framework for Dynamic Demand Simulation.” Technical Report RO-000223, ROSO-DMA-EPFL Ecole Polytechnique Fédérale de Lausanne, CH-1015 Lausanne. http://roso.epfl.ch/mbi/demand-report.pdf. · Zbl 1048.90061 |
| [13] | Bierlaire, M. and M. Thémans. (2005). ”Algorithmic Developments for the Estimate of Advanced Discrete Choice Models.” Proceedings of the 5th Swiss Transportation Research Conference. www.strc.ch. |
| [14] | Chatterjee, K., N. Hounsell, P. Firmin, and P. Bonsall. (2002). ”Driver Response to Variable Message Sign Information in London.” Transportation Research C, 10, 149–169. · doi:10.1016/S0968-090X(01)00008-0 |
| [15] | Conn, A.R., N.I.M. Gould, and P.L. Toint. (1992). ”LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A).” Number 17 in Springer Series in Computational Mathematics, Springer Verlag, Heidelberg, Berlin, New York. · Zbl 0761.90087 |
| [16] | Dennis, J.E. and R.B. Schnabel. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, USA. · Zbl 0579.65058 |
| [17] | Forinash, C.V. and F.S. Koppelman. (1993). ”Application and Interpretation of Nested Logit Models of Intercity Mode Choice.” Transportation Research Record Issue, 1413, 98–106. |
| [18] | Glover, F. (1977). ”Heuristic for Integer Programming Using Surrogate Constraints.” Decision Sciences, 8, 156–166. · doi:10.1111/j.1540-5915.1977.tb01074.x |
| [19] | Hansen, P. (1986). ”The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming.” Technical Report, Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy. |
| [20] | Hansen, P. and B. Jaumard. (1987). ”Algorithms for the Maximum Satisfiability Problem.” Technical Report Rutgers University. · Zbl 0716.68077 |
| [21] | Hansen, P. and N. Mladenovic. (1997). ”An Introduction to Variable Neighborhood Search.” Les Cahiers du GERAD. |
| [22] | Kirkpatrick, S., C.D.J. Gelatt, and M.P. Vecchi. (1983). ”Optimization by Simulated Annealing.” Science, 220, 671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [23] | Kuntsevich, A.V. and F. Kappel. (1997). The Solver for Local Nonlinear Optimization Problems. Institute for Mathematics, KarlFranzens University of Graz, Heinrichstr. 36, A-8010 Graz (Austria). www.kfunigraz.ac.at/imawww/kuntsevich/solvopt/content.html. |
| [24] | Lawrence, C., J. Zhou, and A. Tits. (1997). ”User’s Guide for CFSQP Version 2.5: A C Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints.” Technical Report TR-94-16r1, Institute for Systems Research, University of Maryland, College Park, MD 20742, 1997. |
| [25] | McFadden, D. (1978). ”Modelling the Choice of Residential Location.” In A. Karlquist et al. (eds.), Spatial Interaction Theory and Residential Location, North-Holland, Amsterdam, pp. 75–96. |
| [26] | Murtagh, B.A. and M.A. Saunders. (1987). MINOS 5.1 USER’S GUIDE, Technical Report SOL83-20R, Department of Operations Research, Stanford University, Stanford, USA. |
| [27] | Papola, A. (2004). ”Some Developments on the Cross-Nested Logit Model.” Transportation Research B, 38(9), 833–851. · doi:10.1016/j.trb.2003.11.001 |
| [28] | Prashker, J. and S. Bekhor. (1999). ”Stochastic User-Equilibrium Formulations for Extended-Logit Assignment Models.” Transportation Research Record, 1676, 145–152. |
| [29] | Rossier, Y., M. Troyon, and T.M. Liebling. (1986). ”Probabilistic Exchange Algorithms and Euclidean Traveling Salesman Problems.” OR Spektrum, 8(3), 151–164. · Zbl 0596.90069 · doi:10.1007/BF01784711 |
| [30] | Small, K. (1987). ”A Discrete Choice Model for Ordered Alternatives.” Econometrica, 55(2), 409–424. · Zbl 0654.62093 · doi:10.2307/1913243 |
| [31] | Spellucci, P. (1993). DONLP2 Users Guide, Dept. of Mathematics, Technical University at Darmstadt, 64289 Darmstadt, Germany. |
| [32] | Swait, J. (2001). ”Choice Set Generation Within the Generalized Extreme Value Family of Discrete Choice Models.” Transportation Research B, 35(7), 643–666. · doi:10.1016/S0191-2615(00)00029-1 |
| [33] | Vovsha, P. (1997). ”Cross-Nested Logit Model: An Application to Mode Choice in the Tel-Aviv Metropolitan Area.” Transportation Research Record, 1607, 6–15. · doi:10.3141/1607-02 |
| [34] | Vovsha, P. and S. Bekhor. (1998). ”The Link-Nested Logit Model of Route Choice: Overcoming the Route Overlapping Problem.” Transportation Research Record, 1645, 133–142. · doi:10.3141/1645-17 |
| [35] | Wen, C.-H. and F.S. Koppelman. (2001). ”The Generalized Nested Logit Model.” Transportation Research B, 35(7), 627–641. · doi:10.1016/S0191-2615(00)00045-X |
| [36] | Williams, H. (1977). ”On the Formation of Travel Demand Models and Economic Measures of User Benefit.” Environment and Planning, 9A, 285–344. · doi:10.1068/a090285 |
| [37] | Zeng, L. C. (2000). ”A Heteroscedastic Generalized Extreme Value Discrete Choice Model.” Sociological Methods and Research, 29, 118–144. · doi:10.1177/0049124100029001006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
