Modification of Shortest Path Algorithm for Ambulance in Various Road Conditions for Emergency Patients

Abstract

Road conditions and quality can significantly affect ambulance arrival time. Arrival time can be optimized by choosing the shortest route free from potential congestion. Patient safety during the journey is an essential factor that must be considered. Poor road conditions are one of the factors that can affect patient safety. This study aims to provide ambulance navigation by choosing the shortest safe route for emergency patients in various road conditions. The simulation of finding the shortest route using the modified A* algorithm and the Bellman-Ford algorithm to avoid routes with specific road conditions is an essential factor in the success of this study. The performance of the modified A* and Bellman-Ford algorithms was then evaluated by comparing their accuracy with Google Maps. The modified A* algorithm, namely A* Heuristic Modification and Weight Modification (A*-HMWM) achieved a distance accuracy of 90.92% and a travel time accuracy of 87.66%. The modified Bellman-Ford algorithm, namely Bellman-Ford Weight Modification (BF-WM) achieved a distance accuracy of 92.58% and a travel time accuracy of 91.91%. Both algorithms successfully avoided the edge connecting nodes 61 and 166, which are 300 meters apart, with a road width of 3.5 meters and a road condition quality of 75%. The Bellman-Ford algorithm shows better accuracy than the A* algorithm. The A* algorithm presents a more significant opportunity for development due to its flexible heuristic function. With appropriate modifications to the heuristic function, the accuracy performance of the A* algorithm can be improved for various conditions. Further research is needed to assess the algorithm's performance under real-time conditions with dynamic changes in road density.