SOLUSI PERMASALAHAN GENERALIZED TSP DENGAN ANT COLONY OPTIMIZATION

Abstract

ABSTRACT

Travelling salesman problem is an optimization problems which a salesman travels from starting city visiting several cities and back to starting city again, with a minimum traveled distance and each cities only visited once. Generalized TSP (GTSP) is a variation of TSP, which these n cities partitioned into some groups or clusters, and in each of these groups, exactly one city is visited. ACO algorithm is created based upon a characteristics of real ants, that is a indirect communications between ants and pheromone trails, so that they can find a shortest tour between food source and their nest. These characteristics is used by this algorithm for solving optimization problems, such as TSP etc. This study is reviewing Generalized TSP and these solutions using an Ant Colony Optimization algorithm. Method of this study is conducted by literature study from various sources, both from the books, articles, or journals that are relevant to the study, then explain that concept with an example. From this study noted that ACO formulation for Generalized TSP is slightly different from ACO for TSP , that is a   sets.  in ACO for Generalized TSP is a sets of nodes that are on groups that have not been visited by ant k. From that formulation is tested on 4ulysses16 case, generated a optimal solution that is 50.19336 with a error ratio 0.006886%. It can be concluded that ACO can be applied for solving a Generalized TSP.

Keywords: Travelling Salesman Problem, Generalized TSP, Ant Colony Optimization,  pheromone.

ABSTRAK

Travelling Salesman Problem (TSP) merupakan permasalahan optimisasi dimana seorang sales melakukan perjalanan dari kota awal mengunjungi beberapa kota dan kembali ke kota semula, dengan jarak tempuh yang dilewati minimum dan tiap kota dikunjungi tepat satu kali. Generalized TSP (GTSP) merupakan variasi dari TSP, dimana n kota tersebut dipartisi menjadi beberapa grup atau cluster, dan dalam tiap grup tersebut , tepat satu kota yang dikunjungi. Algoritma ACO dibuat berdasarkan karakteristik tingkah laku semut asli, yaitu komunikasi secara tidak langsung antara para semut dengan jalur pheromone, sehingga mereka dapat menemukan jalur terpendek antara sumber makanan (food) dan sarang mereka. Karasteristik inilah yang digunakan oleh algoritma ini untuk menyelesaikan permasalahan-permasalahan optimasi, misalnya permasalahan TSP dan sebagainya. Penelitian ini mengkaji permasalahan Generalized TSP dan penyelesaiannya dengan menggunakan algoritma Ant Colony Optimization (ACO). Penelitian ini dilakukan dengan cara studi literatur dari berbagai sumber, baik dari buku, artikel maupun jurnal yang relevan dengan penelitian yang dilakukan, kemudian menjelaskan kembali konsep tersebut dengan mengaplikasikannya pada contoh kasus. Melalui penelitian ini diketahui bahwa perumusan ACO untuk Generalized TSP sedikit berbeda dari ACO untuk TSP yaitu pada himpunan .  pada ACO untuk Generalized TSP adalah himpunan titik yang berada pada grup-grup yang belum dikunjungi oleh semut k. Dari perumusan tersebut diujicoba pada kasus 4ulysses16, menghasilkan solusi yang optimal yaitu 50.19336 dengan rasio error 0.006886%. Sehingga dapat disimpulkan ACO dapat diterapkan untuk menyelesaikan permasalahan Generalized TSP .

Kata Kunci: Travelling Salesman Problem, Generalized TSP, Ant Colony Optimization,  pheromone.