PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN METODE TABU SEARCH
Abstract
Travelling Salesman Problem (TSP) merupakan permasalahan yang banyak ditemukan dalam bidang transportasi khususnya masalah perjalanan, yaitu mengunjungi semua lokasi dengan setiap lokasi hanya dikunjungi tepat satu kali. Tujuan dari penyelesaian ini adalah meminimumkan jarak tempuh dan waktu perjalanan sehingga diperoleh rute optimal. Salah satu metode yang digunakan untuk menyelesaikan TSP adalah metode Tabu Search. Tabu Search merupakan salah satu metode heuristik yang berbasis pada pencarian lokal. Proses kinerjanya bergerak dari satu solusi ke solusi berikutnya dengan cara memilih solusi terbaik. Tujuan utama metode ini adalah mencegah proses pencarian agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri. Metode ini menggunakan Tabu List untuk menyimpan sekumpulan solusi yang baru saja dievaluasi, hasilnya akan disesuaikan terlebih dahulu dengan isi pada Tabu List untuk melihat apakah solusi tersebut sudah ada atau tidak. Jika solusi tersebut sudah ada maka solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya. Pada penelitian ini, metode Tabu Search diterapkan pada contoh kasus Salesman PT. XX dalam mengatur rute perjalanannya. Dari hasil perhitungan didapatkan jarak tempuh minimum sebesar 37,8 km dan waktu perjalanan minimum 56,9 menit dengan rute yang dilewati Pos Kota Baru, Pos Gajah Mada, Pos Siantan, Pos Adisucipto, Pos Sei. Raya, dan kembali lagi ke PT. XX.
Kata kunci : rute optimal, metode heuristik
Full Text:
PDFDOI: http://dx.doi.org/10.26418/bbimst.v4i01.9608
Refbacks
- There are currently no refbacks.