Numerical route reservation method in the geoinformatic task of autonomous vehicle routing
Agafonov A.A., Myasnikov V.V.

IPSI RAS – Branch of the FSRC “Crystallography and Photonics” RAS, Molodogvardeyskaya 151, 443001, Samara, Russia;
Samara National Research University, Moskovskoye shosse, 34, 443086, Samara, Russia

 PDF

Abstract:
Autonomous vehicle development is one of many trends that will affect future transport demands and planning needs. Autonomous vehicles management as a part of an intelligent transportation system could significantly reduce traffic jams and decrease the overall travel time. In this work, we investigate a route reservation architecture to manage road traffic within an urban area. The routing architecture decomposes road segments into time and spatial slots for every vehicle, it makes the reservation of appropriate slots on the road segments in the selected route. This approach allows one to predict the traffic in the road network and find the shortest path more precisely. We propose that a rerouting procedure should be utilized to improve the quality of the routing approach. We consider several speed-density relations to estimate the vehicle speed based on a road segment reservation state. The experimental study of the routing architecture is conducted using microscopic traffic simulation in SUMO package.

Keywords:
route reservation approach, vehicle routing, shortest path, traffic simulation, SUMO.

Citation:
Agafonov AA, Myasnikov VV. Numerical route reservation method in the geoinformatic task of autonomous vehicle routing. Computer Optics 2018; 42(5): 912-920. DOI: 10.18287/2412-6179-2018-42-5-912-920.

References:

  1. Eskandarian A. Handbook of intelligent vehicles. New York: Springer; 2012. ISBN: 978-0-85729-084-7.
  2. Miculescu D, Karaman S. Polling-systems-based control of high-performance provably-safe autonomous intersections. Proc 53rd IEEE Conference on Decision and Control 2014: 1417-1423. DOI: 10.1109/CDC.2014.7039600.
  3. Zhou F, Li X, Ma J. Parsimonious shooting heuristic for trajectory design of connected automated traffic part I: Theoretical analysis with generalized time geography. Transportation Research Part B: Methodological 2017; 95(C): 394-420. DOI: 10.1016/j.trb.2016.05.007.
  4. Varaiya P. Smart cars on smart roads: Problems of control. IEEE Transactions on Automatic Control 1993; 38(2): 195-207. DOI: 10.1109/9.250509.
  5. Paden B, Cáp M, Yong SZ, Yershov D, Frazzoli E. A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Transactions on Intelligent Vehicles 2016; 1(1): 33-55. DOI: 10.1109/TIV.2016.2578706.
  6. Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik 1959; 1(1): 269-271. DOI: 10.1007/BF01386390.
  7. Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 1968; 4(2): 100-107. DOI: 10.1109/TSSC.1968.300136.
  8. Goldberg A, Harrelson С. Computing the Shortest Path: A Search Meets Graph Theory. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’05) 2005: 156-165.
  9. Geisberger R, Sanders P, Schultes D, Vetter C. Exact routing in large road networks using contraction hierarchies. Transportation Science 2012; 46(2): 388-404. DOI: 10.1287/trsc.1110.0401.
  10. Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF. Route planning in transportation networks. In Book: Kliemann L, Sanders P, eds. Algorithm Engineering. Cham: Springer; 2016: 19-80. DOI: 10.1007/978-3-319-49487-6_2.
  11. Colak S, Lima A, González MC. Understanding congested travel in urban areas. Nat Commun 2016; 7: 10793. DOI: 10.1038/ncomms10793.
  12. Schmitt EJ, Jula H. Vehicle route guidance systems: Classification and comparison. IEEE Intelligent Transportation Systems Conference 2006: 242-247. DOI: 10.1109/ITSC.2006.1706749.
  13. Agafonov AA, Myasnikov VV. Method for the reliable shortest path search in time-dependent stochastic networks and its application to GIS-based traffic control [In Russian]. Computer Optics 2016; 40(2): 275-283. DOI: 10.18287/2412-6179-2016-40-2-275-283.
  14. Desai P, Loke SW, Desai A, Singh J. Multi-agent based vehicular congestion management. 2011 IEEE Intelligent Vehicles Symposium (IV) 2011: 1031-1036. DOI: 10.1109/IVS.2011.5940493.
  15. Wang S, Djahel S, McManis J. A Multi-Agent based vehicles re-routing system for unexpected traffic congestion avoidance. 17th International IEEE Conference on Intelligent Transportation Systems (ITSC) 2014: 2541-2548. DOI: 10.1109/ITSC.2014.6958097.
  16. Dresner K, Stone P. Sharing the road: Autonomous vehicles meet human drivers. IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence 2007: 1263-1268.
  17. Kanamori R, Takahashi J, Ito T. A study of route assignment strategy based on anticipatory stigmergy. Electronics and Communications in Japan 2016; 99(3): 3-12. DOI: 10.1002/ecj.11683.
  18. Wardrop JG. Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institution of Civil Engineers 1952; 1(3): 325-362. DOI: 10.1680/ipeds.1952.11259.
  19. Hasan MR, Bazzan ALC, Friedman E, Raja A. A multiagent solution to overcome selfish routing in transportation networks. IEEE 19th International Conference on Intelligent Transportation Systems (ITSC) 2016: 1850-1855. DOI: 10.1109/ITSC.2016.7795856.
  20. Jahn O, Möhring RH, Schulz AS, Stier-Moses NE. System-optimal routing of traffic flows with user constraints in networks with congestion. Operations Research 2005; 53(4): 600-616. DOI: 10.1287/opre.1040.0197.
  21. Groot N, De Schutter B, Hellendoorn H. Toward system-optimal routing in traffic networks: A reverse stackelberg game approach. IEEE Transactions on Intelligent Transportation Systems 2015; 16(1): 29-40. DOI: 10.1109/TITS.2014.2322312.
  22. Menelaou C, Kolios P, Timotheou S, Panayiotou CG, Polycarpou MP. Controlling road congestion via a low-complexity route reservation approach. Transportation Research Part C: Emerging Technologies 2017; 81: 118-36. doi:10.1016/j.trc.2017.05.005.
  23. Agafonov A, Myasnikov V. Efficiency comparison of the routing algorithms used in centralized traffic management systems. Procedia Engineering 2017; 201: 265-270. DOI: 10.1016/j.proeng.2017.09.617.
  24. Saw K, Katti BK, Joshi G. Literature review of traffic assignment: static and dynamic. International Journal of Transportation Engineering 2015; 2(4): 339-347. DOI:: 10.22119/ijte.2015.10447.
  25. Li J, Chen Q-Y. Speed-density relationship: from deterministic to stochastic. The 88th Transportation Research Board (TRB) Annual Meeting 2009: 1-20.
  26. Transportation Research Board. Highway Capacity Manual. Washington, DC: Transportation Research Board, National Research Council; 2000. ISBN: 0-309-06681-6.
  27. Chakirov A, Fourie PJ. Enriched sioux falls scenario with dynamic and disaggregate demand. ETH Zurich Research Collection 2014. DOI: 10.3929/ethz-b-000080996.
  28. Krajzewicz D, Erdmann J, Behrisch M, Bieker L. Recent Development and applications of SUMO – Simulation of Urban MObility. International Journal on Advances in Systems and Measurements 2012; 5(3&4): 128-138.
  29. Krauss S, Wagner P, Gawron C. Metastable states in a microscopic model of traffic flow. Physical Review E 1997; 55(5): 5597-5602. DOI: 10.1103/PhysRevE.55.5597.
  30. Simulation of Urban MObility. Source: <https://sourceforge.net/projects/sumo/files/traffic_data/scenarios/TAPASCologne/>.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20