Penerapan Algoritma Cuckoo Search untuk menyelesaikan Probabilistic Traveling Salesman Problem

Abstract

Dalam menentukan harga jual suatu produk, perusahaan harus memperhitungkan semua biaya yang dikeluarkan. Salah satu biaya adalah biaya transportasi. Biaya transportasi umumnya sebanding dengan jarak yang harus ditempuh. Semakin jauh jarak maka biaya yang dibutuhkan semakin besar. Oleh karena itu jarak yang ditempuh harus diminimasi agar biaya transportasi dapat diminimasi juga. Traveling Salesman Problem (TSP) dapat memodelkan pencarian jarak tempuh terkecil. TSP adalah permasalahan salesman yang harus pergi ke beberapa kota dengan total jarak seminimal mungkin dengan syarat setiap kota harus dikunjungi, tiap kota hanya boleh dikunjungi satu kali, dan salesman harus kembali ke kota asal. Dari batasan tersebut, harus dibuat suatu rute yang dapat menghasilkan total jarak terkecil. Namun pada dunia nyata dalam sekali pengiriman terkadang tidak semua kota harus dikunjungi, hal tersebut dikarenakan setiap kota memiliki peluangnya sendiri-sendiri secara independen untuk dikunjungi. Maka dari itu dipakai model perhitungan yang dapat memperhitungkan jarak dan peluang tiap kota untuk dikunjungi. Model turunan TSP, yaitu Probabilistic Traveling Salesman Problem (PTSP) dapat digunakan dalam masalah ini. PTSP bertujuan menghasilkan suatu template rute agar menghasilkan expected length terkecil sehingga dapat memberikan estimasi total jarak yang ditempuh. Dengan adanya probabilitas tiap kota dan jumlah kota yang tidak sedikit maka akan ada banyak kombinasi rute yang mungkin muncul dan harus dihitung. Pendekatan metaheuristic dipakai untuk memecahkan PTSP dan metaheuristic yang dipakai adalah Algoritma Cuckoo Search (CS). Dalam penelitian ini selain untuk mencari solusi dari PTSP, penelitian ini juga ingin melihat apakah rancangan algoritma ini lebih baik dari beberapa algoritma yang sudah pernah dipakai sebelumnya yaitu BA (Adya, 2015) dan DA (Lilian, 2016). Selain itu akan diuji parameter apa saja yang berpengaruh dalam algoritma CS ini. Dari hasil penelitian, CS tidak dapat menghasilkan solusi yang lebih baik dibandingkan dengan BA dan DA. Sedangkan paramaeter yang berpengaruh secara umum pada performansi algoritma adalah parameter jumlah sarang.