A Systematic Cooperation Method for In-Car Navigation Based on Future Time Windows
Abstract
Traffic congestion has become a severe problem, af-fecting travellers both mentally and economically. To al-leviate traffic congestion, this paper proposes a method using a concept of future time windows to estimate the future state of the road network for navigation. Through our method, we can estimate the travel time not only based on the current traffic state, but the state that ve-hicles will arrive in the future. To test our method, we conduct experiments based on Simulation of Urban MO-bility (SUMO). The experimental results show that the proposed method can significantly reduce the overall travel time of all vehicles, compared to the benchmark Dijkstra algorithm. We also compared our method to the Dynamic User Equilibrium (DUE) provided by SUMO. The experimental results show that the performance of our method is a little better than the DUE. In practice, the proposed method takes less time for computation and is insensitive to low driver compliance: with as low as 40% compliance rate, our method can significantly im-prove the efficiency of the unsignalised road network. We also verify the effectiveness of our method in a signalised road network. It also demonstrates that our method can assign traffic efficiently.
References
Melson CL, Levin MW, Hammit BE, Boyles SD. Dynamic traffic assignment of cooperative adaptive cruise control. Transportation Research Part C: Emerging Technologies. 2018;90: 114–133. doi: 10.1016/j.trc.2018.03.002.
Pi X, Ma W, Qian ZS. A general formulation for multi-modal dynamic traffic assignment considering multi-class vehicles, public transit and parking. Transportation Research Part C: Emerging Technologies. 2019;104: 369–389. doi: 10.1016/j.trc.2019.05.011.
Tajtehranifard H, et al. A path marginal cost approximation algorithm for system optimal quasi-dynamic traffic assignment. Transportation Research Part C: Emerging Technologies. 2018;88: 91–106. doi: 10.1016/j.trc.2018.01.002.
Zhang P, Qian S. Path-based system optimal dynamic traffic assignment: A subgradient approach. Transportation Research Part B: Methodological. 2020;134: 41–63. doi: 10.1016/j.trb.2020.02.004.
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.11362.
Han K, Szeto WY, Friesz TL. Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance. Transportation Research Part B: Methodological. 2015;79: 16–49. doi: 10.1016/j.trb.2015.05.002.
Hoang NH, Vu HL, Panda M, Lo HK. A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network. Transportation Research Part B: Methodological. 2019;126: 329–352. doi: 10.1016/j.trb.2017.11.013.
Lu CC, et al. Eco-system optimal time-dependent flow assignment in a congested network. Transportation Research Part B: Methodological. 2016;94: 217–239. doi: 10.1016/j.trb.2016.09.015.
Daganzo CF. The cell transmission model, part II: Network traffic. Transportation Research Part B: Methodological. 1995;29(2): 79–93. doi: 10.1016/0191-2615(94)00022-R.
Daganzo CF. The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological. 1994;28(4): 269–287. doi: 10.1016/0191-2615(94)90002-7.
Yazici A, Kamga C, Ozbay K. Evaluation of incident management impacts using stochastic dynamic traffic assignment. Transportation Research Procedia. 2015;10: 186–196. doi: 10.1016/j.trpro.2015.09.068.
Zhu F, Ukkusuri SV. A cell based dynamic system optimum model with non-holding back flows. Transportation Research Part C: Emerging Technologies. 2013;36: 367–380. doi: 10.1016/j.trc.2013.09.003.
Carey M, Subrahmanian E. An approach to modelling time-varying flows on congested networks. Transportation Research Part B: Methodological. 2000;34: 157–183. doi: 10.1016/S0191-2615(99)00019-3.
Long J, Szeto WY. Link-based system optimum dynamic traffic assignment problems in general networks. Operations Research. 2019;67(1): 167–182. doi: 10.1287/opre.2018.1775.
Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik. 1959;1(1): 269–271. doi: 10.1016/0042-6989(66)90039-3.
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.
Pan J, Sandu Popa I, Zeitouni K, Borcea C. Proactive vehicular traffic rerouting for lower travel time. IEEE Transactions on Vehicular Technology. 2013;62(8): 3551–3568. doi: 10.1109/TVT.2013.2260422.
D'Andrea E, Marcelloni F. Incident detection by spatiotemporal analysis of GPS data. 2016 IEEE International Conference on Smart Computing (SMARTCOMP). 2016. p. 1–5. doi: 10.1109/SMARTCOMP.2016.7501698.
Xiao Q, He R, Ma C. The analysis of urban taxi carpooling impact from taxi GPS data. Archives of Transport. 2018;47(3): 109–120. doi: 10.5604/01.3001.0012.6514.
Zhang K, Sun DJ, Shen S, Zhu Y. Analyzing spatiotemporal congestion pattern on urban roads based on taxi GPS data. Journal of Transport and Land Use. 2017;10(1): 675–694. doi: 10.5198/jtlu.2017.954.
Kyriakou K, Lakakis K, Savvaidis P, Basbas S. Analysis of spatiotemporal data to predict traffic conditions aiming at a smart navigation system for sustainable urban mobility. Archives of Transport. 2019;52: 27–46. doi: 10.5604/01.3001.0014.0206.
Mnih V, et al. Human-level control through deep reinforcement learning. Nature. 2015;518(7540): 529–533. doi: 10.1038/nature14236.
Silver D, et al. Mastering the game of Go with deep neural networks and tree search. Nature. 2016;529(7587): 484–489. doi: 10.1038/nature16961.
Silver D, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science. 2018;362(6419): 1140–1144. doi: 10.1126/science.aar6404.
Zhou B, Song Q, Zhao Z, Liu T. A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game. Applied Mathematics and Computation. 2020;371: 124895. doi: 10.1016/j.amc.2019.124895.
Koh S, et al. Real-time deep reinforcement learning based vehicle navigation. Applied Soft Computing. 2020;96: 106694. doi: 10.1016/j.asoc.2020.106694.
Lin KW, Hashimoto M, Li YL. Near-future traffic evaluation based navigation for automated driving vehicles considering traffic uncertainties. 2018 19th International Symposium on Quality Electronic Design (ISQED). 2018. p. 425–431. doi: 10.1109/ISQED.2018.8357324.
Szeto WY, Lo HK. Dynamic traffic assignment: Properties and extensions. Transportmetrica. 2006;2(1): 31–52. doi: 10.1080/18128600608685654.
Jayakrishnan R, Tsai WK, Chen A. A Dynamic traffic assignment model with traffic-flow relationships. Transportation Research Part C: Emerging Technologies. 1995;3(1): 51–72. doi: 10.1016/0968-090X(94)00015-W.
Tong CO, Wong SC. A predictive dynamic traffic assignment model in congested capacity-constrained road networks. Transportation Research Part B: Methodological. 2000;34(8): 625–644. doi: 10.1016/S0191-2615(99)00045-4.
Carey M, Ge YE, McCartney M. A whole-link travel-time model with desirable properties. Transportation Science. 2003;37: 83–96. doi: 10.1287/trsc.37.1.83.12819.
Drissi-Kaitouni O. A variational inequality formulation of the Dynamic Traffic Assignment Problem. European Journal of Operational Research. 1993;71(2): 188–204. doi: 10.1016/0377-2217(93)90048-R.
Chen Y, Shafi SY, Chen Y. Simulation pipeline for traffic evacuation in urban areas and emergency traffic management policy improvements through case studies. Transportation Research Interdisciplinary Perspectives. 2020;7: 100210. doi: 10.1016/j.trip.2020.100210.
Koh SS, et al. Reinforcement learning for vehicle route optimization in SUMO. 2018 IEEE 20th International Conference on High Performance Computing and Communications. 2018. p. 1468-1473. doi: 10.1109/HPCC/SmartCity/DSS.2018.00242.
Yang F, Yan X, Xu K. Evacuation flow assignment based on improved MCMF algorithm. 2008 First International Conference on Intelligent Networks and Intelligent Systems. 2008. p. 637–640. doi: 10.1109/ICINIS.2008.70.
Ahrens JH, Dieter U. Computer generation of poisson deviates from modified normal distributions. ACM Transactions on Mathematical Software. 1982;8: 163–179. doi: 10.1145/355993.355997.
Ahrens JH, Dieter U. Computer methods for sampling from gamma, beta, poisson and bionomial distributions. Computing. 1974;12: 223–246. doi: 10.1007/BF02293108.
DUE algorithm from SUMO. https://sumo.dlr.de/docs/Demand/Dynamic_User_Assignment.html#oneshot-assignment [Accessed 5th July 2021].
Webster FV. Traffic Signal Setting, Road Research Technical Paper No. 39. London, England: Department of Scientific and Industrial Research; 1958.
Pseudocode of our algorithm. https://github.com/DeusZero/navigation/tree/main [Accessed 5th July 2021].
Copyright (c) 2022 Peiqun LIN, Chuhao ZHOU, Yang CHENG
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
