IMPLEMENTASI METODE ANT COLONY UNTUK TRAVELING SALESMAN PROBLEM MENGGUNAKAN GOOGLE MAPS PADA KOTA-KOTA DI JAWA TENGAH

Abstract

Tujuan penelitian ini adalah mengimplementasikan metode Ant Colony untuk Traveling Salesman Problem (TSP) dengan memanfaatkan Google Maps studi kasus pada kota-kota di Jawa Tengah. Algoritma Ant System yang merupakan salah satu algoritma Ant Colony Optimization (ACO) digunakan untuk membangun sebuah rute yang optimal untuk Traveling Salesman Problem pada Google Maps. Dari hasil pengujian untuk inputan kota kurang dari 10, algoritma Ant System mampu memberikan hasil yang optimal. Sedangkan untuk inputan kota lebih dari 10, algoritma Ant System tidak mampu memberikan hasil yang optimal. Oleh karena itu untuk menambah kinerja algoritma Ant System ditambahkan algoritma Local Search 2opt. Perbandingan hasil perjalanan yang dihasilkan kedua algoritma Ant System sebelum dan setelah ditambah dengan algoritma Local Search 2-opt juga dibandingkan dengan algoritma Greedy. Hasil pengujian menunjukan algoritma Ant System Local Search mempunyai bobot jarak dan waktu tempuh yang paling kecil dari dua algoritma yang lain, serta jalur Traveling Salesman Problem yang dibangun optimal. Pada hasil waktu komputasi dalam perhitungan jalur Traveling Salesman Problem, algoritma Greedy membutuhkan waktu komputasi yang paling sedikit dibandingkan dengan algoritma Ant System dan Ant System Local Search.

The purpose of this study was to implemented Ant Colony method to solve the Traveling Salesman Problem (TSP) using Google Maps on cities of Central Java. Ant System algorithm is one of the Ant Colony Optimization (ACO) algorithm to determine the optimum route on Google Maps and solves Traveling Salesman Problem. Based on results for 10 cities input, the Ant System algorithm can solves optimum route, the otherwise where input is more than 10 cities it can’t solve optimum route. Therefore to improve performance of Ant System algorithm, the Local Search 2-opt algorithm added to Ant System algorithm. The comparison of the results of route optimum construction both algorithm, that shows the Ant System algorithm with Local Search 2-opt have the best minimum cost tour. And the best results of computation time was produced by Greedy algorithm.