47
= 1, jika kota j yang dituju dari kota i
0, sebaliknya
Anggap bahwa
adalah jarak dari kota i
ke kota j, model TSP nya
menjadi seperti :
Minimize z =
=
8 untuk semua i = j
berpokok pada
= 1, i = 1,2, . . . . , n
(1)
= 1, j = 1,2, . . . . , n
(2)
= ( 0, 1)
(3)
Bentuk solusi dari perjalanan n-kota (4)
Batasan (1), (2), dan (3) didefenisikan sebagai model kerja umum. Gambar
2.xx mengambarkan permasalahan 5-kota. Tanda panah menggambarkan
rute 2 arah. Gambar tersebut juga memberikan gambaran solusi perjalanan
dan subtour
dari model kerja yang berhubungan. Jika solusi optimium dari
model kerja (misalnya tidak memasukkan batasan 4) untuk menghasilkan
sebuah perjalanan, berarti menjadi hasil optimum untuk TSP. Sebailknya,
batasan (4) harus diperhitungankan untuk memastikan sebuah solusi
perjalanan.
Beberapa algoritma untuk menghasilkan solusi yang tepat untuk
menyelesaikan permasalahan TSP antara lain
 |