jurnal - aplikasi pencari rute optimum menggunakan algoritma semut di kampus usu dengan dukungan...

6
Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus Universitas Sumatera Utara Dengan Dukungan Sistem Informasi Geografis Friendly Purba, Syahril Efendy, M. Andri Budiman Program Studi S-1 Ilmu Komputer, Universitas Sumatera Utara Jl. Universitas N0. 24-A, Kampus USU, Medan, Indonesia e-mail: [email protected] email: [email protected] email: [email protected] Abstrak −− Pencarian rute terpendek secara umum dapat dibagi menjadi dua metode yaitu metode konvensional dan metode heuristik. Metode heuristik lebih cocok digunakan daripada metode konvensional dalam mencari rute terpendek dengan data yang besar. Metode heuristik yang sering digunakan dalam penentuan rute terpendek adalah algoritma semut. Algoritma Semut ini diadopsi dari perilaku alami semut dimana dengan Algoritma Semut ini pencarian rute terpendek menjadi lebih singkat walaupun menggunakan data yang banyak. Setelah dilakukan pengujian kepada setiap parameter algoritma semut, diperoleh bahwa parameter banyak semut dan siklus mempengaruhi probalitas dalam pencarian titik tujuan dan waktu eksekusi pencarian, parameter τ ij , q 0 dan α mempengaruhi probabilitas dalam pencarian titik tujuan, sedangkan parameter β dan ρ berpengaruh dalam waktu eksekusi pencarian rute optimum. Aplikasi pencari rute optimum yang mengimplementasikan Algoritma Semut ini dibangun dengan menggunakan perangkat lunak Sistem Informasi Geografis MapWindow dan Delphi 2009, diharapkan mampu memberikan informasi yang cukup berguna bagi pengguna jalan di Universitas Sumatera Utara. Keyword −− Graph, Shortest Path, Ant Algorithm, Optimization, Geofraphic Information System. 1. PENDAHULUAN Kampus Universitas Sumatera Utara berlokasi di tengah kota Medan tepatnya di Kelurahan Padang Bulan, Kecamatan Medan Baru. Dengan luas 122 ha dan mahasiswa yang berjumlah 33.000 orang, pencarian rute terpendek akan sangat diperlukan bagi pengguna jalan yang tidak tahu jalan mana yang akan dilalui agar sampai ke tempat tujuannya di areal kampus Universitas Sumatera Utara, apalagi bagi pengguna jalan yang baru pertama kali mengunjungi kampus Universitas Sumatera Utara. Pencarian rute terpendek terbagi menjadi dua metode yaitu metode konvensional dan metode heuristik. Metode konvensional cenderung lebih mudah dipahami daripada metode heuristik, tetapi jika dibandingkan, hasil yang diperoleh dari metode heuristik lebih variatif dan waktu perhitungan yang diperlukan lebih singkat. Salah satu metode heuristik yang sering digunakan adalah Algoritma Semut (Ant Algorithm). 2. ALGORITMA SEMUT Algoritma Semut merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan rute terpendek dari suatu graf. Dalam mencari rute terpendek dalam algoritma semut, ‘semut-semut tiruan’ akan bertindak seperti agen, dimana setiap semut memiliki rute masing- masing dari titik awal menuju titik tujuan dengan tidak mengunjungi suatu titik lebih dari satu kali untuk mendapatkan hasil terbaik. Proses mencari rute optimal tersebut tidak semudah yang kita bayangkan dan tentu saja memerlukan rumus yang pada intinya menerapkan suatu fungsi heuristik yang cukup rumit. [1]. Parameter-parameter algoritma semut adalah sebagai berikut: a. Intensitas feromon (τ ij ). b. Tetapan siklus semut (q 0 ). c. Tetapan pengendali intensitas visibilitas ), nilai β ≥ 0. d. Tetapan pengendali feromon ), nilai α ≥ 0. e. Jumlah semut (m). f. Tetapan penguapan feromon (ρ), nilai ρ harus > 0 dan < 1. g. Jumlah siklus maksimum (NC max ).

Upload: friendlye-faucet-purba

Post on 28-Jul-2015

492 views

Category:

Documents


4 download

TRANSCRIPT

Page 1: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

Aplikasi Pencari Rute Optimum MenggunakanAlgoritma Semut Di Kampus Universitas

Sumatera Utara Dengan DukunganSistem Informasi Geografis

Friendly Purba, Syahril Efendy, M. Andri BudimanProgram Studi S-1 Ilmu Komputer, Universitas Sumatera Utara

Jl. Universitas N0. 24-A, Kampus USU, Medan, Indonesiae-mail: [email protected]

email: [email protected]: [email protected]

Abstrak −− Pencarian rute terpendek secara umum dapat dibagimenjadi dua metode yaitu metode konvensional dan metodeheuristik. Metode heuristik lebih cocok digunakan daripadametode konvensional dalam mencari rute terpendek dengan datayang besar. Metode heuristik yang sering digunakan dalampenentuan rute terpendek adalah algoritma semut. AlgoritmaSemut ini diadopsi dari perilaku alami semut dimana denganAlgoritma Semut ini pencarian rute terpendek menjadi lebihsingkat walaupun menggunakan data yang banyak. Setelahdilakukan pengujian kepada setiap parameter algoritma semut,diperoleh bahwa parameter banyak semut dan siklusmempengaruhi probalitas dalam pencarian titik tujuan danwaktu eksekusi pencarian, parameter τij, q0 dan α mempengaruhiprobabilitas dalam pencarian titik tujuan, sedangkan parameterβ dan ρ berpengaruh dalam waktu eksekusi pencarian ruteoptimum. Aplikasi pencari rute optimum yangmengimplementasikan Algoritma Semut ini dibangun denganmenggunakan perangkat lunak Sistem Informasi GeografisMapWindow dan Delphi 2009, diharapkan mampu memberikaninformasi yang cukup berguna bagi pengguna jalan diUniversitas Sumatera Utara.

Keyword −− Graph, Shortest Path, Ant Algorithm, Optimization,Geofraphic Information System.

1. PENDAHULUAN

Kampus Universitas Sumatera Utara berlokasi di tengahkota Medan tepatnya di Kelurahan Padang Bulan, KecamatanMedan Baru. Dengan luas 122 ha dan mahasiswa yangberjumlah 33.000 orang, pencarian rute terpendek akan sangatdiperlukan bagi pengguna jalan yang tidak tahu jalan manayang akan dilalui agar sampai ke tempat tujuannya di arealkampus Universitas Sumatera Utara, apalagi bagi penggunajalan yang baru pertama kali mengunjungi kampus UniversitasSumatera Utara.

Pencarian rute terpendek terbagi menjadi dua metode yaitumetode konvensional dan metode heuristik. Metodekonvensional cenderung lebih mudah dipahami daripadametode heuristik, tetapi jika dibandingkan, hasil yangdiperoleh dari metode heuristik lebih variatif dan waktu

perhitungan yang diperlukan lebih singkat. Salah satu metodeheuristik yang sering digunakan adalah Algoritma Semut (AntAlgorithm).

2. ALGORITMA SEMUT

Algoritma Semut merupakan teknik probabilistik untukmenyelesaikan masalah komputasi dengan menemukan ruteterpendek dari suatu graf. Dalam mencari rute terpendekdalam algoritma semut, ‘semut-semut tiruan’ akan bertindakseperti agen, dimana setiap semut memiliki rute masing-masing dari titik awal menuju titik tujuan dengan tidakmengunjungi suatu titik lebih dari satu kali untukmendapatkan hasil terbaik. Proses mencari rute optimaltersebut tidak semudah yang kita bayangkan dan tentu sajamemerlukan rumus yang pada intinya menerapkan suatufungsi heuristik yang cukup rumit. [1].

Parameter-parameter algoritma semut adalah sebagaiberikut:a. Intensitas feromon (τij).b. Tetapan siklus semut (q0).c. Tetapan pengendali intensitas visibilitas (β), nilai β ≥ 0.d. Tetapan pengendali feromon (α), nilai α ≥ 0.e. Jumlah semut (m).f. Tetapan penguapan feromon (ρ), nilai ρ harus > 0

dan < 1.g. Jumlah siklus maksimum (NCmax).

Page 2: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

A. Karakteristik Algoritma Semut1) Aturan Transisi StatusAturan transisi status adalah aturan yang digunakan dalam

memilih titik tujuan berikutnya dengan melakukanperhitungan probabilitas masing-masing titik tujuan yangmungkin. Aturan transisi status yang berlaku pada AlgoritmaSemut adalah sebagai berikut:

Seekor semut yang ditempatkan pada titik t memilih untukmenuju ke titik v, kemudian dibangkitkan bilangan acakdimana 0≤q≤1, q sebuah parameter yaitu probabilitas semutmelakukan eksplorasi pada setiap tahapan, dimana (0≤q0≤1)dan pk (t,v) adalah probabilitas dimana semut k memilih untukbergerak dari titik t ke titik v.

Jika q ≤ q0 maka pemilihan titik yang akan ditujumenerapkan aturan yang ditunjukkan oleh persamaan (1)dibawah ini:

niutututtem p o ra ry ii ,...,3,2,1),(.),(),( ,

),(.),(m a x ii ututv dengan v = titik yang akan dituju.Sedangkan jika q>q0 digunakan persamaan (2) berikut ini,

n

iii

iik

utut

vtvtvtpv

1),(.),(

),(.),(),(

Setelah hasil perhitungan probabilitas semut yang akandipilih berikutnya selesai, kemudian dicari probabilitaskumulatifnya (qk) dimana q1 = pi1 sedangkan qk = qk-1 + pijuntuk k = 2,3,4, ..., n. Kemudian dibangkitkan bilanganrandom (r) antara 0 sampai 1. Titik ke-k akan terpilih jikaqk-1 < r ≤ qk.

2) Aturan Pembaruan Feromon LokalSelagi melakukan perjalanan untuk mencari solusi

pencarian rute terpendek, semut mengunjungi sisi-sisi danmengubah tingkat feromon pada sisi-sisi tersebut denganmenerapkan aturan pembaruan feromon lokal yangditunjukkan oleh persamaan (3) dibawah ini.

),(),(.1),( vtvtvt

cLvt

n n .1),(

dimana:Lnn : panjang rute yang diperoleh..c : jumlah titik yang sudah dijalani.ρ : tetapan penguapan feromon.Δτ : perubahan intensitas feromon.

3) Aturan Pembaruan Feromon Global

Pembaruan feromon secara global hanya dilakukan olehsemut yang membuat rute terpendek sejak permulaanpercobaan. Pada akhir sebuah siklus, setelah semua semutmenyelesaikan perjalanan mereka, intensitas feromondiperbaharui pada sisi-sisi yang dilewati oleh seekor semutyang telah menemukan rute optimum. Tingkat feromon itudiperbarui dengan menerapkan aturan pembaruan feromonglobal yang ditunjukkan oleh persamaan (4) dibawah ini.

),(.),(.1),( vtvtvt

0

),(),(

1 terbaikrutevtjikaLvt gb

dimana:τ(t,v) : nilai feromon akhir setelah mengalami pembaruan

lokal.Lgb : panjang rute terpendek pada akhir siklus.α : tetapan pengendali feromon.∆τ : perubahan intensitas feromon. [2].

B. Pseudocode Algoritma Semut

Dari analisis diatas, dapat dibuat pseudocode algoritmasemut yaitu:

Dari analisa terhadap Algoritma Semut ini, beberapa halyang penting adalah:1. Dalam pemilihan titik berdasarkan persamaan probabilitas

diperlukan nilai parameter q dan r yang merupakan sebuahbilangan acak dimana 0 ≤ q ≤ 1 dan 0 ≤ r ≤ 1.

2. Setiap semut harus memiliki daftar_kota untuk menyimpanhasil perjalanannya masing-masing. Daftar_kota berisikumpulan sisi yang merupakan bagian dari rute perjalanansetiap semut. Nilai dari masing-masing daftar_kota akandikosongkan kembali setiap kali semut akan memulairutenya (siklus baru).

3. Proses pembaruan intensitas feromon dipengaruhi oleh duaparameter yaitu ρ dan α ( keduanya bernilai antara 0sampai 1) dan ∆τ (didapat dari satu per hasil perkalianpanjang rute yang ditempuh dengan jumlah verteks yangada pada graf tersebut). [2].

A. Karakteristik Algoritma Semut1) Aturan Transisi StatusAturan transisi status adalah aturan yang digunakan dalam

memilih titik tujuan berikutnya dengan melakukanperhitungan probabilitas masing-masing titik tujuan yangmungkin. Aturan transisi status yang berlaku pada AlgoritmaSemut adalah sebagai berikut:

Seekor semut yang ditempatkan pada titik t memilih untukmenuju ke titik v, kemudian dibangkitkan bilangan acakdimana 0≤q≤1, q sebuah parameter yaitu probabilitas semutmelakukan eksplorasi pada setiap tahapan, dimana (0≤q0≤1)dan pk (t,v) adalah probabilitas dimana semut k memilih untukbergerak dari titik t ke titik v.

Jika q ≤ q0 maka pemilihan titik yang akan ditujumenerapkan aturan yang ditunjukkan oleh persamaan (1)dibawah ini:

niutututtem p o ra ry ii ,...,3,2,1),(.),(),( ,

),(.),(m a x ii ututv dengan v = titik yang akan dituju.Sedangkan jika q>q0 digunakan persamaan (2) berikut ini,

n

iii

iik

utut

vtvtvtpv

1),(.),(

),(.),(),(

Setelah hasil perhitungan probabilitas semut yang akandipilih berikutnya selesai, kemudian dicari probabilitaskumulatifnya (qk) dimana q1 = pi1 sedangkan qk = qk-1 + pijuntuk k = 2,3,4, ..., n. Kemudian dibangkitkan bilanganrandom (r) antara 0 sampai 1. Titik ke-k akan terpilih jikaqk-1 < r ≤ qk.

2) Aturan Pembaruan Feromon LokalSelagi melakukan perjalanan untuk mencari solusi

pencarian rute terpendek, semut mengunjungi sisi-sisi danmengubah tingkat feromon pada sisi-sisi tersebut denganmenerapkan aturan pembaruan feromon lokal yangditunjukkan oleh persamaan (3) dibawah ini.

),(),(.1),( vtvtvt

cLvt

n n .1),(

dimana:Lnn : panjang rute yang diperoleh..c : jumlah titik yang sudah dijalani.ρ : tetapan penguapan feromon.Δτ : perubahan intensitas feromon.

3) Aturan Pembaruan Feromon Global

Pembaruan feromon secara global hanya dilakukan olehsemut yang membuat rute terpendek sejak permulaanpercobaan. Pada akhir sebuah siklus, setelah semua semutmenyelesaikan perjalanan mereka, intensitas feromondiperbaharui pada sisi-sisi yang dilewati oleh seekor semutyang telah menemukan rute optimum. Tingkat feromon itudiperbarui dengan menerapkan aturan pembaruan feromonglobal yang ditunjukkan oleh persamaan (4) dibawah ini.

),(.),(.1),( vtvtvt

0

),(),(

1 terbaikrutevtjikaLvt gb

dimana:τ(t,v) : nilai feromon akhir setelah mengalami pembaruan

lokal.Lgb : panjang rute terpendek pada akhir siklus.α : tetapan pengendali feromon.∆τ : perubahan intensitas feromon. [2].

B. Pseudocode Algoritma Semut

Dari analisis diatas, dapat dibuat pseudocode algoritmasemut yaitu:

Dari analisa terhadap Algoritma Semut ini, beberapa halyang penting adalah:1. Dalam pemilihan titik berdasarkan persamaan probabilitas

diperlukan nilai parameter q dan r yang merupakan sebuahbilangan acak dimana 0 ≤ q ≤ 1 dan 0 ≤ r ≤ 1.

2. Setiap semut harus memiliki daftar_kota untuk menyimpanhasil perjalanannya masing-masing. Daftar_kota berisikumpulan sisi yang merupakan bagian dari rute perjalanansetiap semut. Nilai dari masing-masing daftar_kota akandikosongkan kembali setiap kali semut akan memulairutenya (siklus baru).

3. Proses pembaruan intensitas feromon dipengaruhi oleh duaparameter yaitu ρ dan α ( keduanya bernilai antara 0sampai 1) dan ∆τ (didapat dari satu per hasil perkalianpanjang rute yang ditempuh dengan jumlah verteks yangada pada graf tersebut). [2].

A. Karakteristik Algoritma Semut1) Aturan Transisi StatusAturan transisi status adalah aturan yang digunakan dalam

memilih titik tujuan berikutnya dengan melakukanperhitungan probabilitas masing-masing titik tujuan yangmungkin. Aturan transisi status yang berlaku pada AlgoritmaSemut adalah sebagai berikut:

Seekor semut yang ditempatkan pada titik t memilih untukmenuju ke titik v, kemudian dibangkitkan bilangan acakdimana 0≤q≤1, q sebuah parameter yaitu probabilitas semutmelakukan eksplorasi pada setiap tahapan, dimana (0≤q0≤1)dan pk (t,v) adalah probabilitas dimana semut k memilih untukbergerak dari titik t ke titik v.

Jika q ≤ q0 maka pemilihan titik yang akan ditujumenerapkan aturan yang ditunjukkan oleh persamaan (1)dibawah ini:

niutututtem p o ra ry ii ,...,3,2,1),(.),(),( ,

),(.),(m a x ii ututv dengan v = titik yang akan dituju.Sedangkan jika q>q0 digunakan persamaan (2) berikut ini,

n

iii

iik

utut

vtvtvtpv

1),(.),(

),(.),(),(

Setelah hasil perhitungan probabilitas semut yang akandipilih berikutnya selesai, kemudian dicari probabilitaskumulatifnya (qk) dimana q1 = pi1 sedangkan qk = qk-1 + pijuntuk k = 2,3,4, ..., n. Kemudian dibangkitkan bilanganrandom (r) antara 0 sampai 1. Titik ke-k akan terpilih jikaqk-1 < r ≤ qk.

2) Aturan Pembaruan Feromon LokalSelagi melakukan perjalanan untuk mencari solusi

pencarian rute terpendek, semut mengunjungi sisi-sisi danmengubah tingkat feromon pada sisi-sisi tersebut denganmenerapkan aturan pembaruan feromon lokal yangditunjukkan oleh persamaan (3) dibawah ini.

),(),(.1),( vtvtvt

cLvt

n n .1),(

dimana:Lnn : panjang rute yang diperoleh..c : jumlah titik yang sudah dijalani.ρ : tetapan penguapan feromon.Δτ : perubahan intensitas feromon.

3) Aturan Pembaruan Feromon Global

Pembaruan feromon secara global hanya dilakukan olehsemut yang membuat rute terpendek sejak permulaanpercobaan. Pada akhir sebuah siklus, setelah semua semutmenyelesaikan perjalanan mereka, intensitas feromondiperbaharui pada sisi-sisi yang dilewati oleh seekor semutyang telah menemukan rute optimum. Tingkat feromon itudiperbarui dengan menerapkan aturan pembaruan feromonglobal yang ditunjukkan oleh persamaan (4) dibawah ini.

),(.),(.1),( vtvtvt

0

),(),(

1 terbaikrutevtjikaLvt gb

dimana:τ(t,v) : nilai feromon akhir setelah mengalami pembaruan

lokal.Lgb : panjang rute terpendek pada akhir siklus.α : tetapan pengendali feromon.∆τ : perubahan intensitas feromon. [2].

B. Pseudocode Algoritma Semut

Dari analisis diatas, dapat dibuat pseudocode algoritmasemut yaitu:

Dari analisa terhadap Algoritma Semut ini, beberapa halyang penting adalah:1. Dalam pemilihan titik berdasarkan persamaan probabilitas

diperlukan nilai parameter q dan r yang merupakan sebuahbilangan acak dimana 0 ≤ q ≤ 1 dan 0 ≤ r ≤ 1.

2. Setiap semut harus memiliki daftar_kota untuk menyimpanhasil perjalanannya masing-masing. Daftar_kota berisikumpulan sisi yang merupakan bagian dari rute perjalanansetiap semut. Nilai dari masing-masing daftar_kota akandikosongkan kembali setiap kali semut akan memulairutenya (siklus baru).

3. Proses pembaruan intensitas feromon dipengaruhi oleh duaparameter yaitu ρ dan α ( keduanya bernilai antara 0sampai 1) dan ∆τ (didapat dari satu per hasil perkalianpanjang rute yang ditempuh dengan jumlah verteks yangada pada graf tersebut). [2].

Page 3: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

3. SISTEM INFORMASI GEOGRAFISSistem Informasi Geografis (SIG) merupakan sistem

infomasi berbasis komputer yang menggabungkan antaraunsur peta (geografis) dan informasi tentang peta tersebut(data atribut) yang dirancang untuk mendapatkan, mengolah,memanipulasi, analisa, memperagakan dan menampilkan dataspatial untuk menyelesaikan perencanaan, mengolah danmeneliti permasalahan.

Salah satu alasan mengapa konsep-konsep SIG besertasistem aplikasinya menjadi menarik untuk digunakan diberbagai disiplin ilmu karena SIG dapat menurunkaninformasi secara otomatis tanpa keharusan untuk selalumelakukan interpretasi secara manual.

1) MapWindow GISMapWindow adalah Programmable Geographic

Information System yang mendukung manipulasi, analisis, danmelihat data geospasial dan data atribut terkait dalambeberapa standar data format SIG. MapWindowdikembangkan oleh Prof. Daniel P Ames, dan Jeff Horsbaughdari Utah State University (USU). MapWindow merupakanalat pemetaan, sistem pemodelan SIG, dan aplikasi SIGprogramming interface (API) yang semuanya dikemas dalamsatu paket. MapWindow dikembangkan untuk mengatasikebutuhan pemrograman SIG yang dapat digunakan dalamrekayasa penelitian dan proyek perangkat lunak tanpamembeli sistem SIG yang lengkap atau tanpa menjadi ahliSIG sebelumnya.

MapWindow GIS merupakan sofware aplikasi berlabelfree, salah satu perangkat lunak untuk Sistem InformasiGeografis (SIG) yang berbasis open source. MapWindowbersifat free baik dalam hal lisensi pemakaian maupunpengembangannya. MapWindow dapat digunakan untukberbagai keperluan, misalnya:

1. Sebagai alternatif desktop SIG yang open source.2. Untuk mengkonversi data ke bentuk lain.3. Untuk mengembangkan dan mendistribusikan alat yang

berkaitan dengan analisis data spasial.4. Melakukan task sebagaimana perangkat lunak SIG

lainnya.[3].

4. PEMBAHASANPersoalan pencarian terpendek merupakan salah satu

permasalahan optimasi. Graf yang digunakan dalam pencarianrute terpendek ini adalah graf berbobot. Bobot pada sisi grafmenyatakan jarak antar verteks. Dalam hal ini bobot harusbernilai positif. Rute terpendek dengan verteks awal t danverteks tujuan v didefenisikan sebagai rute terpendek dari t kev dengan bobot minimum dan berupa rute sederhana (simplepath).

Supaya dapat melakukan pencarian rute terpendek, petakampus Universitas Sumatera Utara direpresentasikanmenjadi sebuah graf dimana gedung atau persimpangan jalansebagai verteks (node) dan jalan dengan panjang tertentusebagai sisi (edge) pada graf.

Peta Universitas Sumatera Utara yang berformat *.jpgterlebih dahulu digitasi menggunakan Aplikasi Sistem

Informasi Geografis berbasis dekstop yaitu MapWindow GIS.Peta Kampus Universitas Sumatera Utara yang sudah didigitasi terdiri dari enam layer dalam format *.shp yaituarea.shp, verteks.shp, office.shp, road.shp, road_name.shp,dan edge_and_distance.shp. Keenam layer inilah nantinyaakan membentuk peta Kampus Universitas Sumatera Utaradalam aplikasi yang akan dibangun.

Meskipun demikian, layer-layer dalam format *.shp inibelum langsung dapat ditampilkan pada Delphi 2009 karenaDelphi 2009 belum mendukung data dalam format *.shp. Olehkarena itu diperlukan komponen tambahan yaitu MapWinGISActiveX. Komponen MapWinGIS ActiveX ini adalah objekpemrograman untuk membentuk dan menyediakan built-indata peta *.shp dalam Delphi 2009.

Adapun database yang digunakan dalam sistem ini adalahmysql yang sebelumnya diubah dari format *.dbfmenggunakan aplikasi Kettle yang dibuat oleh Pentaho.Database ini berisi id_jalan, verteks1, verteks2,panjang_jalan, dan koordinat_verteks.

Kode yang digunakan untuk menampilkan peta dalamDelphi 2009 adalah sebagai berikut:

Barisan kode ini hanya kode untuk menampilkan layerroad.shp pada peta kampus Universitas Sumatera Utara yangdiperoleh dari direktori yang telah ditentukan(D:\\MAPWINDOW). Jika direktori yang dimaksud ternyatatidak ditemukan, maka peta road.shp tidak dapat ditampilkan.Kode ini juga dapat digunakan untuk menampilkan kelimalayer yang lainnya dengan mengganti masing-masing namalayer sehingga akan diperoleh peta Universitas SumateraUtara yang lengkap.

5. PENGUJIANNilai dari setiap parameter semut yang digunakan dalam

pembahasan ini adalah:titik awal = t35titk tujuan = t15τij = 0,01q0 = 0α = 0,5β = 1.m = 10ρ = 0,01NCmax = 5

3. SISTEM INFORMASI GEOGRAFISSistem Informasi Geografis (SIG) merupakan sistem

infomasi berbasis komputer yang menggabungkan antaraunsur peta (geografis) dan informasi tentang peta tersebut(data atribut) yang dirancang untuk mendapatkan, mengolah,memanipulasi, analisa, memperagakan dan menampilkan dataspatial untuk menyelesaikan perencanaan, mengolah danmeneliti permasalahan.

Salah satu alasan mengapa konsep-konsep SIG besertasistem aplikasinya menjadi menarik untuk digunakan diberbagai disiplin ilmu karena SIG dapat menurunkaninformasi secara otomatis tanpa keharusan untuk selalumelakukan interpretasi secara manual.

1) MapWindow GISMapWindow adalah Programmable Geographic

Information System yang mendukung manipulasi, analisis, danmelihat data geospasial dan data atribut terkait dalambeberapa standar data format SIG. MapWindowdikembangkan oleh Prof. Daniel P Ames, dan Jeff Horsbaughdari Utah State University (USU). MapWindow merupakanalat pemetaan, sistem pemodelan SIG, dan aplikasi SIGprogramming interface (API) yang semuanya dikemas dalamsatu paket. MapWindow dikembangkan untuk mengatasikebutuhan pemrograman SIG yang dapat digunakan dalamrekayasa penelitian dan proyek perangkat lunak tanpamembeli sistem SIG yang lengkap atau tanpa menjadi ahliSIG sebelumnya.

MapWindow GIS merupakan sofware aplikasi berlabelfree, salah satu perangkat lunak untuk Sistem InformasiGeografis (SIG) yang berbasis open source. MapWindowbersifat free baik dalam hal lisensi pemakaian maupunpengembangannya. MapWindow dapat digunakan untukberbagai keperluan, misalnya:

1. Sebagai alternatif desktop SIG yang open source.2. Untuk mengkonversi data ke bentuk lain.3. Untuk mengembangkan dan mendistribusikan alat yang

berkaitan dengan analisis data spasial.4. Melakukan task sebagaimana perangkat lunak SIG

lainnya.[3].

4. PEMBAHASANPersoalan pencarian terpendek merupakan salah satu

permasalahan optimasi. Graf yang digunakan dalam pencarianrute terpendek ini adalah graf berbobot. Bobot pada sisi grafmenyatakan jarak antar verteks. Dalam hal ini bobot harusbernilai positif. Rute terpendek dengan verteks awal t danverteks tujuan v didefenisikan sebagai rute terpendek dari t kev dengan bobot minimum dan berupa rute sederhana (simplepath).

Supaya dapat melakukan pencarian rute terpendek, petakampus Universitas Sumatera Utara direpresentasikanmenjadi sebuah graf dimana gedung atau persimpangan jalansebagai verteks (node) dan jalan dengan panjang tertentusebagai sisi (edge) pada graf.

Peta Universitas Sumatera Utara yang berformat *.jpgterlebih dahulu digitasi menggunakan Aplikasi Sistem

Informasi Geografis berbasis dekstop yaitu MapWindow GIS.Peta Kampus Universitas Sumatera Utara yang sudah didigitasi terdiri dari enam layer dalam format *.shp yaituarea.shp, verteks.shp, office.shp, road.shp, road_name.shp,dan edge_and_distance.shp. Keenam layer inilah nantinyaakan membentuk peta Kampus Universitas Sumatera Utaradalam aplikasi yang akan dibangun.

Meskipun demikian, layer-layer dalam format *.shp inibelum langsung dapat ditampilkan pada Delphi 2009 karenaDelphi 2009 belum mendukung data dalam format *.shp. Olehkarena itu diperlukan komponen tambahan yaitu MapWinGISActiveX. Komponen MapWinGIS ActiveX ini adalah objekpemrograman untuk membentuk dan menyediakan built-indata peta *.shp dalam Delphi 2009.

Adapun database yang digunakan dalam sistem ini adalahmysql yang sebelumnya diubah dari format *.dbfmenggunakan aplikasi Kettle yang dibuat oleh Pentaho.Database ini berisi id_jalan, verteks1, verteks2,panjang_jalan, dan koordinat_verteks.

Kode yang digunakan untuk menampilkan peta dalamDelphi 2009 adalah sebagai berikut:

Barisan kode ini hanya kode untuk menampilkan layerroad.shp pada peta kampus Universitas Sumatera Utara yangdiperoleh dari direktori yang telah ditentukan(D:\\MAPWINDOW). Jika direktori yang dimaksud ternyatatidak ditemukan, maka peta road.shp tidak dapat ditampilkan.Kode ini juga dapat digunakan untuk menampilkan kelimalayer yang lainnya dengan mengganti masing-masing namalayer sehingga akan diperoleh peta Universitas SumateraUtara yang lengkap.

5. PENGUJIANNilai dari setiap parameter semut yang digunakan dalam

pembahasan ini adalah:titik awal = t35titk tujuan = t15τij = 0,01q0 = 0α = 0,5β = 1.m = 10ρ = 0,01NCmax = 5

3. SISTEM INFORMASI GEOGRAFISSistem Informasi Geografis (SIG) merupakan sistem

infomasi berbasis komputer yang menggabungkan antaraunsur peta (geografis) dan informasi tentang peta tersebut(data atribut) yang dirancang untuk mendapatkan, mengolah,memanipulasi, analisa, memperagakan dan menampilkan dataspatial untuk menyelesaikan perencanaan, mengolah danmeneliti permasalahan.

Salah satu alasan mengapa konsep-konsep SIG besertasistem aplikasinya menjadi menarik untuk digunakan diberbagai disiplin ilmu karena SIG dapat menurunkaninformasi secara otomatis tanpa keharusan untuk selalumelakukan interpretasi secara manual.

1) MapWindow GISMapWindow adalah Programmable Geographic

Information System yang mendukung manipulasi, analisis, danmelihat data geospasial dan data atribut terkait dalambeberapa standar data format SIG. MapWindowdikembangkan oleh Prof. Daniel P Ames, dan Jeff Horsbaughdari Utah State University (USU). MapWindow merupakanalat pemetaan, sistem pemodelan SIG, dan aplikasi SIGprogramming interface (API) yang semuanya dikemas dalamsatu paket. MapWindow dikembangkan untuk mengatasikebutuhan pemrograman SIG yang dapat digunakan dalamrekayasa penelitian dan proyek perangkat lunak tanpamembeli sistem SIG yang lengkap atau tanpa menjadi ahliSIG sebelumnya.

MapWindow GIS merupakan sofware aplikasi berlabelfree, salah satu perangkat lunak untuk Sistem InformasiGeografis (SIG) yang berbasis open source. MapWindowbersifat free baik dalam hal lisensi pemakaian maupunpengembangannya. MapWindow dapat digunakan untukberbagai keperluan, misalnya:

1. Sebagai alternatif desktop SIG yang open source.2. Untuk mengkonversi data ke bentuk lain.3. Untuk mengembangkan dan mendistribusikan alat yang

berkaitan dengan analisis data spasial.4. Melakukan task sebagaimana perangkat lunak SIG

lainnya.[3].

4. PEMBAHASANPersoalan pencarian terpendek merupakan salah satu

permasalahan optimasi. Graf yang digunakan dalam pencarianrute terpendek ini adalah graf berbobot. Bobot pada sisi grafmenyatakan jarak antar verteks. Dalam hal ini bobot harusbernilai positif. Rute terpendek dengan verteks awal t danverteks tujuan v didefenisikan sebagai rute terpendek dari t kev dengan bobot minimum dan berupa rute sederhana (simplepath).

Supaya dapat melakukan pencarian rute terpendek, petakampus Universitas Sumatera Utara direpresentasikanmenjadi sebuah graf dimana gedung atau persimpangan jalansebagai verteks (node) dan jalan dengan panjang tertentusebagai sisi (edge) pada graf.

Peta Universitas Sumatera Utara yang berformat *.jpgterlebih dahulu digitasi menggunakan Aplikasi Sistem

Informasi Geografis berbasis dekstop yaitu MapWindow GIS.Peta Kampus Universitas Sumatera Utara yang sudah didigitasi terdiri dari enam layer dalam format *.shp yaituarea.shp, verteks.shp, office.shp, road.shp, road_name.shp,dan edge_and_distance.shp. Keenam layer inilah nantinyaakan membentuk peta Kampus Universitas Sumatera Utaradalam aplikasi yang akan dibangun.

Meskipun demikian, layer-layer dalam format *.shp inibelum langsung dapat ditampilkan pada Delphi 2009 karenaDelphi 2009 belum mendukung data dalam format *.shp. Olehkarena itu diperlukan komponen tambahan yaitu MapWinGISActiveX. Komponen MapWinGIS ActiveX ini adalah objekpemrograman untuk membentuk dan menyediakan built-indata peta *.shp dalam Delphi 2009.

Adapun database yang digunakan dalam sistem ini adalahmysql yang sebelumnya diubah dari format *.dbfmenggunakan aplikasi Kettle yang dibuat oleh Pentaho.Database ini berisi id_jalan, verteks1, verteks2,panjang_jalan, dan koordinat_verteks.

Kode yang digunakan untuk menampilkan peta dalamDelphi 2009 adalah sebagai berikut:

Barisan kode ini hanya kode untuk menampilkan layerroad.shp pada peta kampus Universitas Sumatera Utara yangdiperoleh dari direktori yang telah ditentukan(D:\\MAPWINDOW). Jika direktori yang dimaksud ternyatatidak ditemukan, maka peta road.shp tidak dapat ditampilkan.Kode ini juga dapat digunakan untuk menampilkan kelimalayer yang lainnya dengan mengganti masing-masing namalayer sehingga akan diperoleh peta Universitas SumateraUtara yang lengkap.

5. PENGUJIANNilai dari setiap parameter semut yang digunakan dalam

pembahasan ini adalah:titik awal = t35titk tujuan = t15τij = 0,01q0 = 0α = 0,5β = 1.m = 10ρ = 0,01NCmax = 5

Page 4: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

Gambar 1. Hasil Pencarian Rute Optimum Menggunakan Algoritma Semut pada Peta Kampus Universitas Sumatera Utara

Pada gambar diatas terlihat bahwa rute optimum ditampilkan berupa garis merah dari titik awal ke titiktujuan yang dalam hal ini dari t35 (Persimpangan Jl. Alumni dengan Jl. Perpustakaan) menuju t15(Persimpangan Jl. Prof. Dr. Sofian dengan Jl. TM Hanafiah).

Hasil Pengujian berdasarkan banyak semut dan siklus akan ditampilkan ddalam tabel dibawah ini:TABEL I

HASIL PENGUJIAN BERDASARKAN BANYAK SEMUT DAN SIKLUS

BanyakSiklus

BanyakSemut

PanjangRute Optimum (m)

WaktuRata-rata Keberhasilan

5 2 900 00:09 35 20 900 01:01 10

10 10 900 01:26 910 50 900 04:10 1020 10 900 03:01 105 100 900 09:59 10

100 50 900 10:30 10

Hasil pengujian berdasarkan parameter τij akan ditampilkan dalam tabel dibawah ini:TABEL II

HASIL PENGUJIAN BERDASARKAN PARAMETER τij

No Parameter PanjangRute Optimum (m)

Waktu(detik) Keberhasilanτij q0 α β ρ

1 0.001 0 0.5 1 0.01 900 01:04 102 0.01 0 0.5 1 0.01 900 01:02 103 0.1 0 0.5 1 0.01 900 01:05 104 0.5 0 0.5 1 0.01 900 01:05 85 1 0 0.5 1 0.01 900 01:05 6

Page 5: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

Hasil pengujian berdasarkan parameter q0 akan ditampilkan dalam tabel dibawah ini:TABEL III

HASIL PENGUJIAN BERDASARKAN PARAMETER q0

No Parameter PanjangRute Optimum (m)

Waktu(detik) Keberhasilanτij q0 α β ρ

1 0.1 0 0.5 1 0.01 900 01:17 102 0.1 0.5 0.5 1 0.01 900 01:01 83 0.1 0.7 0.5 1 0.01 1350 00:51 04 0.1 1 0.5 1 0.01 - 00:36 05 0.1 5 0.5 1 0.01 - 00:36 0

Hasil pengujian berdasarkan parameter α akan ditampilkan dalam tabel dibawah ini:TABEL IV

HASIL PENGUJIAN BERDASARKAN PARAMETER α

No Parameter PanjangRute Optimum (m)

Waktu(detik) Keberhasilanτij q0 α β ρ

1 0.1 0 0 1 0.01 900 01:01 52 0.1 0 0.1 1 0.01 900 01:01 63 0.1 0 0.5 1 0.01 900 01:00 84 0.1 0 0.7 1 0.01 900 01:02 85 0.1 0 1 1 0.01 900 01:00 8

Hasil pengujian berdasarkan parameter β akan ditampilkan dalam tabel dibawah ini:TABEL V

HASIL PENGUJIAN BERDASARKAN PARAMETER β

No Parameter PanjangRute Optimum (m)

Waktu(detik) Keberhasilanτij q0 α β ρ

1 0.1 0 0.5 0.01 0.01 900 00:56 92 0.1 0 0.5 0.1 0.01 900 01:58 93 0.1 0 0.5 0.5 0.01 900 01:01 94 0.1 0 0.5 1 0.01 900 01:03 95 0.1 0 0.5 5 0.01 900 01:05 5

Hasil pengujian berdasarkan parameter ρ akan ditampilkan dalam tabel dibawah ini:TABEL V

HASIL PENGUJIAN BERDASARKAN PARAMETER ρ

No Parameter PanjangRute Optimum (m)

Waktu(detik) Keberhasilanτij q0 α β ρ

1 0.1 0 0.5 1 0.05 900 01:04 82 0.1 0 0.5 1 0.01 900 01:01 83 0.1 0 0.5 1 0.1 900 00:59 84 0.1 0 0.5 1 0.5 900 00:56 55 0.1 0 0.5 1 0.9 900 00:54 7

6. KESIMPULAN

1. Aplikasi Pencari Rute Optimum dengan dukunganSistem Informasi Geografis ini dapat menunjukkanrute terpendek antara dua titik yang diinginkannamun masih memiliki kelemahan yaituketergantungan pada nilai parameter dan sistemrandom yang belum maksimal.

2. Parameter banyak semut dan banyak siklusmempengaruhi peluang dalam pencarian ruteoptimal dan waktu eksekusi dalam pencarian rute

optimal. Semakin banyak semut dan siklus yangdigunakan, maka peluang pencarian rute optimalakan semakin tinggi namun waktu ekseskusinyaakan semakin lama.

3. Parameter τij, q0 dan α mempengaruhi peluangdalam pencarian rute optimal. Semakin kecil nilaiparameter τij dan q0, dan semakin besar nilaiparameter α maka peluang pencarian rute optimalakan semakin tinggi.

4. Parameter ß dan ρ mempengaruhi waktu eksekusidalam pencarian rute optimal. Semakin kecil nilai

Page 6: Jurnal - Aplikasi Pencari Rute Optimum Menggunakan Algoritma Semut Di Kampus USU Dengan Dukungan Sistem Informasi Geografis

ß dan semakin besar nilai ρ maka waktu eksekusipencarian rute optimal akan semakin cepat.

7. DAFTAR PUSTAKA[1] Wardi, Ibnu Sina, 2007. Penggunaan graf dalam algoritma

semut untuk melakukan optimisasi. Jurnal Program StudiTeknik Informatika: hal. 1-10. Institut Teknologi Bandung.

[2] Mindaputra, Eka. 2009. Penggunaan Algoritma Ant ColonySystem Dalam Traveling Salesman Problem (TSP) Pada PT.Eka Jaya Motor. Skripsi. Semarang: Departemen Matematika,Universitas Dipenogoro.

[3] Usman, Ferdinan, dkk. 2008. Teori dan Aplikasi OpensourceGIS menggunakan MapWindows. Yogyakarta: Andi.