BAB 2 LANDASAN TEORI
2.1
Definisi Algoritma Algoritma berasal dari kata Algoris dan Ritmis yang pertama kali diungkapkan
oleh Abu Ja’far Mohammad Ibn Musa Al Khowarizmi dalam buku Al-jabr w’almulqabala (Horowitz dan Sahni 1978, p1). Kata algorism pertama kali dimaksudkan sebagai aturan dalam melakukan fungsi aritmatika menggunakan Hindu-Arab numerik tetapi berkembang dengan penerjemahaan Eropa Latin dari kata yang diberikan oleh Al Khowarizmi menjadi algorithm dalam bahasa Inggris pada abad ke-18. Kata itu berkembang menjadi arti prosedur pasti untuk memecahkan masalah atau melakukan suatu pekerjaan. Kata algorithm akhirnya diterjemahkan ke dalam bahasa Indonesia menjadi algoritma. Beberapa definisi lain tentang algoritma, antara lain : 1. Menurut Abu Ja’far Mohammad Ibn Musa Al Khowarizmi : Algoritma adalah suatu metode khusus untuk menyelesaikan suatu permasalahan. 2. Menurut Goodman dan Hedetniemi (1977): Algoritma adalah urut-urutan terbatas dari operasi-operasi yang terdefinisi dengan baik, yang masing-masing membutuhkan memori dan waktu yang terbatas untuk menyelesaikan suatu permasalahan. 3. Menurut Gamedev.net (http://www.gamedev.net) : Algoritma adalah sekumpulan instruksi untuk melaksanakan suatu tugas. 4. Menurut wikipedia (http://en.wikipedia.org) :
7 Algoritma adalah sebuah prosedur instruksi-instruksi untuk menyelesaikan sebuah tugas yang diberikan state awal dan kemudian dihentikan pada state akhir.
Berdasarkan definisi di atas maka pengertian algoritma bila dipandang dari sudut pandang ilmu komputer adalah suatu fungsi yang terdiri dari serangkaian langkahlangkah yang terstruktur dan dituliskan secara sistematis yang akan dikerjakan untuk menyelesaikan masalah dengan bantuan komputer.
2.2
Teori Graf
2.2.1
Pengenalan Teori Graf Menurut Johnsonbaugh (2002, p2), teori graf pertama kali diperkenalkan pada
1736, akan tetapi waktu itu belum mendapatkan banyak perhatian, dan pada abad ke-19 beberapa hasil penting dihasilkan, tetapi baru pada sekitar tahun 1920 minat akan teori graf berkembang. Minat pada teori graf adalah pada penerapannya pada banyak bidang, termasuk ilmu komputer, kimia, riset operasi, teknik kelistrikan, bahasa, dan ekonomi. Masalah awal yang muncul pada teori graf adalah penggambaran permasalahan seorang pengawas jalan di Wyoming, Amerika Serikat yang harus melakukan perjalanan ke semua jalan dan membuat laporan tentang kondisi jalan, kejelasan jalur-jalur di jalan, keadaan rambu-rambu lalu lintas, dan sebagainya. Karena ia tinggal di Greybull, cara paling ekonomis untuk memeriksa semua jalan harus dimulai dari Greybull, kemudian menyusuri masing-masing jalan dan kembali lagi ke Greybull.
8
Gambar 2.1 Sistem jalan utama di Wyoming Gambar 2.1 tersebut dapat dibuat modelnya sebagai sebuah graf. Kenyataannya, karena graf digambarkan dengan titik-titik dan garis-garis, maka graf mirip dengan peta jalan. Pada gambar 2.2 di bawah, telah digambarkan sebuah graf G yang merupakan model peta dari gambar 2.1 di atas. Titik-titik pada gambar 2.2 disebut verteks dan garisgaris yang menghubungkan verteks-verteks ini disebut rusuk (edge). Pada pemodelan ini setiap verteks merupakan gambaran dari setiap kota dan diberi nama dengan dengan tiga huruf pertama dari setiap kota yang digambarkan, dan setiap rusuk juga ditandai dengan e1,...,e13, di mana setiap rusuk mewakili setiap jalan yang menghubungkan dua verteks yang berbeda.
9
Gambar 2.2 Model graf dari sistem jalan Wyoming Suatu graf dapat dibagi menjadi 2 jenis berdasarkan arahnya, yaitu graf berarah (Directed Graph) dan graf tak berarah (Undirected Graph). Sebuah graf (atau graf tak terarah) G terdiri dari suatu himpunan V dari verteks-verteks (atau simpul-simpul) dan suatu himpunan E dari rusuk-rusuk (atau busur-busur) sedemikian rupa sehingga setiap e
∈ E dikaitkan dengan pasangan verteks tak terurut. Jika terdapat sebuah rusuk e yang menghubungkan verteks v dan w, kita tulis e = (v,w) atau e = (w,v). Dalam konteks ini, (v,w) menyatakan sebuah rusuk antara v dan w dalam sebuah graf tak terarah dan bukan sebuah pasangan terurut. Pada gambar 2.3 dapat dilihat sebuah contoh graf tak terarah di mana V = {A,B,C,D} dan e = {e1,e2,e3,e4}.
10 Sebuah rusuk e dalam sebuah graf (tak terarah atau terarah) yang menghubungkan pasangan verteks v dan w dikatakan insiden pada v dan w, serta v dan w dikatakan insiden pada e dan disebut verteks-verteks damping (adjacent vertices).
A e1 node
B
e4 e2 D
e3
edge
C
Gambar 2.3 Graf tak terarah Pada gambar 2.2 di atas merupakan contoh dari sebuah graf G = (V,E) yang tidak berarah dengan V = {Gre, She, Wor, Buf, Gil, Sho, Cas, Dou, Lan, Mud} merupakan kumpulan verteks dan E = {e1, e2 ,e3 ,e4 ,e5 ,e6 ,e7 ,e8 ,e9 ,e10 ,e11 ,e12 ,e13}. Rusuk e1 menghubungkan pasangan verteks-verteks tak terurut {Gre, She} dan rusuk e10 menghubungkan pasangan verteks-verteks tak terurut {Cas, Dou}. Rusuk e1 dinyatakan dalam (Gre, She) atau (She, Gre) dan rusuk e10 dinyatakan dalam (Cas, Dou) atau (Dou, Cas). Rusuk-rusuk e4 insiden pada Wor dan Buf dan verteks Wor dan Buf berdampingan. Sedangkan sebuah graf terarah atau directed graph G terdiri dari suatu himpunan V dari verteks-verteks (atau simpul-simpul) dan suatu suatu himpunan E dari rusuk-rusuk (atau busur-busur) sedemikian rupa sehingga setiap rusuk e
∈ E menghubungkan
pasangan verteks terurut. Jika terdapat sebuah rusuk tunggal e yang menghubungkan pasangan terurut (v,w) dari verteks-verteks, kita tuliskan e=(v,w), yang menyatakan
11 sebuah rusuk dari v ke w. Pada gambar 2.4 dapat dilihat graf terarah atau directed graph di mana V = {A,B,C,D,E} dan e = {e1, e2, e3, e4, e5}.
B
e3 E
e1 A
e2
e4
e6
e5 C
D e7
Gambar 2.4 Graf terarah Pada gambar 2.4 diatas rusuk terarah ditunjukkan dengan anak panah. Rusuk e1 menghubungkan pasangan verteks-verteks terurut (A,B) dan rusuk e3 menghubungkan verteks-verteks terurut (E,B). Rusuk e1 dinyatakan dalam (A,B) dan rusuk e3 dinyatakan dalam (E,B). Pada suatu graf jika setiap rusuknya memiliki suatu bobot atau nilai di mana bobot itu merupakan suatu nilai yang bisa berupa biaya atau jarak atau lainnya, graf semacam itu dikatakan graf berbobot (weighted graph).
2.2.2
Teori Lintasan dan Siklus Misalkan v0 dan vn adalah verteks-verteks dalam sebuah graf. Sebuah lintasan
dari v0 ke vn dengan panjang n adalah sebuah barisan berselang-seling dari n+1 verteks dan n rusuk yang berawal dengan verteks v0 dan berakhir dengan verteks vn, (v0 ,e1 ,v1 ,e2 ,v2, ... ,vn-1 ,en ,vn), dengan rusuk ei insiden pada verteks vi-1 dan vi untuk i = 1,2,...,n.
12 Sebagai contoh dari gambar 2.4 di atas kita ambil lintasan dari A ke E merupakan lintasan yang dimulai dari A, yang kemudian menuju ke B, lalu menuju ke D dan berakhir di E sehingga lintasan dari A ke E dapat dituliskan (A, e1, B, e4, D, e6,, E) dengan panjang 3. Sedangkan sebuah siklus adalah sebuah lintasan yang mempunyai panjang lintasan tidak nol dari kota pertama sampai kota terakhir yang merupakan kota pertama juga pada suatu graf, 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, di mana kecuali kota pertama dan kota terakhir yang keduanya sama, tidak terdapat node yang dilalui berulang. Untuk mengamati perbedaan antara lintasan, siklus, siklus sederhana, dengan contoh graf pada gambar 2.5 di bawah yang akan disajikan dalam bentuk tabel.
Tabel 2.1 Perbedaan Lintasan, Siklus, dan Siklus Sederhana Lintasan Lintasan Sederhana Siklus (5, 6, 2, 5) Tidak Ya (2, 6, 5, 2, 4, 3, 2) Tidak Ya (6, 5, 2, 4) Ya Tidak (6, 5, 2, 4, 3, 2, 1) Tidak Tidak
Siklus Sederhana Ya Tidak Tidak Tidak
13 3
2 4 1 7 6 5 Gambar 2.5 Sebuah graf yang tidak berarah
2.2.3
Siklus Hamilton (Hamiltonian Cycle) Sebuah graf G = (V,E) yang merupakan sebuah graf yang terhubung dengan n
node, dikatakan sebagai sebuah Hamiltonian Cycle jika dapat membentuk suatu jalur yang melalui n buah rusuk pada G dan mengunjungi setiap node hanya satu kali lalu kembali ke node awal. Dengan kata lain sebuah graf adalah Hamiltonian Cycle jika dimulai dari suatu node vi ∈ G dan semua node dalam G dikunjungi dengan urutan v1, v2, ..., vn+1 dengan rusuk-rusuk yang menghubungkan verteks-verteks tersebut merupakan anggota E dalam G, pada i ≤ i ≤ n dan semua vi berbeda kecuali v1 dan vn+1 yang merupakan node yang sama. Sir William Rowan Hamilton memasarkan sebuah teka-teki pada pertengahan 1800-an dalam bentuk sebuah dodecahedron (lihat Gambar 2.8). Masing-masing sudut yang berjumlah 20 tersebut diberi nama sebuah kota dan masalahnya berawal dari sembarang kota, kemudian menjalani rusuk-rusuk, mengunjungi setiap kota tepat satu kali, dan kembali ke kota semula. Kita sebut siklus dalam graf G yang mengandung
14 setiap verteks di G tepat satu kali, kecuali verteks awal dan akhir yang muncul dua kali, sebagai siklus Hamilton (Hamiltonian Cycle). Pada gambar 2.6 diperlihatkan sebuah contoh graf yang mempunyai siklus Hamilton. Kemudian pada gambar 2.7 diperlihatkan contoh graf yang sebelumnya pada gambar 2.6 diselesaikan sesuai teka-teki Hamilton di mana siklus dalam graf G mengandung setiap verteks tepat satu kali (kecuali verteks awal dan akhir yang muncul dua kali).
A
B
C
E
D
Gambar 2.6 Sebuah graf yang mempunyai siklus Hamilton
A
B
C
E
D
Gambar 2.7 Sebuah solusi siklus Hamilton
15
Gambar 2.8 (a) Teka-teki Hamilton, (b) Pemodelan Dodecahedron dalam graf, (c) Salah satu penyelesaian berbentuk siklus Hamilton
2.3
Vehicle Routing Problem
2.3.1
Pengenalan Vehicle Routing Problem Vehicle Routing Problem (VRP) adalah nama yang dibuat untuk sebuah problem
atau masalah di mana sebuah set rute yang akan dibentuk untuk sejumlah kota atau pelanggan dengan sejumlah kendaraan yang didasarkan atas satu atau beberapa depot. Setiap kota atau pelanggan hanya akan dilalui satu kali dan dilayani oleh satu kendaraan. Tujuan dari Vehicle Routing Problem adalah untuk mengunjungi sejumlah pelanggan atau kota dengan sejumlah kendaraan dan batasan-batasan lain yang diperlukan dan diketahui sehingga rute tersebut mempunyai biaya yang minimum dan rute bermula dan berakhir pada sebuah depot. Masalah ini pertama kali diformulasikan oleh Dantzig dan Ramser pada tahun 1959 sebagai masalah utama dalam bidang transportasi, distribusi, dan logistik. Dalam sektor perdagangan, transportasi berarti semakin baiknya daya jual dari suatu barang. Maka, dikembangkan metode komputerisasi untuk transportasi yang menghasilkan penghematan yang signifikan dari total biaya.
16
Pelanggan
Depot
Gambar 2.9 Contoh visualisasi input dari Vehicle Routing Problem
Pelanggan
Depot
Rute
Gambar 2.10 Salah satu output dari persoalan VRP dari input gambar 2.9 Vehicle Routing Problem bertujuan untuk meminimalkan jarak yang dilalui oleh armada kendaraan yang melayani sekumpulan pelanggan seperti pada gambar 2.9 dan
17 menghasilkan beberapa rute sesuai jumlah kendaraan seperti pada gambar 2.10. Kasus ini sama dengan Travelling Salesman Problem (TSP), hanya saja untuk Travelling Salesman Problem hanya memiliki satu rute, di mana perbaikan rute dilakukan dalam satu rute itu sendiri, sedangkan dalam Vehicle Routing Problem memiliki banyak rute yang jumlahnya sesuai kendaraan yang akan dipakai walaupun tujuan keduanya sama yaitu untuk mencari jarak minimum dengan melewati semua node sekali. Jika VRP direpresentasikan dalam sebuah graf G = (V,E). Notasi yang digunakan adalah : •
V= {v0,v1,v2,...,vn} adalah himpunan verteks, di mana : o Asumsikan depot terletak di verteks v0 o Misalkan V’ = V tanpa elemen {v0} digunakan sebagai himpunan n kota
•
A = {(vi ,vj) | vi, vj ∈ V ; i ≠ j} adalah himpunan edge
•
C adalah matriks jarak atau biaya cij antara pelanggan vi dan vj yang bernilai nonnegatif
•
d adalah vektor dari permintaan / demand dari pelanggan
•
Ri adalah rute dari kendaraan ke-i
•
k adalah jumlah kendaraan (semua identik). Satu rute untuk tiap kendaraan. Dengan setiap verteks vi dalam V’ diasosiasikan dengan sejumlah barang qi yang
akan diantarkan oleh satu kendaraan. Maka 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, biaya dari solusi masalah ini S adalah : FVRP(S) =
k
∑ C ( Ri) i =1
18 Dalam pembahasan kali ini model Vehicle Routing Problem yang digunakan adalah Capacitated Vehicle Routing Problem (CVRP) di mana sejumlah kendaraan untuk mengantar barang harus melayani sejumlah pelanggan untuk 1 jenis barang dari depot dengan biaya transportasi yang minimum. Maka CVRP seperti VRP dengan tambahan konstrain di mana setiap kendaraan harus mempunyai kapasitas tertentu untuk barang tersebut. Asumsikan depot sebagai node 0 dan pelanggan sejumlah N yang akan dilayani oleh kendaraan sejumlah K. Permintaan untuk pelanggan i adalah qi, kapasitas dari kendaraan k adalah Qk, dan jarak maksimum yang diperbolehkan dari kendaraan k adalah Dk. Maka model matematika dari CVRP menurut formulasi Bodin et al.(1983) dideskripsikan sebagai berikut:
Min
K
N
N
∑∑∑
Cijk Xijk
(1)
k =1 i = 0 j = 0
Xijk = 1 jika kendaraan k datang dari pelanggan i ke j,
(2)
Xijk = 0 jika selain itu
K
N
∑∑
Xijk=1,
j=1,2,...,N
(3)
Xijk=1,
i=1,2,...,N
(4)
k =1 i = 0 K
N
∑∑ k =1 j = 0
19 N
∑
Xitk −
∑
Xtjk = 0, k = 1,2,...,K; t=1,2,....,N
(5)
j =0
i =0 N
N
N
∑∑
dijk Xijk ≤ Dk ,
k=1,2,...,K
(6)
k=1,2,...,K
(7)
i =0 j =0 N
∑ j =0 N
∑
N
qj (
∑
Xijk ) ≤ Qk,
i =0
X0jk≤ 1 ,
k=1,2,...,K
(8)
Xi0k ≤ 1 ,
k=1,2,...,K
(9)
i,j=0,1,2,...,N; k=1,2,...,K
(10)
j =1 N
∑ i =1
Xijk ∈ {0,1},
di mana N merepresentasikan jumlah pelanggan, dan K sebagai jumlah kendaraan, dan Cijk adalah biaya perjalanan dari pelanggan i ke pelanggan j oleh kendaraan k dan dijk adalah jarak perjalanan dari pelanggan i ke pelanggan j oleh kendaraan k. Tujuan dari persamaan fungsi (1) adalah untuk meminimalkan total biaya oleh semua kendaraan. Batasan fungsi (3) dan (4) memastikan bahwa setiap pelanggan dilayani hanya sekali. Batasan fungsi (5) memastikan kelanjutan dari rute. Batasan fungsi (6) menunjukkan bahwa jumlah jarak dari setiap rute mempunyai batas. Batasan fungsi (7) menunjukkan bahwa jumlah demand dari setiap rute tidak dapat melebihi kapasitas dari kendaraan. Batasan fungsi (8) dan (9) memastikan bahwa setiap kendaraan hanya digunakan sekali. Batasan fungsi (10) memastikan bahwa variabel yang dipakai hanya menggunakan integer 0 atau 1.
20 2.3.2
Teknik Penyelesaian Vehicle Routing Problem
Ada beberapa teknik penyelesaian yang telah dipakai untuk Vehicle Routing Problem ini, seperti : 1. Dynamic Programming Dynamic Programming adalah implicit enumerative search method yang dapat dilihat sebagai teknik Divide and Conquer. Untuk menyelesaikan masalah yang besar, dilakukan pemecahan masalah tersebut menjadi bagian-bagian kecil yang serupa dan independen di mana bagian-bagian tersebut dapat dipecahkan dengan metode yang serupa dengan masalah induk. Setelah bagian-bagian kecil tersebut diselesaikan maka hasil-hasil yang diperoleh digabung kembali dengan suatu metode tertentu untuk memberi solusi yang sebenarnya pada masalah tersebut. 2. Branch and Bound Pendekatan branch and bound terdiri dari dua prosedur dasar. Branching adalah proses mempartisi masalah yang besar menjadi dua atau lebih masalah kecil dan 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 dan branch yang buruk tidak akan diproses dengan harapan branch yang baik akan memberikan hasil yang optimal di proses selanjutnya. 3. Branch and Cut Pendekatan branch and cut merupakan pendekatan yang menggunakan branch and bound dengan penambahan algoritma pemotongan atau cutting pada solusi yang didapatkan. Proses yang dilakukan adalah dengan mengaplikasikan branch and bound pada masalah yang akan menghasilkan suatu solusi yang nantinya
21 akan dipotong dengan algoritma tertentu untuk mendapatkan hasil yang lebih baik. Proses tersebut akan diulangi sampai tidak ada pemotongan lagi. 4. Nearest Neighbor Algoritma ini merupakan salah satu dari algoritma pertama yang diterapkan pada masalah pencarian jalur dengan menghubungkan node-node yang mempunyai jarak terpendek dari posisinya sekarang. 5. Farthest Insertion Algoritma ini hampir sama dengan algoritma nearest neighbor dengan perbedaan pada penghubungan node-node yang mempunyai jarak terjauh dari posisinya sekarang. 6. k-opt heuristic Algoritma ini merupakan generalisasi dari algoritma pencarian lokal seperti 2-opt dan 3-opt. Algoritma digunakan untuk memperbaiki rute yang telah terbentuk dengan cara menukar rute yang telah ada dengan rute lain yang mungkin dalam permasalahan tersebut. Pertukaran rute dilakukan apabila hasil penukaran akan menghasilkan hasil yang lebih baik. Proses tersebut diulangi sampai proses penukaran tidak lagi menghasilkan hasil yang lebih baik. 7. Simulated Annealing Simulated Annealing merupakan algoritma heuristik untuk masalah optimalisasi global. SA bekerja berdasarkan proses annealing. Annealing adalah teknik dalam metalurgi yang menyangkut pemanasan dan pendinginan yang terkontrol dari suatu material untuk meningkatkan ukuran dari kristal dan mengurangi kekurangannya. Panasnya menyebabkan atom-atom berpindah dari posisi mereka semula dan bergerak secara acak menuju energi yang lebih tinggi. Dan
22 pendinginannya yang lambat memberikan mereka kesempatan untuk mencari konfigurasi dengan energi yang lebih rendah dari sebelumnya. Dengan kata lain, setiap langkah dari algoritma SA menukarkan solusi yang ada sekarang dengan solusi acak lain yang dekat yang dipilih dengan kemungkinan dari perbedaan nilai fungsi yang bersangkutan dan temperatur global, yang akan turun secara bertahap. 8. Tabu Search Tabu Search dimulai dengan membuat solusi acak dan secara berturut-turut pindah ke salah satu tetangganya. Setiap kali pergerakan dilakukan, solusi sebelumnya akan dimasukkan ke dalam suatu daftar yang disebut tabu list. Dari suatu solusi yang diberikan, tidak semua tetangganya dapat dicapai. Setiap perpindahan akan membawanya pada solusi terbaik yang berada di sekitarnya, tetapi jika perpindahan itu ada di dalam tabu list maka hanya akan diterima apabila dapat menurunkan nilai dari fungsi obyektifnya sampai di bawah level yang telah dicapai sejauh ini (aspiration level). 9. Genetic Algorithm Genetic Algorithm merupakan teknik optimalisasi yang mensimulasikan fenomena dari evolusi natural yang pertama kali diteliti oleh Charles Darwin. Genetic Algorithm bekerja dengan sejumlah populasi dari kemungkinan solusi yang digambarkan sebagai kromosom. Dalam kromosom ada gen-gen yang terpisah yang melambangkan variabel-variabel dari masalah yang ditemui. Evolusi dimulai pada sebuah populasi acak dan berlangsung secara generasi. Dalam setiap generasi, fitness dari tiap individu dari sebuah populasi dievaluasi, sejumlah individu akan dipilih dari populasinya berdasarkan fitness-nya dan
23 dimodifikasi dengan crossover atau mutation untuk membentuk populasi baru. Populasi baru ini yang nantinya akan dipakai pada iterasi berikutnya. 10. Ant Colony System Algoritma Ant Colony Optimization (ACO) merupakan teknik probabilistik untuk menjawab masalah komputasi yang bisa dikurangi dengan menemukan jalur yang baik dengan graf. Algoritma ini diinspirasikan oleh kelakukan semut dalam mencari jalur dari koloni mereka ke tempat makanan. Dalam dunia nyata, semut mencari jalan secara acak, menemukan makanan, dan kembali ke sarang sambil meninggalkan jejak pheromone. Jika semut lain menemukan jalur tersebut, maka mereka tidak akan berjalan secara acak lagi tetapi mulai mengikuti jejak pheromone yang ditinggalkan, kembali sambil meninggalkan jejak pheromone yang kemudian menguatkan jejak tersebut. Jejak pheromone tersebut akan memudar seiring berjalannya waktu maka untuk jalur-jalur yang panjang, jejak tersebut akan mulai memudar sedangkan untuk jalur-jalur yang pendek, jejak tersebut akan mempunyai ketebalan pheromone yang tinggi dan membuat jalur tersebut yang akan dipilih dan jalur yang panjang akan ditinggalkan.
2.4
Particle Swarm Optimization
2.4.1
Standard Particle Swarm Optimization
Particle Swarm Optimization (PSO) merupakan teknik komputasi heuristik berbasis populasi paralel yang diajukan oleh Kennedy dan Eberhart (Kennedy dan Eberhart 1995), yang dimotivasi dari perilaku organisme seperti kumpulan ikan atau burung. Misalkan ada sejumlah burung yang sedang mencari makanan di sebuah daerah
24 secara acak. Di daerah tersebut hanya ada satu potong makanan. Semua burung tidak tahu dimana makanan tersebut berada. Tetapi mereka tahu seberapa jauh makanan tersebut dengan setiap perulangan. Jadi strategi yang baik untuk menemukan makanan tersebut adalah dengan mengikuti posisi burung yang terdekat dengan makanan. PSO dilakukan dengan mengikuti skenario seperti di atas dan digunakan untuk mencari optimalisasi dari sebuah permasalahan. Dalam PSO, setiap solusi adalah sebuah “burung” dalam area pencarian. Akan selanjutnya disebut sebagai partikel. Semua partikel mempunyai nilai fitness yang akan dievaluasi oleh sebuah fungsi fitness, dan mempunyai kecepatan yang akan mengarahkan jalannya dari partikel tersebut. Partikel tersebut akan berjalan di daerah permasalahan dengan mengikuti partikel terbaik yang ada. PSO diinisialisasi dengan sebuah grup partikel(solusi) secara acak dan selanjutnya mencari hasil terbaik. Dalam setiap perulangan, setiap partikel diperbaiki oleh dua nilai “best”. Yang pertama adalah solusi terbaik yang partikel tersebut pernah capai sampai saat ini. Nilai ini disebut Pbest . Nilai “best” yang lain yang dilihat dalam PSO adalah nilai terbaik dari seluruh partikel yang ada sampai saat ini. Nilai ini disebut Gbest . Model optimalisasi global yang diajukan oleh Shi dan Eberhart (1999) seperti berikut: Vid = W × Vid + C1 × Rand × (Pbest −Xid) + C2 × rand × (Gbest − Xid)
(11)
Xid = Xid +Vid
(12)
di mana Vid adalah kecepatan dari partikel i, Xid adalah posisi partikel, W adalah berat inersia. C1 dan C2 adalah faktor learning yang menunjukkan pergerakan dari partikel yang cenderung ke arah Pbest(C1) atau cenderung ke arah Gbest(C2) sehingga nilai yang
25 lebih besar akan mempengaruhi pergerakan partikel. Rand dan rand adalah fungsi random dalam interval [0,1], Pbest adalah posisi terbaik dari partikel ke-i dan Gbest adalah posisi terbaik dari semua partikel di dalam populasi/swarm.
Pseudo code dari PSO adalah FOR setiap partikel Inisialisasi partikel END DO FOR setiap partikel Hitung nilai fitness IF nilai fitness lebih baik daripada nilai fitness terbaik(pBest) yang sudah ada SET nilai sekarang sebagai pBest yang baru END
Pilih partikel dengan nilai fitness terbaik dari semua partikel sebagai gBest FOR setiap partikel Hitung kecepatan partikel menurut persamaan (11) UPDATE posisi partikel menurut persamaan (12) END WHILE kriteria iterasi maksimum atau error minimum belum dipenuhi
26 2.4.2
Discrete Particle Swarm Optimization
Dalam menyelesaikan kasus CVRP ini, diadopsi algoritma kuantum diskrit PSO yang dibuat oleh Yang et al.(2004) berupa PSO biner (Binary PSO). Dalam teorinya, sebuah bit sebagai unit pembawa informasi selalu dalam kondisi interval [0, 1]. Vektor partikel didefinisikan sebagai berikut: V = [V1, V2,..., VM ], (Vi = [vi1 ,vi2,...,viN ]) di mana 0 ≤ vij ≤ 1 (i=1,2,...,M; j=1,2,...,N); N adalah panjang partikel dan M adalah ukuran swarm. vij sebagai probabilitas dari partikel ke-i dari bit ke-j yang bernilai 0. Asumsikan X = [X1, X2, X3,..., XM] (Xi = [xi1, xi2,..., xiN]) adalah denotasi partikel untuk masalah yang praktikal. Di mana xij ∈{0,1} (i = 1, 2, …, M; j = 1, 2, …, N) merepresentasikan korespondensi partikel diskrit dari partikel kuantum vij, N adalah panjang partikel dan M adalah ukuran swarm. Untuk setiap vij (i = 1,2,...,M; j = 1,2,...,N), hasilkan angka random dalam interval [0,1]. Jika angka random lebih besar dari vij, maka xij = 1, selain itu xij= 0. Algoritmanya dapat ditulis sebagai berikut: Vlocalbest = α × xlocalbest + β × (1 − xlocalbest)
(13)
Vglobalbest = α × xglobalbest + β × (1 − xglobalbest)
(14)
V = w × V + c1 × Vlocalbest + c2 × Vglobalbest
(15)
di mana α + β = 1, 0 < α, β < 1 adalah parameter pengendali yang mengindikasikan derajat kendali dari V. w + c1 + c2 = 1, 0 < w, c1, c2 < 1. Dalam persamaan (15), bagian pertama merepresentasikan inersia dari probabilitas sebelumnya; bagian kedua adalah “cognition”, yang merepresentasikan probabilitas eksplorasi lokal; bagian ketiga adalah
27 “social”, yang merepresentasikan kerjasama antara semua partikel kuantum. Proses dari implementasi DPSO sebagai berikut: Langkah 1 : Inisialisasi partikel kuantum V dan partikel diskrit X Langkah 2 : Untuk partikel diskrit X, hitung fitness Langkah 3 : Hitung Vlocalbest seperti pada persamaan (13) Langkah 4 : Hitung Vglobalbest seperti pada persamaan (14) Langkah 5 : Hitung probabilitas kuantum V seperti pada persamaan (15) Langkah 6 : Hitung partikel diskrit X, jika random[0,1] > vij, maka xij = 1, selain itu xij=0 Langkah 7 : Ulang ke langkah 2 sampai satu dari kriteria berhenti terpenuhi
2.4.3
Fitness Function
Fitness digunakan untuk mengevaluasi kondisi dari partikel di dalam swarm. Biasanya, memilih fungsi obyektif yang cocok sebagai fitness function adalah salah satu faktor kunci untuk mendapatkan resolusi yang baik pada masalah yang relevan. Dalam CVRP, obyektif yang dicari adalah minimalisasi dari jumlah jarak atau biaya. Maka persamaan yang cocok sebagai fitness function adalah:
Fit = Min
K
N
N
∑
∑
∑
k=1
i=0
j=0
Cijk Xijk
Fungsi tersebut telah dijelaskan dalam bagian sebelumnya. Obyektif pencarian adalah minimalisasi biaya maka partikel dengan fitness yang minimal akan dipertahankan selama proses optimalisasi.
28 2.4.4
Aplikasi DPSO pada CVRP
Permasalahan terletak pada bagaimana cara menerapkan DPSO pada CVRP. Dengan menemukan cara untuk pemetaan yang cocok dari solusi masalah ke partikel DPSO, masalah tersebut dapat diatasi. Asumsikan masalah di mana N pelanggan akan dilayani oleh sejumlah K kendaraan, dan kita dapat membuat area pencarian dalam dimensi N × K. Setiap partikel berisi K bagian dan setiap bagian mempunyai N titik diskrit. Nilai dari setiap titik diskrit tersebut adalah 0 atau 1. Jika nilainya adalah 1, itu melambangkan kalau pelanggan yang bersangkutan dilayani oleh kendaraan yang berkaitan. Posisi dari setiap partikel mengindikasikan urutan dari pelanggan yang dilayani oleh tiap kendaraan. Sebagai contoh, dalam masalah 8 pelanggan yang akan dilayani oleh 2 kendaraan ditampilkan dalam gambar 2.11 yang menampilkan posisi partikel untuk masalah ini.
Penggambaran dari Capacitated Vehicle Routing Problem (Pelanggan, Kendaraan) (1, 2), (2, 1), (3, 1), (4, 2), (5, 1), (6, 2), (7, 2), (8, 1) Pemetaan
Kendaraan pertama Dimensi : Posisi :
Kendaraan kedua
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 Gambar 2.11 Pemetaan DPSO
29 Dalam proses koding, partikel direpresentasikan sebagai sebuah array 2 dimensi seperti tergambar pada gambar 2.11. Untuk CVRP dengan sejumlah N pelanggan yang akan dilayani oleh sejumlah K kendaraan, dimensi pertama dari array 2 dimensi dari partikel adalah vektor berdimensi N × K (s1, s2, ..., sN × K), di mana si (i = 1, 2, ..., N × K) adalah angka yang berada pada interval [1, N × K] yang tidak sama satu dengan yang lainnya. l = si – {(si - 1)/N} × N merepresentasikan pelanggan yang ke-l dan k = {(si 1)/N} + 1 merepresentasikan kendaraan ke-k. Dimensi kedua juga vektor berdimensi N × K, di mana setiap posisi bernilai 0 atau 1. Jika bit ke-(si) bernilai 1, itu melambangkan kalau pelanggan ke-l (l = si – {(si - 1)/N} × N) akan dilayani oleh kendaraan ke-k (k = {(si - 1)/N} + 1). Selain itu, pelanggan ke-l tidak akan dilayani oleh kendaraan ke-k. Didasarkan oleh konstrain CVRP, harus dapat dipastikan bahwa setiap pelanggan dilayani tepat sekali oleh tepat satu kendaraan, panjang maksimum dari setiap rute tidak boleh melebihi konstrain dan total permintaan dari rute manapun tidak boleh melebihi kapasitas dari kendaraan. Tetapi, DPSO tidak dapat memastikan syarat-syarat konstrain tersebut terpenuhi, maka perlu dilakukan pemeriksaan terhadap solusi setelah operasi DPSO, sebagai berikut : Periksa setiap partikel untuk setiap rute. Jika nilai lebih dari satu posisi dari posisi-posisi yang bersangkutan dalam partikel bernilai 1, pilih secara acak satu posisi dari posisi-posisi tersebut dan jadikan nilainya 1 dan lainnya bernilai 0. Jika nilai dari semua posisi dari posisi-posisi tersebut bernilai 0 maka pilih secara acak satu posisi dan jadikan nilainya 1 dan yang lain tidak berubah. Jika total jarak dari sebuah rute melebihi nilai yang dibatasi atau total permintaan dari setiap rute melebihi kapasitas dari
30 kendaraan, solusi tersebut menjadi tidak feasible (tidak mungkin). Untuk solusi-solusi yang tidak feasible, jalankan operasi DPSO sampai solusi menjadi feasible (mungkin).
2.4.5
Pair Exchange
Dalam CVRP, algoritma DPSO dipakai untuk menempatkan posisi-posisi pada jalur-jalur yang ada. Sedangkan pair exchange dapat dipakai untuk merubah urutan dari pelanggan yang akan dilayani oleh tiap kendaraan. Pair exchange dapat mempengaruhi kinerja dari solusi CVRP. Dalam skripsi ini pair exchange dilakukan dengan menukarkan posisi secara berpasangan. Sebagai contoh pada gambar 2.12 adalah hasil dari pair exchange dari rute pertama dengan menukarkan posisi yang bersebelahan. Rute pertama Dimensi : Posisi :
2 1 4 3 6 5 8 7 1 0 0 1 0 1 1 0
Gambar 2.12 Posisi rute setelah dilakukan Pair Exchange
Setelah menukar posisi pelanggan dalam rute yang sama selama beberapa kali, fitness dari solusi baru tersebut dihitung. Jika fitness dari solusi baru tersebut lebih baik maka solusi baru tersebut diterima.
