Comparison of dijkstra and genetic algorithms for shortest path guci
DOI:
https://doi.org/10.35335/mandiri.v13i1.298Keywords:
Algorithm Performance, Dijkstra Algorithm, Genetic Algorithm, Optimization, Shortest PathAbstract
This study aims to compare the performance of the Dijkstra algorithm and the Genetics algorithm in determining the shortest path to the Guci tourist destination. The research design combines experimental methods, quantitative analysis, and model validation. The data used is the distance between points on two alternative routes to Guci. Data pre-processing is done to ensure quality and consistency. The relevant variables are selected, and model optimization is performed to obtain the best parameter configuration for both algorithms. Dijkstra and Genetics algorithms are implemented using Python, taking into account computational efficiency and ease of integration. Model evaluation is done through a series of tests with time execution and convergence metrics. The results showed that Dijkstra's algorithm was superior in finding the shortest path with a distance of 43.0 km and an execution time of 0.0017 seconds, compared to the Genetics algorithm which found a path with a distance of 44.7 km and an execution time of 0.0048 seconds. It can be concluded that Dijkstra's algorithm is more effective and efficient in this case, but Genetics algorithms have the potential for more complex optimization problems.
References
Abbas, M. T., Muhammad, A., & Song, W.-C. (2020). SD-IoV: SDN enabled routing for internet of vehicles in road-aware approach. Journal of Ambient Intelligence and Humanized Computing, 11(3), 1265–1280.
Afero, Y. (2021). Algoritma Best First Search Menentukan Lintasan Jalur Terpendek Pada Kota Wisata Bukittinggi. JOISIE (Journal Of Information Systems And Informatics Engineering), 5(2), 138–145. https://doi.org/10.35145/joisie.v5i2.1717
Aminzadegan, S., Shahriari, M., Mehranfar, F., & Abramović, B. (2022). Factors affecting the emission of pollutants in different types of transportation: A literature review. Energy Reports, 8, 2508–2529.
Chen, H., Nie, F., Wang, R., & Li, X. (2022). Unsupervised feature selection with flexible optimal graph. IEEE Transactions on Neural Networks and Learning Systems.
Chen, Z.-G., Zhan, Z.-H., Kwong, S., & Zhang, J. (2022). Evolutionary computation for intelligent transportation in smart cities: A survey. IEEE Computational Intelligence Magazine, 17(2), 83–102.
Deng, W., Xu, J., Song, Y., & Zhao, H. (2021). Differential evolution algorithm with wavelet basis function and optimal mutation strategy for complex optimization problem. Applied Soft Computing, 100, 106724.
Fragapane, G., De Koster, R., Sgarbossa, F., & Strandhagen, J. O. (2021). Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda. European Journal of Operational Research, 294(2), 405–426.
Liu, C., Feng, Y., Lin, D., Wu, L., & Guo, M. (2020). Iot based laundry services: an application of big data analytics, intelligent logistics management, and machine learning techniques. International Journal of Production Research, 58(17), 5113–5131.
Liu, L., Wang, X., Yang, X., Liu, H., Li, J., & Wang, P. (2023). Path planning techniques for mobile robots: Review and prospect. Expert Systems with Applications, 120254.
Llopis-Albert, C., Rubio, F., & Valero, F. (2021). Impact of digital transformation on the automotive industry. Technological Forecasting and Social Change, 162, 120343.
Merghadi, A., Yunus, A. P., Dou, J., Whiteley, J., ThaiPham, B., Bui, D. T., Avtar, R., & Abderrahmane, B. (2020). Machine learning methods for landslide susceptibility studies: A comparative overview of algorithm performance. Earth-Science Reviews, 207, 103225.
Nan, G., Liu, Z., Du, H., Zhu, W., & Xu, S. (2023). Transmission Line-Planning Method Based on Adaptive Resolution Grid and Improved Dijkstra Algorithm. Sensors, 23(13), 6214.
Pai, C.-K., Liu, Y., Kang, S., & Dai, A. (2020). The role of perceived smart tourism technology experience for tourist satisfaction, happiness and revisit intention. Sustainability, 12(16), 6592.
Pradeep Reddy, G., Kumar, Y. V. P., Kalyan Chakravarthi, M., & Flah, A. (2022). Refined Network Topology for Improved Reliability and Enhanced Dijkstra Algorithm for Optimal Path Selection during Link Failures in Cluster Microgrids. Sustainability (Switzerland), 14(16). https://doi.org/10.3390/su141610367
Qadir, Z., Ullah, F., Munawar, H. S., & Al-Turjman, F. (2021). Addressing disasters in smart cities through UAVs path planning and 5G communications: A systematic review. Computer Communications, 168, 114–135.
Shah, K. J., Pan, S.-Y., Lee, I., Kim, H., You, Z., Zheng, J.-M., & Chiang, P.-C. (2021). Green transportation for sustainability: Review of current barriers, strategies, and innovative technologies. Journal of Cleaner Production, 326, 129392.
Streimikiene, D., Svagzdiene, B., Jasinskas, E., & Simanavicius, A. (2021). Sustainable tourism development and competitiveness: The systematic literature review. Sustainable Development, 29(1), 259–271.
Suanpang, P., Jamjuntr, P., Jermsittiparsert, K., & Kaewyong, P. (2022). Tourism service scheduling in smart city based on hybrid genetic algorithm simulated annealing algorithm. Sustainability, 14(23), 16293.
Sunita, & Garg, D. (2021). Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue. Journal of King Saud University - Computer and Information Sciences, 33(3), 364–373. https://doi.org/10.1016/j.jksuci.2018.03.003
Wang, X., Zhang, H., Liu, S., Wang, J., Wang, Y., & Shangguan, D. (2022). Path planning of scenic spots based on improved A* algorithm. Scientific Reports, 12(1), 1320.
Wang, Z., & Sobey, A. (2020). A comparative review between Genetic Algorithm use in composite optimisation and the state-of-the-art in evolutionary computation. Composite Structures, 233, 111739.
Zhang, H., Huang, R., Zhang, Y., & Buhalis, D. (2022). Cultural ecosystem services evaluation using geolocated social media data: A review. Tourism Geographies, 24(4–5), 646–668.
Zheng, W., Liao, Z., & Lin, Z. (2020). Navigating through the complex transport system: A heuristic approach for city tourism recommendation. Tourism Management, 81, 104162.
Zhou, G., Zhu, Z., & Luo, S. (2022). Location optimization of electric vehicle charging stations: Based on cost model and genetic algorithm. Energy, 247, 123437. https://doi.org/10.1016/j.energy.2022.123437
Zhu, D. D., & Sun, J. Q. (2021). A New Algorithm Based on Dijkstra for Vehicle Path Planning Considering Intersection Attribute. IEEE Access, 9, 19761–19775. https://doi.org/10.1109/ACCESS.2021.3053169
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Sarif Surorejo, Muhammad Raikhan Al Fattah, Wresti Andriani, Gunawan Gunawan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
