SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
aplikasi mereka sendiri untuk PENENTUAN JALUR TERPENDEK menciptakan MENGGUNAKAN digunakan oleh bermacamTEKNOLOGI peranti bergerak, oleh karena itu Android memiliki komunitas besar GOOGLE MAPS MASHUPS DENGAN MOBILE SYSTEM ANDROID pengembang program aplikasi ("apps") yang Satria Prasamya, Ary Mazharuddin S., S.Kom, M.Comp.Sc memperluas fungsionalitas Saat ini ada Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologiperangkat. Sepuluh Nopember Email :
[email protected] lebih dari 70.000 aplikasi yang tersedia untuk
Abstrak - Penentuan jalur (rute) terpendek diperlukan karena dalam kehidupan sering dilakukan perjalanan dari satu tempat ke tempat yang lain dengan mempertimbangkan efisiaensi waktu, jarak tempuh dan biaya. secara umum, terdapat dua metode yang dapat digunakan untuk menentukan jalur terpendek, yaitu metode konvensional dan metode heuristik. untuk menghitung rute yang lebih besar digunakan metode heuristik karena waktu yang dibutukan lebih singkat . Salah satu mtode yang terkenal baik dalam perhitungan rute terpendek yang termasuk dalam metode heuristik adalah metode Ant Colony Optimization yang diambil dari perilaku koloni semut dalam pencarian jalur terpendek antara sarang dan sumber makanan. Terinspirasi dari hal tersebut dalam makalah ini akan diimplementasikan sebuah aplikasi yang berjalan pada mobile system android. Aplikasi ini memanfaatkan metode ant colony optimization dalam pencarian rute terpendek dengan menggunakan teknologi Google Maps. Penggunaan Google Map dirasa tepat mengingat google menyediakan informasi map yang paling lengkap diantara penyedia map yang lain. Uji coba ini di lakukan melalui beberapa skenario, yang mencerminkan fitur fitur yang ada di aplikasi. Hasil uji coba pada tugas akhir ini juga menunjukkan adanya efisiensi waktu dengan menggunakan aplikasi karena terdapat perkiraan waktu yang disediakan oleh Google Map sehingga berguna bagi user. Kata kunci: Jalur terpendek, metode Ant Colony, Google Map, Mobile System Android 1. Pendahuluan Kemajuan dunia teknolgi informasi yang begitu cepat ditunjang dengan penemuan dan inovasi telah membawa banyak perubahan dalam kehidupan manusia. Hal yang tidak luput dari perkembangan teknologi adalah telepon seluler. Saat ini, semua produsen berlomba mengembangkan pirantinya agar dapat bersaing dipasaran. Salah satu hasil dari perkembangan teknologi selular ini adalah lahirnya telepon seluler yang system operasinya menggunakan Android. Android sendiri merupakan system operasi telepon seluler yang berbasis linux. Android menyediakan platform terbuka bagi para pengembang buat
Android. Karena banyaknya aplikasi dan merupakan platform terbuka maka, pasar Android kedepannya dipastikan akan semakin meningkat pesat. Perkembangan teknologi komunikasi tidak sebatas pada telepon seluler saja tetapi mencakup internet sebagai salah satu medianya. Perkembangan internet beberapa tahun terakhir dengan Web 2.0 sebagai versi World Wide Web telah menawarkan konsep baru cara development.,dan usernnya aplikasi di internet. Terdapat berbagai macam layanan yang dapat digunakan secara bebas dan online sehingga dapat digunakan untuk menunjang aplikasi utama yang telah dikembangkan agar menjadi lebih interaktif dan akurat. Salah satu teknologi yang bisa digunakan adalah teknologi live application yang biasa disebut dengan mashup. Saat ini ada banyak teknologi mashup yang tersedia. Salah satu yang populer adalah mapping tools beserta geocoding service. Contoh, Google Maps yang memiliki kemampuan memberikan layanan dari mulai peta digital lengkap dengan foto satelit. Keistimewaan ini dapat dimanfaatkan untuk mendukung berbagai aplikasi sehingga menjadi lebih interaktif dan aktual. Salah satu aplikasi yang akan menjadi lebih interaktif yaitu aplikasi pencarian jalur (rute) terpendek. Aplikasi ini sangat dibutuhkan karena dalam kehidupan sehari hari sering dilakukan perjalanan dari suatu tempat atau kota ke tempat yang lain dengan mempertimbangkan efisiensi, waktu dan biaya sehingga diperlukan ketepatan dalam menentukan jalur terpendek. Permasalahan rute terpendek untuk mengurangi jarak tempuh dapat dikategorikan sebagai Travelling Salesman Problem (TSP). Berdasarkan penelitian M.Dorigo dan M.L Gambardella (1997) dalam penyelesaian kasus TSP, terbukti bahwa metode Ant Colony Optimization (ACO) mampu mendapatkan hasil tur terbaik dibandingkan dengan algoritma genetik (GA), Evoluionary Programming(EP), Simulated Annealing(SA) , dan Annealing-Genetic Algorithm (AG) Dengan memanfaatkan Google map maka proses penentuan sebuah rute terpendek akan dapat ditemukan dan tervisualisasi secara detail Oleh karena itu akan dibuat sebuah aplikasi yang dapat berjalan pada Android yang dapat memudahkan proses pengambilan keputusan dalam pencarian rute terpendek dengan memanfaatkan Google maps mashups dengan menggunakan metode ACO.. 1
Satria Prasamya - 5106100030
SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
1. Intensitas jejak semut antar kota dan perubahannya ( τ ij )
2.
Dasar Teori Pada bab ini akan dijelaskan dasar teori yang menjadi dasar pembuatan tugas akhir. Pokokpokok yang dibahas antara lain masalah optimisasi, pemecahan masalah TSP dengan algoritma Ant Colony serta Google Map. 2.2. Optimisasi Secara umum, masalah pencarian jalur terpendek dapat dikategorikan ke dalam masalah optimisasi. Pengertian nilai optimisasi adalah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai efektif yang dapat dicapai). Dalam disiplin matematika, optimisasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi nyata. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis dilakukan pemilihan nilai variabel integer atau nyata yang akan memberikan solusi optimal. Nilai optimal dapat dicari dengan dua cara, yaitu: • Cara konvensional, yaitu mencoba semua kemungkinan yang ada dengan mencatat nilai yang didapat,cara ini kurang efektif, karena optimasi akan berjalan secara lambat • Cara kedua adalah metode heuristik yaitu menggunakan suatu rumus sehingga nilai optimal dapat diperkirakan dengan cepat dan tepat. Salah satu metode heuristic adalah algoritma Ant Colony Optimization. Algoritma ini merupakan salah satu algoritma terbaik dalam masalah pencarian jalur terpendek seperti Travelling Salesman Problem(TSP). 2.3. Penyelesaian TSP Menggunakan Algoritma Semut TSP adalah salah satu teka-teki optimisasi yang cukup terkenal dikalangan peneliti dan pecinta matematika selamabertahun-tahun.Mereka berlomba untuk mencari penyelesaian kasus TSP dengan tekniknya masing-masing. Teknik yang cukup terkenal adalah simulated annealing, genetic algorithm, and ant colony optimization (algoritma semut). Dalam tugas akhir ini akan membahas teknik yang terakhir, yaitu algoritma semut. Algoritma semut atau Ant Colony Optimization telah digunakan untuk mencari lintasan optimal padaTravelling Salesman Problem (TSP). Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek, yaitu: • Langkah pertama adalah menginisialisasi harga parameter dari algoritma dan inisialisasi kota pertama setiap semut.. Parameter-parameter yang di inisialisasikan adalah :
2. Banyak kota (n) termasuk koordinat (x,y) atau jarak antar kota ( d ij ) 3. Kota berangkat dan kota tujuan 4. Tetapan siklus-semut (Q) 5. Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0 6. Tetapan pengendali visibilitas (β), nilai β≥0 7. Visibilitas antar kota η ij =
1 d ij
8. Banyak semut (m) 9. Tetapan penguapan jejak semut (ρ) , nilai ρ harus > 0 dan < 1 untuk mencegah jejak pheromone yang tak terhingga. 10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan τij akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi. Selanjutnya inisialisasi kota pertama setiap semut yang ditempatkan pada kota pertama tertentu secara acak. • Langkah kedua adalah pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama setiap semut dalam langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota tertentu, yang berarti bahwa setiap tabuk(1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 1. • Setelah itu langkah kemudian adalah penyusunan rute kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari kota pertama masing-masing sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota kedua masing-masing, koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai semua kota satu persatu dikunjungi atau telah menempati tabuk. Jika s menyatakan 2
Satria Prasamya - 5106100030
SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut :
[τ ] ⋅ [η ] α
Ρijk =
β
ij
∑ [τ ] ⋅ [η ] α
ik ' k '∈{N − tabu k }
untuk j ∈ J ij
k
ij
β
ik '
Ρijk = 0 u ntuk j lainnya k
Dimana J ij adalah himpunan titik j yang akan dikunjungi semut k yang berada pada titik i. • Langkah selanjutnya terbagi ke dalam tiga bagian yaitu a. Perhitungan panjang rute setiap semut. Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut : n−1
Lk = dtabuk ( n ),tabuk (1) + ∑ dtabuk ( s ),tabuk ( s+1) s =1
b. Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau LminNC dan harga minimal panjang rute tertutup secara keseluruhan adalah atau Lmin. c.Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejakjejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahan ini adalah m
∆τ ij = ∑ ∆τ ijk k =1
Dengan
∆τ
k ij adalah perubahan harga
intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan :
∆τ ijk = kota tabuk
asal
Q Lk
∆τ ijk = 0
untuk (i,j) ∈ dan kota tujuan dalam
untuk (i,j) lainnya
•
Langkah selanjutnya terbagi dalam dua tahapan yaitu : a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan
persamaan :
τ ij = ρ ⋅ τ ij + ∆τ ij
b.Atur ulang harga perubahan intensitas jejak kaki semut antar kota. Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. • Langkah terakhir adalah Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan. 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. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui. 2.4. Google Map Untuk menambahkan Google Map kedalam website dapat dilakukan dengan menggunakan Google Map API. Google Maps API dapat ditambahkan ke website menggunakan JavaScript. API tersebut menyediakan banyak fasilitas dan utilitas untuk memanipulasi peta dan menambahkan konten ke peta melalui berbagai layanan, memungkinkan untuk membuat aplikasi peta yang kuat pada website user. Pengetahuan yang diperlukan untuk mengembangkan Google Maps API adalah tentang HTML dan JavaScript, sedangkan peta sudah disediakan oleh Google. Jadi developer hanya berkonsentrasi tentang data dan urusan peta ditangani oleh Google, sehingga dapat menghemat waktu. Agar peta dapat ditampilkan ke dalam website , maka diharuskan mempunyai account Google, kemudian mendaftarkan diri dahulu di http://code.google.com/apis/maps/signup.html. Hal ini bertujuan untuk mendapatkan Google Maps API key. 3. Metodologi Pada bab ini akan dijelaskan hal-hal yang berkaitan dengan perancangan sistem yang akan dibuat yang akan dibuat dalam Tugas Akhir ini, 3
Satria Prasamya - 5106100030
SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
dimulai dari deskripsi umum mengenai perangkat lunak yang akan dibuat, perancangan prosesproses yang ada, dan alur proses 3.1 Arsitektur Sistem Pada sistem aplikasi ini, tidak hanya melibatkan 1 perangkat mobile Android, melainkan juga berinteraksi dengan server google map selaku penyedia googlemap API dan juga server khusus sebagai penyedia script yang akan dijalankan pada aplikasi ini
juga script yang akan digunakan untuk mengimplementasikan algoritma ant colony dan juga script untuk menjalankan fungsi-fungsi dari Google Map API. 4. Implementasi Sistem Aplikasi mobile pada sistem ini dibangun dengan bahasa java dalam framework Android. Aplikasi ini berguna hanya sebagai frame yang menampilkan aplikasi web based. Berikut potongan pseudo code : /* webView initialitation */ setupWebView() /* Set Javascript enable on webView */ webView.setJavascriptEnable := true /* Web View Request to URL */ webView.loadURL := MAP_URL /* Get Location From GPS */ location := getSystemLocation() /* view map location from current location */ webView.loadURL(“javascript:setCenter(location.lat, location.lng, 10)”);
Gambar3.2 Fungsi frame yang menampilkan aplikasi web pada Android
Berikut ini pengambilan data cost dari google :
Gambar 3.1 Arsitektur Sistem
Alur dari arsitektur pada Gambar 3.1 yaitu aplikasi pada Android memberikan request ke server aplikasi untuk mendapatkan script yang akan dijalankan di perangkat mobile Android. Setelah script aplikasi ter-download maka aplikasi siap dijalankan. Ketika aplikasi sudah dijalankan yang bekerja hanya perangkat mobile Android dan Google Map Server melalui googlemap API yang telah disediakan oleh Google.Googlemap API bertugas dalam menyediakan data peta (map) beserta data-data penunjang lain seperti koordinat suatu node, jarak antar node, nama jalan dan sebagainya. Sedangkan perangkan mobile Android bertugas mengolah data yang diambil dari googlemap untuk diproses dalam algoritma ant colony optimization dan untuk menampilkan hasilnya dalam bentuk peta, menggunakan bantuan googlemap API lagi sehingga dapat dilihat oleh user. 3.2. Arsitektur Perangkat Lunak Pada sistem ini aplikasi terbagi 2 bagian utama, yaitu aplikasi mobile (starter) dan aplikasi web (html + javascript). Aplikasi starter akan memanggil aplikasi web sesuai URL yang sudah ditentukan. Aplikasi starter hanya seperti sebuah frame yang menampilkan aplikasi web. Pada aplikasi web terdapat gambar peta, tombol-tombol dan konfigurasi untuk menjalankan aplikasi ini. Selain user interface , pada aplikasi web terdapat
Set nextAbove := -1 Set index := currInd For i:=curr + 1 to length(waypoints) do Set index := index + 1 If nextAbove = -1 then Set nextAbove := i Else My_cost[currInd][index]:= cost[distIndex++] My_cost[index][currInd]:= cost[distIndex++] End-if End-for If nextAbove != -1 then My_cost[currInd][currInd+1]:=cost[distIndex++ ] getWayStr(nextBove) My_cost[currInd+1][currInd]:=cost[distIndex++ ]
Gambar3.3 Pengambilan data cost
4.1 Implementasi Algoritma Ant Colony Setelah data table cost (array 2 dimensional) siap, data tersebut diolah dalam algoritma Ant Colony agar diperoleh bestPath yang akan digunakan sebagai pedoman jalur terpendek dalam Traveling Salesmen Problem. Berikut potongan pseudocode procedure ACO algorithm for TSPs while (termination condition not met) do ConstructAntSolutions UpdatePheromones Endwhile End procedure ACO ALgortihm fot TSPs
Gambar3.4 Pseudocode Ant Colony
Setelah data cost diolah di algoritma ant colony maka akan didapatkan bestPath,untuk menampilkannya : Set wayStr is array 1 dimensional For i:=0 to length(bestPath) do wayStr.push(waypoints[bestPath[i]]); End-for googleDirectionAPI.loadFromWayPoints(wayStr, avoid_highways, travel_mode)
Gambar3.5 Menampilkan hasil Ant Colony pada peta
4
Satria Prasamya - 5106100030
SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
5.
Ujicoba dan Evaluasi Pada bagian ini akan dibahas mengenai uji coba dan evaluasi perangkat lunak. Pembahasan meliputi uji coba, penjelasan mengenai skenario pengujian dan hasil uji coba. Perangkat lunak ini diuji coba dari segi fungsionalitas dan performa ketika dijalankan
5.1.2 Fungsi Fitur Roundtrip Selain fitur one way trip, terdapat juga fitur roundtrip yang dapat digunakan oleh user. Fitur roundtrip ini merupakan implementasi dari TSP. Dibawah ini ujicoba fitur roundtrip dengan menggunakan inputan lokasi yang sama dengan fitur one way trip. Berikut ini Gambar hasil ujicoba fitur roundtrip :
5.1. Uji Coba Fungsionalitas Uji coba ini dilakukan untuk melihat apakah fungsi-fungsi dasar dari perangkat lunak ini berjalan sebagaimana mestinya atau tidak 5.1.1.
Fungsi Fitur One Way Trip Setelah node lokasi yang ingin dituju telah diinputkan pada layar maka user dapat memilih fitur pencarian. Fitur one way trip akan mencari rute terpendek dimana lokasi yang pertama diinputkan adalah lokasi awal dan lokasi terakhir menjadi lokasi tujuan. Ujicoba dilakukan dengan 3 node. Hasilnya sebagai berikut : Gambar 5.3 Fitur roundtrip dan directions
Sama halnya dengan fitur one way trip, fitur roundtrip juga dapat dilakukan by walking. Berikut ujicoba fitur roundtrip by walking:
Gambar 5.1 Fitur Oneway trip dan directions
Selain itu fitur ini bisa ditempuh dengan jalan (by walking). Hasilnya sebagai berikut:
Gambar5.4 Fitur round trip by walking dan directions
Gambar diatas menunjukkan sama halnya dengan fitur walking di one way trip, fitur walking dengan roundtrip mempunyai total jarak yang lebih sedikit dibandingkan by driving 5.2. Ujicoba Performa Ujicoba ini untuk melihat kecepatan aplikasi dalam menampilkan rute terhadap inputan lokasi : Gambar5.2 Fitur Oneway trip by walking dan directions
Dari Gambar diatas dapat dilihat jarak tempuh total dan rute yang ditempuh dari fitur one way trip by walking lebih kecil dibandingkan fitur one way trip by driving hal ini disebabkan berbedanya akses jalan yang dapat ditempuh oleh keduanya.
Tabel 5.1 Ujicoba Performa One Way Trip One Way Trip NO
Jumlah Lokasi 2 4 6 8 10 12 14
1 2 3 4 5 6 7
5
t (s) 6.34 10.57 15.80 21.91 28.62 38.09 57.94
Satria Prasamya - 5106100030
SEMINAR TUGAS AKHIR PERIODE JANUARI 2011
Tabel 5.2 Ujicoba Performa Round Trip
[7]
Round trip NO
Jumlah Lokasi 2 4 6 8 10 12 14
1 2 3 4 5 6 7
t (s) 6.03 10.23 16.80 22.91 29.62 40.09 57.08
[8]
Dari data hasil ujicoba table 5.1 dan 5.2 diatas diatas dapat dilihat bahwa kecepatan aplikasi ant22 dalam menampilkan rute terpendek pada fitur one way trip maupun roundtrip tergantung dari jumlah inputan kota yang dimasukkan. Semakin banyak kota yang diinputkan maka proses dalam mengolah dan menampilkan rute terpendek akan semakin lama. 6. Kesimpulan Dari hasil pengamatan selama perancangan dan implementasi perangkat lunak dapat diambil kesimpulan sebagai berikut : 1. Sistem yang dibuat mampu memenuhi tujuan awal pembuatan aplikasi yaitu mampu menampilkan rute terpendek dari inputan beberapa lokasi baik secara roundtrip maupun one way trip. 2. Perangkat lunak ini dapat berjalan pada mobile system android dan mendukung koneksi 3G. 3. Kecepatan menampilkan suatu rute pada map tergantung pada jumlah kota yang diinputkan, provider dan kestabilan koneksi internet. 4. Berdasarkan uji coba, semakin kecil jumlah kota yang dimasukkan maka semakin cepat aplikasi menampilkan rute terpendek pada map. 7.
Mutakhiroh, I., Saptono, F., Hasanah, N., dan Wiryadinata, R,. (2007). Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Denga Algoritma Semut Dan Algoritma Genetika. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 19075022. Yogyakarta Saputra, Bhagas Arga(2010). Implementasi Google Translate API pada Mobile Phone Menggunakan J2ME. Surabaya
Daftar Pustaka [1]
[2]
[3]
[4]
[5]
[6]
http://code.google.com/apis/maps/docu mentation/javascript/v2/reference.html tentang Google Map API Ibnu Sina Wardy, Penggunaan Graf dalam Algoritma Semut untuk Melakukan Optimisasi, ITB Bandung J. Wilson, Robin and J. Watkins, John (1992), GRAPH. University Press IKIP Surabaya. Kapov, Nina Skorin.2010.Heuristic Optimization Methods: Ant Colony Optimization. M. Dorigo dan L.M. Gambardella (1997), Ant Colony for the Travelling Salesman Problem, Cambridge, Massachussets. London, England Mulyadi (2010), Membuat Aplikasi Android. Yogyakarta
6
Satria Prasamya - 5106100030
