46
Problem
dapat dinyatakan sebagai berikut. Seorang sales, memulai dari
sebuah kota, bermaksud untuk mengunjungi setiap kota (n-1) 1 kali dan
hanya 1 kali dan kembali lagi ke kota asal. Permasalahannya adalah
bagaimana menetapkan susunan dalam dimana ia harus mengunjungi kota-
kota tersebut dengan total jarak yang dikunjungi itu minimal, dengan asumsi
bahwa jarak langsung antara semua kota yang berpasangan diketahui. Tidak
hanya jarak yang dapat dihitung, setiap pengukuran efektifitas dapat diganti,
seperti biaya, waktu, dan sebagainya.
Dasar dari permasalahan ini adalah ada berapa kunjungan yang
mungkin (n-1)! dari 1 kunjungan atau lebih yang harus optimal.
Bagaimanapun, bila beberapa kota tidak dapat dilalui, nilai optimal
(minimum) dapat tidak terbatas. Dalam beberapa kasus, dapat diasumsukan
bahwa jarak antara kota i
dan kota lainnya j itu simetris. Oleh karena itu,
jarak antara kota i
ke kota j
adalah sama antara jarak kota j
ke kota i.
Algortima ini disebut dengan algoritma branch and bound, dan pertama kali
dikembangkan oleh Little et al. [41]. Metode ini pertama kali
mengidentifikasi solusi yang layak dan kemudian untuk diuraikan sejumlah
kemungkinan tur yang ada menjadi jumlah yang lebih kecil dan kecil lagi.
(Gracia-Diaz, 1981, p97).
Menurut Taha (2007, p381), permasalahan, pada intinya adalah model
kerja yang mengecualikan subtour. Khususnya, dalam situasi n-kota,
didefinisikan :
 |