II.1
BAB II LANDASAN TEORI 2.1
Traveling Salesmen Problem TSP atau Travelling Salesmen Problem adalah salah satu masalah distribusi
yang cukup lama dibahas dalam kajian optimasi. Masalahnya adalah bagaimana seorang salesman mengunjungi seluruh kota di suatu daerah dan kembali ke kota awal keberangkatan dengan aturan bahwa tidak boleh ada kota yang dikunjungi lebih dari satu kali. Berikut adalah aturan-aturan yang mengidentifikasikan bahwa permasalahan tersebut adalah TSP: 1.
Perjalanan dimulai dan diakhiri di kota yang sama sebagai kota asal sales.
2.
Seluruh kota harus dikunjungi tanpa satupun kota yang terlewatkan.
3.
Salesman tidak boleh kembali ke kota asal sebelum seluruh kota terkunjungi.
4.
Tujuan penyelesaian permasalahan ini adalah mencari nilai optimum dengan meminimumkan jarak total rute yang dikunjungi dengan mengatur urutan kota.
TSP dapat dideskripsikan sebagai pencarian urutan tur kota terdekat yang harus dikunjungi yang meminimalkan total biaya, dimana setiap kota hanya boleh dikunjungi maksimum satu kali. Pencarian tur kota dengan jumlah kota yang sedikit dapat dengan mudah diselesaikan dengan metode pencarian klasik yaitu dengan cara menghitung akumulasi tiap tur dan dipilih tur yang terpendek, namun permasalahan akan muncul bila pencarian tur kota terjadi pada jumlah kota yang besar, maka waktu yang dibutuhkan untuk menyelesaikan permasalahan ini pun akan meningkat luar biasa, belum lagi bila terdapat batas waktu untuk mencapai kota tujuan. Oleh karena itulah TSP termasuk permasalahan “NP-Complete”. Pada permasalahan “NP-Complete”, solusi optimal tidak bisa diperoleh secara efisien, maka demi efisiensi tersebut, pencarian solusi yang dilakukan hanya yang mendekati optimal asalkan selesai dalam orde waktu polinomial.
II.1
II.2
Karena biaya komputasi yang lebih rendah, sebagian besar permasalahan “NPComplete” diselesaikan menggunakan metode heuristik, termasuk permasalahan TSP ini. Metode heuristik bertujuan untuk mencari solusi yang mendekati optimal dari suatu permasalahan optimasi kombinatorial. Pada referensi dijelaskan bahwa TSP juga merupakan permasalahan optimasi kombinatorial yang sangat terkenal dalam teori graf, maka dapat dikatakan bahwa TSP tidak lain adalah permasalahan untuk menemukan Sirkuit Hamilton yang memiliki bobot minimum pada sebuah graf terhubung. Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul terakhir) yang dilalui dua kali. Pada permasalahan TSP ini, jika setiap simpul mempunyai sisi ke simpul lain, disebut dengan graf lengkap berbobot, nilai bobot edge pada suatu graf, didapatkan dari jarak antar dua buah kota. Untuk TSP pada sembarang graf lengkap, sangat mudah menghitung jumlah Sirkuit Hamilton yang ada. Dari simpul pertama ada n1 pilihan, dari simpul kedua ada n-2 pilihan, dst. Sehingga untuk n buah kota, ada pilihan (n-1)! yang mungkin. Namun karena Sirkuit Hamilton terhitung 2 kali maka pilihan yang ada harus dibagi dua menjadi (n–1)!/2 buah Sirkuit Hamilton
2.2
Metode Heuristik Permasalahan penentuan rute biasanya merupakan permasalahan NP-Hard
Problem dimana penyelesaian dengan metode exact seringkali akan memakan waktu yang cukup lama untuk menyelesaikannya. Karena sebab inilah banyak para ahli yang merancang penyelesaian suatu problem dengan menggunakan merode heuristik. Metode Heuristik adalah teknik yang dirancang untuk memecahkan masalah yang mengabaikan apakah solusi dapat dibuktikan benar, tapi yang biasanya menghasilkan solusi yang baik atau memecahkan masalah yang lebih sederhana yang mengandung atau memotong dengan pemecahan masalah yang lebih kompleks. Metode Heuristik ini bertujuan untuk mendapatkan performa komputasi atau penyederhanaan konseptual, berpotensi pada biaya keakuratan atau presisi. Metode heuristik ada dua jenis yakni metode heuristik sederhana dan metaheuristik. Metode heuristik contohnya adalah cheapest II.2
II.3
insertion, Priciest Insertion, Nearest insertion, Farthest Insertion, Nearest addition dan Clarke and Wright Saving Method. Adapun penjelasannya sebagai berikut : 1)
Cheapest insertion hal pertama kali yang dilakukan adalah menentukan
setiap titik yang masih tersisa dan bebas atau titik yang belum dikunjungi yang menghasilkan link optimal untuk menyisipkan titik ini. Ini sesuai dengan minimisasi pertama dalam persamaan: {
{
}}
(2.1)
Penalti penyisipan adalah jumlah jarak ke titik bebas dikurangi jarak dari link yang akan dihapus. Pada Cheapest insertion kemudian dilakukan pemilihan titik untuk disisipkan sebagai titik penyisipan dengan penalti minimum. 2)
Pada Priciest insertion yang dilakukan pertama kali
adalah
menentukan setiap titik yang masih tersisa dan bebas atau titik yang belum dikunjungi yang menghasilkan link optimal untuk menyisipkan titik ini. Ini sesuai dengan minimisasi pertama dalam persamaan: {
}
{
}
(2.2)
Identik dengan proses cheapest insertion, penalti penyisipan adalah jumlah jarak ke titik bebas dikurangi jarak dari link yang akan dihapus. Pricest Insertion kemudian dipilih titik untuk disipkan sebagai titik penyisipan dengan penalti maksimum. 3)
Pada Nearest insertion yang dilakukan pertama kali adalah menentukan
titik untuk disipkan dengan mencari titik bebas yang paling dekat dengan suatu titik pada tur. Algoritma pada dasarnya melakukan sebuah operasi mini-min pada jarak dari titik bebas untuk suatu titik pada tur. {
}
{
}
II.3
(2.3)
II.4
Selanjutnya dengan algoritma ini, ditentukan link terbaik untuk menyisipkan titik ini. Proses ini identik dengan proses pada cheapest insertion dan farthest insertion.
(
4)
)
{
}
(2.4)
Pada farthest insertion yang dilakukan pertama kali adalah menentukan
setiap titik bebas yang memiliki jarak ke titik manapun pada tur terkecil. Kemudian masukkan titik bebas yang memiliki maksimum jarak terkecil ke titik pada tur. Algoritma ini pada dasarnya merupakan sebuah operasi maxi-mnt pada jarak dari titik bebas untuk suatu titik pada tur. {
}
(2.5)
Selanjutnya ditentukan link terbaik untuk menyisipkan titik ini. Proses ini identik dengan proses pada cheapest insertion dan farthest insertion.
(
5)
)
{
}
(2.6)
Pada Nearest addition yang pertama kali dilakukan adalah menentukan
titik yang akan disisipkan dengan mencari titik bebas yang paling dekat dengan suatu titik pada tur. {
}
(2.7)
Selanjutnya ditentukan link terbaik untuk menyisipkan titik ini dengan memeriksa dua link pada insiden tur ke titik tur paling dekat dengan titik bebas tersebut. Ini merupakan pencarian yang lebih terbatas dibanding dengan proses pada cheapest insertion dan farthest insertion. {
}
II.4
(2.8)
II.5
6)
Clarke dan Wright (1964) mengembangkan prosedur konstruksi yang
memanjang sebagian rute atau rute primitif pada dua titik akhir. Secara konseptual algoritma mendefinisikan titik pangkal dan menbangun sebuah tur Eulerian yang memiliki pengertian mengunjungi masing-masing titik lain dan kemudian kembali ke pangkal. Tur Eulerian kemudian dikurangi panjangnya dengan mencari jalan dengan saving terbesar. Saving dihitung sebagai jumlah dari jarak ke titik dasar dari dua titik dikurangi jarak antara dua titik. {
}
(2.9)
i h j
o Gambar II-1 Ilustrasi Clarke and Wright Tour Extension (sumber : http://dazzdays.wordpress.com/tag/penentuan-rute/)
Setelah dua titik telah bergabung, titik tersebut tiidak akan pernah dipisahkan lagi oleh algoritma Clarke dan Wright. Serial varian dari algoritma memperluas parsial satu rute di ujungnya titik, yang tersambung ke titik pangkal. Titik berikutnya kemudian dipilih dengan mencari titik dengan saving terbesar untuk saat ini titik akhir dari tur parsial. *
*
++
(2.10)
Pada kasus ini penulis akan menggunakan metode cheapest insertion untuk menanggulangi masalah Traveling Salesment problem. Pada Cheapest insertion,
II.5
II.6
hal pertama kali yang dilakukan adalah menentukan setiap titik yang masih tersisa dan bebas atau titik yang belum dikunjungi yang menghasilkan link optimal untuk menyisipkan titik ini.
Berikut ini adalah tata urutan algoritma CIH: 1. Penelusuran dimulai dari sebuah kota pertama yang dihubungkan dengan sebuah kota terakhir. 2. Dibuat sebuah hubungan subtour antara 2 kota tersebut. Yang dimaksud subtour adalah perjalanan dari kota pertama dan berakhir di kota pertama, misal (1,3) → (3,2) → (2,1) seperti tergambar dalam Gambar XI.
1
1
1
Gambar II-2 Subtour
3. Ganti salah satu arah hubungan (arc) dari dua kota dengan kombinasi dua arc, yaitu arc (i,j) dengan arc (i,k) dan arc (k,j), dengan k diambil dari kota yang belum masuk subtour dan dengan tambahan jarak terkecil. Jarak diperoleh dari: cik + ckj – cij cik adalah jarak dari kota i ke kota k, ckj adalah jarak dari kota k ke kota j dan cij adalah jarak dari kota i ke kota j 4. Ulangi langkah 3 sampai seluruh kota masuk dalam subtour.
2.3
Hierarchical clustering Pada algoritma clustering, data akan dikelompokkan menjadi cluster-
cluster berdasarkan kemiripan satu data dengan yang lain. Prinsip dari clustering
II.6
II.7
adalah memaksimalkan kesamaan antar anggota satu cluster dan meminimumkan kesamaan antar anggota cluster yang berbeda. Kategori algoritma clustering yang banyak dikenal adalah Hierarchical Clustering. Hierarchical Clustering adalah salah satu algoritma clustering yang dapat digunakan untuk meng-cluster dokumen (document clustering). Dari teknik hierarchical clustering, dapat dihasilkan suatu kumpulan partisi yang berurutan, dimana dalam kumpulan tersebut terdapat: a. Cluster – cluster yang mempunyai poin – poin individu. Cluster – cluster ini berada di level yang paling bawah. b. Sebuah cluster yang didalamnya terdapat poin – poin yang dipunyai semua cluster didalamnya. Single cluster ini berada di level yang paling atas.
Hasil keseluruhan dari algoritma hierarchical clustering secara grafik dapat digambarkan sebagai tree, yang disebut dengan dendogram. Tree ini secara grafik menggambarkan proses penggabungan dari cluster – cluster yang ada, sehingga menghasilkan cluster dengan level yang lebih tinggi. Gambar 1 adalah contoh dendogram.
Gambar II-3 Dendrogram (Sumber : www.mathworks.com)
II.7
II.8
2.3.1
Agglomerative Hierarchical Clustering Metode ini menggunakan strategi desain Bottom-Up yang dimulai dengan
meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkan atomic cluster – atomic cluster tersebut menjadi cluster yang lebih besar dan lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat pula berhenti jika telah mencapai batasan kondisi tertentu. Metode Agglomerative Hierarchical Clustering yang digunakan pada penelitian ini adalah metode AGglomerative NESting (AGNES). Cara kerja AGNES dapat dilihat pada Gambar II-3. . 2.3.2
Metode Single Linkage Input untuk algoritma Single Linkage bisa berujud jarak atau similarities
antara pasangan-pasangan dari objek-objek. Kelompok-kelompok dibentuk dari entities individu dengan menggabungkan jarak paling pendek atau similarities (kemiripan) yang paling besar. Pada awalnya, kita harus menemukan jarak terpendek dalam D = {dik} dan menggabungkan objek-objek yang bersesuaian misalnya, U dan V , untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara (UV) dan cluster W yang lain dihitung dengan cara
d(UV )W = min{ d UW,d VW }
(2.11)
Di sini besaran-besaran dUW dan dVW berturut-turut adalah jarak terpendek antara cluster-cluster U dan W dan juga cluster-cluster V dan W .
2.3.3
Metode Complete linkage Complete linkage memberikan kepastian bahwa semua item-item dalam satu
cluster berada dalam jarak paling jauh (similaritas terkecil) satu sama lain. Algoritma aglomerative pada umumnya dimulai dengan menentukan entri (elemen matriks) dalam D = {dik} dan menggabungkan objek-objek yang bersesuaian misalnya U dan V untuk mendapatkan cluster (UV). Untuk langkah II.8
II.9
dari algoritma metode ini, jarak-jarak antara cluster (UV) dan cluster W yang lain dihitung dengan d(UV )W = maks{ d UW, d VW }
(2.12)
Di sini besaran-besaran dUW dan dVW berturut-turut adalah jarak antara tetangga terdekat cluster-cluster U dan W dan juga cluster-cluster V dan W.
2.4
MATLAB MATLAB (Matrix Laboratory) adalah sebuah program untuk analisis dan
komputasi numerik dan merupakan suatu bahasa pemrograman matematika lanjutan yang dibentuk dengan dasar pemikiran menggunkan sifat dan bentuk matriks. Merupakan bahasa pemrograman tingkat tinggi berbasis pada matriks sering digunakan untuk teknik komputasi numerik, yang digunakan untuk menyelesaikan masalah-masalah yang melibatkan operasi matematika elemen, matrik, optimasi, aproksimasi dll. MATLAB juga berisi toolbox yang berisi fungsi-fungsi tambahan untuk aplikasi khusus. MATLAB bersifat extensible, dalam arti bahwa seorang pengguna dapat menulis fungsi baru untuk ditambahkan pada library ketika fungsi-fungsi built-in yang tersedia tidak dapat melakukan tugas tertentu. Kemampuan pemrograman yang dibutuhkan tidak terlalu sulit bila Anda telah memiliki pengalaman dalam pemrograman bahasa lain seperti C, PASCAL, atau FORTRAN. MATLAB merupakan merk software yang dikembangkan oleh Mathworks.Inc merupakan software yang paling efisien untuk perhitungan numeric berbasis matriks. Dengan demikian jika di dalam perhitungan kita dapat menformulasikan masalah ke dalam format matriks maka MATLAB merupakan software terbaik untuk penyelesaian numericnya. MATLAB adalah sebuah bahasa dengan kemampuan tinggi untuk komputasi teknis. Ia menggabungkan komputasi, visualisasi, dan pemrograman dalam satu
kesatuan
yang mudah
digunakan di
mana masalah dan
penyelesaiannya diekspresikan dalam notasi matematik yang sudah dikenal. Pemakaian MATLAB meliputi : · Matematika dan komputasi II.9
II.10
· Pengembangan algoritma · Akuisisi data · Pemodelan, simulasi dan prototype · Grafik saintifik dan engineering · Perluasan pemakaian, seperti graphical user interface (GUI). MATLAB adalah system interaktif yang mempunyai basis data array yang tidak membutuhkan dimensi. Ini memungkinkan kita dapat menyelesaikan banyak masalah komputasi teknis, khususnya yang berkaitan dengan formulasi matrik dan vector. Sistem MATLAB terdiri atas lima bagian utama : 1. Development Environment. Ini adalah kumpulan semua alat-alat dan fasiltas untuk membantu kita dalam menggunakan fungsi dan file MATLAB. Bagian ini memuat desktop, Command window, command history, editor and debugger, dan browser untuk melihat help, workspace, files. 2. The MATLAB Mathematical Function Library. Bagian ini adalah koleksi semua algoritma komputasi, mulai dari fungsi sederhana seperti sum, sine, cosine sampai fungsi lebih rumit seperti, invers matriks, nilai eigen, fungsi Bessel dan Fast Fourier Transform. 3. The MATLAB language. Ini adalah bahasa matriks/array level tinggi dengan control flow, fungsi, struktur data, input/output, dan fitur objek programming lainnya. 4. Graphics. MATLAB mempunyai fasilitas untuk menampilkan vector dan matriks sebagai grafik. Fasilitas ini mencakup visualisasi data dua / tiga dimensi, pemrosesan citra (image), animasi, dan grafik animasi. 5. The MATLAB Application Program Interface (API). Paket ini memungkinkan kita menulis bahasa C dan Fortran yang berinteraksi dengan MATLAB. Ia memuat fasilitas untuk pemanggilan kode-kode dari MATLAB (dynamic linking), yang disebut MATLAB sebagai mesin penghitung, dan untuk membaca dan menulis MAT-files.
II.10
