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.