Penerapan Algoritma Cuckoo Search untuk menyelesaikan Probabilistic Traveling Salesman Problem

Abstract

Dalam menentukan harga jual suatu produk, perusahaan harus memperhitungkan semua biaya yang dikeluarkan sampai barang tersebut sampai kepada konsumen. Salah satu biaya yang harus diperhitungkan adalah biaya transportasi. Seperti kita ketahui biaya transportasi umumnya sebanding dengan jarak yang harus ditempuh. Semakin jauh jarak yang harus ditempuh 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 satu kali, tiap kota hanya boleh dikunjungi satu kali, dan salesman harus kembali ke kota asal. Dari batasan tersebut maka 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 diperlukan 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. Bila menggunakan perhitungan eksak maka memerlukan waktu yang lama, sehingga untuk mempersingkat digunakanlah pendekatan heuristic. Pendekatan heuristic yang dipakai dalam penelitian ini adalah Algoritma Cuckoo Search (CS). Algortima ini terinspirasi dari cara burung cuckoo berkembang biak. Dalam penelitian ini selain untuk mencari solusi dari PTSP, penelitian ini juga ingin melihat apakah 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.