Abstrak
Salah satu permasalahan utama 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 pencarian metode alternatif masih penting dilakukan. Penelitian ini menggunakan pendekatan metode optimasi metaheuristik koloni semut yang terinspirasi dari prilaku alamiah semut, untuk mencari jalur terpendek antara dua titik, pada data jaringan jalan riil (JJR). Pengujian terhadap metode ant colony optimization (ACO) dilakukan dalam dua tahap. Pertama, pengujian menggunakan data buatan untuk mendapatkan gambaran pengaturan terbaik dari parameter-parameter metode koloni semut. Kedua, pengujian menggunakan data JJR untuk melihat kinerja metode optimasi koloni semut terhadap data JJR. Hasil pengujian optimasi koloni semut pada data JJR kemudian dibandingkan dengan hasil pengujian algoritme jalur terpendek Dijkstra pada JJR dalam hal panjang jalur optimal dan waktu eksekusi. Hasil pengujian menunjukan bahwa secara secara umum metode Dijkstra menghasilkan solusi yang lebih baik dari metode ACO namun pada pengaturan parameter tertentu ACO lebih cepat dari Dijkstra.
Kata Kunci: algoritme Dijkstra, analisis jaringan, jaringan jalan riil, optimasi koloni semut, permasalahan jalur terpendek
Pendahuluan
Analisis jaringan merupakan salah satu analisis kunci dalam sistem informasi geografis yang diaplikasikan dalam berbagai kebutuhan seperti jaringan telekomunikasi, transportasi, penjadwalan, manajemen proyek, navigasi, perencanaan, pengiriman barang, dan lain-lain. Jaringan adalah suatu sistem dari fitur linear dimana terdapat atribut-atribut yang digunakan untuk menyatakan aliran suatu objek berbasis topologi yang terdiri atas garis dan pertemuan antargaris yaitu simpul, dimana garis tersebut memiliki arah (Curtin 2007; Chang 2008). Analisis jaringan bertumpu pada subdisiplin matematika yakni teori graf. Jaringan didefinisikan sebagai sebuah graf berarah, G = (V, E) yang terdiri atas sebuah himpunan simpul dan sebuah himpunan sisi di mana jumlah simpul n = |V| dan jumlah sisi m = |E|, di mana setiap sisi memiliki bobot yang menyatakan ukuran berat, panjang, atau satuan lain sesuai dengan aplikasinya. Analisis jaringan merupakan salah satu area riset yang signifikan dan terus dilakukan dalam ilmu pengetahuan geografis (Curtin 2007). Di antara berbagai analisis jaringan terdapat suatu permasalahan kunci yang disebut permasalahan jalur terpendek yaitu mencari jalur kumulatif minimum pada jaringan (Zhan dan Noon 1998; Zeng dan Church 2008; Leng dan Zeng 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 pada pemanfaatannya digunakan untuk berbagai aplikasi seperti perencanaan lokasi fasilitas (Horner dan Grubesic 2001), analisis konsumen potensial (Farhan dan Murray 2005), serta perencanaan rute pengiriman barang dan layanan darurat yang menghubungkan fasilitas-fasilitas penting (Chang 2008).
Untuk lebih lengkapnya silahkan download di link berikut ini :
Post a Comment
Post a Comment