PENENTUAN RUTE TERPENDEK BERSEPEDA

DI AREA KOTA MALANG MENGGUNAKAN ALGORITMA SEMUT

Dian Eka Ratnawati, Sindy Yudi Prakoso, Yusi Tyroni Mursityo

Program Studi Ilmu Komputer, Program Teknologi Informasi dan Ilmu Komputer, Universitas

Brawijaya, Jl. Veteran Malang, Jawa Timur, 65141

Email: dian_ilkom@ub.ac.id ,jimmz.mail@gmail.com, yusi.tyro@gmail.com

Abstrak

Bersepeda dianggap sebagai transportasi bebas polusi dan menyehatkan, namun diperlukan adanya suatu informasi perjalanan. Informasi perjalanan ini sangat erat kaitannya dengan rute yang dipilih sehingga dapat menghasilkan solusi yang optimal, dalam hal ini adalah meminimalkan jarak perjalanan dari tempat asal menuju tempat tujuannya.

Penelitian ini bertujuan membangun sebuah sistem penentuan jalur terpendek bersepeda di area kota Malang menggunakan algortima semut. Pada penelitian ini ingin diketahui apakah hasil jalur terpendek yang dihasilkan oleh algoritma semut lebih baik dari solusi yang dihasilkan algoritma Dijkstra atau sebaliknya. Dari ujicoba dengan membandingkan algoritma semut dengan Dijkstra diperoleh nilai MSE 0.490746 yang membuktikan bahwa algoritma semut memiliki tingkat akurasi yang cukup tinggi.

Kata Kunci: Algoritma Semut, Ant Colony System, Algoritma Dijkstra, Rute Terpendek.

Abstract

Cycling is considered to be a healthy and pollution-free tranportation, but it needs some kind of travel information. This travel Information is very closely related with the selected route so that it can provide optimal solution, in this case to minimize distance from starting point to the desired destination.

This study aims to build a shortest cycling path determination in Malang City using ant algorithm system. In this study wanted to know whether the results generated by the shortest path ant algorithm is better than Dijkstra algorithm generated solutions. From the test by comparing the ant algorithm Dijkstra is obtained MSE 0.490746 which proved that the ant algorithm has a fairly high degree of accuracy.

Keyword : Ant Algorithm, Dijkstra Algorithm, Shortest Route

PENDAHULUAN

Salah satu inovasi untuk mengurangi polusi dalam transportasi darat yaitu dengan adanya program car free day yang diharapkan bisa memberikan ruang bagi masyarakat Kota Malang untuk bisa berolahraga serta menikmati udara segar bebas asap[1]. Dengan ditunjang dengan slogan Bike to Work ternyata banyak diminati oleh warga kota Malang.

Kebutuhan akan suatu informasi atau petunjuk tentang suatu lokasi baik itu lokasi jalan ataupun lokasi obyek-obyek tertentu sangat diperlukan bagi pengguna sepeda untuk menentukan jalur terpendek dari suatu tempat

ke tempat lainnya. Shortest path problem merupakan salah satu permasalahan optimasi yang dapat diselesaikan dengan menggunakan metode heuristik, seperti algoritma genetika (Genetic Algorithm, GA) dan algoritma semut (Ant Colony, AntCo)[2]. Algoritma semut adalah solusi universal dan fleksibel yang awalnya digunakan pada permasalahan optimasi Traveling Salesman Problem. Analogi pencarian rute terpendek oleh semut-semut, telah menjadi stimulus terciptanya suatu metode untuk menentukan jarak terpendek dari suatu tempat ke tempat lain, Jarak terpendek yang dimaksud adalah hasil dari perhitungan beberapa parameter melalui Ant Colony Optimization [3].

Dalam penelitian ini, pencarian rute terpendek mempunyai tujuan membantu dalam menentukan jalur terpendek dari dan menuju suatu tempat tertentu di Malang khususnya Malang Kota, dengan ditentukannya jalur terpendek maka diharapkan dapat meminimalisasi waktu tempuh perjalanan

TINJAUAN PUSTAKA

2.1 Konsep Dasar Ant Colony Optimization (ACO)

Algoritma Ant Colony Optimization diinspirasikan oleh lingkungan koloni semut pada saat mencari makanan [3]. Semut-semut mempunyai penyelesaian yang unik dan sangat maju yaitu dengan menggunakan jejak pheromone, proses peninggalan pheromone ini dikenal sebagai stigmergy, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan koloninya pada suatu jalur dan membangun solusi, semakin banyak jejak pheromone ditinggalkan, maka jalur tersebut akan diikuti oleh semut lain.

Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek, yaitu[3]:

a. Inisialisasi Parameter

Dalam ACO terdapat beberapa parameter masukan sebagai inisialisasi awal untuk melakukan proses optimasi. Beberapa parameter tersebut adalah:

1.            iij : Intensitas jejak semut antar kota dan perubahannya

2.            n : Banyak titik atau dij (jarak antar kota)

3.            Penentuan kota berangkat dan kota tujuan

4.            Q : Tetapan siklus semut

5.            a : Tetapan pengendali intensitas jejak semut

6.            R : Tetapan pengendali visibilitas

7.            ilij : Visibilitas antar titik (1/dij)

8.            m : Jumlah semut

9.            p : Tetapan penguapan jejak semut

10.         Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan.

11.         Inisialisasi kota pertama setiap semut.

m semut ditempatkan pada kota pertama yang telah ditentukan.

b. Pengisian Tabu List

Pengisian kota pertama ke dalam tabu list. Hasil dari langkah ini adalah terisinya elemen tabu list oleh setiap semut.

c. Pemilihan Rute Perjalanan Semut

Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Perhitungan nilai probabilitas kota untuk dikunjungi seperti pada persamaan 1:

N`]^Oa .Nb]^Oc

\]^ _ = ∑ _defghijkl_m     .Nb]_dOc (1)

N`]_dOa

dimana :

Pij : probabilitas verteks i ke verteks j

i              : verteks ke-i

j              : verteks ke-j

iij : pheromone dari verteks i ke verteks j R : tetapan pengendali visibilitas

a : tetapan pengendali intensitas jejak semut ilij : visibilitas dari verteks i ke verteks j

k : jumlah jalur kemungkinan yang dilalui

d. Perhitungan Panjang Jalur Setiap Semut Perhitungan dilakukan berdasarkan tabuk masing-masing dengan menggunakan persamaan 2:

nk = otapuq (n),tapuq(r)

ntr

+ s otapuq(s),tapuq(sRr) S+r

(2)

dimana :

Lk : panjang lintasan yang dilalui semut k

n : banyak titik

67!E/k(=),7!E/k(=R1) : bobot antara titik ke s

dan s+1 pada tabu list

e. Perhitungan Perubahan Harga Intensitas Pheromone Semut

Persamaan (3) digunakan untuk menghitung perubahan intensitas pheromone semut :

∆v&) = ∑ ∆v&)

' ~ ~+~

dimana : ∆v&) : Intensitas jejak semut antar kota dan perubahannya

∆v&)~ : perubahan harga intensitas jejak kaki semut antar kota setiap semut

m            : jumlah semut

k             : jumlah jalur yang mungkin dilewati

f. Pengosongan Tabu List

Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi.

2.2.Ant Colony System (ACS)

Algoritma Ant Colony System (ACS) merupakan pengembangan dari Algoritma ACO. Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone[4].Peranan utama dari penguapan Pheromone pada ACS adalah untuk mencegah stagnasi.

2.2.1.State Transition Rule

Aturan transisi status yang berlaku pada ACS[5] adalah seperti persamaan 4 :

)

= wjxCyjzf[v&,/O.[{&,/]|}, €,        )&k! ~ ≤ ~G (5k=204&7!=&)

)&k! 7&6!k (5k=2043!=&)

(4)

dimana :

j : titik yang akan dituju. Jumlah Pheromone yang terdapat pada edge antara titik r dan titik s.

q : sebuah bilangan random.

β : parameter pengendali jarak (p > 0 )

Jika q ≤ q0 maka pemilihan titik yang akan dituju menerapkan aturan eksploitasi sedangkan jika q > q0 maka menerapkan eksplorasi.

2.2.2.Update Pheromone Lokal

Lokal updating rule dengan mengubah tingkat pheromone pada edge-edge yang telah dikunjungi semut[5], menggunakan persamaan 5 :

v&) ← (1 − ‚). v&) + ‚. vG

dimana :

‚             : parameter evaporasi lokal.

i0            : nilai awal jejak pheromone.

dengan

1

vG = n.ƒnn

dimana :

n             : jumlah titik.

Cnn : panjang sebuah tour terbaik.

2.2.3.Update Pheromone Global

Global updating rule [5], menggunakan persamaan 7 :

v&) ← (1 − ‚). v&) + ‚. ∆v&)~        (7)

1 wƒE=

G            dengan: „v&)~ =

)&k!(3, =)… 74/3 753E!&k k5=50/3/1!n =5E!0&kn†!

dimana :

ρ : parameter evaporasi global.

Cbs : panjang lintasan terbaik keseluruhan.

iij            : intensitas jejak pheromone pada garis

(i,j)

2.3. Algoritma Dijkstra

Algoritma Dijkstra merupakan salah satu varian dari algoritma greedy, yaitu salah satu algoritma untuk pemecahan persoalan yang terkait dengan masalah optimasi. Algoritma greedy ini hanya memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa memikirkan konsekuensi ke depan. Algoritma greedy ini berupaya membuat pilihan nilai optimum lokal pada setiap langkah dan berharap agar nilai optimum lokal ini mengarah kepada nilai optimum global[6].

Fungsi objektif akan memaksimalkan atau meminimalkan nilai solusi. Tujuannya adalah memilih satu saja solusi terbaik dari masing¬masing anggota himpunan solusi

Penggunaan strategi greedy pada algoritma Dijkstra adalah Pada setiap langkah, ambil sisi berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang terpendek di antara semua lintasannya ke simpul-simpul yang belum terpilih.

2.4 Akurasi

Untuk menghitung akurasi menggunakan metode Mean Square Error (MSE). Semakin kecil nilai MSE mengindikasikan bahwa hasil prediksi semakin akurat[7]. Nilai MSE dapat diperoleh dengan persamaan 8.

nMSE = (Dig − Dik )2

n             (8)

dimana :

‡&8 : jarak aktual semut pada periode i ‡&k : jarak aktual dijkstra pada periode i n : jumlah percobaan

METODOLOGI

3.1. Perancangan Sistem

Gambar 1 merupakan flowchart pencarian rute terpendek menggunakan algoritma semut: 1. Inisialisasi parameter awal, yaitu:

a.            Parameter yang digunakan dalam penentuan rute terpendek yaitu nama jalan, titik penyusun jalan, dan panjang jalan

b.            Parameter algoritma semut, yaitu :

1.            Jumlah semut yang akan digunakan

(m)

2.            Jumlah iterasi yang akan digunakan (NCmax)

3.            Tetapan penguapan jejak semut (p)

4.            Tetapan pengendali intensitas jejak semut (a)

5.            Tetapan pengendali visibilitas (0)

6.            Intensitas jejak semut antar kota (i)

Gambar 1. Flowchart Membangun Rute

Perjalanan

2.            Hasil dari inisialisasi tersebut akan dimasukkan ke dalam tabu list sebagai node awal semut.

3.            Proses simulate ant yaitu mensimulasikan perjalanan semut sampai semua semut tiba pada tujuan tertentu secara random.

4.            Update pheromone lokal dimana setiap semut setelah menuju titik selanjutnya akan selalu melakukan update pheromone untuk membuat tingkat ketertarikan ruas¬ruas yang ada berubah secara dinamis.

5.            Simpan hasil terbaik dari setiap perjalanan semut kedalam tabulist.

6.            Update pheromone global.

7.            Reset tabulist.

8.            Jika kondisi terpenuhi, berhenti dan hasilnya adalah solusi rute terpendek

3.2 Perancangan Basis Data

Gambar 2 merupakan tabel-tabel dalam basisdata digunakan untuk menyimpan seluruh data yang digunakan oleh sistem. Tabel yang dapat disusun berdasarkan kebutuhan sistem ini yaitu tabel Jalan, tabel Cabang, tabel LampuLantas, dan tabel Koordinat Penyusun.

Gambar 2 Entity Relationship Diagram HASIL DAN PEMBAHASAN

Pada penelitian ini dilakukan dua skenario ujicoba. Pada uji coba yang pertama dilakukan pengujian pengaruh parameter semut untuk mendapatkan nilai parameter terbaik dari algoritma semut. Data yang digunakan pada pengujian pertama adalah data jalan kota malang. Uji coba ini dilakukan sebanyak 5 kali pada setiap perubahan nilai parameter. Dari uji coba tersebut akan diperoleh nilai terbaik yang kemudian akan di rata-rata sebagai nilai parameter yang optimal.

Pada ujicoba yang kedua,untuk mengetahui tingkat keoptimalan algoritma ant colony system, dilakukan perbandingan antara algoritma ant colony system dengan algoritma Dijkstra. Dalam melakukan perbandingan ini, parameter yang digunakan algoritma ant colony system adalah nCmax=20, m=500, i0=0.5, a=4, 0=4, p=0.9, dan Q0=0.3.

4.1.Pengujian Parameter Semut

4.1.1.Pengujian Jumlah Semut (m) dan Pheromone Awal(i0)

Pada pengujian ini nilai m antara 100 - 500 dan nilai i0 antara 0,1 - 0,9 didapatkan hasil seperti pada gambar 3.

4.1.2. Pengujian Parameter a dan R

Pengujian untuk mencari nilai a dan R yang terbaik dari nilai 1 sampai dengan 5, didapatkan hasil nilai a dan R terbaik adalah 4 seperti yang ditunjukkan pada gambar 4.

Gambar 4. Grafik Uji a dan R

4.1.3. Pengujian Parameter p

Pengujian untuk mencari nilai p yang terbaik dari nilai 0.1 - 0.9. Setelah 5 kali pengujian, didapatkan hasil nilai p terbaik adalah 0.9 seperti yang ditunjukkan pada gambar 5.

Gambar 5. Grafik Uji p

4.1.4. Pengujian Parameter Q0

Parameter ini merupakan konstanta yang digunakan untuk pemilihan titik-titik yang akan dilalui oleh semut. Didapatkan nilai konstanta Q0 yang terbaik adalah 0.3.seperti pada gambar 6.

Gambar 6. Grafik Uji Q0

4.1.5.Pengujian Konvergensi

Pengujian dengan beberapa generasi dilakukan untuk menghasilkan solusi yang konvergen. Hasil dari pengujian ini digunakan untuk mencari siklus awal terjadinya kestabilan nilai / jarak dengan pengecekan 20 iterasi terakhir yang menghasilkan jarak yang sama.

Gambar 7. Grafik Uji Konvergensi

Berdasarkan gambar 7, dapat diketahui bahwa pada generasi ke 20 sampai 50 memiliki nilai yang sama. Dapat dikatakan bahwa pada generasi ke 20 telah didapatkan hasil yang konvergen.

4.2 Pengujian ACS dengan algoritma Dijkstra

Hasil dari pengujian antara ACS dengan algoritma Dijkstra dapat dilihat pada gambar 8

Gambar 8. Pengujian ACS dengan algoritma Dijkstra

Dari hasil pengujian yang ditunjukkan pada gambar 8, jarak yang dihasilkan oleh ACS dan Dijkstra adalah sama.

Pada Gambar 9 terdapat rute yang dihasilkan oleh ACS dan Dijkstra.

Gambar 9. Rute yang dihasilkan oleh ACS dan Djikstra

Dari beberapa percobaan, algoritma Dijkstra selalu mendapat rute yang optimal untuk semua data uji karena algoritma hanya memikirkan solusi terbaik dengan langsung mengambil jarak terpendek pada saat itu tanpa memikirkan jarak total yang dihasilkan.

0 + 0.7225 + 1.162084 + 0.0784

MSE =

MSE = 0.490746

MSE yang dihasilkan tersebut membuktikan bahwa algoritma semut memiliki tingkat akurasi yang cukup tinggi untuk penyelesaian masalah.

KESIMPULAN

Kesimpulan yang dapat diambil daripenelitian ini adalah:

1.            Pencarian rute terpendek dengan metode

Ant         Colony  System  dapat

diimplementasikan. Proses pencarian rute terpendek di mulai dengan menyebarkan semut ke suatu titik, kemudian semut akan berjalan bebas menuju tujuan perjalanan. Dalam pemilihan jalur terpendek, metode ini tergantung dari nilai parameter yang dimasukkan antara lain jumlah semut, i0, a, R, P, dan Q0.

2.            Perbandingan jarak terpendek yang dihasilkan algoritma Ant Colony System dengan Dijkstra menghasilkan jarak yang relative sama. Hanya saja rute yang dihasilkan oleh algoritma Ant Colony System lebih bervariatif, karena dipengaruhi oleh beberapa parameter.

3.            Dari ujicoba diketahui bahwa algoritma Ant Colony System memiliki tingkat akurasi yang cukup tinggi,

DAFTAR PUSTAKA

[1]          Nugraha, D., & dkk. (2006). Diagnosis Gangguan Sistem Urinari pada Anjing dan Kucing menggunakan VFI 5. Bandung: IPB.Surya Post, 30 November 2011

[2]          Mutakhiroh, I., Saptono, F., Hasanah, N., & Wiryadinata, R. (2007). Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Dengan Algoritma Semut dan Algoritma Genetik. Yogyakarta: Seminar

Nasional              Aplikasi Teknologi

Informasi. ISSN: 1907-5022

[3]          M. Dorigo, V. Maniezzo, dan A. Colorni. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man,and Cybernetics— Part B, 26(1), , pp.1-13.

[4]          Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. England: The MIT Press Cambridge, Massachusetts Institute of Technology.

[5]          Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the traveling

salesman             problem.              Belgium:

Tech.Rep/IRIDIA/1996-003, Université Libre de Bruxelles.

[6]          Novandi, R. A. (2007). Perbandingan Algoritma Dijkstra dan Algoritma Floyd-Warshall dalam Penentuan Lintasan Terpendek (Single Pair Shortest Path). Bandung: Institut Teknologi Bandung.

[7]          Kaur Parvinder, Shakti Kumar,

dalam Pengaplikasian Lintasan Terpendek pada Link-State Routing Protocol. Bandung: Institut Teknologi Bandung

[9] Mutakhiroh, I., Saptono, F., Hasanah, N., & Wiryadinata, R. (2007). Pemanfaatan Metode Heuristik Dalam

Amarpartap        Singh, Optimization of     Pencarian            Jalur Terpendek Dengan

Membership       Functions             Based    on          Algoritma            Semut    dan        Algoritma

AntColony           Algorithm,           (IJCSIS)  Genetik.               Yogyakarta:        Seminar

International      Journal  of Computer       Nasional              Aplikasi Teknologi

Science and Information Security,Vol. 10, No. 4, April 2012, tanggal akses Agustus 2012

[8] Handaka, M. S. (2010). Perbandingan

Algoritma            Dijkstra (Greedy),

Bellman-Ford(BFS-DFS), dan Floyd-Warshall (Dynamic Programming)

Informasi. ISSN: 1907-5022.

[10] Wardy, I. S. (2007). Penggunaan graph dalam algoritma semut untuk melakukan optimasi. Bandung : Institut Teknologi Bandung.