Penyelesaian Multiple Traveling Salesman Problem dengan menggunakan Hybrid Gravitational Algorithm

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.