Исследование численного метода резервирования маршрутов в геоинформационной задаче маршрутизации автономных транспортных средств
Агафонов А.А., Мясников В.В.

ИСОИ РАН – филиал ФНИЦ «Кристаллография и фотоника» РАН, 443001, Россия, г. Самара, ул. Молодогвардейская, д. 151;
Самарский национальный исследовательский университет имени академика С.П. Королева, 443086, Россия, г. Самара, Московское шоссе, д. 34

Аннотация:
Разработка автономных транспортных средств является современным трендом как теоретических, так и практических исследований. Управление автономными транспортными средствами в рамках интеллектуальной транспортной системы позволит значительно сократить уровень дорожных заторов и уменьшить длительность поездок в сети. В работе рассматривается метод резервирования маршрутов движения для управления городским трафиком. В рамках рассматриваемого метода каждое транспортное средство резервирует пространственный и временной слот на дорожном сегменте, входящем в его маршрут, что позволяет прогнозировать загрузку сегментов и находить кратчайший путь с большей точностью. Предложено использовать процедуру перестроения маршрута для повышения качества маршрутизации. Экспериментальное исследование метода маршрутизации проведено с помощью микроскопического моделирования движения транспортных средств.

Ключевые слова:
маршрутизация транспортных средств, резервирование маршрутов, кратчайший путь, моделирование движения.

Цитирование:
Агафонов, А.А.
Исследование численного метода резервирования маршрутов в геоинформационной задаче маршрутизации автономных транспортных средств / А.А. Агафонов, В.В. Мясников // Компьютерная оптика. – 2018. – Т. 42, № 5. – С. 912-920. – DOI: 10.18287/2412-6179-2018-42-5-912-920.

Литература:

  1. Eskandarian, A. Handbook of intelligent vehicles / A. Eskandarian. – New York: Springer, 2012. – 1599 p. – ISBN: 978-0-85729-084-7.
  2. Miculescu, D. Polling-systems-based control of high-performance provably-safe autonomous intersections / D. Miculescu, S. Karaman // Proceedings of the 53rd IEEE Conference on Decision and Control. – 2014. – P. 1417-1423. – DOI: 10.1109/CDC.2014.7039600.
  3. Zhou, F. Parsimonious shooting heuristic for trajectory design of connected automated traffic part I: Theoretical analysis with generalized time geography / F. Zhou, X. Li, J. Ma // Transportation Research Part B: Methodological. – 2017. – Vol. 95(C). – P. 394-420. – DOI: 10.1016/j.trb.2016.05.007.
  4. Varaiya, P. Smart cars on smart roads: Problems of control / P. Varaiya // IEEE Transactions on Automatic Control. – 1993. – Vol. 38, Issue 2. – P. 195-207. – DOI: 10.1109/9.250509.
  5. Paden, B. A survey of motion planning and control techniques for self-driving urban vehicles / B. Paden, M. Cáp, S.Z. Yong, D. Yershov, E. Frazzoli // IEEE Transactions on Intelligent Vehicles. – 2016. – Vol. 1, Issue 1. – P. 33-55. – DOI: 10.1109/TIV.2016.2578706.
  6. Dijkstra, E.W. A note on two problems in connexion with graphs / E.W. Dijkstra // Numerische Mathematik. – 1959. – Vol. 1, Issue 1. – P. 269-271. – DOI: 10.1007/BF01386390.
  7. Hart, P.E. A formal basis for the heuristic determination of minimum cost paths / P.E. Hart, N.J. Nilsson, B. Raphael // IEEE Transactions on Systems Science and Cybernetics. – 1968. – Vol. 4, Issue 2. – P. 100-107. – DOI: 10.1109/TSSC.1968.300136.
  8. Goldberg, A. Computing the shortest path: A search meets graph theory / A. Goldberg, С. Harrelson // Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’05). – 2005. – P. 156-165.
  9. Geisberger, R. Exact routing in large road networks using contraction hierarchies / R. Geisberger, P. Sanders, D. Schul­tes, C. Vetter // Transportation Science. – 2012. – Vol. 46, Issue 3. – P. 388-404. – DOI: 10.1287/trsc.1110.0401.
  10. Bast, H. Route planning in transportation networks / H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R.F. Werneck. – In: Algorithm Engineering / ed. by L. Kliemann, P. Sanders. – Cham: Springer, 2016. – P. 19-80. – DOI: 10.1007/978-3-319-49487-6_2.
  11. Çolak, S. Understanding congested travel in urban areas / S. Çolak, A. Lima, M.C. González // Nature Communications. – 2016. – Vol. 7. – 10793. – DOI: 10.1038/ncomms10793.
  12. Schmitt, E.J. Vehicle route guidance systems: Classification and comparison / E.J. Schmitt, H. Jula // 2006 IEEE Intelligent Transportation Systems Conference. – 2006. – P. 242-247. – DOI: 10.1109/ITSC.2006.1706749.
  13. Агафонов, А.А. Метод определения надёжного кратчайшего пути в зависящей от времени стохастической сети и его применение в геоинформационных задачах управления транспортом / А.А. Агафонов, В.В. Мясников // Компьютерная оптика. – 2016. – Т. 40, № 2. – С. 275-283. – DOI: 10.18287/2412-6179-2016-40-2-275-283.
  14. Desai, P. Multi-agent based vehicular congestion management / P. Desai, S.W. Loke, A. Desai, J. Singh // 2011 IEEE Intelligent Vehicles Symposium (IV). – 2011. – P. 1031-1036. – DOI: 10.1109/IVS.2011.5940493.
  15. Wang, S. A multi-agent based vehicles re-routing system for unexpected traffic congestion avoidance / S. Wang, S. Djahel, J. McManis // 17th International IEEE Conference on Intelligent Transportation Systems (ITSC). – 2014. – P. 2541-2548. – DOI: 10.1109/ITSC.2014.6958097.
  16. Dresner, K. Sharing the road: Autonomous vehicles meet human drivers / K. Dresner, P. Stone // IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence. – 2007. – P. 1263-1268.
  17. Kanamori, R. A study of route assignment strategy based on anticipatory stigmergy / R. Kanamori, J. Takahashi, T. Ito // Electronics and Communications in Japan. – 2016. – Vol. 99, Issue 3. – P. 3-12. – DOI: 10.1002/ecj.11683.
  18. Wardrop, J.G. Some theoretical aspects of road traffic research / J.G. Wardrop // Proceedings of the Institution of Civil Engineers. – 1952. – Vol. 1, Issue 3. – P. 325-362. – DOI: 10.1680/ipeds.1952.11259.
  19. Hasan, M.R. A multiagent solution to overcome selfish routing in transportation networks / M.R. Hasan, A.L.C. Bazzan, E. Friedman, A. Raja // 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC). – 2016. – P. 1850-1855. – DOI: 10.1109/ITSC.2016.7795856.
  20. Jahn, O. System-optimal routing of traffic flows with user constraints in networks with congestion / O. Jahn, R.H. Möhring, A.S. Schulz, N.E. Stier-Moses // Operations Research. – 2005. – Vol. 53, Issue 4. – P. 600-616. – DOI: 10.1287/opre.1040.0197.
  21. Groot, N. Toward system-optimal routing in traffic networks: A reverse stackelberg game approach / N. Groot, B. De Schutter, H. Hellendoorn // IEEE Transactions on Intelligent Transportation Systems. – 2015. – Vol. 16, Issue 1. – P. 29-40. – DOI: 10.1109/TITS.2014.2322312.
  22. Menelaou, C. Controlling road congestion via a low-complexity route reservation approach / C. Menelaou, P. Kolios, S. Timotheou, C.G. Panayiotou, M.P. Polycarpou // Transportation Research Part C: Emerging Technologies. – 2017. – Vol. 81 – P. 118-136. – DOI: 10.1016/j.trc.2017.05.005.
  23. Agafonov, A. Efficiency comparison of the routing algorithms used in centralized traffic management systems / A. Agafonov, V. Myasnikov // Procedia Engineering, – 2017. – Vol. 201. – P. 265-270. – DOI: 10.1016/j.proeng.2017.09.617.
  24. Saw, K. Literature review of traffic assignment: static and dynamic / K. Saw, B.K. Katti, G. Joshi // International Journal of Transportation Engineering. – 2015. – Vol. 2, Issue 4. – P. 339-347. – DOI: 10.22119/ijte.2015.10447.
  25. Li, J. Speed-density relationship: from deterministic to stochastic / J. Li, Q.-Y. Chen // The 88th Transportation Research Board (TRB) Annual Meeting. – 2009. – P. 1-20.
  26. Highway Capacity Manual.  – Washington, D.C.: Transportation Research Board, National Research Council, 2000. – 1207 p. – ISBN: 0-309-06681-6.
  27. Chakirov, A. Enriched sioux falls scenario with dynamic and disaggregate demand / A. Chakirov, P.J. Fourie // ETH Zurich Research Collection. – 2014. – 40 p. – DOI: 10.3929/ethz-b-000080996.
  28. Krajzewicz, D. Recent development and applications of SUMO – Simulation of Urban MObility / D. Krajzewicz, J. Erdmann, M. Behrisch, L. Bieker // International Journal on Advances in Systems and Measurements. – 2012. – Vol. 5, Issues 3&4. – P. 128-138.
  29. Krauss, S. Metastable states in a microscopic model of traffic flow / S. Krauss, P. Wagner, C. Gawron // Physical Review E. – 1997. – Vol. 55, Issue 5. – P. 5597-5602. – DOI: 10.1103/PhysRevE.55.5597.
  30. Simulation of Urban MObility [Electronical Resource]. – URL: https://sourceforge.net/projects/sumo/files/traffic_data/scenarios/TAPASCologne/ (request date 05.06.2018).

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20