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 langkah-

langkah 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 garis-

garis 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

A

B

D C

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).

e1

node e4

e2 edge

e3

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

A

B

C D

E

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}.

e3

e1

e2 e4 e6

e5

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 Siklus Sederhana

(5, 6, 2, 5) Tidak Ya Ya (2, 6, 5, 2, 4, 3, 2) Tidak Ya Tidak (6, 5, 2, 4) Ya Tidak Tidak (6, 5, 2, 4, 3, 2, 1) Tidak Tidak Tidak

13

1

2

3

4

56

7

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

B

E D

C

A

B

E D

C

A

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).

Gambar 2.6 Sebuah graf yang mempunyai siklus Hamilton

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

Gambar 2.9 Contoh visualisasi input dari Vehicle Routing Problem

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

Depot

Pelanggan

Depot

Pelanggan

Rute

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 non-

negatif

• 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

iRiC

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

k

N

i

N

j1 0 0Cij

k Xijk (1)

Xijk = 1 jika kendaraan k datang dari pelanggan i ke j, (2)

Xijk = 0 jika selain itu

∑∑= =

K

k

N

i1 0 Xij

k=1, j=1,2,...,N (3)

∑∑= =

K

k

N

j1 0Xij

k=1, i=1,2,...,N (4)

19

∑=

N

i 0

Xitk − ∑

=

N

j 0Xtj

k = 0, k = 1,2,...,K; t=1,2,....,N (5)

∑∑= =

N

i

N

j0 0dij

k Xijk ≤ Dk , k=1,2,...,K (6)

∑=

N

j 0

qj ( ∑=

N

i 0

Xijk ) ≤ Qk, k=1,2,...,K (7)

∑=

N

j 1

X0jk≤ 1 , k=1,2,...,K (8)

∑=

N

i 1

Xi0k ≤ 1 , k=1,2,...,K (9)

Xijk ∈ {0,1}, i,j=0,1,2,...,N; k=1,2,...,K (10)

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 dij

k

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, xi

2,..., 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 xi

j = 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:

K N N

Fit = Min ∑ ∑ ∑ Cijk Xij

k

k=1 i=0 j=0

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)

Gambar 2.11 Pemetaan DPSO

(1, 2), (2, 1), (3, 1), (4, 2), (5, 1), (6, 2), (7, 2), (8, 1)

Pemetaan

Dimensi : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Posisi : 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

Kendaraan pertama Kendaraan kedua

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.

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.

Dimensi : 2 1 4 3 6 5 8 7 Posisi : 1 0 0 1 0 1 1 0

Rute pertama