PENYELESAIAN TRAVELLING SALESMAN PROBLEM (TSP) DENGAN METODE BRANCH AND BOUND

Abstract

Penelitian ini bertujuan menerapkan metode Branch and Bound dalam penyelesaian Travelling Salesman Problem terhadap rute pengangkutan barang di Kantor Pos Palembang. Fungsi tujuan yang ingin dicapai adalah menentukan rute terpendek dari Kantor Pos Pemeriksa (KPRK) ke tiap Kantor Pos Cabang (KPC) dan kembali ke Kantor Pos Pemeriksa. Setiap Kantor Pos Cabang hanya dilalui sekali. Solusi yang diperoleh berupa bilangan biner, dimana 0 menyatakan solusi tidak optimal dan 1 menyatakan solusi optimal. Hasil yang diperoleh terdapat 2 rute pengangkutan untuk masing-masing wilayah, dimana total jarak terpendek untuk wilayah A adalah 24,3 km dan wilayah B adalah 27,5 km.

Katakunci: Travelling Salesman Problem, Branch and Bound, Biner