BAB2 LANDASAN TEORI 2.1 Teori Graf 2.1.1 Pengenalan Teori Graf Teorigrafadalahcabangilmuyangmempelajarisifat-sifatgraf,yangpertama 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 Knigsberg (Sumber: Rinardi Munir, 2005, p.355) Menurutcatatansejarah,masalahjembatanKnigsbergadalahmasalahyang pertamakalimenggunakangraf(tahun1739)[RinardiMunir,2005,p.354].Dikota Knigsberg(sebelahtimurnegarabagianPrussia,Jerman),sekarangbernamakota Kaliningrad,terdapatsungaiPregalyangmengalirmengitariPulauKneiphoflalu bercabangmenjadiduabuahanaksungaiyangdiperlihatkanolehgambar2.1. Permasalahannyaialahmenemukanpejalananataurutedarisuatukotamelaluiketujuh 11buahjembatanmasing-masingtepatsatukali,kemudiankembalilagiketempatawal. Pulautersebuttidakdapatdicapaiolehruteapapunselainmelaluijembatan-jembatan tersebut. Tahun1736,LeonhardEuleradalahorangpertamayangberhasilmenemukan jawabanmasalahtersebutdenganpembuktianyangsederhana(melaluikaryatulisannya SevenBridgesofKnigsberg).Daratan(titik-titikyangdihubungkanolehjembatan) dinyatakansebagaititikdisebutverteksdanjembatandinyatakansebagaiedge.Dari analisaEulerpadajembatanKnigsbergmenghasilkansebuahmodelgraf,sepertiyang diperlihatkanpadagambar2.2.AnalisisEulermengenaipermasalahanjembatandi Knigsbergtidakmenghasilkansolusi.Karenaorangtidakmungkinmelaluiketujuh jembatanmasing-masingtepatsatukalidankembalilagiketempatawalkeberangkatan jika derajat (banyaknya garis yang bersisian dengan titik) setiap verteks tidak seluruhnya genap.PenemuanEuleradalahkunciyangmenandaiperkembangantopologi,dimana perbedaanantaralayoutsebenarnyadangrafscematicadalahcontohyangbagusuntuk gagasan bahwa topologi tidak dibatasi dengan bentuk kaku dari objek-objek tertentu. Gambar 2.2 Graf yang merepresentasikan jembatan Knigsberg (Sumber: Rinardi Munir, 2005, p.355) CBAD122.1.2Definisi Graf Grafadalahkumpulanverteksataunodeyangdihubungkansatusamalain melaluisisi/rusuk/busur/edge,yangdigunakanuntukmerepresentasikanobjek-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.Vadalah 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-atomsuatuzat,namaanak,jenisbuah,komponenalatelektronikdansebagainya.Edge dapatmenunjukkanhubungansembarangsepertirutepenerbangan,jalanraya, sambungantelepon,ikatankimia,danlain-lain.Jikaterdapatsebuahrusukeyang menghubungkan verteks v dan w, ditulis edge (v, w). 2.1.3Jenis Graf Graf dapat dibagi menjadi 2 jenis berdasarkan arahnya, yaitu sebagai berikut. 1.Graf tidak berarah (undirected graph) Grafyangsisinyatidak mempunyaiorientasiarah. Edge (v, w) = edge (w,v) adalah sisi yang sama, di tampilkan pada gambar 2.3di mana V = {A, B, C, D} dan e = {e1, e2, e3, e4}. 13 Gambar 2.3 Graf tidak berarah 2.Graf berarah (directed graph) Grafyangsetiapsisinyadiberikanorientasiarah,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}. Gambar 2.4 Graf berarah (Sumber: Seymour Lipschutz, 1985, p.119) Sebuahstrukturgrafbisadikembangkandenganmemberibobotataunilaipada tiapedgedimanamerupakansuatunilaiyangdapatberupabiayaataujarak,graf semacaminidisebutgrafberbobot(weightedgraph).Dalampengajaranteorigraf [SeymourLipschutz,1985,p.85],terdapatgrafkhususbeberapadiantaranyaadalah sebagai berikut. e4 e3 e2 e1 edge node DCABABDe1 e2 e3 e4e6 e5 e7 C14a)Completegraphialahgrafdimanasetiapverteksberhubungandengansemua verteksyanglain(semuavertekssalingberhubungan).Biasanya direpresentasikandengansimbolKn,dimanaKadalahcompletegraphdann 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)Bipartitegraphadalahgrafdimanasatuverteksnyadibagikedalamduasubset verteksmdann,sedemikiansehinggatidakadarusukyangmenyebabkan verteks-verteksdalamsubsetyangsama.Biasanyadirepresentasikandengan simbolKm,n ,dimanaKadalahbipartitegraph,danmadalahjumlahsunset verteks m, dan n adalah jumlah subset n. Gambar 2.6 Contoh model bipartite graph (K3,3) (Sumber: Seymour Lipschutz, 1985, p.86) 15c)Completebipartitegraphadalahbipartitegraphdimanasetiapverteksdarim harusmemilikirusukyangberhubungankesemuaverteksdarin.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)Regulargraphadalahgrafdimanasetiapverteksnyamemilikiderajatyang 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.4Teori Lintasan dan Siklus Misalkanvodanvnadalahverteks-verteksdalamsebuahgraf[Richard Johnsonbaugh, 2002, p.12]. Sebuah lintasan dari vo ke vn dengan panjang n adalah sebuah barisanberselang-selingdari(n+1)verteksdannedgeyangberawaldenganverteksvo 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). Sebuahsiklusadalahsebuahlitasanyangmempunyaipanjanglintasantidaknol darikotapertamasampaikotaterakhiryangmerupakankotapertama,dimanatidak terdapat rusuk yang dilalui lebih dari sekali. Sebuahsiklussederhanaadalahsiklusdarikotapertamasampaikotaterakhir yangmerupakankotaterakhirjugapadasuatugraf,yangkecualikotapertamadankota terakhir yang sama, tidak terdapat verteks yang berulang Untukmengamatiperbedananataralintasan,siklus,siklussederhana,dengan contoh graf pada gambar 2.10 dapat dilihat yang akan disajikan dalam bentuk tabel. Gambar 2.10 Graf tidak berarah (Sumber: Richard Johnsonbaugh, 2002, p.12) 123456717Tabel 2.1 Perbedaan Lintasan, Siklus, dan Siklus Sederhana (Sumber: Richard Johnsonbaugh, 2002, p.16) LintasanLintasan SederhaaSiklusSiklus Sederhana ( 5, 6, 2, 5)Tidak YaYa ( 2, 6, 5, 2, 4, 3, 2)TidakYaTidak( 6, 5, 2, 4)YaTidakTidak( 6, 5, 2, 4, 3, 2, 1)TidakTidakTidak 2.1.5Representasi 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: jika {u, v} adalah edge, yaitu vi adjacent terhadap vj lainnya 2.Matriks incident Misalkan M=(mij) adalah matriks m x i didefinisikan oleh: verteks vi adalah incident pada edge ei lainnya Contoh: Diketahui graf G: v1 v2 v3v4v5e1e2e3e4e5e6e7e8=01ija=01m18maka:v1 v2 v3 v4v5 e1 e2 e3 e4 e5e6 e7 e8 =0 1 1 0 11 0 1 0 11 1 0 1 10 0 1 0 11 1 1 1 054321vvvvvA=0 1 1 0 0 0 1 01 0 1 1 0 0 0 01 1 0 0 1 1 0 00 0 0 0 1 0 0 10 0 0 1 0 1 1 154321vvvvvm(a)(b) Gambar 2.11 matriks adjecency (a) dan matriks incidence (b) (Sumber: Seymour Lipschutz, 1985, p.87) 2.1.6Graf Hamiton Lintasan Hamilton ialah lintasan yang melalui tiap verteks di dalam graf tepat satu kali[RinardiMurni,2005,p.408].SirkuitHamiltonialahsirkuityangmelaluitiap verteksdidalamgraftepatsatukali,kecualiverteksasal(sekaligusverteksakhir)yang dilaluiduakali.GrafyangmemilikisirkuitHamiltondinamakangrafHamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton. 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) (a)(b)(c) 12 34 12 34 12 34 19b.Graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1) c.Graf yang tidak memiliki lintasan maupun sirkuit Hamilton 2.2Algoritma Secaraumumalgoritmaialahsejumlahlangkahkomputasiyangmengubah 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:setiaplangkahalgoritmaharusdidefinisikandengantepatdantidak 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. PadaMerriam-WebstersCollegiateDictionaryistilahalgorithmdiartikan sebagaiprosedurlangkahdemilangkahuntukmemecahkanmasalahatau menyeleseikan suatu tugas khususnya dengan menggunakan bantuan komputer. Algoritma[Moh.Sjukani,2004,p.1]adalahalurpikirandalammenyelesaikan suatupekerjaan,yangdituangkandalambentuktertulisyangdapatdimengerti oleh orang lain. 202.3Optimisasi 2.3.1Definisi 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 merujukpadastudipermasalahanyangmencobauntukmencarinilaiminimalatau maksimaldarisuatufungsiriil.Untukdapatmencapainilaioptimalbaikminimalatau maksimaltersebut,secarasistematisdilakukanpemilihannilaivariabelintegeratauriil yangakanmemberikansolusioptimal.Nilaioptimaladalahnilaiyangdidapatmelalui suatuprosesdandianggapmenjadisuatusolusijawabanyangpalingbaikdarisemua solusi yang ada. 2.3.2Macam-Macam Permasalahan Optimisasi Persoalanyangberkaitandenganoptimisasisangatkompleksdalamkehidupan sehari-hari.Nilaioptimalyangdidapatdalamoptimisasidapatberupabesaranpanjang, waktu,jarak,danlain-lain.Berikutiniadalahbeberapapersoalanyangmemerlukan optimisasi: a.Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain. b.Menentukanjumlahpekerjaseminimalmungkinuntukmelakukansuatuproses produksiagarpengeluaranbiayapekerjadapatdiminimalkandanhasilproduksi tetap maksimal. c.Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau. d.Mengaturroutingjaringankabelteleponagarbiayapemasangankabeltidak terlalu besar dan penggunaannya tidak boros. 21Selainbeberapacontohdiatas,masihbanyakpersoalanlainnyayangterdapat dalam kehidupan sehari-hari. 2.3.3Penyelesaian 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 Metodekonvensionalialahmetodeyangmenggunakanperhitunganmatematis 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 DynamicProgramming(DP)adalahprosedurmatematikayangdidesainutama untukmeningkatkanefisienkomputerisasidalammemilihpermasalahan-permasalahan pemograman matematika dengan memecah permasalahan tersebut menjadi bagian-bagian lebihkecil[HamdyA.Taha,1995,p.345].Setiapbagian-bagiantersebutmenghasilkan satu variabel optimasi. Hasil komputasi untuk bagian-bagian yang berbeda dihubungkan denganrecursivecomputationsyangakanmenghasilkansolusioptimalyangfeasible untuk semua permasalahan. 22B.Branch and Bound Teknikbranchandbound(B&B)terdiridariduaprosedurdasar.Branching adalahprosesmempartisimasalahyangbesarmenjadiduaataulebihmasalahkecil. Bounding adalah proses menghitung batas bawah pada solusi optimal dari masalah kecil tersebut.Boundingfunctionyangdigunakanyaitupemrosesanhanyadilakukanpada 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 Teknikbranchandcutmerupakanteknikyangmenggunakanbranchdanbound denganpenambahanalgoritmacuttingpadasolusiyangdidapatkan.Prosesyang dilakukanialahdenganmengaplikasikanbranchandboundpadasolusiyangnantinya 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 berkerjaberdasarkanstrategipencarianpintarpadapemecahanmasalahdengan komputer,denganmenggunakanbeberapapendekatan[http://en.wikipedia.org/wiki/ Heuristic _algorithm].Duatujuandasardalampemecahanmasalahoptimisasipadailmukomputer adalah mencari algoritma yang cepat menyelesaikan masalah dan memperoleh hasil yang 23optimal.Metodeheuristikialahmetodeyangmenghilangkansalahsatuatauduadari tujuantersebut.Misalnya,padapemecahanmasalahoptimisasi,dihasilkansolusiyag cukupoptimal,tetapisecaramanual,belumtentusolusiyanglebihoptimaldapat diperolehkarenakompleksnyapermasalahanyangada.Atau,solusiyangdidapat dihasilkan dengan waktu yang sangat cepat, namun secara manual masih dapat ditemukan hasil yang lebih optimal.Jadi,hasilyangdiperolehbelumtentuyangpalingoptimal.Tetapipenggunaan metodeheuristikyangumumtetapditerapandidunianyata.Karenaterdapatbeberapa masalah, di mana hanya metode heuristik yang memungkinkan untuk memperoleh solusi yang optimal dalam waktu yang sangat singkat. Gambar 2.13 Sistem yang menggunakan kecerdasan buatan (Sumber: Sri Kusumadewi, 2005, p.1) Padagambar2.14[SriKusumadewidanH.Purnomo,2005,p.1],inputyang diberikanpadasistemyangmenggunakankecerdasanbuatanadalahmasalah.Sistem harusdilengkapidengansekumpulanpengetahuanyangadapadabasispengetahuan. Sistem harus memiliki inference engine agar mampu mengambil kesimpulan berdasarkan faktaataupengetahuan.Outputyangdiberikanberupahasilmasalahsebagaihasildari inferensi. Basis PengetahuanInference Engine Sistem yang menggunakan AI MASALAHSOLUSI 24A.Algoritma Generate and Test Padaprinsipnyametodeinimerupakanpenggabunganantaradepth-firstsearch dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaaanawal.Nilaipengujianberupajawabanyaatautidak.Algoritmanyaadalah sebagai berikut. 1.Bangkitkansuatukemungkinansolusi(membangkitkansuatutitikataulintasan tertentu dari keadaan awal). 2.Ujiuntukmelihatapakahnodetersebutbenar-benarmerupakansolusidengan caramembandingkanvertekstersebutatauverteksakhirdarisuatulintasanyang dipilih dengan kumpulan tujuan yang diharapkan. 3.Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama. B.Simulated Annealing SimulatedAnnealing(SA)adalahmetodepencarianlokalyangacak,dimana solusisementaradimodifikasisehinggamengarahpadahasilyanglebihbaik,dengan beberapa kemungkinan. Mekanisme ini dapat mengantisipasi local optima yang burukIdedasarSAterbentukdaripemrosesanlogam.Annealing(memanaskan kemudianmendinginkan)dalampemrosesanlogaminiadalahsuatuprosesbagaimana membuatbentukcairberangsur-angsurmenjadibentukyanglebihpadatseiringdengan penurunantemperature.SAbiasanyadigunakanuntukpenyelesaianmasalahyangmana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas.25PadaSA,ada3parameteryangsangatmenentukanadalahtetangga,gain,dan temperatur.Tetanggaakansangatberperandalambentukperubahanpadasolusi. Pembangkitan bilangan random akan berimplikasi adanya probabilitas. C.Tabu Search Tabu Search (TS) merupakan suatu metode optimisasi yang menggunakan short-termmemoriataumemorijangkapendekuntukmenjagaagarprosespencariantidak terjebakpadanilaioptimumlokal.MetodeinimenggunakanTabuListuntuk menyimpan sekumpulan solusi yang telah dievaluasi. Pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkanterlebih 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 lagisolusiyangtidakmenjadianggotatabulist,makanilaiterbaikyangbarusaja diperoleh merupakan solusi yang sebenarnya. D.Algoritma Genetika GeneticAlgorithm(GA)pertamakalidikembangkanolehJohnHollanddari universitasMichigan(1975).GAadalahalgoritmaheuristikyangdidasarkanatas mekanismeevolusibiologis.Keberagamanpadaevolusibiologisadalahvariasidari kromosom antar individu organisme. Individu yang lebih kuat (fit) akan memilikitingkat 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. 26Kemampuan organisme untuk melakukan reproduksi Keberadaan populasi organisme yang bisa melakukan reproduksiKeberagaman organismedalam suatu populasi Perbedaan kemampuan untuk survive PadaGA,teknikpencariandilakukansekaligusatassejumlahsolusiyang mungkindikenaldenganistilahpopulasi.Individuyangterdapatdalamsatupopulasi disebutdenganistilahkromosom.Kromosominimerupakansuatusolusiyangmasih berbentuksimbol.Populasiawaldibangunsecaraacak,sedangkanpopulasiberikutnya merupakanhasilevaluasikromosom-kromosommelaluiiterasiyangdisebutdengan istilahgenerasi.Padasetiapgenerasi,kromosomakanmelaluiprosesevaluasidengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dalam kromosom menunjukkankualitaskromosomdalampopulasitersebut.Generasiberikutnyadikenal denganistilahanak(off-spring)terbentukdarigabungan2kromosomyangbertindak sebagaiinduk(parent)denganoperatorpenyilangan.Selainoperatorpenyilangan,suatu kromosom dapat dimodifikasidengan menggunakan operator mutasi. E.Harmony Search Harmonysearch(HS)ialahalgoritmametaheuristic(algoritmasoftcomputing ataualgoritmaevolusioner)meniruprosesimprovisasimusisi [http://en.wikipedia.org/wiki/Harmony_search].Setiapmusisimemainkannadauntuk mencariharmoniyangterbaikbersama-sama,samasepertisetiapvariabelkeputusan dalamprosesoptimasimemilikinilaiuntukmenemukanvektorterbaikserentak.HS mencoba mencari vektor x yang meminimalkan beberapa pengeluaran fungsi.27 F.Particle Swarm Optimization ParticleSwarmOptimization(PSO)merupakanteknikkomputasiheuristik berbasispopulasiparallelyangdiajukanolehKennedydanEberhart(1995),yang dimotivasikandariperilakuorganismesepertipopulasiikanataupopulasiburung. Andaikanadasejumlahburungyangsedangmencarimakanandisebuahdaerahsecara acak [http://www.swarmintelligence.org/tutorials.php]. Di daerah tersebut hanya ada satu potong makanan. Semua burung tidak mengetahui posisi makanan berada. Tetapi mereka tahuseberapajauhmakanantersebutdengansetiapperulangan.Jadistrategiyangbaik untukmenemukanmakanantersebutadalahmengikutiposisiburungyangterdekat dengan makanan. 2.4Travelling Salesman Problem Traveling Salesman Problem (TSP) adalah permasalahan pada matematika diskrit danoptimalisasikombinatorial[http://www.tsp.gatech.edu/history/index.html].TSP pertamakalidikemukakanpadatahun1800-anolehseorangmatematikawanasal Irlandia, sir William Howard Hamilton dan seorang matematikawan asal inggris, Thomas PenyngtonKirkman.BentukumumdariTSPpertamadipelajariolehpara matematikawanmulaitahun1930.DiawaliolehKarlMengerdiViennadanHarvard, permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton. TSP memerlukan keputusan dari siklus biaya atau panjang yang minimal, melalui penerusuransetiapnodepadagrafyangrelevan[ThammapimookkuldanChamsethikul, 2001,p.5].Jikabiayaantardualokasitidaktergantungpadaarahlintasan,makaTSP 28jenis ini bersifat simetris. Sedangkan TSP yang bersifat asimetris, yang disebut direcred TSP. TSPsebagaisalahdariNP-completeproblemsdapatdiselesaikandengan Pendekatan heuristik yang terbagi dalam tiga kelas, sebagai beikut. Tourconstructionprocedures,menghasilkanperkiraanperjalananoptimaldari jarakmatriks.SepertiprosedurNearestNeighbor,ClarkeandWrightSaving, prosedur Insertion, Minimal Spanning Tree, dan Christofides heuristic. Tourimprovementprocedures, berusaha mencari perjalanan yang lebih baik dari perjalanan awal. Seperti 2-opt dan 3-opt heuristik dan prosedur k-opt. Tourcompositeprocedures,membuatperjalananawaldarisalahsatucomposite 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.5Multi Travelling Salesman Problem MultiTravellingSalesmanProblem(M-TSP)adalahgeneralisasidariTSP,yang merupakanpersoalanyanglebihmendekatipermasalahandalamdunianyata.Dalam 29masalahinidiperlukanlebihdarisatukendaraanpengangkutuntukpendistribusian 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 TSPyangsamadenganmembuatperbanyaksebanyakmkalidarilokasiyangsama, tetapitidakberhubungansatusamalain.BebearapaformulaM-TSPditurunkansecara independentolehBellmoredanHong(1974),Orloff(1974),SvetskadanHuckfeltz (1973). PadaM-TSPharusterdapatm2salesmanyangmengunjunginkotasecara bebas.Tidakadakotayangdikunjungiolehlebihdarisatusalesmandansetiapm 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.6Vehicle 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 pelanggandidasarkanatassatuataubeberapadepot.Setiapkotaataupelangganakan dilayaniolehsatukendaraandenganbatasan-batasantertentu;rutetersebutdiawalidan diakhiri di depot [http://neo.lcc.uma.es/radi-aeb/WebVRP].PermasalahaninipertamakalidiformulasikanolehDantzingdanRamserpada tahun 1959 sebagai pusat permasalahan utama dalam bidang transportasi, distribusi, dan logistik. Dalam beberapa sektor pasar, transportasi memiliki nilai persentase yang tinggi yangdimasukkandalamkeuntungan.Setelahitudikembangkanmetodekomputerisasi untuk transportasi yang menghasilkan penghematan total biaya yang signifikan. 30VRPadalahgeneralisasidariTSP.Maka,TSPadalahsebuahVRPtanpabatasan 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. Gambar 2.15 Contoh visualisasi input dari Vehicle Routing Problem (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/) Gambar 2.16 Salah satu output dari VRP dari input gambar 2.15 (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/) Depot PelangganRute Depot Pelanggan31TujuandariVehicleRoutingProblemialahuntukmeminimalkanjarakyang dilalui oleh armada kendaraan yang melayani sekumpulan pelanggan seperti pada gambar 2.18danmenghasilkansalahsaturutesepertipadagambar2.19denganbanyaknya kendaraan yang disediakan atau digunakan. Padaperkembangannya[TitipornThammapimookkul,2001,p.3],VRPmemiliki beberapakarateristiksehinggadapatdibagi-bagidalambeberapakategorimasalah, sepertiyangdapatditunjukkandalamtabel2.2.KategoriinidibuatolehBodindan 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) NoKarateristikVarian yang mungkin 1Jumlah kendaraan pengangkut Satu kendaraan pengangkut Multi kendaraan pengangkut 2Tipe kendaraan pengangkut Homogen (satu tipe) Heterogen (multi tipe) Tipe khusus 3Tipe permintaanPermintaan deterministik (telah dikethui sebelumnya) Permintaan stokastikPermintaan kepuasan sebagian 4Lokasi permintaanSimpul Garis campuran 5Tenpat asal kendaraan (pusat) Satu pusat Multi pusat 6Jaringan yang mendasariTidak berarah Berarah Campuran Euclid7Batasan kapasitas kendaraan pengangkut Semuanya sama Jalur yang berbeda Kapasitas tak terbatas 328Rute maksimumSama untuk semua rute Berbeda untuk setiap rute Tidak ditentukan 9Sistem pengoperasianPengambilan saja Pengiriman saja Pengambilan dan pengantaran 10Biaya Variable atau biaya rute Biaya tetap pengoperasian atau biaya tetap kendaraan pengangkut Biaya pengangkut umum 11Tujuan Meminimalkan biaya total ruteMeminimalkan 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 sebuahgrafG=(V,E)[http://neo.lcc.uma.es/radi-aeb/WebVRP],makanotasiyangdigunakan ialah sebagai berikut. V = {v0, v1, , vn} ialah set atau sekumpulan verteks yang menggambarkan depot, pelanggan ataupun persimpangan jalan, di mana: ov0 sebagai depot. ov1, , vnsebagai pelanggan oMisalakan 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. 33kialahbanyaknyakendaraan(semuanyaidentik)dengankapasitasQ.Saturute untuk tiap kendaraan. Dengan setiap verteks vi dalam V diasosiasikan dengan sejumlah barang qi, yang akandiantarkanolehsatukendaraan.VRPbertujuanuntukmenentukansejumlahkrute kendaraandengantotalbiayayangminimum,bermuladanberakhirdisebuahdepot, yangsetiapverteksdalamVdikunjungitepatsekaliolehsatukendaraan.Akhirnya, biaya dari solusi permasalahan ini S adalah: ==kii VRPR C S F1) ( ) ( 2.7Local Search Localsearch(LS)ialahmetaheuristikuntukmenyelesaikanpermasalahan perhitunganoptimisasiyangberat.LSdapatdigunakanpadapermasalahanyang bertujuanmemaksimalkansolusiyangstandardiantarabanyaknyakandidatsolusi [http://en.wikipedia.org/wiki/Local_search_(optimization)].AlgoritmaLSberpindahdari solusi ke solusi dalam kandidat solusi sampai dianggap solusi tersebut optimal. Algoritma LSdipergunakansecaraluasuntukpermasalahanperhitunganyangberat,meliputi permasalahan computer science (artificial intelligence), matematika, operations research, engineering, and bioinformatics.DalamalgoritmaLSyangpalingdasar,dilakukanpenyelusurandalam neighborhoodterhadapperjalanantertentuuntukkemajuanperjalanan.Jikaperjalanan tersebut ditemukan maka rute tersebut menggantikan yang lama dan proses tersebut akan diteruskansampaikemajuanperjalanantidakdapatditemukanlagi.Halinidisebut iterativeimprovementalgorithm.Algoritmatersebutdapatditerapkandalamhal-hal sebagai berikut. 34A.2-Opt 2-Opt ialah algoritma LS yang pertama kali diusulkan oleh Croes pada tahun 1958 untukmenyeleseikanTSP.Idedasardibelakangalgoritmatersebutialahmemindahkan ataumenghapuspasanganruteyangbersilangandanmengembalikansuatuperjalanan yang memungkinkan [http://en.wikipedia.org/wiki/2-opt]. 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 Analisis3-Optmeliputipenghapusantigaedgedalamperjalanan,kemudian menghubungkankembaliperjalanantersebutkedalamperjalananyangmemungkinkan dankemudianmengevaluasitiapmetodepengembalianuntukmencariyangpaling optimum. Proses ini kemudian diulang untuk set tiga set koneksi yang berbeda [http://en. wikipedia.org/wiki/3-opt]. Menghapus 2 edge reconnect(a) (b) 35 Gambar 2.18 3-Opt move (Sumber: http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf) 2.8Algoritma Ant Colony Optimization AlgoritmaAntColonyOptimizationmerupakanteknikprobabilistikuntuk menjawabmasalahkomputasiyangbisadikurangidenganmenemukanjaluryangbaik dengan graf. ACO pertama kali dikembangkan oleh Marco Dorigo pada tahun 1991. Sesuaidengannamaalgoritmanya,ACOdiinspirasiolehkolonisemutkarena tingkah laku semut yang menarik ketika mencari makanan [Heitor S. Lopes et al., 2005, p.2].Semut-semutmenemukanjarakterpendekantarasarangsemutdansumber makanannya.Ketikaberjalandarisumbermakananmenujusarangmereka,semut memberikantandadenganzatferomonsehinggaakanterciptajalurferomon.Feromon adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untukmengenalisesamajenis,individulain,kelompok,danuntukmembantuproses reproduksi.Berbedadenganhormon,feromonmenyebarkeluartubuhdanhanyadapat mempengaruhi dan dikenali oleh individu lain yang sejenis, proses peninggalan feromon ini dikenal sebagai stigmergy. Semut dapat mencium feromon dan ketika mereka memilih Menghapus 3 edge reconnect 36jalurmereka,merekacenderungmemilihjaluryangditandaiolehferomondengan konsentrasiyangtinggi.Apabilasemuttelahmenemukanjaluryangterpendekmaka semut-semut akan terus melalui jalur tersebut. Jalur lain yang ditandai oleh feromon lama akanmemudarataumenguap,seiringberjalannyawaktu.Jalur-jaluryangpendekakan mempunyaiketebalanferomondenganprobabilitikyangtinggidanmembuatjalur tersebutakandipilihdanjaluryangpanjangakanditinggalkan.Jalurferomonmembuat semut dapat menemukan jalan kembali ke sumber makanan atau sarang mereka. AlgoritmaACOtelahbanyakdigunakanuntukmenghasilkanpenyelesaianyang mendekati optimal [Bernd Bullnheimer et al., 1997, p.1]. Aplikasi algoritma semut dalam kehidupan sehari-hari mencakup beberapa persoalan sebagai berikut. a.TravelingSalesmanProblem(TSP),yaitumencarijalurterpendekdalamsebuah graf menggunakan jalur Hamilton. b.QuadraticAssignmentProblem(QAP)yangberusahamenempatkansejumlah sumbernditempatkanpadasejumlahmlokasidenganmeminimalkanbiaya assignment. c.Job-shopSchedulingProblem(JSP),jugasalahsatucontohaplikasialgoritma 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 etal.,2006,p.3].Keduanyaterbentukdarisebuahpopulasiyangterdiridariindividu-individuyangberkerjasamauntukmencapaitujuan.Semutartificialhidupdidunia 37virtual,karenanyamerekahanyamemodifikasinilainumerik(disebutanalogiartificial pheromones)yangberhubungandengankeadaan-keadaanpermasalahanyangberbeda. Sebuahrangkaiandarinilai-nilaiferomonyangberhubungandengankeadaan permasalahan disebut pheromone trail atau jejak feromon. Mekanisme untuk evaporation ataupenguapanferomonpadakolonisemutnyatayangmembuatsemutartificialdapat 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 denganbergerakdarisatukeadaanpermasalahankelainnya.Semut-semutnyatahanya berjalan,memiliharahberdasarkankonsentrasiferomonlokaldankebijakankeputusan stokastik.Semutartificialmembuatsolusisedikitdemisedikit,danbergerakdari keadaanpermasalahanyangtersediadanmembuatkeputusanstokastiksetiaplangkah. Meskipunbegitu,terdapatperbedaanantarayangnyatadansemutartificialsebagai berikut. Semutartificialhidupdiduniadanpadawaktudiskrit,merekaberpindahsecara sekuen melewati set batasan dari permasalahan. Updateferomon(penumpukandanpenguapanferomon)tidakdilakukandengan jalanyangsamapadasemutyangnyatadansemutarficial.Updateferomon dilakukan oleh beberapa dari semut artificial dan terkadang dilakukan saat solusi telah dibangun. Beberapaimplementasidarisemutartificialmenggunakanmekanismetambahan yangtidakadapadasemut-semutnyata,sepertilocalsearch,backtracking,dan lain-lain. 382.8.1Algoritma 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)adalahsalahsatudarimodelyangdikembangkandarialgoritmaAS. StrategidariEASmiripdenganAStetapiberbedadalampenerapanmemberikanjejak feromon karena elite ant atau best ant disertakan sebagai feromon tambahan dalam meng-update jejak semut. Aturan dasar meng-update jejak feromon dalam algoritma AS adalah sebagai berikut. = + =mkkijoldijnewij1) 1 ( .... (1) Sedangkanaturandalammeng-updateferomondenganalgoritmaelitistant system adalah sebagai berikut. = + + =mkbsijkijoldijnewije1) 1 ( .... (2) dengan kij adalahperubahanhargaintensitasjejaksemutantarkotasetiap semut yang dihitung berdasarkan persamaan 3 sebagai berikut. untuk (i,j) kota asal dan tujuan dalam tabuk,v lainnya eadalahparameteryangmendefinisikanbobotyangdiberikanpadaruteyang terbaik pada tabubs dengan panjang Lbs. untuk (i,j) kota asal dan tujuan dalam tabubs lainnya = 01k kijL= 01bs bsijL392.9Capacitated Vehicle Routing Problem dengan Algoritma Elitist Ant System CapacitatedVehicleRoutingProblem(CVRP)dapatdidefinisikansebagai pemberangkatanarmadadaripusatdepot,dengansejumlahpelangganyangmesti dilayani,denganpermintaanyangberbedauntukproduksejenis[HeitorS.Lopesetal., 2005,p.3].Armadakendaraanterbatasdanmempunyaikapasitasyangsama.Batasan-batasan pada CVRP adalah sebagai berikut. Setiap pelanggan hanya dilayani oleh satu pelanggan saja Totalpermintaanyangdilayanikendaraantidakbolehmelebihikapasitas kendaraan. Masing-masing perjalanan kendaraan dimulai dan diakhiri di depot Total panjang perjalanan tidak boleh melebihi batas otonomi kendaraan. CVRPialahpermasalahanyanglebihrumitdariTSP,karenamemerlukandua tahappenyelesaian.Padatahapawal,setiapsemutmenyusunbeberapaperjalananyang independen,danset-setperjalananmelayanisemuapelanggan.Padatahapkedua,setiap perjalanandisampaikanpadasebuahpopulasibaru,yangsistemnyasamadalam algoritmaAntSystem(AS)untukTSP.Padatahapini,algoritmaberkerjauntuk menetapkanbanyaknyasiklus,yangmengarahpadaoptimisasilokalperjalanan.Dua tahapprosestersebut,diulangsampaikriteriapemberhentiandipenuhi.Dengankeadaan totalpermintaansemuapelangganyangdilayanitidakmelebihibataskendaraanyang digunakan pada rute Ri, Notasinya adalah sebagai berikut. =miiQ d1 .... (4) 40DalamalgoritmaEASuntukCVRP,diperlukanlangkah-langkahuntuk 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). ( ) ( )2 2j i j i ijy y x x d + = (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. Tetapanpenguapanjejaksemut(),nilaiharus0>>1untukmencegah jejak feromon yang tak hingga. Visibilitas antar kota (ij). ijijd1= (6) Jumlah siklus maksimum (NCmax). 41ii.Proses iterasi sampai NCmax a.Untuk setiap semut k = 1, , n menbangun solusi yang baru. Pengisiandepotdankotapertamaksemutkedalamtabulistsemut kendaraanawal.Tabulistsemutditulissebagaitabuk,v dimanatabuk,v digunakan menyimpan rute semut k pada kendaraan v. Penyusunan rute kunjungan semut ke setiap kota.Perjalanan koloni semut berlangsung terus-menerus sampai semua kotatelahdikunjungidantidakmelebihibataskapasitaskendaraanyang sesuaidenganrumus4.Untukmenentukankotatujuandigunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut. [ ] [ ][ ] [ ] =hij ijij ij kijp untuk vj . (7) 0 =kijp untuk lainnya (8) Dengan={vjV:vjyangbolehdikunjungi}{v0},kotavj dipilihuntukdikunjungisetelahkotavi.Bilakendaraanvpadasemutk telahmelebihibatasdarikapasitaskendaraanQmakasemutkakan menggunakan kendaraan selanjutnya. b.Perbaiki semua rute kendaraan menggunakan 2-opt heuristik. c.Perhitungan panjang rute kendaraanuntuk setiap semut. Perhitunganpanjangrutetertutup(lengthclosedtour)atauLksetiap semutdilakukansetelahsatusiklusdiselesaikanolehsemuasemut. Perhitunganinidilakukanberdasarkantabuk,vmasing-masingdengan persamaan sebagai berikut. 42= =+ =vinjtabu tabu kj d j d Lv k i k0 0) 1 ( ), (, ,. (9) d.Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rutetertutupsetiapsiklusatauLbsdanhargaminimalpanjangrutetertutup secara keseluruhan adalah Lmin. e.Update jejak feromon. Kolonisemutakanmeninggalkanjejak-jejakpadalintasanantarkota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak semut antar kota. Aturan dasar dalammeng-update jejak feromon dengan algoritma Elitist Ant System yaitu dengan persamaan 2 yang telah disebutkan terdahulu. 2.10Flowcart Salahsatubentukuntukmenyatakanalurpikirandalammenyelesaikansuatu pekerjaan adalah dalam bentuk gambar atau bagan yang disebut program flowchart atau bagan alir suatu program [Moh.Sjukani,2004,p.5].Berikutadalah simbol-simbol yang digunakan untuk menggambarkan diagram alur. Tabel 2.3 Tabel simbol flowchart (Sumber: Moh. Sjukani, 2004, p.9) NotasiArti notasi Terminal, untuk menyatakan mulai dan selesei sebagai tanda, tidak melakukan suatu pekerjaan khusus. 43Process, 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.11State Transition Diagram StateTransitionDiagram(STD)adalahkumpulankeadaan/atributyang menggambarkan seseorang atau suatu benda pada waktu tertentu, bentuk keberadaan atau kondisitertentu,sepertimenungguinstruksiberikutnya,menunggupengisianpassword, 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 manusiapadaberbagaisistemonline(Yourdan,1989,p.270).Carakerjasisteminiada dua macam sebagai berkut. 44PassiveSisteminimelakukankontrolterhadaplingkungan,tetapilebihbersifat memberikanataumenerimadata.Kontrolsuatusistembertugas mengumpulkan/menerima data melalui sinyal yang dikirim oleh satelit. ActiveSisteminimelakukankontrolterhadaplingkungansecaraaktifdandapat menberikan respon terhadap lingkungan sesuai dengan program yang ditentukan. Komponen-komponen utama STD sebagai berikut. 1.State, yang disimbolkan denganStateadalahkumpulanatributyangmencirikanseseorangatausuatu benda pada waktu atau kondisi tertentu. 2.Transition State, yang disimbolkan denganTransitionStateyangdiberilabeldenganekspresiatauarah,labeltersebut menunjukkan kejadian yang menyebabkan transisi terjadi. 3.Condition dan Action Conditionadalahsuatuperistiwapadalingkunganeksternalyangdapat dideteksiolehsistem.Danactionadalahapayangdilakukanolehsistemapabila terjadiperubahanstate,ataubisajugadikatakansebagaireaksisistemterhadap suatu kondisi, aksi akan menghasilkan keluaran/tampilan. Gambar 2.19 Contoh STD (Sumber: Yourdan, 1989, p.265)