Optimasi Rute Perjalanan Kunjungan Sekolah dengan Menggunakan Algoritma GA
Keywords:
Genetic Algorithm, Travelling Salesman Problem, OpenStreetMap, Directed Graph, Optimasi RuteAbstract
Penelitian ini bertujuan untuk mengoptimalkan rute perjalanan kunjungan sekolah di Kota Palembang menggunakan Algoritma Genetika berbasis data jaringan jalan nyata dari OpenStreetMap. Dataset yang digunakan terdiri dari 187 sekolah dengan titik awal perjalanan berada di Gedung Sudirman UMDP. Permasalahan dimodelkan sebagai Travelling Salesman Problem (TSP) dengan mempertimbangkan jaringan jalan berbentuk directed graph sehingga mampu merepresentasikan kondisi lalu lintas satu arah dan konektivitas jalan secara realistis. Untuk mengurangi kompleksitas ruang solusi, dilakukan strategi proximity-based clustering dengan membagi sekolah ke dalam beberapa kelompok berdasarkan kedekatan geografis sebelum proses optimasi dilakukan. Algoritma Genetika diimplementasikan menggunakan kombinasi Order Crossover (OX), swap mutation, dan seleksi elitis dengan parameter 50 generasi dan ukuran populasi sebanyak 20 individu. Hasil penelitian menunjukkan bahwa sistem berhasil memetakan seluruh sekolah ke dalam 37 rute kunjungan dengan total jarak akumulatif sebesar 648,51 km dan rata-rata 17,53 km per rute. Algoritma menunjukkan performa optimal dengan rata-rata pencarian solusi terbaik yang mengonvergi pada generasi ke-5. Penggunaan data jaringan jalan nyata memberikan representasi rute yang lebih akurat dibandingkan pendekatan jarak Euclidean karena mampu memperhitungkan aturan jalan satu arah dan konektivitas asimetris. Sistem yang dibangun berpotensi dikembangkan sebagai alat bantu pengambilan keputusan bagi instansi pendidikan dalam menyusun jadwal dan rute kunjungan sekolah secara lebih terstruktur, efisien, dan terdokumentasi.
References
Agusnur, A. (2025). Optimasi Penjadwalan Produksi dengan Algoritma Genetika. In Jurnal Teknologi dan Informatika Indonesia (Vol. 01, Number 01). http://pustakajurnal.web.id/index.php/jtii
Alanzi, E., & Menai, M. E. B. (2025). Solving the traveling salesman problem with machine learning: a review of recent advances and challenges. Artificial Intelligence Review, 58(9). https://doi.org/10.1007/s10462-025-11267-x
Atwal, K. S., Anderson, T., Pfoser, D., & Züfle, A. (2022). Predicting building types using OpenStreetMap. Scientific Reports, 12(1), 19976. https://doi.org/10.1038/s41598-022-24263-w
Boeing, G. (2025). Modeling and Analyzing Urban Networks and Amenities With OSMnx. Geographical Analysis, 57(4), 567–577. https://doi.org/https://doi.org/10.1111/gean.70009
Ciepliński, P., & Golak, S. (2024). Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm. Applied Sciences, 14(24). https://doi.org/10.3390/app142411786
Dama Alfatikhy, S., Rahman, Z. U., Dinova, K., Zahran, F. A., & Surya Wardhana, A. (2025). Optimasi Parameter Kalibrasi Sensor MEMS Menggunakan Algoritma Genetika dengan Validasi Sistem Pakar. In Shavina Dama Alfatikhy, SNTEM (Vol. 5).
Huang, Z., Liao, X., Naik, P. A., & Lu, X. (2024). On approximating a new generalization of traveling salesman problem. Heliyon, 10(10). https://doi.org/10.1016/j.heliyon.2024.e31297
Khoirush, M., Mahfuzh, S., Tinggi, S., & Dirgantara, T. (2025). Optimasi Trajektori Penerbangan UAV Untuk Misi Pengintaian Berbasis Algoritma Genetika.
Lambora, A., Gupta, K., & Chopra, K. (2019). Genetic Algorithm- A Literature Review. 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), 380–384. https://doi.org/10.1109/COMITCon.2019.8862255
Passos, N. A. R. A., Carlini, E., & Trani, S. (2025). NetworkX-Temporal: Building, manipulating, and analyzing dynamic graph structures. SoftwareX, 31, 102277. https://doi.org/https://doi.org/10.1016/j.softx.2025.102277
mustika, Reza Wahyudin, A., & Pujianto, P. (2025). Penerapan Algoritma Genetika sebagai Metode Optimasi Sistem Penjadwalan Perkuliahan. SEMNASTIK - APTIKOM 2025, 1(1), 149–157. Retrieved from https://ojssemnastik2025.aptikomlampung.id/index.php/semnastik2025/article/view/70
Rahman, M. A., Nazib, K. M., Islam, M. R., & Ali, L. E. (2025). Solving Traveling Salesman Problem Through Genetic Algorithm with Clustering. International Journal of Intelligent Systems and Applications, 17(3), 15–33. https://doi.org/10.5815/ijisa.2025.03.02
Setiawan, I. H., Abdillah, J. M., Al Izzy, M. F., Dipa Aditia, K., & Surya Wardhana, A. (2025). Optimasi Penempatan Sensor Gas pada Tanki Penyimpanan Minyak Menggunakan Algoritma Genetika. In SNTEM (Vol. 5).
Tawanda, T., Nyamugure, P., Kumar, S., & Munapo, E. (2023). A Labelling Method for the Travelling Salesman Problem. Applied Sciences (Switzerland), 13(11). https://doi.org/10.3390/app13116417
Wang, J., Xiao, C., Wang, S., & Ruan, Y. (2023). Reinforcement learning for the traveling salesman problem: Performance comparison of three algorithms. The Journal of Engineering, 2023(9). https://doi.org/10.1049/tje2.12303
