BAB 2 LANDASAN TEORI
2.1
Teori Graf
2.1.1
Pengenalan Teori Graf Teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf, yang pertama
kali diperkenalkan pada tahun 1736. Baru pada sekitar tahun 1920 teori graf berkembang pesat terutama di bidang ilmu komputer, kimia, bahasa, ekonomi, dan riset operasi.
Gambar 2.1 Jembatan utama di Königsberg (Sumber: Rinardi Munir, 2005, p.355) Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf (tahun 1739) [Rinardi Munir, 2005, p.354]. Di kota Königsberg (sebelah timur negara bagian Prussia, Jerman), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari Pulau Kneiphof lalu bercabang menjadi dua buah anak sungai yang diperlihatkan oleh gambar 2.1. Permasalahannya ialah menemukan pejalanan atau rute dari suatu kota melalui ketujuh
11 buah jembatan masing-masing tepat satu kali, kemudian kembali lagi ke tempat awal. Pulau tersebut tidak dapat dicapai oleh rute apapun selain melalui jembatan-jembatan tersebut. Tahun 1736, Leonhard Euler adalah orang pertama yang berhasil menemukan jawaban masalah tersebut dengan pembuktian yang sederhana (melalui karya tulisannya Seven Bridges of Königsberg). Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik disebut verteks dan jembatan dinyatakan sebagai edge. Dari analisa Euler pada jembatan Königsberg menghasilkan sebuah model graf, seperti yang diperlihatkan pada gambar 2.2. Analisis Euler mengenai permasalahan jembatan di Königsberg tidak menghasilkan solusi. Karena orang tidak mungkin melalui ketujuh jembatan masing-masing tepat satu kali dan kembali lagi ke tempat awal keberangkatan jika derajat (banyaknya garis yang bersisian dengan titik) setiap verteks tidak seluruhnya genap. Penemuan Euler adalah kunci yang menandai perkembangan topologi, di mana perbedaan antara layout sebenarnya dan graf scematic adalah contoh yang bagus untuk gagasan bahwa topologi tidak dibatasi dengan bentuk kaku dari objek-objek tertentu.
C
A
D
B Gambar 2.2 Graf yang merepresentasikan jembatan Königsberg (Sumber: Rinardi Munir, 2005, p.355)
12 2.1.2
Definisi Graf Graf adalah kumpulan verteks atau node yang dihubungkan satu sama lain
melalui sisi/rusuk/busur/edge, yang digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G(V,E), yang dalam hal ini. i.
V adalah himpunan tidak kosong dari simpul-simpul (titik/verteks/node).
ii.
E adalah himpunan sisi (rusuk/edge) yang menghubungkan sepasang simpul. Verteks-verteks pada graf dapat merupakan obyek sembarang seperti kota, atom-
atom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Edge dapat menunjukkan hubungan sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. Jika terdapat sebuah rusuk e yang menghubungkan verteks v dan w, ditulis edge (v, w).
2.1.3
Jenis Graf Graf dapat dibagi menjadi 2 jenis berdasarkan arahnya, yaitu sebagai berikut. 1. Graf tidak berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah. Edge (v, w) = edge (w, v) adalah sisi yang sama, di tampilkan pada gambar 2.3 di mana V = {A, B, C, D} dan e = {e1, e2, e3, e4}.
13
A e1
D
e4
node
e2
edge
B e3
C
Gambar 2.3 Graf tidak berarah 2. Graf berarah (directed graph) Graf yang setiap sisinya diberikan orientasi arah, Edge (v, w) ≠ edge (w, v), yang di tampilkan pada gambar 2.4 di mana V = {A, B, C, D} dan e = {e1, e2, e3, e4, e5, e6, e7}.
A
e2
D
e1
e3
e4
e6
e5 e7
B
C
Gambar 2.4 Graf berarah (Sumber: Seymour Lipschutz, 1985, p.119) Sebuah struktur graf bisa dikembangkan dengan memberi bobot atau nilai pada tiap edge di mana merupakan suatu nilai yang dapat berupa biaya atau jarak, graf semacam ini disebut graf berbobot (weighted graph). Dalam pengajaran teori graf [Seymour Lipschutz, 1985, p.85], terdapat graf khusus beberapa diantaranya adalah sebagai berikut.
14 a) Complete graph ialah graf di mana setiap verteks berhubungan dengan semua verteks
yang
lain
(semua
verteks
saling
berhubungan).
Biasanya
direpresentasikan dengan simbol Kn, dimana K adalah complete graph dan n jumlah verteks. Sebuah complete graph dengan n verteks akan mempunyai rusuk sebanyak n(n-1)/2.
Gambar 2.5 Contoh model complete graph (K5) (Sumber: Seymour Lipschutz, 1985, p.85) b) Bipartite graph adalah graf dimana satu verteksnya dibagi kedalam dua subset verteks m dan n, sedemikian sehingga tidak ada rusuk yang menyebabkan verteks-verteks dalam subset yang sama. Biasanya direpresentasikan dengan simbol Km,n , di mana K adalah bipartite graph, dan m adalah jumlah sunset verteks m, dan n adalah jumlah subset n.
Gambar 2.6 Contoh model bipartite graph (K3,3) (Sumber: Seymour Lipschutz, 1985, p.86)
15 c) Complete bipartite graph adalah bipartite graph di mana setiap verteks dari m harus memiliki rusuk yang berhubungan ke semua verteks dari n. Biasanya direpresentasikan dengan simbol Km,n , sama seperti bipartite graph.
Gambar 2.7 Contoh model bipartite graph (K2,3) (Sumber: Seymour Lipschutz, 1985, p.86) d) Regular graph adalah graf dimana setiap verteksnya memiliki derajat yang sama.
Gambar 2.8 Contoh model regular graph berderajat 2 (Sumber: Seymour Lipschutz, 1985, p.85) e) Tree adalah graf yang tidak memiliki cycle. Jika jumlah verteks pada tree adalah n, maka jumlah rusuk pada tree adalah n-1.
Gambar 2.9 Contoh model tree graph (Sumber: Seymour Lipschutz, 1985, p.86)
16
2.1.4
Teori Lintasan dan Siklus Misalkan vo dan vn adalah verteks-verteks dalam sebuah graf [Richard
Johnsonbaugh, 2002, p.12]. Sebuah lintasan dari vo ke vn dengan panjang n adalah sebuah barisan berselang-seling dari (n+1) verteks dan n edge yang berawal dengan verteks vo dan berakhir dengan verteks vn, (v0, e1, v1, e2, v2, …, vn-1, en, vn) Dengan rusuk ei insiden pada verteks vi-1 dan vi ( i= 1, 2, …, n). Sebuah siklus adalah sebuah litasan yang mempunyai panjang lintasan tidak nol dari kota pertama sampai kota terakhir yang merupakan kota pertama, di mana tidak terdapat rusuk yang dilalui lebih dari sekali. Sebuah siklus sederhana adalah siklus dari kota pertama sampai kota terakhir yang merupakan kota terakhir juga pada suatu graf, yang kecuali kota pertama dan kota terakhir yang sama, tidak terdapat verteks yang berulang Untuk mengamati perbedan anatara lintasan, siklus, siklus sederhana, dengan contoh graf pada gambar 2.10 dapat dilihat yang akan disajikan dalam bentuk tabel. 3 2 1
4 7
5
6 Gambar 2.10 Graf tidak berarah (Sumber: Richard Johnsonbaugh, 2002, p.12)
17 Tabel 2.1 Perbedaan Lintasan, Siklus, dan Siklus Sederhana (Sumber: Richard Johnsonbaugh, 2002, p.16) Lintasan ( 5, 6, 2, 5) ( 2, 6, 5, 2, 4, 3, 2) ( 6, 5, 2, 4) ( 6, 5, 2, 4, 3, 2, 1)
2.1.5
Lintasan Sederhaa Tidak Tidak Ya Tidak
Siklus Ya Ya Tidak Tidak
Siklus Sederhana Ya Tidak Tidak Tidak
Representasi Graf Misalkan G adalah sebuah graf dengan verteks-verteks v1, v2, …, vn dan edge e1,
e2, …, en maka didefinisikan dua macam matriks yang berhubungan dengan sebuah graf G [Seymour Lipschutz, 1985, p.87]. 1. Matriks adjacency Misalkan A=(aij) adalah matriks m x n yang didefinisikan oleh: ⎧1 jika {u, v} adalah edge, yaitu vi adjacent terhadap vj aij = ⎨ ⎩0 lainnya 2. Matriks incident Misalkan M=(mij) adalah matriks m x i didefinisikan oleh: ⎧1 verteks vi adalah incident pada edge ei m=⎨ ⎩0 lainnya Contoh: Diketahui graf G: e5 v1
e2 e1
v2
e3
v5 e6 e7
e4
v4 e8
v3
18 maka: v1 v1 ⎛ 0 ⎜ v2 ⎜ 1 A = v3 ⎜ 1 ⎜ v4 ⎜ 1 v5 ⎜⎝ 1
v2 v3 1 1 0 1 1 0 0 1 0 1 (a)
v4 1 0 1 0 1
v5 1⎞ ⎟ 0⎟ 1⎟ ⎟ 1⎟ 0 ⎟⎠
e1 v1 ⎛ 1 ⎜ v2 ⎜ 1 m = v3 ⎜ 0 ⎜ v4 ⎜ 0 v5 ⎜⎝ 0
e2 1 0 0 0 1
e3 1 0 1 0 0
e4 0 1 1 0 0
e5 1 0 0 1 0 (b)
e6 0 0 0 1 1
e7 0 0 1 0 1
e8 0⎞ ⎟ 0⎟ 1⎟ ⎟ 1⎟ 0 ⎟⎠
Gambar 2.11 matriks adjecency (a) dan matriks incidence (b) (Sumber: Seymour Lipschutz, 1985, p.87)
2.1.6
Graf Hamiton Lintasan Hamilton ialah lintasan yang melalui tiap verteks di dalam graf tepat satu
kali [Rinardi Murni, 2005, p. 408]. Sirkuit Hamilton ialah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
1
4
(a)
2
1
3
4
(b)
2
1
3
4
Gambar 2.12 Penggambaran Graf Hamilton (Sumber: Rinardi Murni, 2005, p. 409) Keterangan gambar 2.12: a. Graf yang memiliki lintasan Hamilton (3, 2, 1, 4)
2
(c)
3
19 b. Graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1) c. Graf yang tidak memiliki lintasan maupun sirkuit Hamilton
2.2
Algoritma Secara umum algoritma ialah sejumlah langkah komputasi yang mengubah
masukan (input) menjadi keluaran (output) yang benar [Thompson S. Ngoen, 2004, p.4]. Menurut Donald E. Knuth sebuah algoritma harus memenuhi persyaratan: •
Finitness: algoritma harus berakhir setelah melakukan sejumlah langkah proses
•
Definitness: setiap langkah algoritma harus didefinisikan dengan tepat dan tidak menimbulkan makna ganda (ambiguous).
•
Input: setiap algoritma memerlukan data sebagai masukan untuk diolah
•
Output: setiap algoritma memberikan satu atau beberapa hasil keluaran.
•
Effectiveness: langkah-langkah algoritma dikerjakan dalam waktu yang wajar
Terdapat beberapa pengertian algoritma sebagai berikut. •
Pada
Merriam-Webster’s Collegiate Dictionary istilah algorithm diartikan
sebagai prosedur langkah demi langkah untuk memecahkan masalah atau menyeleseikan suatu tugas khususnya dengan menggunakan bantuan komputer. •
Algoritma [Moh. Sjukani, 2004, p.1] adalah alur pikiran dalam menyelesaikan suatu pekerjaan, yang dituangkan dalam bentuk tertulis yang dapat dimengerti oleh orang lain.
20 2.3
Optimisasi
2.3.1
Definisi Optimisasi Optimisasi ialah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai
efektif yang dapat dicapai) [Ibnu Sina Wardy, 2008, p.2]. Dalam matematika, optimisasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi riil. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis dilakukan pemilihan nilai variabel integer atau riil yang akan memberikan solusi optimal. Nilai optimal adalah nilai yang didapat melalui suatu proses dan dianggap menjadi suatu solusi jawaban yang paling baik dari semua solusi yang ada.
2.3.2
Macam-Macam Permasalahan Optimisasi Persoalan yang berkaitan dengan optimisasi sangat kompleks dalam kehidupan
sehari-hari. Nilai optimal yang didapat dalam optimisasi dapat berupa besaran panjang, waktu, jarak, dan lain-lain. Berikut ini adalah beberapa persoalan yang memerlukan optimisasi: a. Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain. b. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil produksi tetap maksimal. c. Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau. d. Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak terlalu besar dan penggunaannya tidak boros.
21 Selain beberapa contoh di atas, masih banyak persoalan lainnya yang terdapat dalam kehidupan sehari-hari.
2.3.3
Penyelesaian Masalah Optimisasi Secara umum, penyelesaian masalah pencarian jalur terpendek dapat dilakukan
dengan menggunakan dua metode, yaitu: 1. Metode Konvensional 2. Metode Heuristik
2.3.3.1 Metode Konvensional Metode konvensional ialah metode yang menggunakan perhitungan matematis biasa. Semua kemungkinan yang ada dicoba dengan mencatat nilai yang didapat, cara ini kurang efektif karena optimasi akan berjalan secara lambat (polynomial time).
A.
Dynamic Programming Dynamic Programming (DP) adalah prosedur matematika yang didesain utama
untuk meningkatkan efisien komputerisasi dalam memilih permasalahan-permasalahan pemograman matematika dengan memecah permasalahan tersebut menjadi bagian-bagian lebih kecil [Hamdy A. Taha, 1995, p.345]. Setiap bagian-bagian tersebut menghasilkan satu variabel optimasi. Hasil komputasi untuk bagian-bagian yang berbeda dihubungkan dengan recursive computations yang akan menghasilkan solusi optimal yang feasible untuk semua permasalahan.
22 B.
Branch and Bound Teknik branch and bound (B&B) terdiri dari dua prosedur dasar. Branching
adalah proses mempartisi masalah yang besar menjadi dua atau lebih masalah kecil. Bounding adalah proses menghitung batas bawah pada solusi optimal dari masalah kecil tersebut. Bounding function yang digunakan yaitu pemrosesan hanya dilakukan pada branch yang baik; yang buruk tidak akan diproses. Diharapkan bahwa branch yang baik akan memberikan hasil yang optimal pada proses selanjutnya.
C.
Branch and Cut Teknik branch and cut merupakan teknik yang menggunakan branch dan bound
dengan penambahan algoritma cutting pada solusi yang didapatkan. Proses yang dilakukan ialah dengan mengaplikasikan branch and bound pada solusi yang nantinya akan dipotong dengan algoritma tertentu untuk mendapatkan hasil yang lebih baik. Proses tersebut akan diulang sampai tidak ada pemotongan lagi.
2.3.3.2 Metode Heuristik Metode heuristik adalah subbidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Menurut Judea Peral (April, 1984), metode heuristik berkerja berdasarkan strategi pencarian pintar pada pemecahan masalah dengan komputer, dengan menggunakan beberapa pendekatan [http://en.wikipedia.org/wiki/ Heuristic _algorithm]. Dua tujuan dasar dalam pemecahan masalah optimisasi pada ilmu komputer adalah mencari algoritma yang cepat menyelesaikan masalah dan memperoleh hasil yang
23 optimal. Metode heuristik ialah metode yang menghilangkan salah satu atau dua dari tujuan tersebut. Misalnya, pada pemecahan masalah optimisasi, dihasilkan solusi yag cukup optimal, tetapi secara manual, belum tentu solusi yang lebih optimal dapat diperoleh karena kompleksnya permasalahan yang ada. Atau, solusi yang didapat dihasilkan dengan waktu yang sangat cepat, namun secara manual masih dapat ditemukan hasil yang lebih optimal. Jadi, hasil yang diperoleh belum tentu yang paling optimal. Tetapi penggunaan metode heuristik yang umum tetap diterapan di dunia nyata. Karena terdapat beberapa masalah, di mana hanya metode heuristik yang memungkinkan untuk memperoleh solusi yang optimal dalam waktu yang sangat singkat.
Sistem yang menggunakan AI MASALAH
Basis Pengetahuan
Inference Engine
SOLUSI
Gambar 2.13 Sistem yang menggunakan kecerdasan buatan (Sumber: Sri Kusumadewi, 2005, p.1) Pada gambar 2.14 [Sri Kusumadewi dan H. Purnomo, 2005, p.1], input yang diberikan pada sistem yang menggunakan kecerdasan buatan adalah masalah. Sistem harus dilengkapi dengan sekumpulan pengetahuan yang ada pada basis pengetahuan. Sistem harus memiliki inference engine agar mampu mengambil kesimpulan berdasarkan fakta atau pengetahuan. Output yang diberikan berupa hasil masalah sebagai hasil dari inferensi.
24 A.
Algoritma Generate and Test Pada prinsipnya metode ini merupakan penggabungan antara depth-first search
dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaaan awal. Nilai pengujian berupa jawaban ‘ya’ atau ‘tidak’. Algoritmanya adalah sebagai berikut. 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik atau lintasan tertentu dari keadaan awal). 2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusi dengan cara membandingkan verteks tersebut atau verteks akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. 3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
B.
Simulated Annealing Simulated Annealing (SA) adalah metode pencarian lokal yang acak, di mana
solusi sementara dimodifikasi sehingga mengarah pada hasil yang lebih baik, dengan beberapa kemungkinan. Mekanisme ini dapat mengantisipasi local optima yang buruk Ide dasar SA terbentuk dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperature. SA biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas.
25 Pada SA, ada 3 parameter yang sangat menentukan adalah tetangga, gain, dan temperatur. Tetangga akan sangat berperan dalam bentuk perubahan pada solusi. Pembangkitan bilangan random akan berimplikasi adanya probabilitas.
C.
Tabu Search Tabu Search (TS) merupakan suatu metode optimisasi yang menggunakan short-
term memori atau memori jangka pendek untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal.
Metode ini menggunakan Tabu List untuk
menyimpan sekumpulan solusi yang telah dievaluasi. Pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkan terlebih dahulu dengan tabu list untuk melihat apakah solusi tersebut sudah ada pada tabu list. Apabila solusi tersebut sudah ada pada tabu list, maka solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya. Apabila sudah tidak ada lagi solusi yang tidak menjadi anggota tabu list, maka nilai terbaik yang baru saja diperoleh merupakan solusi yang sebenarnya.
D.
Algoritma Genetika Genetic Algorithm (GA) pertama kali dikembangkan oleh John Holland dari
universitas Michigan (1975). GA adalah algoritma heuristik yang didasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Individu yang lebih kuat (fit) akan memiliki tingkat survival dan reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Pada dasarnya ada 4 kondisi yang sangat mempengaruhi proses evalusi adalah sebagai berikut.
26 •
Kemampuan organisme untuk melakukan reproduksi
•
Keberadaan populasi organisme yang bisa melakukan reproduksi
•
Keberagaman organisme dalam suatu populasi
•
Perbedaan kemampuan untuk survive Pada GA, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang
mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evaluasi kromosom-kromosom melalui iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dalam kromosom menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (off-spring) terbentuk dari gabungan 2 kromosom yang bertindak sebagai induk (parent) dengan operator penyilangan. Selain operator penyilangan, suatu kromosom dapat dimodifikasi dengan menggunakan operator mutasi.
E.
Harmony Search Harmony search (HS) ialah algoritma metaheuristic (algoritma soft computing
atau
algoritma
evolusioner)
meniru
proses
improvisasi
musisi
[http://en.wikipedia.org/wiki/Harmony_search]. Setiap musisi memainkan nada untuk mencari harmoni yang terbaik bersama-sama, sama seperti setiap variabel keputusan dalam proses optimasi memiliki nilai untuk menemukan vektor terbaik serentak. HS mencoba mencari vektor x yang meminimalkan beberapa pengeluaran fungsi.
27
F.
Particle Swarm Optimization Particle Swarm Optimization (PSO) merupakan teknik komputasi heuristik
berbasis populasi parallel yang diajukan oleh Kennedy dan Eberhart (1995), yang dimotivasikan dari perilaku organisme seperti populasi ikan atau populasi burung. Andaikan ada sejumlah burung yang sedang mencari makanan di sebuah daerah secara acak [http://www.swarmintelligence.org/tutorials.php]. Di daerah tersebut hanya ada satu potong makanan. Semua burung tidak mengetahui posisi makanan berada. Tetapi mereka tahu seberapa jauh makanan tersebut dengan setiap perulangan. Jadi strategi yang baik untuk menemukan makanan tersebut adalah mengikuti posisi burung yang terdekat dengan makanan.
2.4
Travelling Salesman Problem Traveling Salesman Problem (TSP) adalah permasalahan pada matematika diskrit
dan optimalisasi kombinatorial [http://www.tsp.gatech.edu/history/index.html]. TSP pertama kali dikemukakan pada tahun 1800-an oleh seorang matematikawan asal Irlandia, sir William Howard Hamilton dan seorang matematikawan asal inggris, Thomas Penyngton Kirkman. Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai tahun 1930. Diawali oleh Karl Menger di Vienna dan Harvard, permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton. TSP memerlukan keputusan dari siklus biaya atau panjang yang minimal, melalui penerusuran setiap node pada graf yang relevan [Thammapimookkul dan Chamsethikul, 2001, p.5]. Jika biaya antar dua lokasi tidak tergantung pada arah lintasan, maka TSP
28 jenis ini bersifat simetris. Sedangkan TSP yang bersifat asimetris, yang disebut direcred TSP. TSP sebagai salah dari NP-complete problems dapat diselesaikan dengan Pendekatan heuristik yang terbagi dalam tiga kelas, sebagai beikut. •
Tour construction procedures, menghasilkan perkiraan perjalanan optimal dari jarak matriks. Seperti prosedur Nearest Neighbor, Clarke and Wright Saving, prosedur Insertion, Minimal Spanning Tree, dan Christofides heuristic.
•
Tour improvement procedures, berusaha mencari perjalanan yang lebih baik dari perjalanan awal. Seperti 2-opt dan 3-opt heuristik dan prosedur k-opt.
•
Tour composite procedures, membuat perjalanan awal dari salah satu composite procedures dan kemudian mencari perjalanan yang lebih baik menggunakan satu atau lebih dengan tour improvement procedures.
Gambar 2.14 Solusi TSP dengan 91 verteks (Sumber: http://www.visualbots.com/tsp_project.htm)
2.5
Multi Travelling Salesman Problem Multi Travelling Salesman Problem (M-TSP) adalah generalisasi dari TSP, yang
merupakan persoalan yang lebih mendekati permasalahan dalam dunia nyata. Dalam
29 masalah ini diperlukan lebih dari satu kendaraan pengangkut untuk pendistribusian barang. Pada M-TSP, keadaan pengangkut berjumlah m akan mengunjungi semua verteks yang ada dengan total jarak yang minimum. M-TSP dapat selalu dikonversikan ke dalam TSP yang sama dengan membuat perbanyak sebanyak m kali dari lokasi yang sama, tetapi tidak berhubungan satu sama lain. Bebearapa formula M-TSP diturunkan secara independent oleh Bellmore dan Hong (1974), Orloff (1974), Svetska dan Huckfeltz (1973). Pada M-TSP harus terdapat m ≥ 2 salesman yang mengunjungi n kota secara bebas. Tidak ada kota yang dikunjungi oleh lebih dari satu salesman dan setiap m salesman dapat memulai dari kota awal yang berbeda atau yang sama dan berakhir pada kota yang sama dengan kota awal pada masing-masing salesman.
2.6
Vehicle Routing Problem Vehicle Routing Problem (VRP) adalah salah satu problem atau permasalahan dari
combinatorial optimization di mana sebuah set rute akan dibentuk dari sejumlah kota atau pelanggan didasarkan atas satu atau beberapa depot. Setiap kota atau pelanggan akan dilayani oleh satu kendaraan dengan batasan-batasan tertentu; rute tersebut di awali dan diakhiri di depot [http://neo.lcc.uma.es/radi-aeb/WebVRP]. Permasalahan ini pertama kali diformulasikan oleh Dantzing dan Ramser pada tahun 1959 sebagai pusat permasalahan utama dalam bidang transportasi, distribusi, dan logistik. Dalam beberapa sektor pasar, transportasi memiliki nilai persentase yang tinggi yang dimasukkan dalam keuntungan. Setelah itu dikembangkan metode komputerisasi untuk transportasi yang menghasilkan penghematan total biaya yang signifikan.
30 VRP adalah generalisasi dari TSP. Maka, TSP adalah sebuah VRP tanpa batasan seperti depot, pelanggan dan permintaan. M-TSP adalah VRP dengan sebuah depot dan m kendaraan pengangkut, termasuk bila tidak ada permintaan dari pelanggan. MTSP adalah transformasi dari TSP dengan memperbanyak jumlah depot. Pelanggan
Depot
Gambar 2.15 Contoh visualisasi input dari Vehicle Routing Problem (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
Pelanggan
Depot Rute
Gambar 2.16 Salah satu output dari VRP dari input gambar 2.15 (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
31 Tujuan dari Vehicle Routing Problem ialah untuk meminimalkan jarak yang dilalui oleh armada kendaraan yang melayani sekumpulan pelanggan seperti pada gambar 2.18 dan menghasilkan salah satu rute seperti pada gambar 2.19 dengan banyaknya kendaraan yang disediakan atau digunakan. Pada perkembangannya [Titiporn Thammapimookkul, 2001, p.3], VRP memiliki beberapa karateristik sehingga dapat dibagi-bagi dalam beberapa kategori masalah, seperti yang dapat ditunjukkan dalam tabel 2.2. Kategori ini dibuat oleh Bodin dan Golden (1981), yang memaparkan berbagai karakteristik umum, yang membedakan VRP. Keseluruhan tabel memberikan gambaran singkat tentang masalah routing.
Tabel 2.2 Kategori masalah dalam VRP (Sumber: Titiporn Thammapimookkul, 2001, p.3) No Karateristik 1 Jumlah kendaraan pengangkut 2 Tipe kendaraan pengangkut 3
Tipe permintaan
4
Lokasi permintaan
5
Tenpat asal kendaraan (pusat) Jaringan yang mendasari
6
7
Batasan kapasitas kendaraan pengangkut
Varian yang mungkin Satu kendaraan pengangkut Multi kendaraan pengangkut Homogen (satu tipe) Heterogen (multi tipe) Tipe khusus Permintaan deterministik (telah dikethui sebelumnya) Permintaan stokastik Permintaan kepuasan sebagian Simpul Garis campuran Satu pusat Multi pusat Tidak berarah Berarah Campuran Euclid Semuanya sama Jalur yang berbeda Kapasitas tak terbatas
32 8
Rute maksimum
9
Sistem pengoperasian
10
Biaya
11
Tujuan
Sama untuk semua rute Berbeda untuk setiap rute Tidak ditentukan Pengambilan saja Pengiriman saja Pengambilan dan pengantaran Variable atau biaya rute Biaya tetap pengoperasian atau biaya tetap kendaraan pengangkut Biaya pengangkut umum Meminimalkan biaya total rute Meminimalkan jumlah kendaraan yang diperlukan Meminimalkan fungsi kegunaan berdasarkan pada pelayanan dan kenyamanan Meminimalkan fungsi kegunaan berdasarkan pada prioritas pelanggan
Jika VRP salah satu permasalahan kombinatorial direpresentasikan dalam sebuah graf G = (V, E) [http://neo.lcc.uma.es/radi-aeb/WebVRP], maka notasi yang digunakan ialah sebagai berikut. •
V = {v0, v1, …, vn} ialah set atau sekumpulan verteks yang menggambarkan depot, pelanggan ataupun persimpangan jalan, di mana: o v0 sebagai depot. o v1, …, vn sebagai pelanggan o Misalakan V` = V tanpa elemen {v0} digunakan sebagai himpunan n kota
•
C ialah matriks cij sebagai biaya atau jarak antara pelanggan vi dan vj yang bernilai non-negatif.
•
A = {(vi, vj) | vi, vj Є V; i ≠ j} adalah himpunan rusuk atau edge. Edge dapat yang berarah (i, j) Є A dan tidak berarah e Є E
•
d ialah vektor dari permintaan / demand pelanggan.
•
Ri ialah rute dari kendaraan ke-i.
33 •
k ialah banyaknya kendaraan (semuanya identik) dengan kapasitas Q. Satu rute untuk tiap kendaraan. Dengan setiap verteks vi dalam V’ diasosiasikan dengan sejumlah barang qi, yang
akan diantarkan oleh satu kendaraan. VRP bertujuan untuk menentukan sejumlah k rute kendaraan dengan total biaya yang minimum, bermula dan berakhir di sebuah depot, yang setiap verteks dalam V’ dikunjungi tepat sekali oleh satu kendaraan. Akhirnya, k
biaya dari solusi permasalahan ini S adalah: FVRP ( S ) = ∑ C ( Ri ) i =1
2.7
Local Search
Local search (LS) ialah metaheuristik untuk menyelesaikan permasalahan perhitungan optimisasi yang berat. LS dapat digunakan pada permasalahan yang bertujuan memaksimalkan solusi yang standar di antara banyaknya kandidat solusi [http://en.wikipedia.org/wiki/Local_search_(optimization)]. Algoritma LS berpindah dari solusi ke solusi dalam kandidat solusi sampai dianggap solusi tersebut optimal. Algoritma LS dipergunakan secara luas untuk permasalahan perhitungan yang berat, meliputi permasalahan computer science (artificial intelligence), matematika, operations research, engineering, and bioinformatics. Dalam algoritma LS yang paling dasar, dilakukan penyelusuran dalam neighborhood terhadap perjalanan tertentu untuk kemajuan perjalanan. Jika perjalanan tersebut ditemukan maka rute tersebut menggantikan yang lama dan proses tersebut akan diteruskan sampai kemajuan perjalanan tidak dapat ditemukan lagi. Hal ini disebut iterative improvement algorithm. Algoritma tersebut dapat diterapkan dalam hal-hal sebagai berikut.
34 A.
2-Opt
2-Opt ialah algoritma LS yang pertama kali diusulkan oleh Croes pada tahun 1958 untuk menyeleseikan TSP. Ide dasar dibelakang algoritma tersebut ialah memindahkan atau menghapus pasangan rute yang bersilangan dan mengembalikan suatu perjalanan yang memungkinkan [http://en.wikipedia.org/wiki/2-opt].
reconnect
Menghapus 2 edge
(a)
(b)
Gambar 2.17 2-Opt move (a) dan 2-Opt optimal (b) (Sumber: http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf)
B.
3-Opt
Analisis 3-Opt meliputi penghapusan tiga edge dalam perjalanan, kemudian menghubungkan kembali perjalanan tersebut ke dalam perjalanan yang memungkinkan dan kemudian mengevaluasi tiap metode pengembalian untuk mencari yang paling optimum. Proses ini kemudian diulang untuk set tiga set koneksi yang berbeda [http://en. wikipedia.org/wiki/3-opt].
35 Menghapus 3 edge
reconnect
Gambar 2.18 3-Opt move (Sumber: http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf)
2.8
Algoritma Ant Colony Optimization
Algoritma Ant Colony Optimization merupakan teknik probabilistik untuk menjawab masalah komputasi yang bisa dikurangi dengan menemukan jalur yang baik dengan graf. ACO pertama kali dikembangkan oleh Marco Dorigo pada tahun 1991. Sesuai dengan nama algoritmanya, ACO di inspirasi oleh koloni semut karena tingkah laku semut yang menarik ketika mencari makanan [Heitor S. Lopes et al., 2005, p.2]. Semut-semut menemukan jarak terpendek antara sarang semut dan sumber makanannya. Ketika berjalan dari sumber makanan menuju sarang mereka, semut memberikan tanda dengan zat feromon sehingga akan tercipta jalur feromon. Feromon adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi. Berbeda dengan hormon, feromon menyebar ke luar tubuh dan hanya dapat mempengaruhi dan dikenali oleh individu lain yang sejenis, proses peninggalan feromon ini dikenal sebagai stigmergy. Semut dapat mencium feromon dan ketika mereka memilih
36 jalur mereka, mereka cenderung memilih jalur yang ditandai oleh feromon dengan konsentrasi yang tinggi. Apabila semut telah menemukan jalur yang terpendek maka semut-semut akan terus melalui jalur tersebut. Jalur lain yang ditandai oleh feromon lama akan memudar atau menguap, seiring berjalannya waktu. Jalur-jalur yang pendek akan mempunyai ketebalan feromon dengan probabilitik yang tinggi dan membuat jalur tersebut akan dipilih dan jalur yang panjang akan ditinggalkan. Jalur feromon membuat semut dapat menemukan jalan kembali ke sumber makanan atau sarang mereka. Algoritma ACO telah banyak digunakan untuk menghasilkan penyelesaian yang mendekati optimal [Bernd Bullnheimer et al., 1997, p.1]. Aplikasi algoritma semut dalam kehidupan sehari-hari mencakup beberapa persoalan sebagai berikut. a. Traveling Salesman Problem (TSP), yaitu mencari jalur terpendek dalam sebuah graf menggunakan jalur Hamilton. b. Quadratic Assignment Problem (QAP) yang berusaha menempatkan sejumlah sumber n ditempatkan pada sejumlah m lokasi dengan meminimalkan biaya assignment. c. Job-shop Scheduling Problem (JSP), juga salah satu contoh aplikasi algoritma semut untuk menjadwalkan sejumlah j pekerjaan menggunakan sejumlah m mesin sehingga seluruh pekerjaan diselesaikan dalam waktu yang minimal. d. Vehicle Routing Problem (VRP), pengaturan jalur kendaraan e. Pewarnaan graf Koloni semut yang nyata dan artificial terdapat banyak kemiripan [Marco Dorigo et al., 2006, p.3]. Keduanya terbentuk dari sebuah populasi yang terdiri dari individuindividu yang berkerja sama untuk mencapai tujuan. Semut artificial hidup di dunia
37 virtual, karenanya mereka hanya memodifikasi nilai numerik (disebut analogi artificial pheromones) yang berhubungan dengan keadaan-keadaan permasalahan yang berbeda. Sebuah rangkaian dari nilai-nilai feromon yang berhubungan dengan keadaan permasalahan disebut pheromone trail atau jejak feromon. Mekanisme untuk evaporation atau penguapan feromon pada koloni semut nyata yang membuat semut artificial dapat melupakan sejarah (jalur-jalur yang pernah diambil) dan fokus pada arah pencarian baru yang menjanjikan. Seperti semut-semut nyata, semut-semut artificial membuat solusi secara berurut dengan bergerak dari satu keadaan permasalahan ke lainnya. Semut-semut nyata hanya berjalan, memilih arah berdasarkan konsentrasi feromon lokal dan kebijakan keputusan stokastik. Semut artificial membuat solusi sedikit demi sedikit, dan bergerak dari keadaan permasalahan yang tersedia dan membuat keputusan stokastik setiap langkah. Meskipun begitu, terdapat perbedaan antara yang nyata dan semut artificial sebagai berikut. •
Semut artificial hidup di dunia dan pada waktu diskrit, mereka berpindah secara sekuen melewati set batasan dari permasalahan.
•
Update feromon (penumpukan dan penguapan feromon) tidak dilakukan dengan jalan yang sama pada semut yang nyata dan semut arficial. Update feromon dilakukan oleh beberapa dari semut artificial dan terkadang dilakukan saat solusi telah dibangun.
•
Beberapa implementasi dari semut artificial menggunakan mekanisme tambahan yang tidak ada pada semut-semut nyata, seperti local search, backtracking, dan lain-lain.
38 2.8.1
Algoritma Elitist Ant System
Ant System (AS) adalah bentuk awal dari algoritma ACO yang telah dimodifikasi oleh para peneliti sampai saat ini [Ayan Acharya et al., 2008, p.1]. Algoritma Elitist Ant System (EAS) adalah salah satu dari model yang dikembangkan dari algoritma AS. Strategi dari EAS mirip dengan AS tetapi berbeda dalam penerapan memberikan jejak feromon karena elite ant atau best ant disertakan sebagai feromon tambahan dalam mengupdate jejak semut. Aturan dasar meng-update jejak feromon dalam algoritma AS adalah sebagai berikut. m
τ ijnew = (1 − ρ )τ ijold + ∑ Δτ ijk ……………..……….….…… (1) k =1
Sedangkan aturan dalam meng-update feromon dengan algoritma elitist ant system adalah sebagai berikut. m
τ ijnew = (1 − ρ )τ ijold + ∑ Δτ ijk + eΔτ ijbs ………..…………..…… (2) k =1
dengan Δτ ijk adalah perubahan harga intensitas jejak semut antar kota setiap semut yang dihitung berdasarkan persamaan 3 sebagai berikut. ⎧1 L Δτ ijk = ⎨ k ⎩ 0
untuk (i,j) ∈ kota asal dan tujuan dalam tabuk,v lainnya
e adalah parameter yang mendefinisikan bobot yang diberikan pada rute yang terbaik pada tabubs dengan panjang Lbs. Δτ
bs ij
⎧1 L = ⎨ bs ⎩ 0
untuk (i,j) ∈ kota asal dan tujuan dalam tabubs lainnya
39 2.9
Capacitated Vehicle Routing Problem dengan Algoritma Elitist Ant System
Capacitated Vehicle Routing Problem (CVRP) dapat didefinisikan sebagai pemberangkatan armada dari pusat depot, dengan sejumlah pelanggan yang mesti dilayani, dengan permintaan yang berbeda untuk produk sejenis [Heitor S. Lopes et al., 2005, p.3]. Armada kendaraan terbatas dan mempunyai kapasitas yang sama. Batasanbatasan pada CVRP adalah sebagai berikut. •
Setiap pelanggan hanya dilayani oleh satu pelanggan saja
•
Total permintaan yang dilayani kendaraan tidak boleh melebihi kapasitas kendaraan.
•
Masing-masing perjalanan kendaraan dimulai dan diakhiri di depot
•
Total panjang perjalanan tidak boleh melebihi batas otonomi kendaraan.
CVRP ialah permasalahan yang lebih rumit dari TSP, karena memerlukan dua tahap penyelesaian. Pada tahap awal, setiap semut menyusun beberapa perjalanan yang independen, dan set-set perjalanan melayani semua pelanggan. Pada tahap kedua, setiap perjalanan disampaikan pada sebuah populasi baru, yang sistemnya sama dalam algoritma Ant System (AS) untuk TSP. Pada tahap ini, algoritma berkerja untuk menetapkan banyaknya siklus, yang mengarah pada optimisasi lokal perjalanan. Dua tahap proses tersebut, diulang sampai kriteria pemberhentian dipenuhi. Dengan keadaan total permintaan semua pelanggan yang dilayani tidak melebihi batas kendaraan yang digunakan pada rute Ri, Notasinya adalah sebagai berikut. m
∑d i =1
i
≤ Q …………………..………….….…… (4)
40 Dalam algoritma EAS untuk CVRP, diperlukan langkah-langkah untuk menentukan jalur terpendek sebagai berikut. i.
Inisialisasi Parameter-parameter yang di inisialisasi adalah:
Intensitas jejak semut antar antar kota dan perubahannya (τij).
Banyak pelanggan (n) termasuk koordinat pelanggan (x, y).
Jarak antar pelanggan (dij). d ij =
(x − x ) + (y − y ) 2
i
j
2
i
j
……………………………… (5)
Permintaan atau demand pelanggan (qn).
Banyak kendaraan (v) dengan kapasitas kendaraan (Q).
Banyak semut (k).
Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0.
Tetapan pengendali visibilitas (β), nilai β ≥ 0.
Tetapan penguapan jejak semut (ρ), nilai harus 0 > ρ > 1 untuk mencegah jejak feromon yang tak hingga.
Visibilitas antar kota (ηij).
ηij =
1 ………………………………………… (6) d ij
Jumlah siklus maksimum (NCmax).
41 ii.
Proses iterasi sampai NCmax a. Untuk setiap semut k = 1, …, n menbangun solusi yang baru.
Pengisian depot dan kota pertama k semut ke dalam tabu list semut kendaraan awal. Tabu list semut ditulis sebagai tabuk,v di mana tabuk,v digunakan menyimpan rute semut k pada kendaraan v.
Penyusunan rute kunjungan semut ke setiap kota. Perjalanan koloni semut berlangsung terus-menerus sampai semua kota telah dikunjungi dan tidak melebihi batas kapasitas kendaraan yang sesuai dengan rumus 4. Untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut.
[τ ] [η ] = ∑ [τ ] [η ] α
k ij
p
β
ij
ij
α
h∈Ω
ij
β
untuk vj ∈ Ω ……………….……… (7)
ij
pijk = 0 untuk lainnya ………………………………… (8) Dengan Ω = {vj ∈ V : vj yang boleh dikunjungi} ∪ {v0}, kota vj dipilih untuk dikunjungi setelah kota vi. Bila kendaraan v pada semut k telah melebihi batas dari kapasitas kendaraan Q maka semut k akan menggunakan kendaraan selanjutnya. b. Perbaiki semua rute kendaraan menggunakan 2-opt heuristik. c. Perhitungan panjang rute kendaraan untuk setiap semut. Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan tabuk,v masing-masing dengan persamaan sebagai berikut.
42 v
n
Lk = ∑∑ d tabuk ,i ( j ), d tabuk ,v ( j + 1) ……………….……… (9) i =0 j =0
d. Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau Lbs dan harga minimal panjang rute tertutup secara keseluruhan adalah Lmin. e. Update jejak feromon. Koloni semut akan meninggalkan jejak-jejak pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak semut antar kota. Aturan dasar dalam meng-update jejak feromon dengan algoritma
Elitist Ant System yaitu dengan persamaan 2 yang telah disebutkan terdahulu.
2.10 Flowcart
Salah satu bentuk untuk menyatakan alur pikiran dalam menyelesaikan suatu pekerjaan adalah dalam bentuk gambar atau bagan yang disebut program flowchart atau bagan alir suatu program [Moh. Sjukani, 2004, p.5]. Berikut adalah simbol-simbol yang digunakan untuk menggambarkan diagram alur.
Tabel 2.3 Tabel simbol flowchart (Sumber: Moh. Sjukani, 2004, p.9) Notasi
Arti notasi Terminal, untuk menyatakan mulai dan selesei sebagai tanda, tidak melakukan suatu pekerjaan khusus.
43
Process, untuk menyatakan assignment statement Input/Output operation, untuk menyatakan proses baca dan proses tulis Decision, untuk menyatakan pengambilan keputusan sesuai dengan suatu kondisi Garis, untuk menyatakan pelaksanaan, atau alur proses
Preparation, pemberi nilai awal suatu variabel Call, memanggil suatu subprogram
Titik connector yang berada pada halaman yang sama. Titik connector yang berada pada halaman yang lain.
2.11 State Transition Diagram
State Transition Diagram (STD) adalah kumpulan keadaan/atribut yang menggambarkan seseorang atau suatu benda pada waktu tertentu, bentuk keberadaan atau kondisi tertentu, seperti menunggu instruksi berikutnya, menunggu pengisian password, dan lain-lain.
STD merupakan modeling tools yang sangat kuat untuk mendekripsikan kelakuan yang dibutuhkan pada sistem yang mempunyai sifat real-time, dan juga bagian interface manusia pada berbagai sistem online (Yourdan, 1989, p.270). Cara kerja sistem ini ada dua macam sebagai berkut.
44
Passive Sistem ini melakukan kontrol terhadap lingkungan, tetapi lebih bersifat memberikan
atau
menerima
data.
Kontrol
suatu
sistem
bertugas
mengumpulkan/menerima data melalui sinyal yang dikirim oleh satelit.
Active Sistem ini melakukan kontrol terhadap lingkungan secara aktif dan dapat menberikan respon terhadap lingkungan sesuai dengan program yang ditentukan. Komponen-komponen utama STD sebagai berikut.
1. State, yang disimbolkan dengan
State adalah kumpulan atribut yang mencirikan seseorang atau suatu benda pada waktu atau kondisi tertentu. 2. Transition State, yang disimbolkan dengan
Transition State yang diberi label dengan ekspresi atau arah, label tersebut menunjukkan kejadian yang menyebabkan transisi terjadi. 3. Condition dan Action
Condition adalah suatu peristiwa pada lingkungan eksternal yang dapat dideteksi oleh sistem. Dan action adalah apa yang dilakukan oleh sistem apabila terjadi perubahan state, atau bisa juga dikatakan sebagai reaksi sistem terhadap suatu kondisi, aksi akan menghasilkan keluaran/tampilan.
Gambar 2.19 Contoh STD (Sumber: Yourdan, 1989, p.265)
