Penyelesaian Travelling Salesman Problem Menggunakan Algoritme Ant Colony Optimization dan Particle Swarm Optimization

Abstract

Travelling Salesman Problem (TSP) adalah salah satu permasalahan distribusi yang sering kali ditemui. Penyelesaian dari permasalahan dalam Travelling Salesman Problem ini adalah mencari rute terpendek atau jarak minimum. Terdapat beberapa metode yang dikembangkan untuk menyelesaikan permasalahan ini. Mulai dari metode eksak hingga metode modern atau meta heuristic. Dalam penelitian ini, dua metode heuristik digunakan untuk menyelesaikan Travelling Salesman Problem (TSP), yaitu Particle Swarm Optimization (PSO) dan Ant Colony Optimization (ACO). Solusi yang diperoleh kemudian dibandingkan dengan menggunakan metode eksak dalam bentuk Mixed-Integer Linear Programming (MILP). Hasil yang didapat menunjukkan waktu eksekusi metode Particle Swarm Optimization lebih baik daripada metode Mixed-Integer Linear Programming dan algoritme Ant Colony Optimization (ACO). Namun, ada perbedaan yang mencolok dari ketiga metode dalam total jarak perjalanan.

The Travelling Salesman Problem (TSP) is one of the distribution problems that is often encountered. The solution of TSP is to find the shortest route or minimum distance. Several methods have been developed to solve this problem. Starting from exact methods to modern methods or meta heuristics. In this study, two heuristic methods will be used to solve TSP, Particle Swarm Optimization and Ant Colony Optimization. The solution obtained will be compared with the solution obtained using the exact method in the form of Mixed-Integer Linear Programming (MILP). The results obtained show that the execution time of the Particle Swarm Optimization method is better than the Mixed-Integer Linear Programming method and Ant Colony Optimization algorithm. However, there is a significant difference among the three methods in the total travel distance.