PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA BRANCH AND BOUND - Yogo dwi prasetyo (Universitas Asahan, 2017)
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 ﬁrst search, exhaustive search.