Bi-Weighted Graph-Based Optimal Path Selection for a Network

Laxminarayan Sahoo¹ , Rakhi Das² , Sovan Samanta³

1. Dept. of Computer and Information Science, Raiganj University, Raiganj-733134, India.
2. Dept. of Computer and Information Science, Raiganj University, Raiganj-733134, India.
3. Dept. of Mathematics, Tamralipta Mahavidyalaya, Tamluk-721636, India.

Section:Research Paper, Product Type: Journal-Paper
Vol.10 , Issue.4 , pp.1-8, Aug-2023

Online published on Aug 31, 2023

Copyright © Laxminarayan Sahoo, Rakhi Das, Sovan Samanta . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

165 Views    203 Downloads    39 Downloads

Abstract :
With the aid of the Bi-Weighted Graph concept, this research attempts to determine the most effective path (optimal path) for a transportation network. Identifying the most effective path (a low-risk path over the network that traverses the shortest or nearly shortest distance) from a source node to the destination node is commonly referred to as optimal path selection. We have used a kind of shortest path algorithm known as the Dijkstra Algorithm to select the shortest path. Here, we have utilized the risk matrix to determine the risk of the path in a network. Due to risk factors that we commonly ignore, it sometimes becomes apparent that the shortest path is not always the most effective or "best path" of a network. Therefore, we have considered a path`s risk factor in this study when figuring out the best network path. The road network system has been imitated in this paper utilizing the idea of a bi-weighted graph, and the shortest path through it has been identified. In this scenario, we have used an actual transportation network for illustration purposes and the estimated outcomes have been presented.

Key-Words / Index Term :
Shortest path algorithm, Bi-weighted graph, Optimal Path, Risk matrix

References :
[1]. A. Conca, C. Ridella, & E. Sapori, “A Risk assessment for road transportation of dangerous good: A routing solution." Transportation Research Procedia, Vol.14, pp.2890-2899, 2016.
[2]. Md. A. Javaid, “Understanding Dijkstra’s Algorithm. Member Vendor Advisory Council,” CompTIA, pp.1-27, 2013.
[3]. Y. Y. Win, H. S. Hlaing, T. T. Thein, “Shortest Path Analysis Based on Dijkstra`s Algorithm in Myanmar Road Network”, International Journal of Research, Vol. 6, Issue 10, pp.132-139, 2019.
[4]. E. W. Dijkstra, “A note on Two Problems in Connexion with Graphs”, Numerische mathematic, Vol. 1, Issue 1, pp.269–271, 1959.
[5]. D.C. Lee, “Proof of a modified Dijkstra`s algorithm for computing shortest bundle delay in networks with deterministically time-varying links”, IEEE Communications Letters, Vol. 10, Issue 10, pp.734-736, 2006.
[6]. S. Samanta, V. K. Dubey, K. Das, “Coopetition bunch graph: Competition and cooperation COVID-19 research”, Information science, Vol. 589, pp.1-33, 2022.
[7]. H. Wang, Q. Liang, “Risk Analysis and Route Optimization of Dangerous Goods Transportation Based on the Empirical Path Set”, Journal of Advanced Transportation, Vol.2020, pp. 1-13, 2020.
[8]. P. Cassini, “Road transportation of dangerous goods: quantitative risk assessment and route comparison”, Journal of Hazardous Materials, Vol. 6, Issue (1–3), pp.133–138, 1998.
[9]. P. Serafini, “Dynamic programming and minimum risk paths”, European Journal of Operational Research, Vol 175 Issue 1, pp.224-237, 2006.
[10]. N. J. Duijm, “Recommendations on the use and design of risk matrices”. Department of Management Engineering, Vol 76, pp.21-31, 2015.
[11]. M. W. Adler, J. V. Ommeren, P. Rietveld, “Road congestion and incident duration”. Economics of Transportation, Vol 2, Issue 4, pp.109–118, 2013.
[12]. C. Shew, A. Pande, C. Nuworsoo, “Transfer ability and robustness of real-time freeway crash risk assessment”. Journal of Safety Research, Vol 46, pp.83–90, 2013.
[13]. J. Yang, F. Li , J. Zhou, L. Zhang, L. Huang, J. Bi, “A survey on hazardous materials accidents during road transport in China from 2000 to 2008”. Journal of Hazardous Material. Vol 184, pp.647–653, 2010.
[14]. R. Kumar, S. A. Edalatpanah, & H. Mohapatra, “Note on Optimal path selection approach for fuzzy reliable shortest path problem”, Journal of Intelligent & Fuzzy System, Vol 32, Issue 1, pp.1-3, 2020.
[15]. Md. Z. Alam, I. Adhicandra, & A. Jamalipour, “Optimal best path selection algorithm for cluster-based multi-hop MIMO cooperative transmission for vehicular communications”. IEEE Transactions on Vehicular Technology, 1–1, 2019.
[16]. T. Korkmaz, M. Krunz, “Multi-constrained optimal path selection, EEE Computer and Communications Society (Cat. No.01CH37213), Vol 2, pp.834–843, 2001.
[17]. M. Zhou, N. Gao, “Research on Optimal Path based on Dijkstra Algorithms”, Advances in Computer Science Research, Vol 87, pp.884-891, 2019.
[18]. S. Peyera, D. Rautenbach, J. Vygen, “A generalization of Dijkstra`s shortest path algorithm with applications to VLSI routing”. Journal of Discrete Algorithm. Vol 7, Issue 4, pp.377–390, 2009.
[19]. L. Meng, Z. Hu, C. Huang, W. Zhang, T. Jia, “Optimized Route Selection Method Based on the Turns of Road Intersections: A Case Study on Oversized Cargo Transportation”. ISPRS International Journal of Geo-Information, Vol 4, Issue 4, pp.2220-9964, 2015.
[20]. M. Elmontsri, “Review of the strengths and weaknesses of risk matrices”, Journal of Risk Analysis and Crisis Response, Vol 4, Issue 1, pp.49-57, 2014.
[21]. Y. Z. Chen, S. F. Shen, T. Chen, R. Yang “Path Optimization Study for Vehicles Evacuation Based on Dijkstra algorithm”, Procedia Engineering, Vol 7, pp.159 – 165, 2014.
[22]. S. Mathew, & M. S. Sunitha, “Cycle connectivity in weighted graphs”, Proyecciones Journal of Mathematics, Vol 30, Issue 1, pp.1-17, 2011.
[23]. A. S, Markowski, & M. S, Mannan, “Fuzzy risk matrix. Journal of hazardous materials”. Vol 159, Issue 1, pp.152-157, 2008.
[24]. S. Kukadapwar, D. Parbat, “Estimation of optimal path on urban road networks using AHP algorithm”. International Journal for Traffic and Transport Engineering, Vol 6, Issue 1, pp.13–24, 2016.
[25]. T. Korkmaz, M. Krunz, “Multi-constrained optimal path selection”. IEEE Computer and Communications Society, Vol 2, pp.834–843, 2001.
[26]. M. Zhou. & N. Gao. “Research on Optimal Path based on Dijkstra Algorithms”, Journal of Nanchang Institute of Technology, pp.30-33, 2019.
[27]. M. Zhou, & Z. Zhang, “Optimal Route Selection Decision-Making Based on Intelligent Network”, Journal of Mathematics, Vol 2021, pp.1-14, 2021.
[28]. W. Wei, F. Gao, R. Scherer, R. Damasevicius, D. Po?ap, “Design and Implementation of Autonomous Path Planning for Intelligent Vehicle”. Journal of Internet Technology, Vol 22, pp.957-965, 2021.
[29]. J. B, Orlin, K. Madduri, K, Subramani, & M. Williamson, “A faster algorithm for the single source shortest path problem with few distinct positive lengths”. Elsevier, Vol 8, pp.189-198, 2010.
[30]. M. Thorup, “Undirected single source shortest paths in linear time”, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.2–21, 1997.
[31]. U. Meyer, “Single-source shortest-paths on arbitrary directed graphs in linear average-case time”, Proceedings of the Twelfth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA-01), pp. 797–806, 2001.
[32]. D. K. Malviya, N. Malviya, “Survey on implementation of graph theory in routing protocols of wired computer network”, International Research Journal of Engineering and Technology (IRJET), Vol 5, Issue 12, pp.325-330, 2018.
[33]. A. Fitriansyah, N. W. Parwati, D. R. Wardhani, N. Kustian, “Dijkstra`s Algorithm to Find Shortest Path of Tourist Destination in Bali”. Journal of Physics: Conference Series, Vol 1338, pp. 1-8, 2019.
[34]. R. Das, L. Sahoo, S. Samanta, V. Simic, T. Senapati, “Identifying the Shortest Path of a Semidirected Graph and Its Application”. Mathematics, MDPI, Vol 10, Issue 24, pp.4807, 2022.
[35]. B. Mishra, “A Purview and the inter-relations of Fuzzy Sets, Intuitionistic Fuzzy Sets, Rough Sets, and their Extensions”, IJSRMSS, Vol.9, Issue.6, pp.43-49, Dec-2022.
[36]. S.A. Mithy, S. Hossain, S. Akter, U. Honey, S.B. Sogir, “Classification of Iris Flower Dataset using Different Algorithms”, IJSRMSS, Vol.9, Issue.6, pp.1-10, Dec-2022.
[37]. K. Das, S. Samanta, M. Pal, “Study on centrality measures in social networks: a survey”, Social Network Analysis and Mining, Vol.8, Issue 1, pp. 2-11, 2018.
[38]. S Samanta, VK Dubey, B Sarkar, “Measure of influences in social networks”, Applied Soft Computing, Vol. 99, Issue. 106858, pp. 1-42, 2020.