Travelling Salesman Problem (TSP)

Travelling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi klasik yang sulit untuk dipecahkansecara konvensional. Penyelesaian eksak terhadap persoalanini akan melibatkan algoritma yang mengharuskan mencarikemungkinan semua solusi yang ada [1]. Sehingga akanterjadi ledakan kombinasi dan membuat kompleksitas waktudari eksekusi algoritma sangat tinggi.

Masalah TSP melibatkan seorang sales yang harus melakukan kunjungan ke sejumlah kota dalam menjajakan produknya. Rangkaian kota-kota yang dikunjungi harusmembentuk suatu jalur sedemikian sehingga kota-kotatersebut hanya boleh dilewati tepat satu kali dan kemudiankembali lagi ke kota awal.

Kasus seperti ini sering diistilahkandengan sirkuit hamilton, representasinya dikenal dengan istilah hamiltonian. Penyelesaian terhadap permasalahanTSP ini adalah untuk memperoleh jalur terpendek. Penyelesaian eksak terhadap masalah TSP mengharuskan untuk melakukan perhitungan terhadap semua kemungkinan rute yang dapat diperoleh, kemudian memilih salah satu rute yang terpendek. Untuk itu jika terdapat  n  kota yang harusdikunjungi, maka terdapat n! kombinasi kota yang akandi bandingkan jarak masing-masing. Dengan cara ini waktu komputasi yang dibutuhkan akan jauh meningkat seiring dengan bertambahnya jumlah kota yang harus dikunjungi.

Di dalam algoritma greedy prinsip Pencarian jalurter pendek memakai fungsi seleksi dan itu sangat berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat sesuai dengan asumsi diatas. Dalam penerapannya, algoritma ini tidak selalu mendapatkan solusi optimal namun pasti menemukan solusi. Kelebihan algoritma ini adalah kemampuannya menemukan solusi dengan jumlah node yang banyak dilakukan dengan sangat cepat. Algoritma greedy biasanya digunakan untuk menentukan memecahkan masalah lintasan linier dimana asal dan tujuan merupakan node yang berbeda. Hal ini menjadi kendala apabila diterapkan pada kasus TSP, dimana jalur yang ada merupakan jalur hamiltonian. Hal ini dapat diatasi dengan menggunakan penanda.

Penanda

TSP merupakan jalur Hamiltonian, sehingga setiap node dimungkinkan memiliki dua arah. Jika kita menggunakan algoritma greedy pada kasus ini, maka harus dilengkapi dengan kemampuan untuk mengenali kota yang telah dilewati agar tidak terjadi perulangan. Dengan kata lain, satu kota hanya dikunjungi sekali. Untuk menyelesaikan hal tersebut, dibutuhkan sebuah penanda setiap kota yang telah dikunjungi. Kota atau node yang telah dikunjungi harus ditandai,  misalnya inisialisasi setiap kota mempunya tanda = 0, jika kota telah dikunjungi, maka tandanya berubah menjadi 1. Ketika proses pelacakan jalur terjadi, kota dengan tanda = 1 tidak perlu dilewati/diproses. Dengan adanya penanda pada algoritma greedy, proses pelacakan dapat dilakukan tanpa ada kota yang dikunjungi berulang. Hal ini memudahkan pelacakan untuk kembali kekota asal.

Kompleksitas Algoritma

Untuk memudahkan menghitung kompleksitas algoritma greedy dengan penanda, berikut diberikan contoh lintasan TSP beserta costnya. Misalnya terdapat 4 kota yaitu ABCDE, dimana jarak A ke B = 7, A ke C = 3, A ke D = 4, B ke C = 5,B ke D = 8 dan C ke D = 2. Grafnya dapat dilihat dibawah ini.

           Graf TSP dengan empat node

Proses pelacakan / penentuan lintasan sesuai dengan pseudocode dapat digambarkan dalam bentuk tree seperti berikut:

Contoh Pelacakan dalam bentuk tree

 Dari Gambar, ditemukan solusi jalur terpendek adalah A-C-D-B-A dengan total cost   adalah 20. Kompleksitas yang terjadi pada contoh diatas untuk mendapatkan solusi sebanyak7 rute, yaitu A-B, A-C, A-D, C-B, C-D, D-B dan B-A. Dengan cara yang sama, jika terdapat 3 node, makadi peroleh kompleksitas sebanyak 4 rute, 5 node, kompleksitasnya adalah 11, 10 node, kompleksitasnya adalah 46. Hal tersebut membentuk sebuah pola sehingga dapat disimpulkan bahwa untuk menghitung kompleksitas Algoritma Greedy dengan penanda dalam menyelesaikan TSP, jika diinput n kota, maka akan terjadi (n(n-1)/2)+1.

Pseudo Code

Ide sederhana untuk membuat pseudo codenya adalahsebagai berikut :

1.         Input jumlah node

2.         Input jarak antar kota, dimana jarak yang diinputcukup sekali, misalnya cukup menginput jarak antarakota A ke kota B, secara otomatis, program akanmengisi jarak antara kota B ke kota A.

3.         Setiap yang telah dilewati diberi penanda = 1,sementara kota yang belum dilewati secara defaultmempunyai penanda = 0.

4.         Gunakan algoritma greedy untuk mencari optimumlocal step by step dengan tidak memproses kota yangtelah dilewati (yaitu ditandai dengan penanda=1).

5.         Outpunya berupa jalur optimal sesuai prinsip greedydan total cost yang dibutuhkan.

Pseudo code untuk aplikasi pemecahan TSP mengunakanalgoritma greedy dengan penanda sebagai berikut:

Dengan menginput jumlah node (n) dan jarak antar kota (cost[i,j]) pseudo code diatas akan menghasilkan jalur optimal(Lintasan) beserta total jarak yang dibutuhkan (cost) sesuai prinsip greedy.