PENYELESAIAN MULTIPLE-TRAVELLING SALESMAN PROBLEM DENGAN SIMULATED ANNEALING

Abstract

Travelling Salesman Problem (TSP) adalah permasalahan perjalanan seorang salesman yang harus mengunjungi n buah kota tepat satu kali dan pada akhirnya harus kembali ke kota awal dengan mempertimbangkan biaya perjalanan. Pada saat ini banyak perusahaan berskala besar maupun yang masih dalam tahap berkembang memiliki lebih dari satu orang sales yang siap mendistribusikan barang perusahaan ke konsumen, dimana jumlah kota yang harus dilalui sangat banyak. Oleh karena itu, diperlukan pendekatan penyelesaian untuk permasalahan yang kompleks tersebut agar TSP dapat diselesaikan secara efisien. Salah satu pendekatan untuk menyelesaikan persoalan tersebut dengan menggunakan Multiple Travelling Salesman Problem (m-TSP). m-TSP dapat diselesaikan dengan metode heuristik salah satunya yaitu Simulated Annealing. Metode ini beranalogi pada proses annealing (pendinginan) yang diterapkan dalam pembuatan material glassy (butir kristal). Kebanyakan metode heuristik yang digunakan yaitu menerima solusi baru yang lebih baik, namun pada metode Simulated Annealing solusi baru yang lebih buruk kadang-kadang dapat diterima, sehingga solusi dapat terhindar dari maksimum lokal. Tujuan yang ingin dicapai dalam penulisan skripsi ini adalah mendapatkan rute optimal dari perjalanan sales-sales melalui Simulated Annealing. Hasil penelitian ini diharapkan dapat memberikan alternatif penyelesaian m-TSP sehingga dapat dijadikan pertimbangan untuk bidang usaha yang menerapkan m-TSP dalam aktivitas kerjanya. Data yang digunakan adalah data primer berupa waktu tempuh perjalanan antar kecamatan dan data sekunder berupa jumlah kecamatan yang dikunjungi dan jumlah sales. Penelitian dilaksanakan dalam 4 tahap, yaitu (i) mengidentifikasi wilayah kerja sales yang berupa jumlah kecamatan, waktu tempuh antar kecamatan, dan jumlah sales, (ii) mengaplikasikan Simulated Annealing untuk mencari rute optimal dalam penyelesaian m-TSP, (iii) membuat algoritma pemrograman dari masalah tersebut, dan (iv) membuat program menggunakan software PHP. Program tersebut dapat digunakan untuk data yang berbeda pada semua permasalahan m-TSP. Input dari program tersebut adalah banyak kota, banyak salesman, matriks waktu, dan parameter bebas untuk menentukan berapa banyak iterasi yang dilakukan. Dari hasil program tersebut, didapatkan rute perjalanan salesman dengan waktu tempuh optimal. Pada metode Simulated Annealing pemilihan solusi awal, desain dari neighbourhood atau solusi tetangga, dan pemilihan nilai parameter bebas sangat berpengaruh dalam memperoleh solusi optimal dengan waktu tempuh perjalanan yang minimum.