TARGET BERORIENTASI METODE CABANG DAN BATAS UNTUK OPTIMISASI GLOBAL

Abstract

Abstrak: Fokus utama dari penulisan ini adalah pencarian metode terbaik untuk menyelesaikan permasalahan traveling salesman problem dengan menggunakan solusi masalah clique maksimum dengan menggunakan metode cabang dan batas. Permasalahan TSP (Traveling Salesman Problem) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal. Tujuannya adalah menentukan rute dengan jarak total atau biaya yang paling minimum. Permasalahan TSP merupakan permasalahan yang memang mudah untuk diselesaikan dengan algoritma Brute Force, tetapi hal itu hanya dapat dilakukan dengan jumlah kota atau simpul yang tidak banyak. Oleh karena itu, dalam penelitian ini akan dikaji pencarian penyelesaian masalah TSP dengan menggunakan masalah clique maksimum dengan menggunakan metode cabang dan batas.

Kata kunci: Traveling Salesman Problem, Cabang dan Batas