Penyelesaian Travelling Salesman Problem Menggunakan Algoritma Genetika dan Ant Colony Optimization

Syarifah Elza Ramadhania, Aina Musdholifah, S.Kom., M.Kom., Ph.D.

2024 | Tesis | S2 Ilmu Komputer

Penelitian ini mengusulkan model kombinasi baru dari Algoritma Genetika dan Ant Colony Optimization, yaitu Sequential-GACO, untuk menyelesaikan masalah Traveling Salesman Problem (TSP). Keunggulan utama dari model yang diusulkan adalah untuk meningkatkan kualitas rute TSP dan mengurangi waktu pemrosesan. Sequential-GACO menggunakan GA dan ACO secara berurutan, bukan sebagai hibrid. Eksperimen dilakukan dengan menggunakan tujuh dataset TSP dengan jumlah kota yang berbeda telah dilakukan untuk mengevaluasi kinerja Sequential-GACO. Selain itu, tujuh variasi parameter yang berbeda diamati untuk mengevaluasi dampaknya terhadap hasil optimal pada berbagai dataset TSP. Hasil eksperimen menunjukkan bahwa Sequential-GACO yang diusulkan mengungguli yang lainnya, dalam hal rute terpendek, Sequential-GACO mampu menghasilkan hasil yang jauh lebih baik hingga 20 kali dibandingkan dengan GA. Sequential-GACO yang diusulkan ini dapat digunakan untuk menyelesaikan masalah TSP dengan rute cepat dan optimal, terutama untuk jumlah kota yang besar.

This research proposes a new combination model of the Genetic Algorithm and Ant Colony Optimization, called Sequential-GACO, to solve the Traveling Salesman Problem (TSP). The main advantage of the proposed model is its ability to improve the quality of TSP routes and reduce processing time. Sequential-GACO utilizes GA and ACO sequentially, rather than as a hybrid. Experiments were conducted using seven TSP datasets with varying numbers of cities to evaluate the performance of Sequential-GACO. Additionally, seven different parameter variations were observed to assess their impact on optimal results across various TSP datasets. The experimental results demonstrate that the proposed Sequential-GACO outperforms others; in terms of the shortest route, Sequential-GACO achieves significantly better results—up to 20 times better compared to GA. This proposed Sequential-GACO can be used to solve TSP problems with fast and optimal routes, especially for large numbers of cities.

Kata Kunci : Travelling Salesman Problem, Genetic Algorithm, Ant Colony Optimization