Jurnal Teknik Informatika Vol. 1 September 2012
Optimasi Pemilihan Jalur Taksi Berdasarkan Posisi Pelanggan dengan Pendekatan Algoritma A Star (A *) Robby Ardan1), Dini Nurmalasari2), dan Yusapril Eka Putra3) 1) Jurusan Teknik Informatika Politeknik Caltex Riau, Pekanbaru 2 8 2 6 5 , email:
[email protected] 2) Politeknik Caltex Riau, Pekanbaru 2 8 2 6 5 , email:
[email protected] 3) Politeknik Caltex Riau, Pekanbaru 2 8 2 6 5 , email:
[email protected] Abstrak – Penggunaan jalur terpendek oleh taksi menuju
ke posisi tujuan tentu dapat mengurangi biaya transportasi dan menghemat waktu. Hal ini dapat memberikan keuntungan bagi kemajuan perusahaan taksi. Taksi sebagai salah satu alat transportasi di kota Pekanbaru diminati karena kenyamanan, efisien, dan mudah dipesan dari tempat yang diinginkan. Pelanggan yang sudah memesan taksi melalui operator akan segera dijemput oleh supir taksi. Karena keterbatasan informasi data jalan, sehingga membuat supir taksi membutuhkan waktu untuk mengetahui letak posisi pelanggan serta rute dengan jarak terpendek menuju ke posisi pelanggan. Dengan luasnya jalur taksi di kota Pekanbaru, memungkinkan adanya alternatif jalan yang dapat dilalui taksi untuk menjemput pelanggan dengan jalur yang lebih singkat. Untuk itu dibuatlah sistem informasi geografis pencarian jalur terpendek dari posisi supir taksi ke posisi pelanggan dengan menggunakan algoritma A Star. Dari pengujian data dilapangan dan data dari google map dapat diketahui bahwa algoritma A Star berhasil mencari jalur terpendek yang dapat dilewati oleh supir taksi berdasarkan paramater jarak dan fungsi heuristik yang digunakan dalam perhitungan algoritma tersebut. Kata kunci : alat tranportasi, jalur terpendek, algoritma A Star.
1. PENDAHULUAN Peta digunakan untuk mempermudah menemukan sebuah lokasi. Peta memberikan kemudahan karena dapat melihat jalur yang dapat dilalui dari posisi awal hingga ke posisi tujuan. Hal ini tentu akan lebih baik jika mengetahui jalur terpendek menuju ke posisi tujuan. Alat transportasi yang menggunakan rute terpendek dalam ruang lingkup kerjanya, tentu dapat memberikan banyak keuntungan, baik disisi waktu maupun biaya. Salah satu alat transportasi adalah taksi di kota Pekanbaru. Luasnya jalur taksi di kota Pekanbaru, memungkinkan adanya alternatif jalan yang dapat dilalui taksi untuk menjemput pelanggan dengan jalur yang lebih singkat. Taksi dapat dipesan dengan mudah oleh masyarakat, yaitu dengan cara memanggil langsung taksi yang sedang melintas maupun dengan memesan secara langsung ke operator taksi. Setelah pelanggan melakukan permintaan, operator akan memberi tahu alamat pelanggan kepada supir taksi, lalu supir taksi akan pergi menuju ke tempat posisi pelanggan berada. Karena keterbatasan informasi
data jalan, sehingga membuat supir taksi membutuhkan waktu untuk mengetahui letak posisi pelanggan dan memilih rute dengan jarak terpendek menuju ke posisi pelanggan. Dari permasalahan diatas, dibutuhkan suatu optimasi untuk menemukan solusi mencari rute terpendek. Menurut Paul E Black (2001), optimasi merupakan suatu masalah komputasional yang bertujuan untuk menemukan solusi terbaik dari semua solusi yang mungkin. Secara lebih formal, menemukan sebuah solusi yang berada dalam daerah yang mungkin (feasible region) yang memiliki nilai minimum (atau maksimum) dari fungsi objektif. Optimasi akan berjalan dengan baik dengan algoritma yang baik pula. Algoritma adalah urutan dari barisan instruksi untuk menyelesaikan suatu masalah (Astuti, 2006). Masalah tersebut dapat berupa apapun dengan catatan untuk setiap masalah memiliki kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Beberapa contoh algoritma optimasi adalah Dijkstra, Greedy, dan A Star. Algoritma yang digunakan untuk mencari rute terpendek dalam proyek akhir ini adalah algoritma A Star. Algoritma A Star menurut Hart, Nilsson, dan Raphael (2003) adalah algoritma pencarian yang mampu menemukan jalur dengan biaya pengeluaran paling sedikit dari titik permulaan yang diberikan sampai ke titik tujuan yang diharapkan. Algoritma ini memeriksa node dengan menggabungkan G(n), yaitu cost yang dibutuhkan untuk mencapai sebuah node dan H(n) yaitu cost yang didapat dari node ke tujuan.
2. DASAR TEORI 2.1 Sistem Informasi Geografis Sistem informasi geografis (SIG) menurut dari buku yang disusun oleh tim GIS Consortium Aceh Nias (2007) merupakan suatu komponen yang terdiri dari perangkat keras, perangkat lunak, data geografis dan sumberdaya manusia yang bekerja bersama secara efektif untuk memasukan, menyimpan, memperbaiki, memperbaharui, mengelola, memanipulasi, mengintegrasikan, menganalisa dan menampilkan data dalam suatu informasi berbasis geografis. Kemampuan SIG yang dapat mengolah data spasial (data yang berorientasi geografis) membuatnya menjadi salah saru pembeda dengan sistem informasi lainnya. SIG mengolah data yang berkaitan dengan bentuk muka bumi, seperti pemodelan, koordinat, dan lain-lain. SIG mempunyai kemampuan untuk menghubungkan berbagai
Jurnal Teknik Informatika Vol. 1 September 2012 data pada suatu menggabungkannya, memetakan hasilnya.
titik tertentu di bumi, menganalisa dan akhirnya
2.2 Data Spasial Data yang diolah dalam SIG merupakan data spasial, yaitu data yang berorientasi geografis. Data ini memiliki sistem koordinat tertentu sebagai dasar referensinya dan mempunyai dua bagian penting yang berbeda dari data lain, yaitu informasi lokasi (spasial) dan informasi deskriptif (atribut) yang dijelaskan berikut ini : 1.
Informasi lokasi (spasial), berkaitan dengan suatu koordinat baik koordinat geografi (lintang dan bujur) dan koordinat XYZ, termasuk diantaranya informasi datum dan proyeksi.
2.
Informasi deskriptif (atribut) atau informasi nonspasial, suatu lokasi yang memiliki beberapa keterangan yang berkaitan dengannya. Contoh jenis vegetasi, populasi, luasan, kode pos, dan sebagainya.
2.3 Graf Graf menurut Yuni Dwi Astuti dari bukunya Logika dan Algoritma, merupakan hubungan antara dua pasang himpunan, yaitu himpunan V dan himpunan E. Himpunan V disebut sebagai elemen simpul atau titik atau vertex, sedangkan himpunan E merupakan pasangan tak terurut dari simpul, disebut ruas atau edge. Berikut adalah gambar suatu graf :
Gambar 2.1 Graf
a.
Titik-titik dalam gambar(1,2,3,4) diatas disebut vertex (dalam proses pencarian ini disebut node)
b.
Garis-garis yang menghubungkan antar nomor disebut edge.
2.4 Algoritma A Star Menurut Hart, Nilsson, dan Raphael dari buku Artificial Intelligence: A Modern Approac (1995) Algoritma A Star merupakan salah satu algoritma pencarian graf terbaik yang mampu menemukan jalur dengan biaya pengeluaran paling sedikit dari titik permulaan yang diberikan sampai ke titik tujuan yang diharapkan (dari satu atau lebih mungkin tujuan). Dalam buku Artificial Intelligencce yang dikarang oleh Suyanto (2007) biaya yang diperhitungkan dalam algoritma A Star didapat dari biaya sebenarnya ditambah biaya perkiraan. Dalam notasi matematika dapat dituliskan sebagai berikut : F(n) = g(n) + h(n)
(Persamaan I)
Keterangan : a.
G(n) adalah biaya (cost) yang dibutuhkan oleh sebuah jalur (path) untuk mencapai node n dari node awal
b.
H(n) adalah estimasi biaya (cost) sebuah jalur (path).
c.
F(n) adalah estimasi total biaya (cost) sebuah jalur (path) dari node awal ke node tujuan (goal) melalui node n.
Secara detail algoritma A Star menggunakan dua senarai yaitu OPEN dan CLOSED. OPEN merupakan list yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristik yang telah dihitung tetapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain OPEN berisi simpul-simpul yang masih memiliki peluang. Sedangkan CLOSED adalah simpulsimpul yang sudah pernah dibangitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). Terdapat tiga kondisi bagi setiap suksesor yang dibangkitkan, yaitu sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda. Jika suksesor sudah pernah di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai g-nya melalui parent lama atau parent baru. Jika parent baru memberikan nilai g yang lebih kecil, maka dilakukan perubahan parent. Jika pengubahan parent dilakukan, maka dilakukan pula perubahan (update) nilai g dan f pada suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai simpul terbaik (best node). Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node). Jika suksesor tidak berada di OPEN maupun CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h. Nilai h adalah fungsi heuristik, yaitu jarak garis lurus dari simpul n meninju simpul tujuan. Hal ini karena jarak terdekat dari dua titik adalah dengan menarik garis lurus. Jarak dari garis lurus antara dua titik dapat dihitung dengan rumus : (Persamaan II)
Dimana : a. x = Koordinat x dari node awal b. y = Koordinat y dari node awal c. x1= Koordinat x dari node awal d. y1= Koordinat y dari node awal
Jurnal Teknik Informatika Vol. 1 September 2012 2.5 PostgreSQL, PostGis, dan PgRouting PostgreSQL merupakan suatu software object-relational database management system (ORDBMS) berbasis pada POSTGRES, versi 4.2 yang dikembangkan di University of California at Berkeley Computer Science Department. PostgreSQL sering juga disebut sebagai Postgres. Postgres didistribusikan dalam dua kategori yaitu server dan client. Server diperlukan untuk menyediakan layanan basis data sedangkan client diperlukan untuk mengakses basis data. Postgres merupakan suatu database yang termasuk open source yang memiliki kinerja tinggi. Postgres banyak didukung oleh bahasa pemograman terkenal, diantaranya Java, C/C++, Perl, Python, dan TCL. Postgres banyak digunakan dikalangan perusahaan, individu, sekolah maupun oraganisasi-organisasi lain.
3.1 Data Flow Diagram Penggunaan Data Flow Diagram dimasukkan untuk mendeskripsikan suatu proses yang umum menjadi proses yang detail dan spesifik. Pada aplikasi ini, pengguna dibedakan menjadi dua, yaitu Admin dan pelanggan. dt_konfirmasi_update_data dt_update_data dt_konfirmasi_input_data dt_input_data
dt_log in konfirmasi_login dt_pos_pelangg an
1 dt_pos_pelangg an
dt_pos_pelangg an ADMIN
dt_pos_taxi dt_pos_taxi
SIG Jalur Taxi
konfirmasi_pengiriman
Pelang g an
output_jalurterpendek
+ dt_update_data konfirmasi_update_data
PostGIS merupakan suatu tambahan pada PostgreSQL yang dapat mengenal fungsi objek geomertri (GeoObject) sebagai sistem database spasial, dengan begitu data spasial SIG dapat disimpan ke dalam database server. PostGIS bersifat open source, sehingga dapat digunakan dalam kegiatan non-profit maupun komersial. PostGIS terus dikembangkan hingga saat ini (PostGis Team, t t) dan telah mendukung beberapa fungsi/prosedur berdasarkan PG/PLSQL untuk memproses kebutuhankebutuhan standar SIG seperti buffering, crossing, penghitungan luas area, panjang baris, dan lain lain. Dukungan penuh terhadap berbagai bentuk/format fitur geometri, point, line, polyline, polygon, multipolygon bahkan Feature Collections, dan format geodata (WKT,WKB,XML,dll) menjadikan postgis berbeda dengan database yang lain. PgRouting (PgRouting Team, t t) merupakan suatu tambahan pada database geospasial PostgreSQL maupun PostGis, sehingga dapat ditambahkan fungsi routing untuk menghitung jarak terpendek pada data spasial (data SIG). PgRouting dapat digunakan dengan menggunakan bahasa prosedural PG/PLSQL. PgRouting bersifat open source dan terus dikembangkan hingga saat ini
3. PERANCANGAN Pada perancangan ini sistem dibawah ini, terdapat dua pengguna dalam aplikasi, yaitu calon penumpang dan admin yang mengelola permintaan dari calon penumpang. Kedua pengguna saling memberikan data ke sistem melalui server dan data tersebut disimpan pada database.
dt_update_data dt_konfirmasi_update_data
Gambar 3.2 Perancangan Data Flow Diagram
DFD diatas menggambarkan hal-hal yang terjadi didalam sistem. Terdapat dua pengguna yaitu Admin dan pelanggan. Pelanggcan memberikan masukan data berupa data posisi ke sistem dan akan menerima konfirmasi pengiriman dari sistem setelah memasukkan data kesistem. Admin memberikan masukan berupa data untuk melakukan login, menginput posisi taksi, serta memasukan data untuk keperluan sistem. Setelah Admin memasukkan data kesistem, sistem akan memberikan data konfirmasi ke pengguna Admin. 3.2 Flow Chart Flow chart merupakan suatu metode yang digunakan untuk menggambarkan alur suatu program secara lebih mudah dan sederhana. 1.
Flow Chart Calon Penumpang START
INPUT POSISI
KIRIM DATA KE SERVER
T
Validasi
Y KONFIRMASI PENGIRIMAN DATA BERHASIL
END
Gambar 3.3 Flow chart calon penumpang
Gambar 3.1 Perancangan sistem
Calon penumpang memasukkan posisi dari interface aplikasi, dan setelah itu data posisi akan dikirimkan ke server. Calon penumpang akan mendapatkan konfirmasi status pengirim posisinya berhasil.
Jurnal Teknik Informatika Vol. 1 September 2012 2.
Flow Chart Admin START
HALAMAN UTAMA
LIHAT DATA
MEMASUKKAN DATA
T
MEMPERBARUI DATA
T
T
MENCARI RUTE TERPENDEK
Y
Y
Y
Y
LIHAT DATA
MEMASUKKAN DATA
PERBARUI DATA
MASUKKAN POSISI PELANGGAN DAN TAXI
MENAMPILKAN DATA
MEMASUKKAN DATA
MEMPERBARUI DATA
MELAKUKAN PENCARIAN RUTE TERPENDEK DENGAN A STAR
DATA TAMPIL
KONFIRMASI MENGINPUTKAN DATA
KONFIRMASI MEMPERBARUI DATA
HASIL PENCARIAN RUTE TERPENDEK
Gambar 4.1 Gambar lokasi Masjid Al-Mujahidin dan RS Ibnu Sina 50
51
46 8
7
52 64 END
6 53
Gambar 3.4 Flowchart Admin
Admin akan memasuki form halaman utama setelah melakukan login. Dari halaman utama, Admin dapat melihat data, menambah data, dan memperbarui data. Selain itu, Admin juga dapat mencari jalur terpendek dengan cara menginputkan posisi pelanggan dan posisi taksi.
54
ADMIN
Date Id_request
nama_pemesan
sandi Id_report
Date
target
nohp
JALAN
n
3
4
5
12
137 55
56
57
58
152
59
60
61
62
132 130
151 142
138
Gambar 4.2 Gambar node Masjid Al-Mujahidin dan RS Ibnu Sina
REQUEST
n
Report
2(2)
Berikut ditampilkan hasil perhitungan manual dalam bentuk bagan tree dari perhitungan pencarian jalur terpendek dari lokasi masjid Al-Mujahidin yang bernode 2(2) ke RS Ibnu Sina yang bernode 6.
email
username
2(1)
131
3.3 Entity Relationship Diagram (ERD) ERD berfungsi untuk menggambarkan hubungan antar tabel yang akan digunakan pada sistem ini. nama
63
1
Status Gid
2 (2)
y2 Alamat nohp
nama
0,013368491 = 0 + 0,013368491
source
x2 Id_request
target
Alamat The_geom
nama_pemesan
2 (1)
3
y1 0,013427973 = 0,00323980878 + 0,013427973
0,015163187 = 0,00089776251 + 0,014265424
x1
source
target
length
1
2(2)
0,017253757 = 0,00205353066 + 0,014302464
3
2
0,015223498 = 0,00323980878 + 0,010188165
Judul
Isi
4
0,019848108 = 0,00323980878 + 0,013368491
0,013709781 = 0,00689221593 + 3,577756879E-3
Titiklokasi
NEWS
Id_berita
2 (2)
0,015164016 = 0,00089776251 + 0,013368491
Penginput
Tanggal
gid
Nama_lokasi
Kecamatan
No
The_geom
63
0,016958711 = 0,00089776251 + 0,014265424
62
0,01419744 = 0,00105112078 + 3,014295035E-3
5
0,02787341 = 0,00755678649 + 0,0101846
0,015802685 = 0,00300166821 + 2,668992834E-3
Kategori
4 0,015505306 = 0,00689221593 + 3,577756879E-3
2(2)
4
0,019301587 = 0,00089776251 + 0,013368491
64
6
0,015812019 = 0,00105112078 + 3,577756879E-3
0,015802681 = 0,00266898892 + 0
12 0,021299246 = 0,00333677098 + 4,828783016E-3
0,01514129 = 0,00101580296 + 2,900115761E-3
Gambar 3.5 Entity Relationship Diagram
4. HASIL DAN PEMBAHASAN Pengujian dilakukan dengan cara membandingkan hasil dari perhitungan algoritma secara manual dan pengujian dari program. Dalam implementasi, pengujian dilakukan terhadap penentuan titik lokasi dari Masjid Al-Mujahidin menuju Rumah Sakit Ibnu Sina.
63 0,015992965 = 0,00105112078 + 3,014295035E-3
62
5
0,029668936 = 0,00755678649 + 0,0101846
0,01759821 = 0,00300166821 + 2,668992834E-3
8 0,016652966 = 0,00127273379 + 3,181284283E-3
63 0,016264363 = 0,00105112078 + 3,014295035E-3
Gambar 4.3 Perhitungan manual
Total nilai cost dari algoritma a star setelah dilakukan perhitungan manual adalah 0,015802681 dengan jalur terpendek yang dilewati adalah node 2(2), node 3, node 4, node 5, dan node 6. Sedangkan total nilai cost yang didapat dari menjalankan program adalah 0.0158026818673987. Dari perhitungan manual dan
Jurnal Teknik Informatika Vol. 1 September 2012 perhitungan dari sistem diketahui bahwa perhitungan memiliki total nilai cost yang sama
hasil
Setelah dilakukan pengujian terhadap hasil perhitungan manual dan perhitungan dari sistem, langkah selanjutnya adalah melakukan analisa. Diperlukan beberapa data jarak dari lokasi Masjid Al Mujahidin menuju ke Rumah Sakit Ibnu Sina untuk melakukan analisa hasil perhitungan algoritma A Star. Data yang digunakan dalam analisa perhitungan adalah data yang didapat dari pengukuran dilapangan dan data yang didapat dari Google Map. Berikut diketahui data pengukuran jalan dari Lokasi Masjid Al Mujahidin menuju ke Rumah Sakit Ibnu Sina.
dilihat pada tabel 4.3 dan tabel 4.4. Tabel 4.3 merupakan jalur yang dilewati dari lokasi Pemancar TVRI yang bernode 59 ke Ibnu Sina yang bernode 6, sedangkan pada tabel 4.4 merupakan jalur yang dilewati dari lokasi Sidi Macho yang bernode 152 ke Pasar Pagi Lama yang bernode 62. Dari kedua tabel diketahui bahwa hasil pencarian rute dari program selalu mengarah ke jalur terpendek dari data pengukuran dilapangan dan data dari Google Map. Tabel 4.3 Tabel jarak jalan dari node 59 ke 6
Node Awal
Node Tujuan
Sumber Data
Tabel 4.1 Tabel jarak jalan berdasarkan pengukuran dilapangan
No
Jalur
Jarak
1
Jalan Jendral – Jalan Dahlia – Jalan Dahlia Ujung – Jalan Melati
1,6 Km
2
Jalan Jendral – Jalan Dahlia – Jalan Melur – Jalan Cempaka – Jalan Melati
2,3 Km
3
Jalan Jendral – Jalan Dahlia – Jalan Rajawali – Jalan Durian – Jalan KH Ahmad Dahlan – Jalan Tulip – Jalan Melati
3,5 Km
59
6
Program
59
6
Data dilapang an
59
6
Data dilapang an
59
6
Data dilapang an
59
6
Google Map
59
6
Google Map
59
6
Google Map
Sedangkan untuk data yang didapat dari pengukuran di Google Map, dapat dilihat pada tabel berikut. Tabel 4.2 Tabel jarak jalan yang didapat dari Google Map
No
Jalur
Jarak
1
Jalan Jendral – Jalan Dahlia – Jalan Dahlia Ujung – Jalan Melati
1,8 Km
2
Jalan Jendral – Jalan Dahlia – Jalan Melur – Jalan Cempaka – Jalan Melati
2.3 Km
Jalan Jendral – Jalan Dahlia – Jalan Rajawali – Jalan Durian – Jalan KH Ahmad Dahlan – Jalan Tulip – Jalan Melati
3,6 Km
3
Total nilai cost yang didapat dari menjalankan program dari lokasi Masjid Al-Mujahidin menuju Rumah Sakit Ibnu Sina adalah 0.0158026818673987, dengan melewati Jalan Jendral, Jalan Dahlia, Jalan Dahlia Ujung, dan Jalan Melati. Dari data diatas, diketahui bahwa jalur terpendek yang dilalui adalah Jalan Jendral – Jalan Dahlia – Jalan Dahlia Ujung – Jalan Melati. Hal ini sesuai dengan data dilapangan, perhitungan manual algoritma dan perhitungan dari program. Dilakukan pengujian terhadap jalur lain selain dari lokasi Masjid Al-Mujahidin yang bernode 2 menuju ke Rumah Sakit Ibnu Sina yang bernode 6. Untuk lebih jelas dapat
Jalur Jalan Durian Jalan Rajawali - Jalan Dahlia Ujung - Jalan Melati Jalan Durian Jalan Rajawali - Jalan Dahlia Ujung - Jalan Melati Jalan Durian Jalan KH Ahmad Dahlan - Jalan Tulip - Jalan Dahlia Ujung Jalan Melati Jalan Durian Jalan Soekarno Hatta - Jalan Jendral - Jalan Dahlia - Jalan Dahlia Ujung Jalan Melati Jalan Durian Jalan Rajawali - Jalan Dahlia Ujung - Jalan Melati Jalan Durian Jalan KH Ahmad Dahlan - Jalan Tulip - Jalan Dahlia Ujung Jalan Melati Jalan Durian Jalan Soekarno Hatta - Jalan Jendral - Jalan Dahlia - Jalan Dahlia Ujung Jalan Melati
Jarak
1.8 Km
1.9 Km
2.1 Km
3.7 Km
1.9 Km
2.1 Km
3.8 Km
Jurnal Teknik Informatika Vol. 1 September 2012 Tabel 4.4 Tabel jarak jalan node 152 ke 62
Node Awal 152
152
152
152
152
152
152
Node Tujuan 62
62
62
62
62
62
62
Sumber Data Program
Data dilapangan
Data dilapangan
Data dilapangan
Google Map
Google Map
Google Map
Jalur Jalan Garuda Jalan Durian Jalan Garuda Jalan Durian Jalan Garuda Jalan Taskurun Jalan Rajawali Jalan Durian Jalan Soekarno Hatta Jalan Jendral Jalan Dahlia Jalan Rajawali Jalan Durian Jalan Garuda Jalan Durian Jalan Garuda Jalan Taskurun Jalan Rajawali Jalan Durian Jalan Soekarno Hatta Jalan Jendral Jalan
Dahlia Jalan Rajawali Jalan Durian
Jarak
1.5 Km
5. KESIMPULAN 1.6 Km
Setelah dilakukan pengujian kesimpulan sebagai berikut :
dan
analisa
didapat
1.
Algoritma A Star yang digunakan pada sistem informasi geografis jalur taksi di kota Pekanbaru berhasil menentukan jalur terpendek yang dapat dilalui oleh supir taksi, hal ini sesuai dengan hasil perhitungan manual, perhitungan dari program, data dilapangan, dan data dari google map.
2.
Berdasarkan pengujian yang dilakukan dengan jalur berbeda dan nilai cost yang relatif sama, terbukti algoritma A Star dapat digunakan sebagai algoritma optimasi jalur terpendek taksi.
3.
Algoritma A Star dapat menyelesaikan pencarian rute terpendek melewati node-node dengan hasil yang optimal dan total nilai cost yang minimum berdasarkan parameter jarak antar node dan fungsi heuristik yang digunakan.
1.7 Km
3.2 Km
DAFTAR REFERENSI [1]
1.7 Km
[2]
[3]
1.8 Km
[4]
[5] [6]
3.3 Km
[7]
Astuti, Yuni Dwi. (2006). Logika dan Algoritma. Universitas Gunadarma Black, E, Paul. (2001). Dictionary of Algorithms, Data Structures, and Problems. Diakses pada 26 November 2011, dari : http://www.nist.gov/dads/html GIS Consortium Aceh Nias. (2007). Modul Pelatihan ArcGIS Tingkat Dasar. Banda Aceh : Badan Rehabilitasi dan Rekonstruksi Nanggroe Aceh Darussalam – Nias (BRR NAD-Nias). J. Russell, Stuart & Norvig, Peter. (2003). Artificial Intelligence: A Modern Approac. Pearson Education: New Jersey. PgRouting Team. (t t). PgRouting. Diakses pada 28 April 2012, dari http://www.pgrouting.org PostGis Team. (t t). PostGis. Diakses pada 28 April 2012, dari http://postgis.refractions.net/ Suyanto. (2011). Artificial Intelligence. Bandung : Penerbit Informatika.
