48
1.
Algoritma Heuristic
Algoritma terdiri dari 2 jenis yaitu algoritma the nearest-neighbour
dan
algoritma the subtour-reversal. Algoritma the nearest-neighbour
dapat
dengan mudah diimplementasikan dan algoritma the subtour-reversal
membutuhkan perhitungan komputer. Berdasarkan pengujian, algoritma
the subtour-reversal
dapat memberikan hasil yang lebih baik daripada
algoritma the nearest-neighbour. Namun pada akhirnya, kedua algoritma
ini digabungkan menjadi satu algoritma heuristic, dimana hasil dari
algoritma the nearest-neighbour
digunakan sebagai inputan untuk
algoritma subtour-reversal. ( Taha, 2007, p385). Pada situasi n-kota,
algoritma subtour-reversal heuristic
dimawali dengan perjalanan yang
mungkin dan kemudian dicoba untuk diperbaiki dengan me-reverse
2-
kota subtour, kemudian 3-kota subtour dan berlanjut sampai mencapai n-
1 subtour. (Taha, 2007, p386)
2.
Algoritma Branch-and-Bound
Ide dari algoritma
B&B diawali dengan solusi optimum yang
berhubungan dengan permasalahan penugasan. Jika sebuah solusi adalah
sebuah perjalanan, proses berhenti. Namun sebaliknya, batasan digunakan
untuk menghilangkan subtour. Hasil optimum ini dapat dicapai dengan
membuat
branch
(cabang) sebanyak jumlah variabel
yang
berhubungan dengan salah satu subtour. Setiap branch
atau cabang akan
 |