AMFC: A New Approach Efficient Junctions Detect via Maximum Flow Approach

Year 2023, , 1054 - 1068, 28.12.2023

Furkan Öztemiz

https://doi.org/10.17798/bitlisfen.1325877

Abstract

In this study, max flow analysis processes are carried out with a graph theory-based approach that can be used in optimizing the traffic load in transportation networks. The data used in the study consists of 2 years of vehicle number data consisting of 438 million vehicle passes of a real city. Bottleneck points affecting traffic flow, maximum flow values, and effectiveness values of traffic generating and attracting locations were determined in the uniquely created transportation network. The Ford-Fulkerson algorithm was used to determine the maximum flow and bottleneck road connections in the designed transportation network. According to the maximum traffic flow to the junction point, the most effective junction points were determined by the PageRank algorithm. In addition, a unique algorithm is presented in the study that determines the effective intersection points that transfer vehicle traffic at maximum capacity to all junction points according to the maximum demand capacity data.

Keywords

Maximum Flow, Ford-Fulkerson Algorithm, Maximum Road Capacity, Transport Network, Graph Theory

References

• [1] S. Si̇ddi̇qui̇ and Ş. G. Eren, “The analysis of the sustainability pillars of Karachi city’s transportation system,” Mimar. Bilim. ve Uygulamaları Derg. (MBUD), pp. 181–190, 2022.
• [2] F. Öztemi̇z and A. Karci̇, “Topluluk Tespiti Yöntemi ile Ulaşım Ağında Verimli Yeşil Dalga Koridorlarının Belirlenmesi,” Politeknik Dergisi, pp. 1–1, 2023.
• [3] A. Erath, M. Löchl, and K. W. Axhausen, “Graph-theoretical analysis of the Swiss road and railway networks over time,” Netw. Spat. Econ., vol. 9, no. 3, pp. 379–400, 2009.
• [4] Z. Yi, X. C. Liu, N. Markovic, and J. Phillips, “Inferencing hourly traffic volume using data-driven machine learning and graph theory,” Comput. Environ. Urban Syst., vol. 85, no. 101548, p. 101548, 2021.
• [5] D. Granata, R. Cerulli, M. G. Scutellà, and A. Raiconi, “Maximum flow problems and an NP-complete variant on edge-labeled graphs,” in Handbook of Combinatorial Optimization, New York, NY: Springer New York, 2013, pp. 1913–1948.
• [6] D. Blazek, O. Blazekova, and M. Vojtekova, “Analytical model of road bottleneck queueing system,” Transp. Lett., vol. 14, no. 8, pp. 888–897, 2022.
• [7] A. R. Mahlous, R. J. Fretwell, and B. Chaourar, “MFMP: Max Flow Multipath Routing Algorithm,” in 2008 Second UKSIM European Symposium on Computer Modeling and Simulation, 2008.
• [8] A. Akhmediyarova, D. Kassymova, A. Utegenova, and I. Utepbergenov, “Development and research of the algorithm for determining the maximum flow at distribution in the network,” Open Comput. Sci., vol. 6, no. 1, pp. 213–218, 2016.
• [9] E. J. Moore, W. Kichainukon, U. Phalavonk, “Maximum flow in road networks with speed-dependent capacities – application to Bangkok traffic,” Songklanakarin Journal of Science and Technology (SJST), vol. 35, 489-499, 2013.
• [10] A. Ngaosai and J. Chawachat, “Traffic signal management using maximum flow approach for consecutive intersections,” in 2018 15th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), 2018.
• [11] X. Sun, Z. Bai, K. Lin, P. Jiao, and H. Lu, “Optimization model of traffic sensor layout considering traffic big data,” J. Adv. Transp., vol. 2020, pp. 1–11, 2020.
• [12] M. G. H. Bell, F. Kurauchi, S. Perera, and W. Wong, “Investigating transport network vulnerability by capacity weighted spectral analysis,” Trans. Res. Part B: Methodol., vol. 99, pp. 251–266, 2017.
• [13] V. Torrisi, M. Ignaccolo, and G. Inturri, “Analysis of road urban transport network capacity through a dynamic assignment model: validation of different measurement methods,” Transp. Res. Procedia, vol. 27, pp. 1026–1033, 2017.
• [14] C. Li, W. Yue, G. Mao, and Z. Xu, “Congestion propagation based bottleneck identification in urban road networks,” IEEE Trans. Veh. Technol., vol. 69, no. 5, pp. 4827–4841, 2020.
• [15] S. Kamishetty, S. Vadlamannati, and P. Paruchuri, “Towards a better management of urban traffic pollution using a Pareto max flow approach,” Transp. Res. D Transp. Environ., vol. 79, no. 102194, p. 102194, 2020.
• [16] N. Abdullah, T. Hua, “Traffic Congestion Problem In Kota Kinabalu, Sabah Using Ford-Fulkerson Algorithm And Max Flow-Min Cut Theorem,” International Conference on Business, Tourism & Technology, Port Dickson, Negeri SembilanVolume: 2, 2017.
• [17] Y. Gao, Z. Qu, X. Song, and Z. Yun, “Modeling of urban road network traffic carrying capacity based on equivalent traffic flow,” Simul. Model. Pract. Theory, vol. 115, no. 102462, p. 102462, 2022.
• [18] A. Chen and P. Kasikitwiwat, “Modeling capacity flexibility of transportation networks,” Transp. Res. Part A Policy Pract., vol. 45, no. 2, pp. 105–117, 2011.
• [19] R. Ghanbari, M. Jalili, and X. Yu, “Analysis of cascaded failures in power networks using maximum flow based complex network approach,” in IECON 2016 - 42nd Annual Conference of the IEEE Industrial Electronics Society, 2016.
• [20] M. Bulut and E. Özcan, “Optimization of electricity transmission by Ford–Fulkerson algorithm,” Sustain. Energy Grids Netw., vol. 28, no. 100544, p. 100544, 2021.
• [21] Y. M. Omar and P. Plapper, “Maximum flow of complex manufacturing networks,” Procedia CIRP, vol. 86, pp. 245–250, 2019.
• [22] Y.-C. Tu, M. C. Chen, and Y. S. Sun, “A two-stage link scheduling scheme for variable-bit-rate traffic flows in wireless mesh networks,” IEEE Trans. Wirel. Commun., vol. 13, no. 11, pp. 6232–6244, 2014.
• [23] W. Wang, Y. Zhang, Y. Li, C. Liu, and S. Han, “Vulnerability analysis of a natural gas pipeline network based on network flow,” Int. J. Pressure Vessels Piping, vol. 188, no. 104236, p. 104236, 2020.
• [24] H. Su, E. Zio, J. Zhang, and X. Li, “A systematic framework of vulnerability analysis of a natural gas pipeline network,” Reliab. Eng. Syst. Saf., vol. 175, pp. 79–91, 2018.
• [25] T. Werho, V. Vittal, S. Kolluri, and S. M. Wong, “Power system connectivity monitoring using a graph theory network flow algorithm,” IEEE Trans. Power Syst., vol. 31, no. 6, pp. 4945–4952, 2016.
• [26] M. Du, X. Jiang, and A. Chen, “Identifying critical links using network capacity-based indicator in multi-modal transportation networks,” Transp. B Transp. Dyn., vol. 10, no. 1, pp. 1126–1150, 2022.
• [27] İ. Akgün, B. Ç. Tansel, and R. Kevin Wood, “The multi-terminal maximum-flow network-interdiction problem,” Eur. J. Oper. Res., vol. 211, no. 2, pp. 241–251, 2011.
• [28] Maksimum Flow, Retrieved from https://www.scaler.com/topics/data-structures/ford-fulkerson-algorithm-for-maximum-flow-problem/. January 3, 2023.
• [29] J. Kleinberg, and É. Tardos, Algorithm Design. Pearson Education, 337–411. isbn: 0-321-29535-8, 2006.
• [30] S. Långström, E. Frıdsäll, “Optimizing Traffic Flow On Congested Roads,” Stockholm, Degree Project In Electronics And Computer Engineering, Fırst Cycle, 2019.
• [31] J. Yuan, E. Bae, and X.-C. Tai, “A study on continuous max-flow and min-cut approaches,” in 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010.
• [32] T. Mukherjee, I. Sangal, B. Sarkar, and T. M. Alkadash, “Mathematical estimation for maximum flow of goods within a cross-dock to reduce inventory,” Math. Biosci. Eng., vol. 19, no. 12, pp. 13710–13731, 2022.
• [33] A. R. Mahlous, R. J. Fretwell, and B. Chaourar, “MFMP: Max Flow Multipath Routing Algorithm,” in 2008 Second UKSIM European Symposium on Computer Modeling and Simulation, 2008.
• [34] F. Öztemi̇z, “Sinyalizasyon Verileri Ile Malatya Kenti Ulaşim Aği Kavşak Noktalarinin Merkezlilik Analizi,” Computer Science, 2021.
• [35] F. Öztemi̇z and A. Karci̇, “Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım,” Deu Muhendis. Fak. Fen Ve Muhendis., vol. 24, no. 70, pp. 143–155, 2022.
• [36] F. Öztemi̇z and A. Karci̇, “Malatya İli ulaşım ağı kavşak noktalarının merkezlilik analizi,” Gazi Üniv. Mühendis.-Mimar. Fak. Derg., 2021