Penyelesaian Asymmetric Travelling Salesman Problem dengan Particle Swarm Optimization, Ant Colony System, dan Genetic Algorithm

Abstract

Asymmetric Travelling Salesman Problem (ATSP) merupakan varian dari Travelling Salesman Problem (TSP) yang dimana jarak dari kota X ke kota Y dengan jarak dari kota Y ke kota X dapat berbeda. ATSP dapat diselesaikan dengan dua metode, yakni metode eksak dan metode pendekatan (metode heuristic dan metaheuristic). Pada penelitian ini, ATSP diselesaikan menggunakan metode metaheuristic. Tujuan penelitian ini adalah menyelesaikan ATSP dengan Particle Swarm Optimization (PSO), Ant Colony System (ACS), dan Genetic Algorithm(GA), melihat pengaruh parameter dari ketiga algoritme tersebut, dan membandingkan ketiga algoritme dengan metode eksak. Bahasa pemrograman yang digunakan yaitu Python. Hasil yang diperoleh menunjukkan bahwa setiap parameter baik parameter PSO, ACS, dan GA memiliki pengaruh terhadap solusi yang didapatkan. Algoritme ACS lebik baik dalam memperoleh solusi yang mendekati solusi eksak dibandingkan algoritme PSO dan GA. Namun, algoritme PSO lebih baik dalam waktu komputasinya dibandingkan algoritme lainnya.

Asymmetric Travelling Salesman Problem (ATSP) is a variant of the Travelling Salesman Problem (TSP) where the distance from city X to city Y and the distance from city Y to city X can be different. ATSP can be solved by two methods, namely the exact method and approximation method (heuristic and metaheuristic method). In this study, ATSP solved using metaheuristic method. The purpose of this study is to solve ATSP with Particle Swarm Optimization (PSO), Ant Colony System (ACS), and Genetic Algorithm (GA), to see the effect of PSO, GA, and ACS parameters, and compare PSO, GA, and ACS with the exact method. The programming language used is Python. The result obtained show that each PSO, ACS, and GA parameter has an influence on the solution obtained. The distance obtained by the ACS algorithm is closer to the exact distance than PSO and GA. However, computation time of the PSO algorithm is better than other algorithms.