Shortest Path Clustering Dalam Menyaring Tingkat Kepadatan Arus Lalu Lintas
DOI:
https://doi.org/10.30865/jurikom.v10i2.5979Keywords:
Graph Clustering, Shortest Path, Traffic, DBSCAN, Ant AlgorithmAbstract
This study explores the application of graph clustering in identifying and analyzing the shortest traffic-related routes. Graph clustering groups points (vertices) based on road attributes. The DBSCAN method and ant algorithm are applied to classify vertices based on traffic intensity and find the optimal shortest path. This case study focuses on the Tangerang Selatan region, resulting in three clusters and identifying seven noises. Two of the three clusters are selected to calculate the shortest distance, resulting in the sequence [7, 6, 0, 1, 2, 3, 4, 8, 5] and a distance of 0.2526. This research provides insights into how to graph clustering can be used to optimize traffic routes and is expected to serve as a foundation for further exploration
References
F. Daniel and P. N. L. Taneo, Teori Graf, 1st ed. Yogyakarta: Deepublish, 2019.
G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, 6th ed. New York: Chapman and Hall/CRC, 2015. doi: 10.1201/b19731.
K. Pramono, K. Wijaya, W. Cuosman, D. Hartanto, A. Dharma, and S. Wardani, “Shortest Path Search Simulation on Busway Line using Ant Algorithm,†J Phys Conf Ser, vol. 1230, no. 1, p. 12094, Jul. 2019, doi: 10.1088/1742-6596/1230/1/012094.
D. Y. A. Fallo and V. R. Bulu, “Penerapan Algoritma A Star (A*) Pada Game Labirin,†Jurnal Pendidikan Teknologi Informasi (JUKANTI), no. 5, pp. 2621–1467, 2022.
W. Prijodiprodjo, “Penerapan Bee Colony Optimization Algorithm untuk Penentuan Rute Terpendek (Studi Kasus : Objek Wisata Daerah Istimewa Yogyakarta),†IJCCS, vol. 7, no. 1, pp. 65–76, 2013.
N. Selvia, E. W. Ambarsari, and N. Dwitiyanti, “Korelasi Gejala Penyakit Flu Pada Anak Balita Dengan Menggunakan Algoritma Semut,†JITEK, vol. 2, no. 2, pp. 167–174, 2022.
N. Dwitiyanti, S. Wulandari, and N. Selvia, “Implementasi Graph Clustering Algorithm Modification Maximum Standard Deviation Reduction (MMSDR) dalam Clustering Provinsi di Indonesia Menurut Indikator Kesejahteraan Rakyat,†Faktor Exacta, vol. 13, no. 2, p. 73, Aug. 2020, doi: 10.30998/faktorexacta.v13i2.5863.
A. Gahardina and I. Z. Yadi, “Analisis Graph Clustering Terhadap User Behaviour Di Official Account Facebook Universitas Bina Darma Palembang,†in Bina Darma Conference on Computer Science, 2021, pp. 188–198.
R. Liu, S. Feng, R. Shi, and W. Guo, “Weighted graph clustering for community detection of large social networks,†in Procedia Computer Science, 2014, vol. 31, pp. 85–94. doi: 10.1016/j.procs.2014.05.248.
S. Sieranoja and P. Fränti, “Adapting k-means for graph clustering,†Knowl Inf Syst, vol. 64, no. 1, pp. 115–142, Jan. 2022, doi: 10.1007/s10115-021-01623-y.
P. Moradi and M. Rostami, “Integration of graph clustering with ant colony optimization for feature selection,†Knowl Based Syst, vol. 84, pp. 144–161, 2015, doi: https://doi.org/10.1016/j.knosys.2015.04.007.
D. T. Hidayat, C. Fatichah, and R. V. H. Ginardi, “Pengelompokan Data Menggunakan Pattern Reduction Enhanced Ant Colony Optimization dan Kernel Clustering,†Jurnal Nasional Teknik Elektro Dan Teknologi Informasi, vol. 5, no. 3, pp. 155–160, 2016.
U. Boryezka, “Ant Clustering Algorithm,†in Intelligent Information Systems, 2008, pp. 377–386.
O. A. M. Jafar and R. Sivakumar, “Ant-based Clustering Algorithms: A Brief Survey,†International Journal of Computer Theory and Engineering, pp. 787–796, 2010, doi: 10.7763/ijcte.2010.v2.242.
W. Gao, “Improved ant colony clustering algorithm and its performance study,†Comput Intell Neurosci, vol. 2016, 2016, doi: 10.1155/2016/4835932.
S. F. Hussain, I. A. Butt, M. Hanif, and S. Anwar, “Clustering uncertain graphs using ant colony optimization (ACO),†Neural Comput Appl, vol. 34, no. 14, pp. 11721–11738, 2022, doi: 10.1007/s00521-022-07063-1.
H. Jiang, J. Li, S. Yi, X. Wang, and X. Hu, “A new hybrid method based on partitioning-based DBSCAN and ant clustering,†Expert Syst Appl, vol. 38, no. 8, pp. 9373–9381, 2011, doi: https://doi.org/10.1016/j.eswa.2011.01.135.
S. Liu, Z.-T. Dou, F. Li, and Y.-L. Huang, “A new ant colony clustering algorithm based on DBSCAN,†in Proceedings of 2004 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.04EX826), 2004, vol. 3, pp. 1491–1496 vol.3. doi: 10.1109/ICMLC.2004.1382009.
R. Adha, N. Nurhaliza, and U. Soleha, “Perbandingan Algoritma DBSCAN dan K-Means Clustering untuk Pengelompokan Kasus Covid-19 di Dunia,†Jurnal Sains, Teknologi dan Industri, vol. 18, no. 2, pp. 206–211, 2021, [Online]. Available: https://covid19.who.int.
R. Sitanggang and E. Saribanon, “Faktor-Faktor Penyebab Kemacetan di DKI Jakarta,†Jurnal Manajemen Bisnis Transportasi Dan Logistik, vol. 4, no. 3, pp. 289–296, 2018.
