OPTIMASI RUTE MULTIPLE-TRAVELLING SALESMAN PROBLEM MELALUI PEMROGRAMAN INTEGER DENGAN METODE BRANCH AND BOUND
Abstract
Multiple-Travelling Salesman Problem (m-TSP) merupakan sebuah persoalan
pencarian rute terpendek, untuk sejumlah n kota dan ditambahkan m orang sales yang
berkumpul dan berangkat dari kota yang sama dan selanjutnya n – 1 kota lainnya
dikunjungi tepat satu kali oleh satu orang sales, dan akhirnya semua sales kembali ke
kota asal. Beberapa metode penyelesaian m-TSP telah dikenalkan dan banyak
dikembangkan. Dalam skripsi ini dibahas metode penyelesaian m-TSP yang
diformulasikan dengan pemrograman integer.
Tujuan yang ingin dicapai adalah mendapatkan rute optimal MultipleTravelling
Salesman Problem (m-TSP)
melalui
pemrograman
integer dengan metode
Branch
and Bound.
Langkah-langkah yang dilakukan untuk
mencapai
tujuan tersebut
yaitu
merumuskan
formulasi
pemrograman
integer m-TSP
yang disusun oleh jumlah
kota
(n),
jumlah
sales (m),
dan jumlah minimal
kota yang harus dilewati oleh tiap
sales
(K);
menyelesaikan
pemrograman
linier relaksasi
dari pemrograman
integer mTSP
dengan LPSolve
IDE 5.5.0.5;
dan dilanjutkan langkah optimasi
menggunakan
metode
Branch
and Bound.
Dalam metode Branch and Bound, jika batas atas dan batas bawah bernilai
sama maka didapatkan solusi optimal m-TSP. Solusi optimal m-TSP berupa total
jarak perjalanan terpendek dan rute perjalanan masing-masing sales. Untuk m-TSP 10
kota, 15 kota, dan 20 kota dengan jumlah sales yang divariasikan, solusi optimal
diperoleh jika jumlah sales yang digunakan paling sedikit (2 sales). Dalam
penggunaan sejumlah kota dan sales yang konstan bisa didapatkan nilai K yang tidak
tunggal. Untuk nilai K yang berbeda, pada umumnya diperoleh total jarak perjalanan yang semakin pendek dengan semakin kecilnya nilai K.