PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA BRANCH AND BOUND

Yogo dwi prasetyo

Abstract


Pencarian rute terpendek oleh seorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awal keberangkatan merupakan salah satu masalah optimisasi kombinatorial. Travelling Salesman Problem (TSP) dapat diselesaikan dengan algoritma branch and bound yang menggunakan skema Breadth First Search (BFS) yang lebih pintar yaitu menggunakan fungsi pembatas bound untuk menentukan simpul yang diperluas (branch). Keakuratan penyelesaian optimal bergantung pada fungsi pembatas yang dipilih. Fungsi pembatas dipilih berdasarkan instinc dan pengalaman sehingga terkadang tidak memberikan hasil yang optimal. Algoritma ini bisa menjadi pilihan dalam menyelesaikan optimisasi kombinatorial jika dipandang dari aspek waktu penyelesaiannya.

 

Kata kunci:  travelling salesman problem, algoritma branch and bound, optimisasi kombinatorial, breadth first search, exhaustive search.


Full Text:

PDF

References


Bayram, H. dan Sahin, R. 2013. ”A New Simulated Annealing Approach for Travelling Sales-man Problem”, Mathematical and computational Appli-cations, 18 (3): 313 – 322

Brualdi, R.A. 2010. Introductory Combinatorics, Fifth Edition. Pearson Education, Inc., Prentice Hall.

Munawar, H. 2007. Penerapan Algoritma Branch and Bound dalam Optimasi Assignment Problem. Bandung: STEI-ITB.

Riyanti, E. 2004. Penerapan Algoritma Branch and Bound untuk Penentuan Rute Objek Wisata. Jakarta: UNIKOM.

Salaki, D.T. dan Rindengan, A. J. 2010. Optimasi Rute Distribusi Barang dengan Menggunakan Metode Heuristik. Jurnal Ilmiah Sains. 10 (1); 75 – 80




DOI: https://doi.org/10.36294/jmp.v1i2.143

Refbacks

  • There are currently no refbacks.