Optimalisasi Rute Traveling Salesman Menggunakan Algoritma Genetika

Yesi Fitria Sari(1*), Muhammad Munsarif(2)


(1) University of Muhammadiyah Semarang
(2) Universitas Muhammadiyah Semarang
(*) Corresponding Author

Abstract


Masalah Traveling Salesman (TSP) bertujuan mencari rute paling efisien bagi seorang salesman yang harus mengunjungi sejumlah kota yang berbeda hanya satu kali sebelum kembali ke titik awal. Penelitian ini menerapkan Algoritma Genetika (AG) sebagai metode optimasi untuk mengatasi TSP, dengan memanfaatkan dataset koordinat lokasi sebagai representasi titik-titik yang harus dikunjungi. Algoritma ini bekerja berdasarkan prinsip seleksi alam, reproduksi, dan mutasi yang memungkinkan pencarian solusi optimal yang meminimalkan jarak tempuh keseluruhan. Penelitian ini juga menganalisis pengaruh parameter AG, seperti ukuran populasi, tingkat crossover, dan tingkat mutasi, terhadap kualitas solusi yang dihasilkan. Hasil eksperimen menunjukkan bahwa dengan pengaturan parameter yang tepat, AG dapat menghasilkan rute yang mendekati optimal secara efisien dan konsisten.

Full Text:

PDF

References


R. M. F. Alves and C. R. Lopes, “Using genetic algorithms to minimize the distance and balance the routes for the multiple Traveling Salesman Problem,” in 2015 IEEE Congress on Evolutionary Computation (CEC), IEEE, May 2015, pp. 3171–3178. doi: 10.1109/CEC.2015.7257285.

B. A. Ajayi, M. A. Magaji, S. Musa, R. F. Olanrewaju, and A. A. Salihu, “A Comparative Analysis of Optimization Heuristics Algorithms as Optimal Solution for Travelling Salesman Problem,” in 2022 5th Information Technology for Education and Development (ITED), IEEE, Nov. 2022, pp. 1–8. doi: 10.1109/ITED56637.2022.10051627.

S. Kavita and S. S. K., “Metaheuristic Evolutionary Algorithms: Types, Applications, Future Directions, and Challenges,” in 2023 3rd International Conference on Intelligent Technologies (CONIT), IEEE, Jun. 2023, pp. 1–6. doi: 10.1109/CONIT59222.2023.10205592.

S. Prayudani, A. Hizriadi, E. B. Nababan, and S. Suwilo, “Analysis Effect of Tournament Selection on Genetic Algorithm Performance in Traveling Salesman Problem (TSP),” J Phys Conf Ser, vol. 1566, no. 1, p. 012131, Jun. 2020, doi: 10.1088/1742-6596/1566/1/012131.

A. M. Aibinu, H. Bello Salau, N. A. Rahman, M. N. Nwohu, and C. M. Akachukwu, “A novel Clustering based Genetic Algorithm for route optimization,” Engineering Science and Technology, an International Journal, vol. 19, no. 4, pp. 2022–2034, Dec. 2016, doi: 10.1016/j.jestch.2016.08.003.

J. Wu and S. Feng, “Improved biogeography-based optimization for the traveling salesman problem,” in 2017 2nd IEEE International Conference on Computational Intelligence and Applications (ICCIA), IEEE, Sep. 2017, pp. 166–171. doi: 10.1109/CIAPP.2017.8167201.

Y.-F. CHEN and X.-H. WU, “Improved Genetic Algorithm for Optimizing TSP Problem,” DEStech Transactions on Social Science, Education and Human Science, no. iced, Nov. 2017, doi: 10.12783/dtssehs/iced2017/15154.

S. Dhouib, “A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1,” International Journal of Recent Engineering Science, vol. 8, no. 1, pp. 6–10, Feb. 2021, doi: 10.14445/23497157/IJRES-V8I1P102.

A. Bertagnon and M. Gavanelli, “Improved Filtering for the Euclidean Traveling Salesperson Problem in CLP(FD),” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 02, pp. 1412–1419, Apr. 2020, doi: 10.1609/aaai.v34i02.5498.

H. Du, Z. Wang, W. Zhan, and J. Guo, “Elitism and Distance Strategy for Selection of Evolutionary Algorithms,” IEEE Access, vol. 6, pp. 44531–44541, 2018, doi: 10.1109/ACCESS.2018.2861760.


Article Metrics

Abstract view : 11 times
PDF - 3 times

DOI: https://doi.org/10.26714/jkti.v3i2.16251

Refbacks

  • There are currently no refbacks.


=======================================================================================

Penerbit:

  • JKTI | Jurnal Komputer dan Teknologi Informasi
  • Program Studi S1 Informatika,  Unimus| Universitas Muhammadiyah Semarang
  • Sekretariat: Gedung Kuliah Bersama II (GKB II) Lantai 7,  Jl. Kedungmundu Raya No 18 Semarang
  • email: informatika@unimus.ac.id, Phone: + +62 813 2504 3677
  • e-ISSN: 2986-7592

Paper Template: Download

View My Stats

------------------------------------------------------------------------------------------------------------------------------------------------------