Travelling Salesman Problem

Traveling Salesman Problem (TSP) adalah permasalahan untuk mencari rute terpendek yang dapat dilalui untuk mengunjungi beberapa kota tanpa harus mendatangi kota yang sama lebih dari satu kali.

1.      Nearest Neightbour Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan total jarak terpendek. Metode ini sangat sederhana dan lebih banyak digunakan daripada metode lain yang dalam menyelesaikan masalah TSP. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dari lintasan.

2. Pilih titik dengan sisi yang terkait yang memiliki bobot minimum.

3. Dari titik baru, pilih titik yang belum terpilih pada lintasan dengan bobot sisi minimum. 
4. Kembali lakukan langkah 3 sampai semua titik telah termuat dalam lintasan. Selanjutnya hubungkan titik awal dengan titik akhir sehingga terbentuk sikel.
 

 2. Cheapest Insertion Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan jumlah bobot yang minimum. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dan siklus S hanya terdiri dari titik awal tersebut.

2. Cari titik j di luar S sehingga Cij minimum dan membentuk sikel tertutup {(i, j), (j, i)}.

3. Pemilihan. Cari titik k (bukan dalam sikel) yang terdekat ke sembarang titik di S.

4. Penyimpanan. Cari sisi (i, j) dalam sikel dengan Cik + Ckj – Cij yang memiliki nilai minimum, masukkan k di antara i dan j sehingga diperoleh (i, k) dan (k, j).

5. Jika sikel telah terisi oleh semua titik maka terbentuklah sikel Hamilton sehingga iterasi berhenti.

3. Metode Koloni Semut

Algoritma Koloni Semut terinspirasi oleh tingkah laku semut pada saat mencari makan.Intinya adalah komunikasi tak langsung antar semut. Semut memiliki zat khusus yang disebut pheromone, yang digunakan oleh semut untuk memeberikan jejak pada jalan yang dilewati,dan juga sebagai komunikasi antar semut. Semut akan memilih salah satu jalan, yaitu jalan yang terdapat banyak pheromone yang menunjukkan bahwa jalan tersebut banyak dilewati oleh semut lain, sehingga akan lebih cepat untuk mencapai sumber makanan dan kembali ke sarang. Pembahasan dari algoritma Koloni Semut untuk menyelesaikan masalah Travelling Salesman Problem (TSP), adalah sebagai berikut:

a.       bi (t) (i=1,2,3,… n) adalah banyaknya semut pada kota I dalam waktu t.

b.      m =  adalah jumlah semua semut pada semua kota dalam waktu t.

c.       di j adalah jarak lintasan yang menghubungkan antara kota i dan kota j

adalah intensitas lintasan sisi (I,j) dalam waktu t.

Masing-masing semut pada waktu t akan memilih kota berikutnya, sehingga waktunya akan menjadi t+1. Yang dimaksud 1 iterasi dari algoritma Koloni Semut ini adalah satu kali perjalanan pergi-pulang yang dilakukan oleh satu semut pada interval (t, t+1), dan intensitas lintasan akan diperbaharui dengan rumus, dengan adalah koefisien penguapan lintasan antara waktu t dan t+n, nilai (0 <1). n= 1,2,…,q, dengan q adalah banyaknya rute yang mungkin dilewati  =  , dengan adalah banyaknya pheromone yang ditinggalkan oleh k-semut pada sisi (I,j) dalam waktu t dan t+n,

Q adalah konstanta relatif banyaknya lintasan yang dilewati oleh semut, nilai Q € (0, 10, 100, 1000) dan Lk panjang sisi yang dibuat oleh k-semut. Hasil yang diharapkan adalah rute terpendek yang diperoleh dari banyaknya pheromone yang ditinggalkan oleh masing-masing semut pada setiap jalan yang dilewatinya.(Dorigo, 1996).

4. Cheapest Link

Langkah-langkah:

1.   Dalam metode ini kita tidak memilih simpul awal yang  memilih link atau sisi dengan bobot terkecil pada graph.

2.      Kita  memilih sisi dengan bobot  terkecil kedua (sisi ini tidak perlu berbagi dengan ujung simpul sebelumnya). Lakukan teruslangkah ini, kecuali kita menolak setiap sisi jika:
1) membentuk sebuah "hubungan pendek" (sirkuit yang bukan Hamilton sirkuit) , atau
2) mengakibatkan 3 pertemuan sisi di simpul yang sama.

3.      Telah terpilih n-1 sisi, yang ujung-ujungnya membentuk lintasan Hamilton.
Lalu untuk sisi terakhir kita pilih satu sisi yang menggabungkan dengan simpul  terakhir.

5.  Algoritma Brute Force 

Algoritma bruteforce menyelesaikan masalah TSP dengan cara:

-          Mengenumerasi semua Sirkuit Hamilton dari graf lengkap TSP,

-          Menghitung bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1,

-          Memilih sirkuit Hamilton yang mempunyai bobot terkecil.

Karena algoritma ini menghitung bobot untuk setiap Sirkuit Hamilton yang mungkin terjadi, maka kompleksitasnya sebesar jumlah Sirkuit Hamilton untuk graf lengkap bersimpul n yang dimulai dari sebuah simpul, yakni permutasi dari n buah simpul = n1* ... * 1 = (n1)!.

Maka, kompleksitasnya adalah O(n!)

  
6.Algoritma DFS

Algoritma DFS untuk menyelesaikan TSP adalah seperti ini:

-          Bangun sebuah pohon yang cabangnya berupasimpul pada graf, Lakukan metode DFS pada tiap cabang sampai semua simpul dipilih (tidak ada yang dipilih dua kali),

-          Hitung bobotnya,

-     Lakukan langkah ke2 dan ke3 sampai seluruhsimpul asal telah dipilih. Apabila pada waktu membangkitkan simpul anak ternyata tidak lebih kecil dari minimum sementara, maka simpul tersebut dimatikan (tidak diekspansi lebih lanjut).