PENERAPAN METODE BRANCH AND BOUND PADA PENYELESAIAN MASALAH TRAVELING SALESMAN PROBLEM (TSP )

Traveling Salesman Problem (TSP ) adalah permasalahan pendistribu- sian barang atau jasa yang mengharuskan seseorang mengunjungi setiap tempat dengan mempertimbangkan jarak atau biaya seminimal mungkin. Selain itu TSP merupakan kasus nyata dari graf Hamilton dimana setiap titik harus tepat dile- wati satu kali. Secara umum terdapat dua metode untuk kasus TSP, yaitu metode aproksimasi (pendekatan) dan metode eksak (matematis). Branch and Bound me- rupakan salah satu dari metode eksak. Prinsip dari metode Branch and Bound adalah membagi masalah menjadi sub-sub masalah dan membatasi setiap perca- bangan dengan batas bawah untuk masalah minimalisasi. Traveling Salesman Problem (TSP) is a problem of distribution of goods or services that require a person to visit each place by considering the minimum distance or cost. Besides, TSP is a real case of Hamilton graph where each point must be precisely bypassed once. In general, there are two methods for TSP case, i.e approximation (approach) and exact (mathematics) methods. Branch and Bound is one of the exact method. The principle of Branch and Bound method is divides the problem into subproblems and limits each branching to the lower limit for the minimalization problem