Best Response Dynamics for Collective Route optimization
Keywords:
Best response dynamics, collaborative routes, Nash equilibrium, shortest path problem, traffic behavior modeling, traffic vehicular congestionAbstract
Urban traffic congestion remains a critical challenge for modern cities, impacting travel efficiency, environmental sustainability, and quality of life. This paper introduces the Collective Optimization Scheme (COS), a collaborative routing framework that integrates Best Response Dynamics with Dijkstra’s algorithm to promote cooperative decision-making among drivers. Unlike traditional navigation systems that optimize routes individually, COS computes routes that account for prevailing congestion conditions and aim to minimize the total travel time across all trips. The proposed approach is evaluated through extensive simulations on real-world urban maps, demonstrating substantial reductions in travel time particularly under low to moderate congestion levels. These results highlight COS as a scalable and effective strategy for sustainable congestion management and improved urban mobility.
Downloads
References
F. Ahmad and L. Al-Fagih, ”Game theory applications in micro and macroscopic simulations in transportation networks: A comprehensive review,” IEEE Access, 2023, doi: 10.1109/ACCESS.2023.3308048
I. Alvarez, A. Poznyak, and A. Malo Tamayo, ”Urban traffic control problem: A game theory approach,” Proc. IEEE Conf. Decision and
Control, 2008, pp. 2168–2172, doi: 10.1109/CDC.2008.4739461
L. Alvarez, P. Behrisch, M. Bieker-Walz, L. Erdmann, J. Fl¨otter¨od, Y. Hilbrich, R. L¨ucken, L. Rummel, J. Wagner, and P. Wießner,
”Microscopic traffic simulation using SUMO,”2019 IEEE Intelligent Transportation Systems Conf. (ITSC), 2019, pp. 2575–2582, doi:
1109/ITSC.2018.8569938
A. Choudhary, S. Gokhale, P. Kumar, C. Pradham, and S. Sahu, ”Urban traffic congestion: Its causes, consequences, and mitigation,” Research Journal of Chemistry and Environment, vol. 26, no. 12, pp. 164–176, 2022, doi: 10.25303/2612rjce1640176
T. Cabannes, M. Sangiovanni, A. Keimer, and A. Bayen, ”Regrets in routing networks: Measuring the impact of routing apps on traffic,” ACM Trans. Spatial Algorithms and Systems, vol. 5, no. 2, Article 9, 2019, doi: 10.1145/3325916
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, ”Introduction to Algorithms”, MIT Press, 2009, ISBN: 978-0-262-03384-8, doi:
5555/1614191
Roger A. McCain, ”Game Theory: A Nontechnical Introduction to the Analysis of Strategy, Revised Edition”, World Scientific Publishing Company, New Jersey, August 2010, 632 p´aginas; ISBN: 978-981-4289658; doi: 10.1142/7517
J. Hofbauer and K. Sigmund, ”Evolutionary Games and Population Dynamics,” Cambridge University Press, 1998, ISBN: 9781139173179,
doi: 10.1017/CBO9781139173179
J. Arsanjani, A. Zipf, et al., ”An introduction to OpenStreetMap in geographic information science: Experiences, research, and applications”, Springer, 2015, doi: 10.1007/978-3-319-14280-7 1
D. Large, G. Burnett, S. Benford, and K. Oliver, ”Crowdsourcing good landmarks for in-vehicle navigation systems,” Behaviour & Information Technology, pp. 806–816, 2016, doi: 10.1080/0144929X.2016.1158317
Z. Li, I. V. Kolmanovsky, E. M. Atkins, J. Lu, D. P. Filev, and Y. Bai, ”Road disturbance estimation and cloud-aided comfort-based route
planning,” IEEE Trans. Cybernetics, vol. 47, no. 11, pp. 3879–3891, 2017, doi: 10.1109/TCYB.2016.2587673
B. Li, D. Saad, and A. Y. Lokhov, ”Reducing urban traffic congestion due to localized routing decisions,” Physical Review Research, vol. 2, p. 032059, 2020, doi: 10.1103/PhysRevResearch.2.032059
D. Lanning, ”Dijkstra’s algorithm and Google Maps,” in Proc. 2014 ACM Southeast Regional Conf., 2014, doi: 10.1145/2638404.2638494
T. Lei, S. Wang, J. Li, and F. Yang, ”A cooperative route choice approach via virtual vehicle in IoV,” Vehicular Communications, pp. 281–287, 2017, doi: 10.1016/j.vehcom.2017.05.001
S. Liu and Q. Qiang, ”Dynamic collective routing using crowdsourcing data,” Transportation Research Part B: Methodological, vol. 93, pp. 450–469, 2016, doi: 10.1016/j.trb.2016.08.005
J. F. Nash, ”Equilibrium points in N-person games,” Proc. National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950, doi:
1073/pnas.36.1.48
M. J. Osborne and A. Rubinstein, ”A Course in Game Theory”, MIT Press, 1994, ISBN: 0-262-15041-7, doi: 10.2307/136062
H. Peters, ”Game Theory: A Multi-leveled Approach”,Springer, 2015, doi: 10.1007/978-3-662-46950-7
M. N. Prasad, N. Dimitrov, and E. Nikolova, ”Non-Aggressive Adaptive Routing in Traffic,” Mathematics, vol. 11, no. 17, p. 3639, 2023, doi: 10.3390/math11173639
R. Ravish and S. Rangaswamy, ”Intelligent traffic management: A review of challenges, solutions, and future perspectives,” Transport and Telecommunication, vol. 22, no. 2, pp. 163–182, 2021, doi: 10.2478/ttj-2021-0013
T. Roughgarden, ”Algorithmic Game Theory,” Communications of the ACM, pp. 78–86, 2010, doi: 10.1145/1785414.1785439
C¸ olak, S., Lima, A., Gonz´alez, M., ”Understanding congested travel in urban areas”, Nat Commun 7, 10793 (2016), doi: 10.1038/ncomms10793
M. Treiber and A. Kesting, ”Representation of Cross-Sectional,” in Traffic Flow Dynamics, Springer, 2013, pp. 25–36, doi: 10.1007/978-3-642-32460-4
J. G. Wardrop, ”Some theoretical aspects of road traffic research,” Proc. Institution of Civil Engineers, vol. 1, no. 2, pp. 325–378, 1952, doi: 10.1680/ipeds.1952.11362
J. Yasel, N. Casta˜no, and F. Jhon, ”Optimization based on multi-type ants for the Traveling Salesman Problem,” in Computing
Colombian Conf. (9CCC), Pereira, Colombia, 2014, doi: 10.1109/ColumbianCC.2014.6955338
P. H. Young, ”Strategic Learning and its Limits”,Oxford University Press, 2005, doi: 10.1093/acprof:oso/9780199269181.001.0001
