PENERAPAN ALGORITMA BRANCH AND BOUND UNTUK OPTIMASI RUTE WISATA DI KALIMANTAN TIMUR BERDASARKAN TRAVELING SALESMAN PROBLEM

Pasia Rande; Stefania Sesilia G. Witin; Welly Dona Permatasari; Nur Aminah; Fidia Deny Tisna Amijaya; Desi Febriani Putri

Authors

Pasia Rande Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia
Stefania Sesilia G. Witin Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia
Welly Dona Permatasari Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia
Nur Aminah Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia
Fidia Deny Tisna Amijaya Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia
Desi Febriani Putri Matematika, FMIPA, Universitas Mulawarman, Samarinda, Indonesia

Abstract

Kalimantan Timur merupakan daerah yang memiliki potensi wisata tinggi, terutama dengan adanya pembangunan Ibu Kota Nusantara (IKN). Untuk mendukung efisiensi kunjungan wisata, dibutuhkan rute perjalanan yang optimal agar waktu dan biaya yang digunakan dapat diminimalkan. Penelitian ini membahas penerapan algoritma Branch and Bound dalam menyelesaikan permasalahan Travelling Salesman Problem (TSP) guna menentukan rute wisata terpendek di Kalimantan Timur. Algoritma ini bekerja dengan prinsip pencabangan dan pembatasan untuk mengevaluasi semua kemungkinan jalur, lalu memilih solusi dengan jarak tempuh minimum. Data jarak antar lokasi wisata diperoleh dari Google Maps, kemudian dimodelkan dalam bentuk graf berbobot tak berarah. Dari hasil penelitian ini diperoleh rute terpendeknya adalah Bandara Sepinggan Balikpapan, Hutan Mangrove Margomulyo, Pantai Melaw, Samboja Lodge, Bukit Bingkirai, Batu Dinding Long Melaha, Taman Ekologis Anang Hasyim, Bandara Sepinggan Balikpapan dengan total jarak tempuh km.