OPTIMASI METAHEURISTIK KOLONI SEMUT UNTUK SOLUSI PERMASALAHAN JALUR TERPENDEK PADA DATA JARINGAN JALAN RIIL EDWIN TENDA

OPTIMASI METAHEURISTIK KOLONI SEMUT UNTUK SOLUSI PERMASALAHAN JALUR TERPENDEK PADA DATA JARINGAN JALAN RIIL

EDWIN TENDA

SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2014

PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA* Dengan ini saya menyatakan bahwa tesis berjudul Optimasi Metaheuristik Koloni Semut untuk Solusi permasalahan Jalur Terpendek pada Data Jaringan Jalan Riil adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Oktober 2014 Edwin Tenda NIM G651120371

RINGKASAN EDWIN TENDA. Optimasi Metaheuristik Koloni Semut untuk Solusi Permasalahan Jalur Terpendek pada Data Jaringan Jalan Riil dibimbing oleh IMAS SUKAESIH SITANGGANG dan BABA BARUS. Salah satu permasalahan utama dalam analisis jaringan pada Sistem Informasi Geografis (SIG) adalah menentukan jalur terpendek antara dua lokasi dalam suatu jaringan. Meski terdapat beberapa metode untuk menyelesaikan permasalahan ini tetapi pengembangan dan kajian terhadap metode alternatif masih penting dilakukan. Penelitian ini menggunakan metode optimasi metaheuristik Koloni Semut yang terinspirasi dari prilaku alamiah semut, untuk mencari jalur terpendek antara dua titik, pada data jaringan jalan riil. Terdapat empat tahapan penelitian. Pertama, pembuatan jaringan buatan dan praproses data jaringan jalan riil. Kedua, implementasi algoritme Koloni Semut. Ketiga, pengujian pada data buatan dan data jaringan jalan riil. Keempat, pembandingan kinerja metode Koloni Semut dan metode Dijkstra dalam hal panjang jalur optimal dan waktu eksekusi. Pengujian menggunakan data buatan bertujuan untuk mendapatkan gambaran pengaturan terbaik dari parameter metode Koloni Semut. Pengujian menggunakan data jaringan jalan riil bertujuan untuk mengevaluasi kinerja metode Optimasi Koloni Semut terhadap data jaringan jalan riil. Hasil pengujian menunjukan bahwa, dengan menggunakan kombinasi parameter tertentu pada karakter data tertentu metode Koloni Semut dapat memiliki waktu eksekusi yang lebih cepat dibandingkan dengan metode Dijkstra. Untuk panjang jalur terpendek, algoritme Dijkstra lebih baik dibandingkan dengan metode Koloni Semut namun metode Koloni Semut juga dapat memberikan hasil yang setara dengan metode Dijkstra.

Kata kunci: algoritme dijkstra, analisis jaringan, jaringan jalan riil, optimasi koloni semut, permasalahan jalur terpendek.

SUMMARY EDWIN TENDA. Ant Colony Metaheuristic Optimization for Shortest Path Problem Solution in Real Road Network. Supervised by IMAS SUKAESIH SITANGGANG and BABA BARUS. One of the main problems in network analysis in Geographic Information Systems (GIS) is to determine the shortest path between two locations in a network. Although several methods exist to solve the problem, the development and evaluation for alternative methods is still important. This study uses the Ant Colony metaheuristic optimization method, that inspired by the natural behavior of ants, to find the shortest path between two points on the real road network (RRN) data. Tests on Ant Colony Optimization method were done in four stages. First, the artificial network and the RRN data preprocess. Second, the implementation of the Ant Colony Algorithm. Third, the test on the artificial network data and the RRN data. Fourth, the Ant Colony and Dijkstra method performance were compared in terms of the optimal path length and the execution time. The test uses the artificial data in order to get the idea of the best settings of the Ant Colony method parameters. The test used the RRN to evaluate the performance of Ant Colony Optimization method on RRN data. The test results show that by using a particular parameter combination and on particular data, the Ant Colony Method is faster than the Djikstra method. In terms of the length optimal path, the Dijkstra method generates better solution than the Ant colony Optimization method, although the Ant colony method can generates equal result as Dijkstra method. Keywords: Ant colony optimization, Dijkstra algorithm, network analysis, real road network, shortest path problem.

© Hak Cipta Milik IPB, Tahun 2014 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB

OPTIMASI METAHEURISTIK KOLONI SEMUT UNTUK SOLUSI PERMASALAHAN JALUR TERPENDEK PADA DATA JARINGAN JALAN RIIL

EDWIN TENDA

Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Komputer pada Program Studi Ilmu Komputer

SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2014

Penguji Luar Komisi Pada Ujian Tesis: Dr. Eng. Wisnu Ananta Kusuma, ST MT

Judul Tesis : Optimasi Metaheuristik Koloni Semut untuk Permasalahan Jalur Terpendek pada Data Jaringan Jalan Riil Nama : Edwin Tenda NIM : G651120371

Disetujui oleh Komisi Pembimbing

Dr Imas Sukaesih Sitanggang, S.Si M.Kom Ketua

Dr Baba Barus, M.Si Anggota

Diketahui oleh

Ketua Program Studi Ilmu Komputer

Dekan Sekolah Pascasarjana

Dr Eng Wisnu Ananta Kusuma, ST MT

Dr Ir Dahrul Syah, MSc.Agr

Tanggal Ujian: 3 Oktober 2014

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus, karena anugerah-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Desember 2013 ini adalah kecerdasan komputasional dengan judul Optimasi Metaheuristik Koloni Semut untuk Solusi Permasalahan Jalur Terpendek pada Data Jaringan Jalan Riil. Penulisan tesis ini merupakan salah satu syarat memperoleh gelar Magister Komputer pada program studi Ilmu Komputer Sekolah Pascasarjana Institut Pertanian Bogor. Penulis menyadari bahwa bantuan-bantuan dan arahan-arahan dari kedua pembimbing sangat membantu dalam menyelesaikan karya tulis ini. Terima kasih penulis ucapkan kepada Ibu Dr Imas Sukaesih Sitanggang, SSi MKom selaku pembimbing I dan Bapak Dr Baba Barus, MSi selaku pembimbing II. Penulis juga menyampaikan terima kasih kepada: 1. Prof Dr Ir Herry Suhardiyanto, MSc selaku Rektor Institut Pertanian Bogor. 2. Dr Ir Dahrul Syah, MSc Agr selaku Dekan Sekolah Pascasarjana Institut Pertanian Bogor. 3. Dr Eng Wisnu Ananta Kusuma, ST MT selaku Ketua Program Studi Ilmu Komputer dan juga sebagai penguji luar komisi pada ujian tesis. 4. Seluruh dosen dan staf pegawai tata usaha Departemen Ilmu Komputer. 5. Direktorat Jenderal Pendidikan Tinggi (DIKTI) sebagai sponsor Beasiswa On Going. 6. Orang tua, saudara dan seluruh keluarga yang selalu memberikan dorongan dan mendoakan untuk keberhasilan studi bagi penulis. 7. Seluruh mahasiswa Departemen Ilmu Komputer khususnya teman-teman angkatan tahun 2012 pada program studi S2 Ilmu Komputer. 8. Teman-teman Asrama Sam Ratulangi di Sempur, Bogor Baru I, Bogor Baru II. 9. Sahabat-sahabat yang tak dapat disebutkan satu persatu yang telah banyak membantu penulis dalam penyelesaian tesis ini. Semoga segala bantuan, bimbingan, dan motivasi yang telah diberikan kepada penulis senantiasa mendapat balasan dari Tuhan Yang Maha Esa. Akhirnya, semoga penulisan tesis ini dapat memperkaya pengalaman belajar serta wawasan kita semua.

Bogor, Oktober 2014 Edwin Tenda

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

1 PENDAHULUAN Latar Belakang Perumusan Masalah Tujuan Penelitian Ruang Lingkup Manfaat Penelitian

1 1 2 2 2 2

2 TINJAUAN PUSTAKA Permasalahan Jalur Terpendek Definisi dan Formulasi Permasalahan Jalur Terpendek Algoritme Dijkstra untuk Permasalahan Jalur Terpendek Kompleksitas Algoritme Dijkstra Metode Optimasi Koloni Semut Metaheuristik Koloni Semut Algoritme Optimasi Koloni Semut Kompleksitas Algoritme Koloni Semut Optimasi Koloni Semut dalam Permasalahan Jalur Terpendek Data Spasial Praproses Data Spasial Algoritme Permasalahan Jalur Terpendek pada Jaringan Jalan Riil

3 3 3 4 5 5 5 6 8 8 9 9

3 METODE PENELITIAN Lokasi dan Waktu Bahan dan Alat Tahapan Penelitian Pembuatan Jaringan Buatan dan Praproses Data Jaringan Jalan Riil Implementasi Metode Optimasi Koloni Semut Pengujian pada Data Jaringan Buatan dan Data Jaringan Jalan Riil Perbandingan Hasil Optimasi Koloni Semut dan Dijkstra

10 11 11 11 11 11 12 12 13

4 HASIL DAN PEMBAHASAN Jaringan Buatan dan Jaringan Jalan Riil Implementasi Metode Koloni Semut dan Metode Dijkstra Pengujian pada Data Jaringan Buatan dan Data Jaringan Jalan Riil Pengujian pada Data Jaringan Buatan Pengujian pada Data Jaringan Jalan Riil Pengujian pada Data Jalur Bus Karyawan IPB

14 14 15 16 16 18 21

5 SIMPULAN DAN SARAN Simpulan

22 22

Saran

23

DAFTAR PUSTAKA

24

LAMPIRAN

26

RIWAYAT HIDUP

35

DAFTAR TABEL 1 Karakteristik data jaringan buatan 2 Karakteristik data JJR 3 Hasil percobaan pada graf buatan dengan jumlah sisi v = 4 dan iterasi t = 10 4 Hasil percobaan pada graf buatan dengan jumlah sisi v = 5 dan iterasi t = 10 5 Hasil percobaan pada data JJR Aceh 6 Jalur terbaik untuk percobaan pada data JJR Aceh 7 Hasil percobaan pada data JJR Bogor Tengah 8 Jalur terbaik untuk percobaan pada data JJR Bogor Tengah 9 Hasil percobaan pada data jalur bus karyawan IPB

14 14 17 17 18 18 19 20 22

DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9

Graf lengkap berarah berpola persegi dengan jumlah node tepian v=4 Struktur topologi Arc-Node JJR Provinsi Aceh (a) dan JJR Kota Bogor Tengah (b) Jaringan jalan rute bus IPB Baranangsiang-Dramaga Kode program fungsi pemilihan simpul Kode program fungsi penguapan feromon Kode program fungsi tambahkan feromon Kode program fungsi utama algoritme Dijkstra Jalur terbaik hasil ACO (a) dan hasil Dijkstra (b) untuk data Aceh pada percobaan 5 10 Jalur terbaik hasil ACO (a) dan hasil Dijkstra (b) untuk data Bogor Tengah pada percobaan 4 11 Jaringan jalur bus karyawan IPB Baranangsiang-Dramaga 12 Solusi jalur Jalan baru (a) dan solusi jalur Stasiun kereta (b)

12 13 14 15 15 15 16 16 19 21 21 22

DAFTAR LAMPIRAN 1 2 3 4 5

Kode program ACO Kode program Djikstra Hasil percobaan lengkap pada data JJR Aceh Hasil percobaan lengkap pada data JJR Bogor Tengah Percobaan pada data buatan dengan nilai iterasi t = 20

26 29 32 33 34

1 PENDAHULUAN Latar Belakang Analisis jaringan merupakan salah satu area riset yang signifikan dan terus dilakukan dalam ilmu pengetahuan geografis (Curtin 2007). Dalam Sistem Informasi Geografis (SIG), analisis jaringan digunakan dalam berbagai kebutuhan antara lain jaringan telekomunikasi, transportasi, penjadwalan, manajemen proyek, navigasi, perencanaan, pengiriman barang dan lain-lain. Jaringan adalah suatu sistem dari fitur linear di mana terdapat atribut-atribut yang digunakan untuk menyatakan aliran suatu objek, yang berbasis topologi yang terdiri dari garis dan pertemuan antar garis yaitu simpul, di mana garis tersebut memiliki arah (Curtin 2007; Chang 2008). Analisis jaringan bertumpu pada subdisiplin matematika yakni teori Graf. Dalam teori graf, jaringan didefinisikan sebagai sebuah graf berarah, G = (V, E) yang terdiri dari sebuah himpunan simpul dan sebuah himpunan sisi dengan jumlah simpul n = |V| dan jumlah sisi m = |E|, di mana setiap sisi memiliki bobot yang menyatakan ukuran yang dapat berupa berat, panjang atau satuan lain sesuai dengan aplikasinya. Di antara berbagai analisis jaringan terdapat suatu permasalahan kunci yang disebut shortest path problem atau permasalahan jalur terpendek yaitu mencari jalur kumulatif minimum dalam jaringan (Zhan 1998; Zeng & Church 2008; Leng & Sheng 2009). Jalur dapat didefinisikan sebagai hubungan antara dua simpul yaitu titik awal dan titik tujuan ataupun memiliki titik perhentian di antara kedua simpul tersebut (Chang 2008). Permasalahan jalur terpendek dalam SIG pada pemanfaatannya digunakan untuk berbagai aplikasi seperti perencanaan lokasi fasilitas (Horner & Grubesic 2001), analisis konsumen potensial (Farhan & Murray 2005), serta perencanaan rute pengiriman barang dan layanan darurat yang menghubungkan fasilitas-fasilitas penting (Chang 2008). Permasalahan jalur terpendek sudah menjadi topik penelitian selama bertahun-tahun. Meskipun banyak algoritme yang dikembangkan serta studi empirik yang sudah dilakukan, tetapi didapati bahwa tidak ada algoritme tunggal yang terbaik ketika menghadapi semua data uji ataupun semua model representasi jaringan sehingga belum ada jawaban yang jelas untuk algoritme atau set algoritme yang terbaik (Zhan 1998; Leng & Zeng 2009). Metode optimasi Koloni Semut atau Ant Colony Optimization (ACO) adalah metode yang terinspirasi dari prilaku alamiah semut dalam mencari makanan di mana semut mencari jalur terdekat dari sarang menuju ke sumber makanan dengan mengandalkan kerjasama kelompok dalam bentuk komunikasi. Pada penerapannya ACO telah digunakan pada banyak kasus antara lain, penjadwalan proyek (Merkle et al. 2002), Maximum clique (Fenet dan Solnon 2003), pewarnaan graf (Jabber et al. 2006) dan Travelling Salesman Problem (Brezina dan Cickova 2011). Penelitian ini menerapkan metode metaheuristik ACO untuk memecahkan permasalahan jalur terpendek pada model representasi jaringan jalan riil (JJR) yang diperoleh dari praproses peta dasar. Dalam penelitian ini juga dilakukan pembandingan kinerja metode metaheuristik dengan metode pemecahan permasalahan jalur terpendek lain yaitu metode Dijkstra.

2

Perumusan Masalah Kajian terhadap masalah jalur terpendek masih penting dilakukan untuk mencari, mengembangkan dan menerapkan algoritme yang dapat digunakan untuk memecahkan permasalahan jalur terpendek. Permasalahan jalur terpendek adalah permasalahan dasar dalam banyak aplikasi jaringan. Saat ini terdapat berbagai metode untuk menyelesaikan permasalahan jalur terpendek dengan kinerja yang berbeda-beda untuk setiap metode tersebut. Kinerja dari metode untuk permasalahan jalur terpendek dinilai berdasarkan panjang jalur akumulatif minimum dan waktu eksekusi. Kinerja dari metode untuk permasalahan jalur terpendek dipengaruhi oleh model representasi data jaringan sebagai masukan dari metode. Dalam penelitian-penelitian terkait metode penyelesaian permasalahan jalur terpendek sebelumnya, umumnya menggunakan data jaringan buatan yang dibuat secara acak sehingga jaringan yang dihasilkan tidak dapat merepresentasikan karakteristik permasalahan yang nyata. Data JJR merepresentasikan keadaan karakteristik jaringan pada dunia nyata sehingga ideal dari sisi aplikatif. Metode Koloni Semut merupakan sebuah teknik optimasi metaheuristik yang meniru prilaku semut dalam menyusun jalur terbaik. Kinerja dari metode Koloni Semut dipengaruhi oleh kombinasi parameternya oleh karena itu perlu dicari kombinasi parameter terbaik berdasarkan kasus yang akan diselesaikan. Dalam penelitian ini dikembangkan algoritme yang berdasarkan pada metode Koloni Semut untuk menyelesaikan permasalahan jalur terpendek pada data jaringan jalan riil. Algoritme yang dikembangkan diharapkan memiliki kinerja yang baik, sehingga berpotensi untuk diterapkan pada aplikasi permasalahan jalur terpendek.

Tujuan Penelitian ini bertujuan untuk mencari solusi permasalahan jalur terpendek antara dua titik pada data JJR menggunakan algoritme optimasi metaheuristik Koloni Semut dan membandingkan kinerja algoritme Koloni semut dengan kinerja algoritme permasalahan jalur terpendek Dijkstra dalam hal panjang jalur dan waktu eksekusi.

Ruang Lingkup Penelitian ini dibatasi untuk kasus permasalahan jalur terpendek berupa Single source single destination shortest path problem atau permasalahan jalur terpendek antara dua titik dengan model representasi data jaringan jalan satu arah.

Manfaat Penelitian Penelitian ini diharapkan memberikan kontribusi berupa metode alternatif untuk penyelesaian masalah jalur terpendek berbasis metode metaheuristik dan juga sebagai pembanding bagi metode pemecahan permasalahan jalur terpendek pada kasus menggunakan dataset jaringan jalan riil.

3

2 TINJAUAN PUSTAKA Permasalahan Jalur Terpendek Permasalahan jalur terpendek adalah suatu masalah optimasi dasar yang diimplementasikan pada banyak jenis aplikasi seperti jaringan telekomunikasi, transportasi, penjadwalan, manajemen proyek dan lain-lain. Permasalahan jalur terpendek merupakan masalah kombinatorial klasik yang mengandung unsur dari permasalahan arus pada jaringan yang merupakan titik awal dalam mempelajari permasalahan jaringan yang lebih kompleks (Resende & Pardalos 2006). Dalam Resende & Pardalos (2006) permasalahan jalur terpendek dapat dikategorikan dalam tiga jenis yaitu: 1. Menemukan jalur terpendek antara dua simpul. 2. Menemukan jalur terpendek dari satu simpul tunggal ke semua simpul lain. 3. Menemukan jalur terpendek dari beberapa simpul sumber ke sejumlah simpul tujuan. Agar solusi dapat diperoleh maka perlu dilakukan asumsi sebagai berikut: 1. Semua sisi bernilai integer atau direpresentasikan dalam bentuk bilangan rasional. 2. Graf terhubung dengan kuat. Asumsi ini dapat dilakukan dengan mendefinisikan jarak antara simpul yang tidak terhubung menjadi sama dengan +∞. 3. Graf tidak memiliki directed cycle bernilai bernilai negatif untuk permasalahan jalur terpendek. Definisi dan Formulasi Permasalahan Jalur Terpendek Masukan dari permasalahan jalur terpendek antara dua titik yaitu (G, s, c) di mana G=(V, E, c) suatu graf berarah, V adalah himpunan dari simpul dan E adalah himpunan dari sisi E={(i , j) | i, j V }, di mana s V adalah simpul sumber dan c : E  ℝ sebagai fungsi panjang dari sisi. Tujuannya adalah untuk mencari jalur terpendek dari simpul s menuju ke simpul tujuan di mana diasumsikan bahwa semua simpul dalam G dapat dijangkau dari s dalam G. Jalur adalah sebuah rute yang dilalui tanpa melewati simpul yang sudah dilalui sebelumnya. Jalur yang melewati sebuah sisi (i, j) disebut forward path jika jalur tersebut melewati i sebelum j dan disebut backward path jika sebaliknya. Jika sebuah jalur tidak memiliki backward path maka disebut directed simple path. Panjang dari path didefinisikan sebagai jumlah dari bobot seluruh sisi yang dilewati oleh jalur di mana tidak boleh terdapat backward path (Cherkassky et al. 1996; Resende & Pardalos 2006). Permasalahan jalur terpendek memiliki formulasi matematika sebagai berikut (Resende & Pardalos 2006): ∑ (

(

) (

)

)

Sedemikian hingga, ∑ (

)

( )

∑ (

( )

)

bf = 1, bd = -1 ; bi = 0, I ≠ f, d ; x(i, j)

{1,0}, ∀ (i, j)

E

4

Nilai c merupakan nilai bobot dari sisi (i, j) dan x adalah jumlah jalur yang menggunakan setiap sisi (i, j) E. Tujuannya adalah untuk mencari suatu jalur graf berarah yang dibentuk oleh v dari s menuju d dengan bobot atau jarak yang paling minimum. Beberapa penelitian terkait penerapan algoritme jalur terpendek antara lain, Behzadi et al. (2008) mengembangkan sebuah algoritme genetika untuk mencari jalur terpendek pada data berformat raster. Awalnya dilakukan praproses peta agar dapat gunakan oleh algoritme genetika. Pertama, dilakukan rotasi terhadap pikselpiksel pada area sedemikian rupa sehingga simpul awal dan simpul akhir berada dalam satu baris. Kedua, piksel diubah kedalam nilai integer yang nilainya bervariasi sesuai dengan karakteristik fitur jalan dari piksel tersebut sedangkan piksel fitur lainnya diberi nilai 0. Ukuran dari individu adalah sebanyak jumlah piksel horizontal antara simpul awal dan simpul akhir. Pengujian algortime menggunakan data JJR Kota Teheran, Iran. Hasil menunjukan algoritme yang diusulkan mampu membangun jalur terpendek meskipun tidak menghasilkan hasil optimal. Leng & Zeng (2009) mengembangkan sebuah algoritme yang diberi nama Minimum label delimiting TWO-Q (Mild TWO-Q) yang berdasar dari algoritme algoritme Graph growth yang diketahui tidak efisien pada pencarian jalur terpendek jarak dekat karena harus menguji semua simpul dalam jaringan sehingga memiliki waktu eksekusi yang besar. Pengujian menggunakan dataset Los Angeles County, California, USA. Hasil pengujian menunjukan bahwa algoritme Mild Two-Q berhasil menurunkan jumlah scanning pada jaringan untuk jalur dengan simpul yang berdekatan. Pada awal interval pengujian hingga pada interval tertentu algoritme Mild Two-Q memiliki waktu eksekusi yang lebih baik dari pada algoritme Two-Q walaupun pada titik interval yang makin besar waktu eksekusi menjadi sama. Algoritme Dijkstra untuk Permasalahan Jalur Terpendek Algoritme untuk menyelesaikan permasalahan jalur terpendek sudah dikembangkan sejak tahun 1950-an. Terdapat beberapa algoritme yang digunakan untuk memecahkan permasalahan tersebut diantaranya algoritme Dijkstra. Algoritme Dijkstra ditemukan oleh Edsger Dijkstra pada tahun 1956 (Dijkstra 1959) yang merupakan algoritme pencarian dalam graf untuk memecahkan permasalahan mencari jalur terpendek antara dua simpul pada graf berarah G = (V, E) yang seluruh bobot pada sisinya bernilai positif. Algoritme Dijkstra adalah salah satu algoritme terbaik dan paling dikenal dalam permasalahan mencari jarak terpendek (Zeng & Church 2008). Algoritme Dijkstra adalah sebagai berikut (Cormen et al. 2009): Algoritme 1 Algoritme Dijkstra DIJKSTRA (G, l, s) Initialize-Single-Source (G, s) S=Ø Q = G.V while Q ≠ Ø u = Extract – Min (Q) S = S ∪ {u} for each vertex v ∈ G. Adj[u]

5

//relaxation process if v.d > u.d + l(u, v) v.d = u.d + l(u, v) v.π = u Algoritme Dijkstra menyimpan dua himpunan simpul yaitu S yaitu himpunan simpul yang jarak terpendek dari sumber telah ditentukan, dan V-S yaitu himpunan simpul yang tersisa. Nilai l merupakan bobot dari semua simpul v yang terhubung ke simpul u jalur yang terbentuk. Sedangkan nilai d merupakan bobot dari sisi. Proses relaxation adalah proses memperbaharui bobot dari semua simpul v, yang terhubung ke simpul u, untuk meningkatkan perkiraan jalur terpendek terbaik ke simpul v dengan memasukkan (u, v) di jalur yang terbentuk menuju v. Algoritme Dijkstra pada penelitian ini digunakan sebagai pembanding dari kinerja dari algoritme Koloni Semut pada data JJR. Kompleksitas algoritme Dijkstra Dalam Cormen et al. (2009) kompleksitas dari algoritme Dijkstra dipengaruhi oleh cara implementasi yang dipakai. Untuk implementasi menggunakan struktur data array Dijkstra kompleksitas algoritme Dijkstra adalah O(V2 + E) = O(V2). Untuk implementasi menggunakan min-priority queue dengan binary min-heap kompleksitas algoritme adalah O = ((V + E) log V) = O(E log V) dengan syarat yaitu berupa graf jarang dengan E = o(V2 / log V).

Metode Optimasi Koloni Semut Optimasi Koloni Semut adalah teknik optimasi metaheuristik yang terinspirasi dari pola tingkah laku semut dalam mencari makan (Englebrecht 2007). Penelitian terkait pola tingkah laku serangga awalnya dilakukan oleh Marais yang dipublikasi pada tahun 1927 dengan objek penelitian pada rayap. Kemudian Grase pada tahun 1959 berdasarkan penelitian sebelumnya melakukan riset terkait prilaku komunikasi rayap dalam membangun sarangnya, di mana disimpulkan bahwa terdapat bentuk komunikasi tidak langsung antar individu yang disebut stigmergi yaitu sebuah mekanisme yang menantarai interaksi antar serangga dalam sistem mereka. Pada tahun 1990 Deneubourg dan kawan-kawan mempelajari tentang contoh stigmergi yang disebut komunikasi feromonal. Berdasarkan penelitian tersebut maka mulai dikembangkan algoritme-algoritme yang terinspirasi dari perilaku semut. Salah satu penelitian awal yang dilakukan adalah tentang bagaimana kemampuan dari semut untuk mencari jalur terpendek antara sarang dengan sumber makanan. Berdasarkan penelitian yang dilakukan ditemukan bahwa jalur terpendek tersebut ditemukan tanpa melalui mekanisme koordinasi yang aktif terpusat namun ditemukan melalui suatu pola tidak teratur dan acak. Berdasarkan penelitian-penelitian tersebut Dorigo mengembangkan model optimasi metaheuristik yang disebut Ant colony optimization dalam penelitian desertasinya yang dipublikasikan pada tahun 1992. Metaheuristik Koloni Semut Dalam Dorigo & Stutzle (2004) metaheuristik adalah sebuah kerangka kerja atau sebuah set algoritme yang dapat diaplikasikan untuk berbagai permasalahan

6

optimasi dengan melakukan sedikit adaptasi sesuai dengan kebutuhan permasalahan tersebut. Metaheuristik dapat dikatakan sebagai suatu metode general purpose heuristic yang dibangun untuk mendapatkah solusi berkualitas tinggi terhadap permasalahan optimasi. Metaheuristik dalam optimasi Koloni Semut adalah bagaimana koloni semut buatan bekerja sama untuk mencapai satu tujuan yaitu solusi terhadap permasalahan optimasi. Kerjasama dari semut-semut buatan merupakan kunci desain dari optimasi Koloni Semut di mana solusi didapatkan lewat alokasi sumber daya komputasi dalam bentuk semut buatan yang berkomunikasi secara tidak langsung lewat mekanisme stigmergy. Sebuah optimasi Koloni Semut dapat dilihat sebagai kesatuan dari tiga prosedur yang saling mempengaruhi yaitu Construct a t’s solution, Update pheromon dan Daemon actions (Dorigo & Stutzle 2004). Prosedur Construct a t’s solution merupakan fungsi untuk mengelola sebuah koloni semut yang secara bersamaan dan serempak bergerak mengunjungi titik-titik yang berdekatan dengan masalah yang dikaji dengan bergerak melalui titik tetangga pada graf permasalahan yang dikaji. Pergerakan dilakukan secara stokastik dengan pengaturan tertentu. Pada bagian ini semut buatan, menyusun solusi terhadap permasalahan optimasi yang makin lama makin meningkat. Prosedur Update pheromon adalah prosedur di mana nilai feromon pada jejak yang dilalui dimodifikasi, yang nilainya bertambah seiring dengan semut yang melewati jejak tersebut ataupun berkurang akibat penguapan feromon. Prosedur terakhir yaitu Daemon actions digunakan untuk mengimplementasi aksi-aksi terpusat yang tidak dapat dilakukan oleh seekor semut saja, seperti aktivasi dari prosedur optimasi lokal dan pengumpulan informasi global. Fungsi Schedule activities tidak menentukan bagaimana ketiga prosedur ini dijadwalkan dan disinkronisasikan yang berarti perancang dapat dengan bebas menentukan bagaimana ketiga prosedur ini berinteraksi sesuai dengan karakteristik dari permasalahan yang ingin dioptimasi. Prosedur metaheuristik optimasi Koloni Semut adalah sebagai berikut (Dorigo & Stutzle 2004): procedure Ant_Colony_Metaheuristic Schedule_Activities Construct_Ants_Solutions Update_Pheromones Daemon_Actions % optional end-Schedule_Activities end-procedur Algoritme Optimasi Koloni Semut Metode optimasi Koloni Semut merupakan suatu metode yang didasarkan pada mekanisme aksi dari koloni semut yang bekerjasama mengkonstruksi solusi melalui suatu bentuk komunikasi. Semut memiliki suatu mekanisme komunikasi tak langsung yang disebut stigmergy dimana selama pencarian semut akan meletakan sejumlah feromon di sepanjang jalur yang dilewati sebagai penanda. Semut lain akan memilih jalur berdasarkan intensitas feromon dari tiap kemungkinan jalur. Walaupun terjadi penguapan feromon, rute yang dilewati semut secara berulang-ulang menyebabkan pertambahan feromon dalam jalur hingga lama kelamaan jalur pilihan semut akan konvergen pada satu jalur terpendek. Salah satu varian dari algoritme optimasi Koloni Semut adalah Simple ant colony optimization (SACO). Pada SACO, dalam menyusun solusi, semut buatan yang berada pada simpul i menentukan simpul berikutnya yaitu

7

menggunakan persamaan probabilitas transisi (Persamaan 1) dimana adalah himpunan dari simpul-simpul tetangga yang terhubung dengan node i (feasible nodes), yang dapat dilalui oleh semut k (Dorigo & DiCaro 1999).

∈ ( ) {

∑

(1)

Intensitas feromon pada tiap jalur mengalami penguapan, dimana untuk setiap sisi (i, j), feromon akan menguap sejumlah Persamaan 2, dengan nilai ρ [ ] sebagai konstanta tingkat penguapan feromon. Konstanta ρ mengendalikan pengaruh ingatan pencarian. Dalam Dorigo & DiCaro (1999), formula penguapan feromon adalah: (t ← 1-ρ) ( ) (2) Pada saat semut buatan telah berhasil membangun solusi jalur dari simpul sumber ke simpul tujuan maka semut buatan akan kembali ke simpul sumber mengikuti jalur yang dibuat sebelumnya sambil menaruh sejumlah feromon di tiap sisi jalur tersebut. Dalam Dorigo & DiCaro (1999), jumlah feromon yang ditambahkan pada tiap sisi sepanjang solusi pada iterasi ke t adalah sebesar Persamaan 3 di mana (t) adalah panjang dari jalur solusi yang dibangun oleh semut k pada langkah ke t. Δ

( )

(3)

( )

Jumlah feromon yang diletakan disepanjang jalur solusi adalah sebesar Persamaan 4 (Dorigo & DiCaro 1999): (t + 1)=

( )

∑

( )

(4)

Kualitas solusi Koloni Semut dihitung berdasarkan total bobot dari jalur yang ditempuh. Jika xk(t) menyatakan sebuah solusi pada iterasi ke t maka f(xk(t)) menyatakan kualitas dari solusi di mana solusi terbaik dengan mencari nilai f paling minimum. Terminasi dari proses dapat dilakukan berdasarkan beberapa kondisi yaitu jika nilai iterasi sudah mencapai nilai yang ditentukan, jika solusi yang dapat diterima sudah ditemukan dengan f(xk(t)) ≤ ϵ, dimana ϵ suatu batas nilai tertentu, atau jika semua semut atau sebagian besar semut sudah melewati jalur yang sama. Algoritme SACO lengkap adalah sebagai berikut (Englebrecht 2007): Algoritme 2 Algoritme SACO I al ze ij (0) to small random values; Let t = 0; Place nk ants on the origin node; repeat for each ant k = 1 … nk do //Construct a path ( ) ( ) = Ø; Repeat //select next node based on the probability defined in equation:

8

∈ ( )

∑

{ add link (i, j) to path ( ) until destination node has been reached; remove all loops from ( ) calculate the path length ( ( )) end for each link (i, j) of the graph do //pheromone evaporation; Reduce the pheromone (t), using equation: ij(t ← 1-ρ ij(t) end for each ant k = 1 … for each link (i, j) of Δ ; (

(t+1) =

k do

( ) do

( ))

() ∑

1Δ

()

end end Until stopping condition is true; Return the path ( ) with smallest (

( )) as the solution;

Kompleksitas algoritme Koloni Semut Penelitian terkait analisis kompleksitas algoritme Koloni Semut pertama dilakukan oleh Neuman & Witt (2007) dimana analisis dilakukan pada beberapa varian algoritme Koloni Semut seperti algoritme One-Max dimana hasil analisis menunjukan kompleksitasnya adalah O(n2). Selanjutnya Attiratanasunthron & Fakcharoenphol (2008) melakukan analisis kompleksitas algoritme Koloni Semut untuk permasalahan single destination shortest path problem pada graf berarah tanpa cycle dimana untuk graf dengan n simpul dan m sisi kompleksitasnya adalah O(1/ρ mn2log n) atau sama dengan O (1/ρ n2 log n). Optimasi Koloni Semut dalam Permasalahan Jalur Terpendek Ok et al. (2009) mengajukan algoritme Koloni Semut untuk permasalahan jalur terpendek yang didalamnya memiliki faktor preferensi dari pengguna dimana tak selalu dibutuhkan jalur terpendek namun jalur yang reliable dan flexible. Data preferensi didapatkan dari pengguna sistem navigasi. Dikembangkan algoritme berdasarkan algoritme Ant system dimana dilakukan modifikasi terhadap fungsi pemilihan simpul dan fungsi pembaruan feromon. Digunakan beberapa data dengan ukuran 64, 128,192,256 simpul dengan 118, 242, 362 dan 484 sisi. Hasil percobaan

9

menunjukan bahwa algoritme yang dikembangkan berhasil mengakomodasi faktor preferensi. Selain itu didapati pengaruh dari pengaturan parameter seperti jumlah semut, jumlah iterasi dan koefisien heuristik dimana peningkatan jumlah semut dan jumlah iterasi berbanding lurus terhadap solusi yang memiliki faktor preferensi lebih baik. Kolavi & Bhatnagar (2009) melakukan pengembangan terhadap algoritme MAF-ACO (Multi agent foraging ACO) yaitu sebuah algoritme jarak terpendek pada dua titik dimana panjang dari suatu sisi dibagi ke dalam sejumlah stage sesuai nilai panjang sisinya. Pada setiap stage agen memiliki dua parameter yaitu parameter jejak feromon dan parameter pembelajaran agen. Dalam penelitian ini dikembangkan empat buah varian dengan melakukan modifikasi pada skema pembelajaran semut dan skema pembaharuan feromon. Simulasi dilakukan terhadap graf buatan, dengan satu pasang simpul sumber dan tujuan dengan 12 buah simpul antara yang dibagi dalam tiga fase yang pada tiap fasenya terhubung semi lengkap. Percobaan dilakukan dengan menggunakan jumlah agen sebanyak 32, 64, 128 dan 256. Hasil percobaan menunjukan bahwa varian kedua dari algoritme yang dikembangkan menghasilkan persentasi hasil optimal yang jauh lebih baik dari algoritme MAF-ACO dan ketiga varian lainnya yaitu 65%, 88%, 99% dan 100% untuk jumlah semut 32, 64, 128 dan 256.

Data Spasial Data spasial adalah data yang memiliki komponen spasial yaitu terhubung ke suatu tempat di atas permukaan bumi. Data spasial menggambarkan lokasi dari suatu fitur spasial yang dapat berupa diskrit atau kontinyu. Fitur diskrit adalah fitur yang dapat dibedakan seperti titik yang merepresentasikan lokasi sumur, garis yang merepresentasikan jalan dan area yang merepresentasikan lapangan sepak bola sedangkan fitur kontinyu seperti ketinggian dan pengendapan. Lokasi dari fitur spasial pada permukaan bumi berbasis pada sistem koordinat pada bidang dua dimensi yaitu x, y (Chang 2008). Untuk membuat data spasial diperlukan peta dasar yang menggambarkan penampakan muka bumi serta data terkait fitur spasial yakni atribut-atribut yang disiapkan melalui praproses data spasial. Jaringan Jalan Riil (JJR) atau real road network adalah data yang merepresentasikan jaringan jalan yang nyata yang dapat diperoleh dari praproses data spasial. Praproses Data Spasial Agar dapat menggunakan data spasial maka diperlukan praproses data spasial sesuai dengan kebutuhan dari analisis yang diperlukan. Beberapa langkah yang perlu dilakukan untuk praproses data spasial yaitu: 1. Penyiapan peta Sebelum proses pendigitasian perlu dilakukan pengecekan terhadap peta untuk melihat apakah unsur-unsur penting dari peta sudah lengkap termasuk memeriksa apakah peta terbebas dari kerusakan fisik. Peta diperoleh melalui proses pemetaan yang menghasilkan peta analog ataupun digital. 2. Georeferensi Georeferensi merupakan prosedur awal yang harus dilakukan pada data mentah sebelum diproses dengan SIG. Setiap data harus tergeoreferensi untuk memastikan bahwa data tersebut sudah berada pada posisi yang tepat

10

dipermukaan bumi atau dengan kata lain dilakukan penyesuaian terhadap posisi geografisnya. Menurut kamus ESRI georeferensi adalah proses menyelaraskan data geografis ke sistem koordinat sehingga dapat dilihat, di query, dan dianalisis dengan data geografis lainnya. Georeferensi melibatkan menggeser, memutar, skala, dan dalam beberapa kasus warping, rubber shetting, atau ortorektifikasi data (www.support.esri.com/knowledgebase). 3. Dijitasi Dijitasi adalah proses mengkonversi fitur-fitur pada peta dengan cara menelusuri menggunakan perangkat pendigitasian (digitizer) untuk merekam titik-titik dalam bentuk koordinat dari objek-objek berupa titik, garis ataupun area dan disimpan secara otomatis dalam format digital sebagai data spasial. Salah satu teknik dijitasi adalah screen digitizing di mana peta yang sudah dipersiapkan terlebih dahulu ditampilkan pada layar kemudian pendigitasian dilakukan mengikuti garis, titik atau gambaran lain yang tampak pada layar (Barus & Wiradisastra 2009). Algoritme Permasalahan Jalur Terpendek pada Jaringan Jalan Riil Zhan dan Noon (1998) melakukan evaluasi terhadap lima belas algoritme jalur terpendek yaitu algoritme TWO-Q, algoritme PAPE, algoritme THRESH, algoritme DIKBA, algoritme DIKB, DIKBM, algoritme GOR, algoritme DIKBD, algoritme DIKR, algoritme DIKH, algoritme DIKF, algoritme GOR1, algoritme BFP, algoritme DIKQ serta algoritme BF. Digunakan dua dataset yang terdiri dari sepuluh data JJR dari jalur jalan bebas hambatan di Amerika yaitu JJR dari Negara bagian Nebraska, Alabama, Minnesota, Iowa, Missisipi, South Carolina, Florida, Missouri, Lousiana, Georgia. Hasil pengujian menunjukan bahwa untuk kasus jalur terpendek dari satu simpul ke semua simpul algoritme TWO_Q adalah yang paling direkomendasikan sedangkan untuk kasus jalur terpendek antara dua simpul atau dari satu simpul ke beberapa simpul direkomendasikan dua varian algoritme Dijkstra, yaitu DIKBA untuk jaringan yang panjang sisi maksimumnya kurang dari sama dengan 1.50 derajat desimal dan DIKBD untuk jaringan yang panjang sisi maksimumnya lebih dari sama dengan 1.50 derajat desimal. Lim & Kim (2005) mengusulkan perbaikan pada algoritme k-shortest path problem yang digunakan pada aplikasi navigasi, yaitu algoritme jalur terpendek yang dapat memberikan beberapa alternatif solusi, namun memiliki masalah overlapping dan similaritas dari dari jalur solusi yang dihasilkan. Penelitian ini mengembangkan algoritme yang disebut Link based shortest path dengan mengakomodir batasan dari jalur jalan pada jaringan tanpa perlu menambah sisi dan simpul pada jaringan. Pengujian dilakukan menggunakan satu data buatan dan satu data riil. Untuk data buatan digunakan graf berarah dengan 8 simpul, 9 sisi dengan 2 sisi memiliki batasan jalur jalan. Untuk data riil digunakan jaringan jalan di Siox Fall dengan 24 simpul dan 76 sisi. Hasil percobaan menunjukan bahwa algoritme yang diusulkan memberikan hasil yang lebih efisien dari algoritme kshortest path problem. Selain itu algoritme yang diusulkan mengatasi permasalahan overlapping dan similaritas dari algoritme k-shortest path problem. Zeng & Church (2008) menerapkan algoritme pencarian A* untuk mencari jalur terpendek pada data jaringan jalan riil. Selain itu pengujian juga dilakukan terhadap enam algoritme lain untuk melihat perbandingan kinerja algoritme A* yaitu algoritme DIKH, DIKBD, DIKBA, Two-Q, ASH, ASBD, ASBA dengan fokus pada waktu eksekusi. Pada eksperimen digunakan dua dataset jaringan jalan

11

riil yaitu data jalan di Los Angeles dan Santa Barbara masing-masing dengan rasio sisi simpul sebesar 2,36 dan 2,73. Dari hasil percobaan ditemukan bahwa pada kedua dataset algoritme ASBA memiliki waktu eksekusi yang paling baik dari seluruh algoritme yang dijalankan.

3 METODE PENELITIAN Lokasi dan Waktu Penelitian dilakukan pada bulan Januari sampai dengan bulan Juli 2014. Lokasi penelitian bertempat di bagian Komputasi Terapan, Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.

Bahan dan Alat Penelitian ini menggunakan dua jenis data yaitu pertama data jaringan buatan dan kedua data JJR yang diperoleh dari praproses peta dasar. Untuk data buatan dibuat dua buah data yang digunakan dalam pengujian parameter metode algoritme Koloni Semut. Dalam penelitian ini digunakan tiga buah data JJR yaitu jaringan jalan di Provinsi Aceh, jaringan jalan Kota Bogor Tengah dan jaringan jalan rute bus karyawan IPB dari Kampus Baranangsiang menuju Kampus Dramaga dan sebaliknya. Dalam penelitian digunakan perangkat lunak aplikasi Quantum GIS versi 2.0.1 untuk pembuatan dan pengolahan data jaringan jalan. Untuk implementasi algoritme menggunakan bahasa pemrograman Python versi 3.3. Program dikembangkan dan diuji menggunakan komputer dengan spesifikasi perangkat keras yaitu prosesor AMD A6 2.40 GHz dan RAM 4 GB.

Tahapan Penelitian Secara garis besar tahapan penelitian ini dibagi dalam empat bagian yaitu, 1) Pembuatan jaringan buatan dan praproses data JJR, 2) implementasi algoritme ACO dan Dijkstra, 3) pengujian terhadap data buatan dan data jaringan jalan riil, dan 4) perbandingan kinerja dengan algoritme Dijkstra sebagai salah satu algoritme terbaik pada permasalahan rute terpendek antara dua titik (Zeng & Church 2008). Pembuatan Jaringan Buatan dan Praproses Data Jaringan Jalan Riil Pada penelitian ini dibuat graf buatan berupa graf lengkap berarah berpola persegi di mana jumlah simpul (v) dan sisi (e) pada ke empat tepian berjumlah sama (Gambar 1). Jumlah sisi dari tiap tepian adalah v-1 dengan bobot masing-masing bernilai satu. Data jaringan jalan buatan diperlukan bagi pengujian yang bertujuan untuk memperoleh gambaran pengaruh parameter-parameter algoritme Koloni Semut terhadap kinerja algoritme dan untuk mendapatkan konfigurasi parameter Koloni Semut yang memberikan hasil paling baik.

12

Gambar 1 Graf lengkap berarah berpola persegi dengan jumlah node tepian v =4 Pada praproses data JJR, peta dasar diambil dari layanan peta Google Map. Dilakukan tiga tahapan praproses peta. Pertama, pengecekan peta untuk memastikan apakah unsur-unsur dalam peta sudah lengkap. Pada tahapan ini peta dasar yang dipilih dipastikan memiliki semua unsur jalan yang diperlukan untuk analisis jaringan. Tahapan kedua adalah proses georeferensi untuk memastikan bahwa posisi peta pada representasi muka bumi sudah tepat secara geografis. Tahapan ini dilakukan dengan cara menentukan setidaknya empat titik kontrol pada peta dasar di mana koordinat dari setiap titik menjadi input georeferensi. Selain itu ditentukan jenis proyeksi yang digunakan yaitu proyeksi WGS1984. Proses ketiga yaitu digitasi, yaitu dilakukan konversi atau perekaman fitur-fitur peta, baik titik yang merepresentasikan titik awal, titik akhir atau persimpangan jalan dan garis yang merepresentasikan segmen jalan. Struktur atribut dibuat mengikuti model topologi Arc-Node yang menyatakan informasi bagaimana suatu segmen jalan diapit oleh simpul awal dan simpul akhir (Gambar 2). Implementasi Metode Optimasi Koloni Semut Metode optimasi metaheuristik Koloni Semut pada penelitian ini menggunakan algoritme yang diusulkan oleh Dorigo & DiCaro (1999) yaitu algoritme SACO yang dimodifikasi. Pada SACO terdapat beberapa parameter yaitu (koefisien pengaruh feromon bernilai positif) ρ (konstanta penguapan feromon), t (jumlah iterasi) dan nk (jumlah semut) dimana penentuan konfigurasi parameter akan sangat menentukan kinerja dari algoritme SACO. Pengujian pada Data Jaringan Buatan dan Data Jaringan Jalan Riil Pengujian pada data jaringan buatan dilakukan untuk melihat pengaruh parameter algoritme Koloni Semut yaitu α, ρ, nk dan t terhadap hasil optimal dan waktu eksekusi pada jaringan buatan. Pengujian dilakukan dengan menentukan simpul pertama sebagai simpul sumber dan simpul terakhir sebagai simpul tujuan. Percobaan diulang sebanyak lima kali untuk mendapatkan nilai rata-rata dari

13

panjang jalur dan waktu eksekusi. Penghentian program dilakukan saat proses sudah menyelesaikan seluruh iterasi sebanyak t. Dari hasil pengujian didapatkan gambaran pengaruh parameter terhadap panjang jalur. Selanjutnya dipilih kombinasi α, ρ k dan t yang memberikan hasil terbaik pada data buatan.

Bobot

Segmen Simpul

Gambar 2 Struktur topologi Arc-Node Pada data JJR, dilakukan pengujian menggunakan algoritme ACO dan algoritme Dijkstra. Pada ACO pengujian dilakukan dengan menentukan sepasang simpul yaitu simpul sumber dan simpul tujuan. Untuk setiap percobaan dilakukan lima kali ulangan. Pada percobaan ini digunakan kombinasi parameter ACO yang terbaik hasil percobaan pada data jaringan buatan. Pada algoritme Dijkstra dilakukan pengujian dengan menggunakan pasangan simpul yang sama dengan percobaan pada algoritme Koloni Semut juga dengan lima ulangan untuk tiap percobaan. Dari hasil ulangan pada tiap percobaan dihitung nilai rata-rata parameter kinerja. Waktu eksekusi yang diukur yaitu total waktu dari masing-masing metode dalam mengkonstruksi jalur terpendek. Perbandingan Hasil Optimasi Koloni Semut dan Dijkstra Hasil dari algoritme Koloni Semut kemudian dibandingkan dengan hasil dari algoritme Dijkstra baik pada jumlah simpul, panjang jalur serta waktu eksekusi dari solusi yang dihasilkan oleh masing-masing algoritme. Perbandingan kinerja dilakukan untuk melihat kualitas solusi yaitu panjang jalur dan waktu eksekusi dari algoritme Koloni Semut terhadap algoritme Dijkstra.

14

4 HASIL DAN PEMBAHASAN Jaringan Buatan dan Jaringan Jalan Riil Untuk jaringan buatan yang digunakan adalah jaringan berukuran v = 4 (4 × 4) dan v = 5 (5 × 5) sedangkan dari praproses data JJR dihasilkan tiga buah data JJR yaitu JJR Kota Bogor Tengah dan JJR Provinsi Aceh (Gambar 3) serta JJR rute Bus karyawan IPB Baranangsiang-Dramaga (Gambar 4). Karakteristik dari data dapat dinyatakan oleh rasio sisi terhadap simpul yang menunjukan kompleksitas dari jaringan jalan. Makin besar nilai rasio sisi terhadap simpul maka makin banyak persimpangan yang terbentuk, makin banyak alternatif jalur yang terbentuk dalam jaringan jalan atau dengan kata lain makin kompleks jaringan jalan tersebut. Tabel 1 menunjukan karakteristik dari data buatan sedangkan Tabel 2 menunjukan karakteristik dari data JJR. Tabel 1 Karakteristik data jaringan buatan No

Data

1 2

Data Buatan 4 × 4 Data Buatan 5 × 5

Jumlah Jumlah simpul sisi 42 16 72 25

Ratio sisi terhadap simpul 2.625 2.88

Tabel 2 Karakteristik data JJR No

Data

1 2 3

Data JJR Aceh Data JJR Bogor Tengah Data JJR Bus IPB

Jumlah Jumlah simpul sisi 224 161 534 372 41 36

Rasio sisi terhadap simpul 1.391 1.43 1.13

N

(a)

(b)

Gambar 3 JJR Provinsi Aceh (a) dan JJR Kota Bogor Tengah (b)

15

Gambar 4 Jaringan jalan rute bus IPB Baranangsiang-Dramaga

Implementasi Metode Koloni Semut dan Metode Dijkstra Metode koloni Semut dan Dijkstra diimplementasikan dalam bahasa Python versi 3. Pada algoritme SACO dilakukan dua modifikasi. Pertama dengan menambahkan suatu nilai acak terkontrol, yaitu nilai acak yang berada pada selang tertentu pada fungsi probabilitas transisi yang memungkinkan semut mengkonstruksi jalur alternatif lebih cepat. Kedua penambahan fungsi mekanisme mundur pada semut buatan sehingga saat semut berada pada simpul buntu yaitu posisi dimana tidak terdapat kemungkinan simpul selanjutnya (feasible node), semut buatan akan kembali ke simpul sebelumnya dan melanjutkan pencarian dengan tidak memperhitungkan lagi simpul buntu tersebut. Pada algoritme SACO terdapat tiga fungsi utama yaitu fungsi pemilihan simpul atau probabilitas transisi (Gambar 5) yang digunakan untuk konstruksi jalur, fungsi penguapan feromon (Gambar 6), dan fungsi penambahan feromon (Gambar 7). Pada algoritme SACO digunakan tipe data List. Kode lengkap SACO yang dimodifikasi dapat dilihat pada Lampiran 1.

Gambar 5 Kode program fungsi pemilihan simpul

Gambar 6 Kode program fungsi penguapan feromon

16

Gambar 7 Kode program fungsi penambahan feromon Pada algoritme Dijkstra digunakan tipe data List dengan struktur data Heapq atau juga disebut Priority queue. Penggalan fungsi utama algoritme Dijkstra dapat dilihat pada Gambar 8. Kode lengkap Dijkstra dapat dilihat pada Lampiran 2.

Gambar 8 Kode program fungsi utama algoritme Dijkstra

Pengujian pada Data Jaringan Buatan dan Data Jaringan Jalan Riil Pengujian pada Data Jaringan Buatan Pengujian pada data buatan dilakukan dengan menguji beberapa kombinasi parameter. Untuk nilai konstanta di tentukan lima buah nilai dalam selang [0, 2] yaitu 0.1, 0.5, 1, 1.5, 2. Untuk nilai konstanta ρ ditentukan tiga buah nilai dalam selang [0, 1] yaitu 0.1, 0.5 dan 0.9. Untuk jumlah semut (nk) ditentukan sebanyak 5 semut dalam tiap iterasi, dimana untuk penentuan jumlah semut didapatkan dari percobaan awal yang menunjukan bahwa jumlah semut 5 menghasilkan jumlah jalur alternatif yang sesuai dengan kebutuhan evaluasi alternatif solusi tanpa menggunakan sumberdaya yang berlebih. Untuk jumlah iterasi (t) dilakukan sebanyak t = 10 dengan pertimbangan waktu eksekusi dimana berdasarkan percobaan lainnya dengan nilai t lebih tinggi mengakibatkan waktu eksekusi bertambah sebanding penambahan nilai iterasi dengan perubahan kualitas panjang jalur yang tidak signifikan seperti ditunjukan dalam percobaan dengan t = 20 pada Lampiran 5. Hasil pengujian disajikan pada Tabel 3 dan Tabel 4. Dari hasil percobaan pada Tabel 3 dan Tabel 4, didapati bahwa kombinasi parameter yang memberikan hasil paling baik adalah nilai α = 0.1 dan ρ = 0.1. Makin kecil nilai nilai α dan ρ maka cenderung makin baik jalur yang dipilih. Pengaruh parameter ρ adalah yang paling signifikan terhadap hasil optimal. Untuk nilai ρ yang besar maka feromon akan menguap dengan cepat. Jika ρ = 1 pencarian sepenuhnya dilakukan secara acak. Nilai ρ yang kecil mengakibatkan pengaruh ingatan semut yang kuat terhadap sejarah pencarian sehingga kecenderungan untuk memilih jalur terbaik lebih besar. Untuk nilai α, makin kecil α maka makin kecil nilai probabilitas transisi.

17

Tabel 3 Hasil percobaan pada graf buatan dengan jumlah sisi v = 4 dan jumlah iterasi t = 10 Koefisien Koefisien pengaruh penguapan feromon feromon (ρ) 0.1 0.1 0.5 0.1 1 0.1 1.5 0.1 2 0.1

Waktu eksekusi rata-rata (detik)

Panjang rata-rata (satuan)

0.011722355 0.010703740 0.010842939 0.010084452 0.011196122

3 4 4.4 4.6 5.4

0.1 0.5 1 1.5 2

0.5 0.5 0.5 0.5 0.5

0.011288297 0.011680298 0.020442197 0.012060135 0.011336070

3.6 5 5.4 6 5.6

0.1 0.5 1 1.5 2

0.9 0.9 0.9 0.9 0.9

0.011754790 0.012116114 0.022121595 0.012536691 0.024868075

3.4 5.6 6.2 6 6.8

Tabel 4 Hasil percobaan pada graf buatan dengan jumlah sisi v = 5 dan jumlah iterasi t = 10 Koefisien Koefisien pengaruh penguapan feromon feromon (ρ) 0.1 0.1 0.5 0.1 1 0.1 1.5 0.1 2 0.1

Waktu eksekusi rata-rata (detik)

Panjang rata-rata (satuan)

0.024612652 0.023728416 0.233701525 0.023400748 0.021809152

4.4 5.2 6.4 6.2 6

0.1 0.5 1 1.5 2

0.5 0.5 0.5 0.5 0.5

0.025014911 0.025922887 0.024634829 0.025321331 0.025042314

4.6 7.6 7.7 7.4 7.4

0.1 0.5 1 1.5 2

0.9 0.9 0.9 0.9 0.9

0.024547880 0.020357798 0.02719 0.023244680 0.024236478

5.2 6.4 7.6 7 7.4

18

Pengujian pada Data Jaringan Jalan Riil Pengujian pada data JJR menggunakan parameter terbaik hasil percobaan pada data buatan yaitu α = 0.1 dan ρ = 0.1 dengan jumlah semut nk = 5 dan jumlah iterasi t = 10. Hasil percobaan pada data JJR Aceh dan Bogor Tengah disajikan pada Tabel 5, Tabel 6, Tabel 7 dan Tabel 8. Untuk hasil percobaan lengkap JJR Aceh dapat dilihat pada Lampiran 3 dan untuk JJR Bogor Tengah pada Lampiran 4. Tabel 5 Hasil percobaan pada data JJR Aceh ACO Percobaan

Jumlah simpul

Panjang jalur (meter)

Dijkstra Waktu eksekusi (detik)

Jumlah simpul

Panjang jalur (meter)

Selisih jumlah simpul

Waktu eksekusi (detik)

Selisih panjang jalur (meter)

Selisih waktu eksekusi (detik)

1

17.2

310900.2

0.01048173

19

309007

0.0124853

-1.8

1893.2

-0.00201

2

12

243879

0.00567874

12

243879

0.0133240

0

0

-0.00765

3

34.8

448907.8

0.01701526

36

447978

0.0182357

1.2

929.8

-0.00122

4 5

28.6 34.6

563910.2 755725.4

0.02301478 0.02254130

30 33

557987 744507

0.0198447 0.0210351

-1.4 1.6

5923.2 11218.4

0.00317 0.00150

Tabel 6 Jalur terbaik untuk percobaan pada data JJR Aceh Jalur terbaik pada percobaan

Percobaan 1

2 3

4

5

ACO

Dijkstra

121-76-77-84-74-71-70-69164-65-63-62-68-163-56-5553-54-57-64 121-76-77-84-74-71-70-69164-65-63-62-68 162-126-124-121-76-77-84-7471-70-69-65-63-62-68-56-5553-54-38-34-13-29-32-33-2012-2-5-4-3-6-8-9-10-22 162-126-124-121-76-77-84-7471-70-69-65-63-62-67-68-16356-55-53-54-57-64-66-85-91107-134-135-140-139 162-126-124-121-76-77-84-7471-70-69-65-62-68-56-58-5457-64-66-85-91-107-134-135140-139-136-138-142

121-76-77-84-74-71-70-69-16465-63-62-68-163-56-55-53-5457-64 121-76-77-84-74-71-70-69-16465-63-62-68 162-126-124-121-76-77-84-7471-70-69-164-65-63-62-68-16356-55-53-54-38-34-13-29-3233-20-12-2-5-4-3-6-8-9-10-22 162-126-124-121-76-77-84-7471-70-69-164-65-63-62-68-16356-55-53-54-57-64-66-85-91107-134-135-140-139 162-126-124-121-76-77-84-7471-70-69-164-65-63-62-68-16356-55-53-54-57-64-66-85-91107-134-135-140-139-136-138142

Dari hasil percobaan pada data JJR Aceh, untuk panjang jalur, Dijkstra lebih baik dibandingkan dengan ACO meskipun pada percobaan 2 ACO menghasilkan solusi yang sama baiknya dengan Dijkstra. Hasil konstruksi jalur terbaik dari kedua algoritme pada data JJR Aceh disajikan dalam Tabel 6. Contoh hasil visualisasi dari jalur yang dibangun oleh metode Dijkstra dan ACO untuk percobaan pada data JJR Aceh dapat dilihat pada Gambar 9. Untuk waktu eksekusi, pada Tabel 5 untuk

19

percobaan 1, 2 dan 3 ACO memiliki waktu eksekusi yang lebih baik dibandingkan dengan Dijkstra sedangkan Dijkstra memiliki waktu eksekusi yang lebih baik pada percobaan 4 dan 5. Hasil percobaan untuk data JJR Bogor Tengah disajikan dalam Tabel 7. Dari hasil percobaan pada data JJR Bogor Tengah, untuk panjang jalur pada semua percobaan Dijkstra lebih baik dibandingkan dengan ACO. Hasil konstruksi jalur terbaik dari kedua algoritme pada data JJR Bogor Tengah disajikan dalam Tabel 8.

(a) (b) Gambar 9 Jalur terbaik hasil ACO (a) dan hasil Dijkstra (b) untuk data Aceh pada Percobaan 5 Contoh hasil visualisasi dari jalur terbaik yang dibangun oleh metode ACO dan Dijkstra untuk percobaan pada data JJR Bogor Tengah dapat dilihat pada Gambar 10. Untuk waktu eksekusi, pada seluruh percobaan yang dilakukan, ACO memiliki waktu eksekusi yang lebih baik dibandingkan dengan algoritme Dijkstra. Tabel 7 Hasil percobaan pada data JJR Bogor Tengah ACO Percobaan

Dijkstra

Jumlah simpul

Panjang jalur (meter)

Waktu eksekusi (detik)

1

18.4

2981.2596

2

40.6

3

46.4

4 5

Selisih jumlah simpul

Selisih panjang jalur (meter)

Selisih waktu eksekusi (detik)

-0.6

138.596

-0.003597

0.0489059

1.6

534.677

-0.003831

0.0565414

-0.6

317.698

-0.001303

3364.15

0.0386806

4.4

1059.61

-0.005351

2723.20

0.0422749

0.8

196.775

-0.018679

Jumlah simpul

Panjang jalur (meter)

Waktu eksekusi (detik)

0.0207825

19

2842.66

0.0243798

6467.4899

0.0450747

39

5932.81

8314.9096

0.0552381

47

7997.21

27.4

4423.7667

0.0333297

23

19.8

2919.9741

0.0235961

19

Berdasarkan hasil percobaan pada data jaringan jalan Provinsi Aceh dan jaringan jalan Bogor Tengah, untuk panjang jalur, algoritme Dijkstra menghasilkan panjang jalur yang lebih baik dibandingkan dengan metode Koloni Semut, walaupun pada satu percobaan (Tabel 5 percobaan ke 2) algoritme Koloni Semut dapat menghasilkan panjang jalur yang sama dengan panjang jalur dari algoritme

20

Dijkstra. Untuk waktu eksekusi, metode Koloni Semut memiliki waktu eksekusi rata-rata yang lebih cepat daripada algoritme Dijkstra kecuali pada percobaan ke 4 dan 5 dalam Tabel 7. Tabel 8 Jalur terbaik untuk percobaan pada data JJR Bogor Tengah Jalur terbaik pada percobaan

Percobaan 1

2

3

4

5

ACO

Dijkstra

0-2-4-5-6-13-20-24-54-99-95112-201-120-340-118-218-219241-222 0-2-4-5-6-13-20-24-53-52-95112-201-120-340-118-218-219241-222-324-239-183-182-176166-154-155-158-146-87-78-7068-63-49-36-30-31-355-329-330 0-2-4-5-6-13-20-24-54-99-334112-201-120-340-341-219-241222-324-239-183 183-182 182176-166-154-155-158-254-171165-151-153-136-137-141-139138-140-142-144-221-230-266261-281-384 0-2-4-5-6-13-20-24-54-99-334112-201-202-337-338-169-160152-134-125-110-100-86-84-8285-381 236-199-167-166-154-155-158254-171-165-151-153-136-137141-139-138-140-142-144

0-2-4-5-6-13-20-24-54-99-334112-201-120-340-118-218-219241-222 0-2-4-5-6-13-20-24-54-99-334112-201-120-340-118-218-219241-222-324-239-183-182-176166-154-155-158-146-87-76-7558-38-40-35-28-329-330 0-2-4-5-6-13-20-24-54-99-334112-201-120-340-118-218-219241-222-324-239-183-182-176166-154-155-158-254-171-165151-153-136-137-141-139-138140-142-144-221-230-266-261281-384 0-2-4-5-6-13-20-24-54-99-334336-335-168-169-160-152-134125-113-84-82-85-381 236-199-167-166-154-155-158254-171-165-151-153-136-137141-139-138-140-142-144

Dari hasil percobaan yang dilakukan pada data JJR Aceh dan JJR Bogor Tengah, pada sebagian besar percobaan algoritme Koloni Semut lebih cepat dibandingkan dengan algoritme Dijkstra kecuali pada data JJR Aceh percobaan ke 4 dan 5. Secara teori, kompleksitas dari algoritme Koloni Semut adalah O(1/ρ n2 log n) dan algoritme Dijkstra yang diimplementasikan menggunakan min-priority queue dengan binary min-heap adalah O(E log V). Berdasarkan percobaan yang dilakukan, waktu eksekusi algoritme Koloni Semut yang lebih cepat dibandingkan dengan algoritme Dijkstra dimungkinkan oleh karena pada algoritme Koloni Semut penyusunan jalur solusi akan berhenti saat semut sudah berada pada titik tujuan sehingga proses pencarian jalur terpendek untuk beberapa kasus pasangan titik awal dan titik tujuan pencarian hanya akan melibatkan sebagian dari jaringan atau dilakukan pada sub graf dari graf tersebut. Makin jauh letak titik awal dan titik tujuan maka makin luas pula bagian dari jaringan yang perlu dieksplorasi oleh semut buatan sehingga berakibat pada bertambahnya waktu eksekusi. Sebaliknya untuk algoritme Dijkstra konstruksi jalur solusi dilakukan dengan menguji semua simpul yang terdapat pada jaringan. Untuk percobaan pada data Aceh khususnya untuk percobaan 4 dan 5 JJR algoritme Koloni Semut memiliki waktu eksekusi

21

yang lebih lambat yang diakibatkan oleh dua hal. Pertama, pada percobaan 4 dan 5 letak dari titik awal dan titik tujuan berada pada ujung jaringan sehingga area pencarian semut hampir meliputi seluruh jaringan. Kedua, pada data Aceh simpul dan sisi tidak menyebar merata dalam jaringan sehingga terdapat area yang memiliki derajat simpul tinggi yang berarti dalam area tersebut terdapat banyak alternatif jalur yang dieksplorasi semut buatan dan berakibat pada waktu eksekusi. Pengujian pada Data Jalur Bus Karyawan IPB Pengujian juga dilakukan terhadap data jalur bus karyawan IPB dengan rute Kampus Baranangsiang ke Kampus Dramaga dan sebaliknya. Pada pengujian ini dilakukan pengujian untuk mencari jalur terpendek dan jalur tercepat. Jalur bus karyawan IPB tersebut melewati tiga jalur yaitu jalur Jalan Baru, jalur Stasiun Kereta Bogor dan jalur Sukasari-Pasir kuda (Gambar 11). Hasil percobaan dapat dilihat pada Tabel 9. Hasil visualisasi dari solusi untuk kasus JJR Bus IPB dapat dilihat pada Gambar 12.

(a) (b) Gambar 10 Jalur terbaik hasil ACO (a) dan hasil Dijkstra (b) untuk data Bogor Tengah pada Percobaan 4

Gambar 11 Jaringan jalur bus karyawan IPB Baranangsiang-Dramaga

22

Tabel 9 Hasil percobaan pada data jalur bus karyawan IPB ACO Jalur

Parameter

Baranang siangDramaga

Jarak (meter) Waktu (menit)

DramagaBaranangsi ang

Jarak (meter) Waktu (menit)

Dijkstra

Selisih waktu eksekusi (detik)

Rute

0 0

-0.004738 -0.004269

Jalan baru Jalan baru

0.007359

0

-0.004483

St.kereta

0.007766

0

-0.004777

Jalan baru

Panjang jalur (meter)

Waktu eksekusi (detik)

Panjang jalur (meter)

Waktu eksekusi (detik)

14247.83 50

0.002872 0.002842

14247.83 50

0.007611 0.007110

14519.90

0.002876

14519.90

72

0.002990

72

Selisih Panjang (meter)

(a) (b) Gambar 12 Solusi jalur Jalan Baru (a) dan solusi jalur Stasiun kereta (b) Dari hasil percobaan pada data jalur bus karyawan IPB, untuk jalur pagi dari Kampus Baranangsiang menuju Kampus Dramaga baik rute terpendek dan tercepat adalah melewati jalur jalan baru dengan panjang jarak ± 14.247 km dan waktu tempuh ± 50 menit. Untuk rute sore dari Kampus Dramaga menuju Kampus Baranangsiang jalur terpendek adalah melalui jalur Stasiun kereta Bogor dengan jarak ± 14.519 km sedangkan untuk waktu tempuh yang lebih cepat adalah melalui jalur Jalan baru dengan waktu tempuh ± 72 menit.

5 SIMPULAN DAN SARAN Simpulan Berdasarkan percobaan yang dilakukan pada data jaringan jalan riil dengan menggunakan kombinasi parameter α = 0.1, ρ = 0.1, nk = 5 dan t = 10, pada sebagian besar percobaan menunjukan bahwa algoritme Koloni Semut memiliki waktu eksekusi yang lebih cepat dibandingkan dengan algoritme Dijkstra. Hasil penelitian menunjukan bahwa pada terdapat kasus-kasus tertentu dimana algoritme Koloni Semut dapat memiliki waktu eksekusi yang lebih cepat dibandingkan dengan algoritme Dijkstra dimana hal tersebut dapat dipengaruhi oleh letak dari simpul awal dan simpul akhir serta penyebaran simpul dan sisi pada jaringan.

23

Untuk panjang dari jalur terpendek, dari sebagian besar percobaan algoritme Dijkstra lebih baik dibandingkan dengan algoritme Koloni Semut namun algoritme Koloni Semut juga dapat menghasilkan panjang jalur yang setara dengan algoritme Dijkstra.

Saran 1. 2. 3. 4.

Penelitian selanjutnya dapat mengakomodir JJR dua arah. Melakukan pencarian parameter optimal menggunakan teknik seperti Grid search dan mencoba varian algoritme lainnya dari metode Koloni Semut. Memanfaatkan fitur-fitur dalam SIG seperti fitur buffer untuk mengendalikan ukuran ruang pencarian. Perlu dicari formulasi untuk menggabungkan beberapa variabel seperti jarak, waktu dan biaya menjadi satu nilai tunggal sebagai bobot dari sisi.

24

DAFTAR PUSTAKA Attiratanasunthron N, Fakcharoenphol J. 2008. A running time analysis of an ant colony optimization algorithm for shortest path in directed acyclic graphs. Information Processing Letters.105:88-92. Behzadi S, Alesheikh AA, Poorazizi E. 2008. Developing a genetic algorithm to solve shortest path problem on raster a data model. Journal of applied science. 8(18): 3289-3293. Barus B, Wiradisastra US. 2009. Sistem informasi geografi sarana manajemen sumberdaya. Bogor (ID). Laboratorium Ilmu Tanah IPB. Brezina I, Cickova Z. 2011. Solving the travelling salesman problem using the ant colony optimization. Management Information Systems. 6: 010-014. Chang KT. 2008. Introduction to GIS Ed ke-4. New York (US). McGraw Hill. Cherkassky BV, Goldberg AV, Radzik T. 1996. Shortest path algorithms: theory and experimental evaluation. Mathematical Programming: Series A and B. 73: 129-174. Cormen T, Leiserson CE, Rivest LR, Stein S. 2009. Introduction to Algorithms 3rd Edition. Massachusetts (US). MIT Press. Curtin KM. 2007. Network analysis in geographic information science: review, assessment and projection. Cartography and Geographic Information Science. 34(2): 103-111. Dijkstra EW. 1959. A Note on two problems in connection with graphs. Numerishce Mathematik. 1: 269-271. Farhan B, Murray AT. 2005. A SIG based approach for delineating market areas for park and ride facilities. Transaction in GIS. 9: 91-108. Horner M, Grubesic T. 2001. A SIG based planning approach to locating urban rail terminals. Transportation. 28: 55-77. Dorigo M, DiCaro G. 1999. The ant colony optimization meta-heuristic. Di dalam: Corne D, Dorigo M, Glover F, editor. New ideas in optimization; Maidenhead (UK).McGraw Hill. 11-32. Dorigo M, Stutzle T. 2004. Ant Colony Optimization. MIT Press. Massachusetts. Engelbrecht A.P. 2007. Computational Intelligence: An Introduction 2nd Edition.New York (US). Wiley. Jabber FM, Ali KH, Hassan KR. 2006. Ant Colony Optimization for Coloring Problem. Basrah Journal of Science. 24(2):38-47. Fenet S, Solnon C. (2003). Searching for maximum cliques with ant colony optimization. Hart E, Johnson CG, Marchiori E (Editor). Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2003 of Lecture Notes in Computer Science. 2611: 236–245. Berlin (DE). SpringerVerlag. Kolavi SR, Bhatnagar S. 2009. Ant Colony Optimization Algorithms for Shortest Path Problems. Network Control and Optimization Lecture Notes in Computer Science. 5425: 37-44. Springer. Leng J, Zeng W. 2009. An improved shortest path algorithm for computing one-toone shortest paths on road networks. The 1st International conference on information science and engineering (ICSE); 2009 Des 26-28; Nanjing, Tiongkok. Nanjing (CH): IEEE. 1979-1982.

25

Lim Y, Kim H. 2005. A Shortest Path Algorithm for Real Road Network Based on Path Overlap. Journal of the Eastern Asia Society for Transportation Studies. 6: 1426-1438. Merkle D, Middendorf M, Schmeck H. 2002. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation. 6(4): 333–346. Neuman F, Witt C. 2009. Runtime analysis of a simple ant colony optimization algorithm. Algorithmica. 54(2): 243-255. Resende MGC, Pardalos PM. 2006. Handbook of optimization in telecommunications. New York (US). Springer. Zeng W, Church RL. 2008. Finding shortest path on real road networks: the case for A*. International journal of geographical information science. 23: 531-543. Zhan FB, Noon CE. 1998. Shortest path algorithms: an evaluation using real road networks. Transportation Science. 32 (1):65-73. Sumber internet

26

LAMPIRAN Lampiran 1 Kode Program ACO ##---Modified Simple Ant Colony Code---## ##©Edwin Tenda, Imas Sukaesih Sitanggang & Baba Barus @ILKOM IPB. 2014## import sys import time import random search_spaceS=[] search_spaceE=[] search_spaceL=[] links_feromon=[] combined_ST=[] links_feromon_init=random.random() #beri nilai awal feromon tiap link ##Load Data from File## source=open("D:/Project_thesis/Data/ACO_aceh.txt", "r") for line in (source) : line_=line.split(" ") search_spaceS.append(line_[0]) search_spaceE.append(line_[1]) search_spaceL.append(line_[2]) links_feromon.append(links_feromon_init) combined_ST.append(line_[0]+"-"+line_[1]) source.close ##Set Parameter dan S/E Node## start_node='162' end_node='142' global_start_node=start_node alfa =0.1 rho =0.1 iteration_=10 ant_total=5 current_node="" global_k_solution_lst=[] ##list untuk menyimpan set solusi global global_k_solution_length=[] ##list untuk menyimpan nilai solusi local/f(x) for k in range (iteration_): t1 = time.clock() ant=0 global_solution_lst=[] global_solution_length=[] for ant in range(1,ant_total+1): path_list=[] ##list untuk menyimpan set solusi local path_list_clear=[]##list untuk menyimpan set solusi local bebas loop local_solution_length=[] ##list untuk menyimpan nilai solusi local lst_solution_lenght=[] While True :

27

##Cari dan muat feasible nodes## feasible_nodes=[] ##list berisi feasible nodes dari titik current state## for index, item in enumerate(search_spaceS): if item == start_node:##mencari semua edge yang berasal dari start node feasible_nodes.append (index) ##menambahkan feasible nodes pada list feasible_nodes## if len(feasible_nodes)== 0 and len(path_list)!=0: del_index=path_list[-1] start_node=search_spaceS[(path_list[-1])] search_spaceS[del_index]="-" search_spaceE[del_index]="-" search_spaceL[del_index]="0" path_list.pop() continue elif len(feasible_nodes)==0 and len(path_list)==0: sys.exit("Tidak ada Feasible nodes") ##list untuk nilai feasible nodes links_feromon ## feas_fer_value=[] feas_fer_value_power_alfa=[] ##nilai feasible nodes links_feromon power alfa## for idx, val in enumerate(feasible_nodes): feas_fer_value.append (links_feromon[val]) feas_fer_value_power_alfa.append ((links_feromon[val])**alfa) lst_trans_prob_val=[] lst_trans_prob_idx=[] for idx, val in enumerate(feasible_nodes): cur_link_links_feromon= links_feromon[ val] Pk_ij=((cur_link_links_feromon** alfa)/(sum(feas_fer_value_power_alfa))) *random.uniform(0.7, 1) lst_trans_prob_val.append(Pk_ij) ##node untuk local solution## path_list.append(feasible_nodes[(lst_trans_prob_val.index(max(lst_t rans_prob_val)))]) current_node= search_spaceE[ feasible_nodes[(lst_trans_prob_val.index(max(lst_trans_prob_val)))] ] start_node=current_node if current_node==end_node : path_list_clear=[] for items, val in enumerate (path_list): if len(path_list_clear)==0: path_list_clear.append(val) else: if path_list_clear[-1]==val: pass else: path_list_clear.append(val) ##Tambahkan solusi lokal ke ant solution## global_solution_lst.append(path_list_clear) ##hitung panjang dari path yang terbentuk## for idx, val in enumerate(path_list_clear): lst_solution_lenght.append (float(search_spaceL[val])) global_solution_length.append (sum( lst_solution_lenght)) ##Uapkan feromon pada semua sisi##

28

for idx, val in enumerate(links_feromon): links_feromon[idx]=(1-rho)*links_feromon[idx] ##Tambahkan feromon## delta_links_feromon= 1/(sum( lst_solution_lenght)) for idx, val in enumerate(path_list_clear): links_feromon[val]= links_feromon[val]+delta_links_feromon lst_solution_lenght=[] ##Kosongkan list untuk perulangan berikut## feasible_nodes=[] feas_fer_value =[] feas_fer_value_power_alfa=[] lst_trans_prob_val=[] lst_trans_prob_idx=[] lst_solution_lenght=[] break start_node=global_start_node ant+=1 t2 = time.clock() ##--------------------------Daemon Actions-----------------------## global_k_solution_lst.append(global_solution_lst[global_solution_le ngth.index(min(global_solution_length))]) global_k_solution_length.append(global_solution_length[global_solut ion_length.index(min(global_solution_length))]) global_solution_length=[] global_solution_lst=[] ##Cetak solusi solusi global## print("---Final Solution----") print ("min global k ant length: ",global_k_solution_length [global_k_solution_length.index(min(global_k_solution_length))]) print ("waktu:",t2-t1) print ("global solution path:", global_k_solution_lst[global_k_solution_length.index(min(global_k_s olution_length))]) ###Konversi index hasil optimal kedalam bentuk path ----## path_index=[] for idx, val in enumerate(global_k_solution_lst[global_k_solution_length.index(min( global_k_solution_length))]): for index, value in enumerate(search_spaceS): if index==val: stringresult= "[" + str(value) +"-"+ str(search_spaceE[val]) + "]" path_index.append(stringresult) print (path_index) print ("total nodes:", len(path_index))

29

Lampiran 2 Kode Program Dijkstra ##Credit to: Max Burstein--> https://github.com/mburst/dijkstrasalgorithm ## import heapq import sys import time import random ##Set Parameter dan S/E Node## start_node='162' end_node='142' class Graph: def __init__(self): self.vertices = {} def add_vertex(self, name, edges): self.vertices[name] = edges def shortest_path(self, start, finish): distances = {} # Distance from start to node# previous = {} # Previous node in optimal path from source# nodes = [] # Priority queue of all nodes in Graph# for vertex in self.vertices: if vertex == start: # Set root node as distance of 0# distances[vertex] = 0 heapq.heappush(nodes, [0, vertex]) else: distances[vertex] = sys.maxsize heapq.heappush(nodes, [sys.maxsize, vertex]) previous[vertex] = None while nodes: smallest = heapq.heappop(nodes)[1] # Vertex in nodes with smallest distance in distances# if smallest == finish: # If the closest node is our target we're done so print the path# path = [] while previous[smallest]: # Traverse through nodes til we reach the root which is 0# path.append(smallest) smallest = previous[smallest] return path if distances[smallest] == sys.maxsize: # All remaining vertices are inaccessible from source# break for neighbor in self.vertices[smallest]: # Look at all the nodes that this vertex is attached to# alt = distances[smallest] + self.vertices[smallest][neighbor] # Alternative path distance if alt < distances[neighbor]: # If there is a new shortest path update our priority queue (relax)# distances[neighbor] = alt previous[neighbor] = smallest for n in nodes: if n[1] == neighbor: n[0] = alt break heapq.heapify(nodes) return distances

30

def __str__(self): return str(self.vertices) if __name__ == '__main__': g = Graph() for line in open("D:/Project_thesis/Data/Dijkstra_aceh.txt", "r"): line2=line.split() name = ' '.join(line2[0:1]) grades = line2[1:] grades_dict = {grades[i]: float(grades[i+1])for i in xrange(0,len(grades),2)} string= str("("+"'"+ str(name)+"', " + str(grades_dict)+")") g.add_vertex(str(name), grades_dict) print ("---------------------Dijkstra Result---------------------------") t1=time.clock() hasil=[] hasil =g.shortest_path(start_node, end_node) hasil.reverse() hasil.insert(0, start_node) print (hasil) t2=time.clock() total= len(hasil) list_solution=[] a=1 for i in xrange (0, total-1): list_solution.append(hasil[i]+"-"+hasil[a]) a+=1 print ("List solution:",list_solution) #Pair dari startnode-end node# ##Delete doubled value index## duplicates_x=[] duplicates_x= [x for i, x in enumerate ( combined_ST) if combined_ST.count(x) > 1] duplicates_x= list(set(duplicates_x)) double_nodes=[] for idx, val in enumerate(duplicates_x): for index, value in enumerate(combined_ST): if val==value: double_nodes.append(index) break #Find the solution list index from the search space# path_index2=[] #hasilnya adalah index dari fitur# for idx, val in enumerate(list_solution): for index, value in enumerate(combined_ST): if value==val: path_index2.append(index) for idx, val in enumerate(double_nodes): for index, value in enumerate(path_index2): if value==val: path_index2.remove(val) #Count The Total Length# length_total=0 for idx,val in enumerate(path_index2): for index,value in enumerate(search_spaceL): if index==val: length_total+=float(value)

31

##--Dijkstra final solution--## print ("Length Total:", length_total) print("Dijkstra time:", t2-t1) print ("path index 2 :", path_index2) print ("total nodes:", len(path_index2))

32

Lampiran 3 Hasil Percobaan lengkap pada data JJR Aceh Simpul awalSimpul akhir 1.1 121-64 1.2 121-64 1.3 121-64 1.4 121-64 1.5 121-64 Rata-rata 2.1 121-68 2.2 121-68 2.3 121-68 2.4 121-68 2.5 121-68 Rata-rata 3.1 162-22 3.2 162-22 3.3 162-22 3.4 162-22 3.5 162-22 Rata-rata 4.1 162-139 4.2 162-139 4.3 162-139 4.4 162-139 4.5 162-139 Rata-rata 5.1 162-142 5.2 162-142 5.3 162-142 5.4 162-142 5.5 162-142 Rata-rata

Percoba an

ACO Panjang jalur (m)

Waktu eksekusi (s)

310713 309007 311162 313567 310052 310900.2 243879 243879 243879 243879 243879 243879 448264 449842 448897 447978 449558 448907.8 559295 560675 559565 580272 559744 563910.2 748615 770421 746860 747547 765184 755725.4

0.011818065 0.009432324 0.008897437 0.014235314 0.008025499 0.010481728 0.004833031 0.004381675 0.00426737 0.007316224 0.007595391 0.005678738 0.016685534 0.017660054 0.017377223 0.015387884 0.017965599 0.017015259 0.020718433 0.029461999 0.021578648 0.018067447 0.025247385 0.023014783 0.020594604 0.022976681 0.0242714 0.021470206 0.0233936 0.022541298

Dijkstra Jlh Node

Panjang jalur (m)

Waktu eksekusi (s)

Jlh Node

17 19 19 14 17 17.2 12 12 12 12 12 12 36 31 36 35 36 34.8 28 27 25 33 30 28.6 27 43 29 31 43 34.6

309007 309007 309007 309007 309007 309007 243879 243879 243879 243879 243879 243879 447978 447978 447978 447978 447978 447978 557987 557987 557987 557987 557987 557987 744507 744507 744507 744507 744507 744507

0.01448957 0.01227821 0.01186276 0.01358099 0.01021487 0.01248528 0.01012401 0.01761389 0.01761389 0.01118573 0.01008225 0.01332395 0.01848583 0.01842208 0.01748640 0.01849682 0.01828726 0.01823568 0.02047004 0.02108919 0.01794362 0.01901046 0.02071037 0.01984474 0.02427067 0.02214577 0.01959810 0.01918631 0.01997399 0.02103497

19 19 19 19 19 19 12 12 12 12 12 12 36 36 36 36 36 36 30 30 30 30 30 30 33 33 33 33 33 33

33

Lampiran 4 Hasil percobaan lengkap pada data JJR Bogor Tengah Percoba an

Simpul awalSimpul akhir 1.1 0-222 1.2 0-222 1.3 0-222 1.4 0-222 1.5 0-222 Rata-rata 2.1 2.2 2.3 2.4 2.5

0-330 0-330 0-330 0-330 0-330 Rata-rata 3.1 0-384 3.2 0-384 3.3 0-384 3.4 0-384 3.5 0-384 Rata-rata 4.1 0-381 4.2 0-381 4.3 0-381 4.4 0-381 4.5 0-381 Rata-rata 5.1 236-144 5.2 236-144 5.3 236-144 5.4 236-144 5.5 236-144 Rata-rata

ACO

Dijkstra

Panjang jalur (m)

Waktu eksekusi (s)

Jlh node

Panjang jalur (m)

Waktu eksekusi (s)

Jlh Node

3162.347 2940.351 2872.614 2872.614 3058.371 2981.260

0.019858218 0.019165064 0.024003957 0.020873038 0.02001209 0.020782473

18 19 19 19 17 18.4

2842.66402 2842.66402 2842.66402 2842.66402 2842.66402 2842.66402

0.02494257 0.02467659 0.02361561 0.02412925 0.02453518 0.02437984

19 19 19 19 19 19

6455.396 6567.647 6917.816 6120.187 6276.402 6467.490 8033.450 8316.894 8396.982 7997.211 8830.010 8314.909 4363.788 4323.420 4646.731 4431.524 4353.370 4423.767 3048.056 3115.932 2989.485 2723.197 2723.199 2919.974

0.038790277 0.045447052 0.043194666 0.05404041 0.043901009 0.045074683 0.057972926 0.055036911 0.058160503 0.051442912 0.05357733 0.055238116 0.033615065 0.033992416 0.033663424 0.032979062 0.032398747 0.033329743 0.024071367 0.024472898 0.024022275 0.023729186 0.021684893 0.02359612

40 41 39 41 42 40.6 47 45 48 46 46 46.4 27 27 29 27 27 27.4 19 20 22 19 19 19.8

5932.81264 5932.81264 5932.81264 5932.81264 5932.81264 5932.81264 7997.2115 7997.2115 7997.2115 7997.2115 7997.2115 7997.2115 3364.15511 3364.15511 3364.15511 3364.15511 3364.15511 3364.15511 2723.19883 2723.19883 2723.19883 2723.19883 2723.19883 2723.1988

0.04937737 0.04822040 0.04847466 0.05032844 0.04812881 0.04890594 0.06778040 0.05173380 0.06283801 0.04931582 0.05103918 0.05654144 0.03835284 0.03869429 0.04144859 0.03389863 0.04100896 0.03868066 0.03935520 0.04347237 0.04570497 0.04156875 0.04127347 0.04227495

39 39 39 39 39 39 46 46 46 46 46 46 23 23 23 23 23 23 19 19 19 19 19 19

34

Lampiran 5 Percobaan pada data buatan dengan nilai iterasi t = 20 Hasil percobaan pada graf dengan jumlah sisi v = 4 dan jumlah iterasi t = 20 Koefisien Koefisien pengaruh penguapan feromon feromon (ρ)

Waktu eksekusi rata-rata (detik)

Panjang rata-rata

0.1 0.5 1 1.5 2

0.1 0.1 0.1 0.1 0.1

0.023509042 0.021453641 0.021509615 0.017383722 0.021703349

3 3.8 5 3.6 4.8

0.1 0.5 1 1.5 2

0.5 0.5 0.5 0.5 0.5

0.023831875 0.023315167 0.028189055 0.022169793 0.020478841

3.6 4.6 5.2 5.2 4.6

0.1 0.5 1 1.5 2

0.9 0.9 0.9 0.9 0.9

0.023154410 0.019222095 0.021382122 0.020886815 0.022341540

3.2 4.2 5.6 5 5.4

Hasil percobaan pada graf dengan jumlah sisi v = 5 dan jumlah iterasi t = 20 Koefisien Koefisien pengaruh penguapan feromon feromon (ρ)

Waktu eksekusi rata-rata (detik)

Panjang rata-rata

0.1 0.5 1 1.5 2

0.1 0.1 0.9 0.1 0.1

0.047855867 0.046673564 0.043233916 0.050596940 0.047911553

4.2 6.2 6.8 6.4 6.2

0.1 0.5 1 1.5 2

0.5 0.5 0.5 0.5 0.5

0.049693800 0.049877271 0.038756287 0.049877271 0.045340029

4.4 6.8 6.6 7.4 6.8

0.1 0.5 1 1.5 2

0.9 0.9 0.9 0.9 0.9

0.048335207 0.046112454 0.034458174 0.043833868 0.048661410

5.2 6.2 6.8 6.4 7.2

35

RIWAYAT HIDUP Penulis dilahirkan di Minahasa Selatan, Sulawesi Utara pada tanggal 8 April 1987 sebagai anak ke empat dari empat bersaudara, dari pasangan Bapak Jootje A Tenda dan Ibu Margootje Rumondor. Penulis menamatkan studi Sekolah Menengah Atas (SMA) pada tahun 2004 di SMA N 5 Manado. Pada tahun 2004, Penulis melanjutkan studi S1 di Universitas Nusantara Manado, Fakultas Ilmu Komputer, Jurusan Teknik Informatika dan lulus pada tahun 2008. Tahun 2012 Penulis melanjutkan studi S2 di Institut Pertanian Bogor (IPB) pada program studi Ilmu Komputer.