Tło teoretyczne dla adaptacyjnego, dynamicznego modelu wyboru ścieżki w modelu ruchu

• Autorzy: Kucharski R.

Warianty tytułu

EN

Theoretical background for adaptive and dynamic path choice model in traffic modelling

• Konferencja: Modelowanie podróży i prognozowanie ruchu (15-16.11.2012 ; Kraków, Polska)
• Języki publikacji: PL EN

Abstrakty

PL

Niniejszy artykuł stanowi podstawę teoretyczną dla zagadnienia adaptacyjnego wyboru ścieżki w sieci transportowej. Na jego podstawie możliwe będzie sformułowanie adaptacyjnego modelu wyboru ścieżki na potrzeby makroskopowego modelowania ruchu, co jest przedmiotem pracy doktorskiej autora. W artykule autor omawia w szczególności podstawy i najnowsze teorie dla następujących trzech obszarów modelowania: - wyszukiwania najkrótszej ścieżki w sieci transportowej (ang. shortest path search), - próbkowania ścieżek (ang.: path sampling), - wyboru ścieżki (ang.: route choice). W części pierwszej opisano podstawowe i bardziej zaawansowane algorytmy wyszukiwania najkrótszej ścieżki w sieci transportowej. Pokazano zarówno klasyczne algorytmy, ich modyfikacje, jak i najnowsze propozycje. Omówiono przypadki dla sieci statycznej, dynamicznej i stochastycznej. Część ta jest podstawą dla dalszych części, w których omawiane są modele zawierające implicite algorytmy wyszukiwania najkrótszej ścieżki. Część druga to omówienie metod próbkowania ścieżek, czyli określania zbioru potencjalnie efektywnych ścieżek łączących źródło z celem. Pokazano próby rozwiązania tego problemu, który (jak argumentuje wielu badaczy) jest dotąd nierozwiązany w praktyce, a istniejące metody dostarczają jedynie heurystycznych przybliżeń. Pokazano tu w szczególności autorską propozycje rozszerzenia istniejącej metody próbkowania Łańcuchem Markowa Metropolisa-Hastingsa na przypadek zmiennej w czasie sieci stochastycznej. Część trzecia to omówienie modeli wyboru ścieżki spośród możliwych. Pokazano tu zarówno klasyczne modele logitowe, ich modyfikacje, jak i nieliczne alternatywne metody wyboru ścieżki. W końcowej części omówiono podejście do adaptacyjności w każdej z metod omawianych wcześniej. Wiele użytych w artykule nazw jest własną próbą tłumaczenia nazw angielskich, jako że autor zdaje sobie sprawę z ułomności własnych tłumaczeń, w nawiasach przy każdym pierwszym użyciu podano odpowiednik angielski.

EN

Article is a theoretical background needed to define adaptive route choice model for transport modelling. The aim is to define state-of-the-art and state-of-the-practice in theoretical models which constitute route choice modelling, namely shortest path search, route sampling, and route choice modelling. Article shows basic and advanced techniques of solving mentioned models. Static, dynamic, and stochastic cases of transport networks are discussed. Examples include the most recent proceedings. Adaptive aspects of models are emphasized.

Słowa kluczowe

PL

najkrótsza ścieżka; problem najkrótszej ścieżki dynamiczny; próbowanie ścieżek; wybór ścieżki w sieci transportowej; adaptacja modeli ruchu

EN

shortest path; dynamic problem of the shortest path; path sampling; route choice in transportation network; adaptation of traffic models

• Wydawca: Stowarzyszenie Inżynierów i Techników Komunikacji Rzeczpospolitej Polskiej. Oddział w Krakowie
• Czasopismo: Zeszyty Naukowo-Techniczne Stowarzyszenia Inżynierów i Techników Komunikacji w Krakowie. Seria: Materiały Konferencyjne
• Rocznik: 2012
• Tom: Nr 2(98)
• Strony: 134--150
• Opis fizyczny: Bibliogr. 49 poz.

Twórcy

autor

Kucharski R.

• Katedra Systemów Komunikacyjnych, Politechnika Krakowska, ul. Warszawska 24, 01-155 Kraków

Bibliografia

• [1] Abraham I., Delling D., Goldberg A. V., Werneck R., 2010. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, Microsoft Research Silicon Valley.
• [2] Bast H., S. Funke S., Sanders P., Schultes D., 2007, Fast Routing in Road Networks with Transit Nodes, Science, Vol. 316. no. 5824, p. 566, 27. April 2007.
• [3] Bekhor, S., Ben-Akiva, M. E., & Ramming, M. S., 2006. Evaluation of choice set generation algorithms for route choice models. Annals of Operations Research, 144(1), 235–247. doi:10.1007/s10479-006-0009-8
• [4] Bell, M. G. H., Trozzi, V., Hosseinloo, S. H., Gentile, G., & Fonzone, A., 2012. Time-dependent Hyperstar algorithm for robust vehicle navigation. Transportation Research Part A: Policy and Practice, 46(5), 790–800. doi:10.1016/j.tra.2012.02.002
• [5] Ben-Akiva, M., Bergman, M.J., Daly, A.J., Ramaswamy, R., 1984. Modeling inter-urban route choice behaviour. Proceedings of the Ninth International Symposium on Transportation and Traffic Theory. VNU Science Press, Utrecht. pp. 299–330.
• [6] Ben-Akiva, M. and Ramming, S., 1998. Lecture notes: Discrete choice models of traveler behavior in networks. Prepared for Advanced Methods for Planning and Management of Transportation Networks. Capri, Italy
• [7] Ben-Elia, E., & Shiftan, Y., 2010. Which road do I take? A learning-based model of route-choice behavior with real-time information. Transportation Research Part A: Policy and Practice, 44(4), 249–264. doi:10.1016/j.tra. 2010.01.007
• [8] Bliemer, M.C.J., Bovy, P.H.L., 2008. Impact of route choice set on route choice probabilities. Transportation Research Record, 2076, 10-19.
• [9] Bovy, P.H.L., Bekhor, S., Prato, C.G., 2009. Route sampling correction for stochastic route choice set generation. Proceedings of the 88th Annual Meeting of the Transportation Research Board, Washington, D.C.
• [10] Bovy, P.H.L., Fiorenzo-Catalano, S., 2007. Stochastic route choice set generation: behavioral and probabilistic foundations. Transportmetrica, 3(3), 173-189.
• [11] Cantillo, V., Heydecker, B., Ortuzar, J.d.D., 2006. A discrete choice model incorporating thresholds for perception in attribute values. Transportation Research Part B, 40(9), 807-825.
• [12] Cascetta, E., Nuzzolo, A., Russo, F. and Vitetta, A., 1996. A modified logit route choice model overcoming path overlapping problems. Spec- ification and some calibration results for interurban networks, in J. B. Lesort (ed.), Proceedings of the 13th International Symposium on Trans- portation and Traffic Theory, Lyon, France.
• [13] Cascetta, E., Papola, A., 2001. Random utility models with implicit availability perception of choice travel for the simulation of travel demand. Transportation Research Part C, 9(4), 249-263.
• [14] Cooke, K., Halsey, E., 1966. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications 14, 493–498.
• [15] De la Barra, T., B. Perez, and J. Anez., 1993. Multidimensional Path Search and Assignment. In Proceedings of the 21st PTRC Summer Meeting, pp. 307–319.
• [16] De Palma A., Hansen P. And Labbé M., 1993. Commuters’ paths with penalties for early or late arrival times, Transportation Science 24, 276-286
• [17] Dijkstra, E. W., 1959. A note on two problems in connexion with graphs
• [18] Dionne, R., 1978. E´ tude et extension d’un algorithme de Murchland. INFOR 16, 132–146.
• [19] Dubois D., Prade H., 1980, Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, 1980.
• [20] Fakcharoemphol J. and Rao S. Planar graphs, negative weight edges, shortest paths, and near linear time. In Proc. of the 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS’01), Las Vegas, Nevada, pages 232–241, 2001.
• [21] Flötteröd, G., & Bierlaire, M., 2011. Metropolis-Hastings sampling of paths.
• [22] Frank H., 1969, Shortest paths in probability graphs, Operations Research 17 (4) (1969) 583–599.
• [23] Frejinger, E., Bierlaire, M., & Ben-Akiva, M., 2009. Sampling of alternatives for route choice modeling. Transportation Research Part B: Methodological, 43(10), 984–994. doi:10.1016/j.trb.2009.03.001
• [24] Frejinger, Emma., 2008. Route choice analysis: data, models, algorithms and applications, 4009. Retrieved from http://biblion.epfl.ch/EPFL/theses/2008/4009/EPFL_TH4009.pdf
• [25] Frejinger, Emma., 2009. Route choice modeling without route choice, 1–14.
• [26] Gao, S., Frejinger, E., & Ben-Akiva, M., 2010. Adaptive route choices in risky traffic networks: A prospect theory approach. Transportation Research Part C: Emerging Technologies, 18(5), 727–740. doi:10.1016/j.trc.2009.08.001
• [27] Gao, Y., 2011. Shortest path problem with uncertain arc lengths. Computers & Mathematics with Applications, 62(6), 2591–2600. doi:10.1016/j.camwa.2011.07.058
• [28] Gao, S, Huang, H., 2012. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks. Transportation Research Part C: Emerging Technologies, 21(1), 196–213. doi:10.1016/j.trc.2011.09.007
• [29] Gentile, G., Meschini, L., Papola, N., 2004. Fast heuristics for continuous dynamic shortest paths and all-or-nothing assignment.
• [30] Hart, P. E., Nilsson, N. J., Raphael, B., 1972. "Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"". SIGART Newsletter 37: 28–29.
• [31] Henzinger M.R., Klein P., Rao S., and Subramanian S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3–23, August 1997
• [32] Hoogendoorn-Lanser, S., 2005. Modelling Travel Behaviour in Multi-modal Networks, PhD thesis, Delft University of Technology.
• [33] Johnson, D. B., 1975. Priority queues with update and finding minimum spanning trees, Information Processing Letters 4 (3): 53–57.
• [34] Leyzorek, M., Gray, R. S., Johnson, A. A., Ladew, W. C., Meaker, Jr., S. R., Petry, R. M., Seitz, R. N., 1957. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
• [35] Liu B., 2007, Uncertainty Theory, 2nd ed., Springer-Verlag, Berlin, 2007.
• [36] Liu W., 2010, Uncertain programming models for shortest path problem with uncertain arc lengths, in: Proceedings of the First International Conference on Uncertainty Theory, Urumchi, China, August 11–19, 2010, pp. 148–153.
• [37] Menghini, G., Carrasco, N., Schüssler, N., & Axhausen, K. W., 2010. Route choice of cyclists in Zurich. Transportation Research Part A: Policy and Practice, 44(9), 754–765. doi:10.1016/j.tra.2010.07.008
• [38] Nielsen, O.A., 2004. Behavioral responses to road pricing schemes: description of the Danish AKTA experiment. Journal of Intelligent Transportation Systems 8 (4), 233–251.
• [39] Pallottino, S., Scutella`, M., 1997. Dual algorithms for the shortest path tree problem. Networks 29, 125–133.
• [40] Papinski, D., Scott, D. M., & Doherty, S. T., 2009. Exploring the route choice decision-making process: A comparison of planned and observed routes obtained using person-based GPS. Transportation Research Part F: Traffic Psychology and Behaviour, 12(4), 347–358. doi:10.1016/j.trf.2009.04.001
• [41] Prato, C. G. 2009). Route choice modeling : past, present and future research directions, 2(1), 65–100.
• [42] Prato, C.G., Bekhor, S., 2006. Applying branch & bound technique to route choice set generation. Transportation Research Record, 1985, 19-28.
• [43] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, 1993. Network Flows: Theory, Algorithms and Applications.
• [44] Sedgewick R., Wayne K., 2011. Algorithms (4th Edition) Addison-Wesley Professional.
• [45] Sheffi, Y., Powell, W.B., 1982. An algorithm for the equilibrium assignment problem with random link times. Networks, 12, 191-207.
• [46] Snowdon, J., & Fangohr, P. H., 2012. Evolution of adaptive route choice behaviour in drivers, (January), 1–12.
• [47] Tarjan, R. E., 1983. Data structures and network algorithms. Philadelphia: Society for Industrial and Applied Mathematics.
• [48] van der Zijpp, N. J., & Fiorenzo Catalano, S., 2005. Path enumeration by finding the constrained K-shortest paths. Transportation Research Part B: Methodological, 39(6), 545–563. doi:10.1016/j.trb.2004.07.004
• [49] Zhan, F. B., & Noon, C. E., 1998. Shortest Path Algorithms: An Evaluation using Real Road Networks, 10, 65–73.