Abstract:
Travelling Salesman Problem (TSP) adalah masalah pencarian rute terpendek atau rute dengan
total jarak minimum oleh seorang salesman dari suatu kota asal ke sejumlah kota lain tepat satu
kali dan kembali ke kota asal. Multiple Travelling Salesman Problem (MTSP) dapat dipandang
sebagai pengembangan atau bentuk umum dari TSP, dimana banyaknya salesman dan kota asal
bisa lebih dari satu.
Permasalahan Multiple Travelling Salesman Problem (MTSP) merupakan permasalahan
optimisasi kombinatorial, yaitu suatu cara yang digunakan untuk mencari semua kemungkinan
nilai real dari suatu fungsi objektif. Dengan kata lain, optimisasi kombinatorial mencari jarak
minimum yang ditempuh salesmen. Algoritma dari optimalisasi kombinatorial digunakan untuk
menyelesaikan masalah yang cukup rumit dan memiliki ruang lingkup yang cukup besar seperti
Multiple Travelling Salesman Problem (MTSP). Beberapa algoritma yang dapat digunakan
untuk permasalahan optimisasi kombinatorial adalah algoritma genetik dan algoritma pencarian
gravitasional.
Algoritma genetik yang mengadopsi proses evolusi makhluk hidup, pada penerapannya
mengikuti langkah pembentukan populasi, menentukan nilai fitness, melakukan proses seleksi,
melakukan pindah silang dan mutasi, dan membentuk individu baru. Populasi yang dibentuk
berisi individu-individu yang berisi urutan kota dan urutan salesmen yang menempuh kota
tersebut. Proses pindah silang dan mutasi akan membuat urutan kota dan urutan salesmen
berubah sehingga menghasilkan individu baru.
Algoritma pencarian gravitasional merupakan algoritma pencari kumpulan partikel yang
berinteraksi satu sama lain. Algoritma ini terinspirasi dari fenomena alam yaitu hukum gravitasi
dan gerak Newton dimana setiap partikel saling tarik menarik dan bergerak menuju partikel
yang terbaik. Implementasi dari algoritma pencarian gravitasional yaitu memilih satu partikel
terbaik yang akan dijadikan acuan terhadap partikel-partikel lain yang kurang baik sehingga
partikel-partikel yang kurang baik tersebut bergerak mendekati partikel terbaik.
Hasil dari penelitian dalam skripsi ini adalah algoritma genetik dan algoritma pencarian
gravitasional dapat diimplementasikan untuk mencari solusi MTSP, yaitu rute minimum yang
dapat ditempuh oleh seluruh salesman. Perangkat lunak sudah diuji fungsionalitasnya dengan
parameter input yang berbeda dan uji eksperimental perangkat lunak menghasilkan solusi yang
mendekati optimal untuk kasus yang dicoba di dalam eksperimen.
