Floyd-Warshall Application for the Shortest Route Search in a Traffic Accident Notification App

  • Haniah Mahmudah Politeknik Elektronika Negeri Surabaya
  • M. Fajar Ibrahim Politeknik Elektronika Negeri Surabaya
  • Okkie Puspitorini Politeknik Elektronika Negeri Surabaya
  • Ari Wijayanti Politeknik Elektronika Negeri Surabaya
  • Nur Adi Siswandari Politeknik Elektronika Negeri Surabaya
Keywords: Traffic Accidents, Android Apps, Floyd-Warshall Algorithm, Black Box

Abstract

In the case of an accident, a prompt response is needed to prevent accidents or provide assistance to traffic accident victims. Several ways can be carried out to address this problem. One of them is by developing several smartphone applications for accident detection and accident notification that provide aid in traffic accidents. The existing application to assist the victims merely presents the shortest route from the respondent to the victim’s location without any features that help the respondent find a route to the nearest hospital and police station. Therefore, this study develops a smartphone application for accident alerts for victims’ relatives and respondents, which assists in locating the victim’s position and the closest hospitals and police stations. This accident notification app for smartphones utilizes open-source software and is very scalable. The outcome of this study is an Android application capable of sending accident notification broadcasts, allowing the victim’s relatives and respondents to get accident notifications and drive to the accident place using the route given by the application. In addition, the developed app also provides information about the location of the nearest hospital and police station, allowing respondents nearby the location to help the victim promptly. The results of testing the application using the black box method on the Android platform indicated that 100% of the features of this application were running well. The shortest route with the Floyd-Warshall algorithm was 4.199 km, with no route deviations from the distance testing scenario. The average speed of notification delivery response from victims to respondents was 27.86 ms.

References

E. Lesmana et al., “The Application of Floyd-Warshall Algorithm in Solving Shortest Path Problem for Fire Evacuation System at High Rise Building (Case Study at eL Royale Hotel Bandung),” 9th Int. Conf. Ind. Eng., Oper. Manag., 2019, pp 2169–2178.

R. Bhoraskar, N. Vankadhara, B. Raman, and P. Kulkarni, “Wolverine: Traffic and Road Condition Estimation Using Smartphone Sensors,” 2012 Fourth Int. Conf. Commun. Syst., Netw. (COMSNETS 2012), 2012, pp. 1–6.

P. Mohan, V.N. Padmanabhan, and R. Ramjee, “TrafficSense: Rich Monitoring of Road and Traffic Conditions Using Mobile Smartphones”, Proc. 6th ACM Conf. Embed. Netw. Sensor Syst., pp 323–336, 2008.

S. Sharma and S. Sebastian, “IoT Based Car Accident Detection and Notification Algorithm for General Road Accidents,” Int. J. Elect., Comput. Eng. (IJECE), Vol. 9, No. 5, pp. 4020–4026, Oct. 2019.

S. Farhan, S. Andryana, and N. Hayati, “Implementasi Bellman-Ford dan Floyd-Warshall dalam Menentukan Jalur Terpendek Menuju Universitas Nasional Berbasis Android”, J. Ilm. Penelit., Pembelaj. Inform. (JIPI), Vol. 5, No.2, pp. 123–132, Dec. 2020.

F.W. Ningrum and T. Andrasto, “Penerapan Algoritma Floyd-Warshall dalam Menentukan Rute Terpendek pada Pemodelan Jaringan Pariwisata di Kota Semarang,” J. Tek. Elekt., Vol. 8, No. 1, pp. 21–24, Jan.-Jun. 2016.

K. Manaf, et al., “Designing Futsal Match Finder Application with Floyd-Warshall,” J. Phys.: Conf. Ser., Vol. 1280, No. 2, pp. 1–8, Nov. 2019.

V.A. Nawagusti, “Penerapan Algoritma Floyd Warshall dalam Aplikasi Penentuan Rute Terpendek Mencari Lokasi BTS (Base Tower Station) pada PT. GCI Palembang,” J. Nas. Teknol., Sist. Inf., Vol. 4, No. 2, pp. 81–88, Aug. 2018.

B.I.A. Prasetyo and A. Maslan, “Analisis Perbandingan pada Algoritma Bellman Ford dan Dijkstra pada Google Map,” Khazanah Ilmu Berazam, Vol. 3, No. 2, pp. 337–349, 2020.

N.R. Chopde and M.K. Nichat, “Landmark Based Shortest Path Detection by Using A* and Haversine Formula,” Int. J. Innov. Res. Comput., Commun. Eng., Vol. 1, No. 2, pp. 298–302, Apr. 2013.

Ramadiani, D. Bukhori, Azainil, and N. Dengen, “Floyd-Warshall Algorithm to Determine the Shortest Path Based on Android,” 2018 IOP Conf. Ser.: Earth Environ. Sci., Vol. 144, pp. 1-8, May 2018.

K. Gutenschwager, S. Völker, A. Radtke, and G. Zeller, “The Shortest Path: Comparison of Different Approaches and Implementations for the Automatic Routing of Vehicles,” Proc. 2012 Winter Simul. Conf. (WSC), 2012, pp. 3312-3323.

M. Kairanbay and H.M. Jani,”A Review and Evaluations of Shortest Path Algorithms,” Int. J. Sci., Technol. Res., Vol. 2, No. 6, pp. 99-104, Jun. 2013

U.E. Chukwuka, J.A. Oladunjoye, and S. Emmanuel, “A Study of Intelligent Route Guidance System Using Dijkstra's Heuristic Shortest Path Algorithm,” Int. J. Inf. Technol., Innov. Africa, Vol. 13, No. 2, pp. 1-23, Apr. 2018.

S. Sanan, L. Jain, and B. Kappor, “Shortest Path Algorithm,” Int. J. Appl., Innov. Eng., Manag. (IJAIEM), Vol. 2, No. 7, pp. 316-320, Jul. 2013.

M. Gł ̨abowski, B. Musznicki, P. Nowak, and P. Zwierzykowski, “Efficiency Evaluation of Shortest Path Algorithms,” AICT 2013: The Ninth Adv. Int. Conf. Telecommun., 2013, pp. 154-160.

P. Charoenporn, “Comparison of Algorithms for Searching Shortest Path and Implementations for the Searching Routing System via Web Services,” Proc. 2018 the 8th Int. Workshop Comput. Sci., Eng. (WCSE 2018), 2018, pp. 516-520.

R. Kampf, O. Stopka, L. Bartuška, and K. Zeman, “Circulation of Vehicles as an Important Parameter of Public Transport Efficiency,” Proc. 19th Int. Conf. Transp. Means, 2015, pp. 143-146.

W. Xing et al., “An Improved Savings Method for Vehicle Routing Problem”, 2016 2nd Int. Conf. Control Sci., Syst. Eng. (ICCSSE), 2016, pp. 1-4.

Y.Z. Mehrjerdi, “A Multiple Objective Stochastic Approach to Vehicle Routing Problem,” Int. J. Adv. Manuf. Technol., Vol. 74, pp. 1149-1158, Sep. 2014.

M. Stanojevic, B. Stanojevic, and M. Vujoševic, “Enhanced Savings Calculation and Its Applications for Solving Capacitated Vehicle Routing Problem,” Appl. Math., Comput., Vol. 219, No. 20, pp. 10302-10312, Jun. 2013.

Published
2022-11-15
How to Cite
Haniah Mahmudah, M. Fajar Ibrahim, Okkie Puspitorini, Ari Wijayanti, & Nur Adi Siswandari. (2022). Floyd-Warshall Application for the Shortest Route Search in a Traffic Accident Notification App. Jurnal Nasional Teknik Elektro Dan Teknologi Informasi, 11(4), 251-257. https://doi.org/10.22146/jnteti.v11i4.2201
Section
Articles