Sistem Informasi Jalur Alternatif Menggunakan Top-k Query Berbasis WEB Pada BlackBerry™ Doni Rusdiyatno1), Eko Pramunanto2), Ahmad Zaini3) Teknik Komputer dan Telematika, Jurusan Teknik Elektro, Fakultas Teknologi Industri, Institut Teknologi Sepuluh Nopember Sukolilo, Surabaya 60111 1)
Mahasiswa Sarjana Lintas Jalur (
[email protected]) 2) Dosen Pembimbing (
[email protected]) 3) Dosen Pembimbing (
[email protected])
Abstrak— Salah satu upaya mencegah bertambahnya tingkat kemacetan lalu lintas adalah dengan penyampaian informasi jalur alternatif kepada pengguna jalan. Tugas akhir ini dibuat untuk mengakomodasi kebutuhan akan informasi jalur alternatif. Sistem dibuat berdasarkan preferensi pengguna yang dapat diakses secara online oleh pengguna melalui perangkat mobile dengan sistem operasi BlackBerry™ dengan menerapkan metode Top-k query yang dibantu pencarian Depth First Search. Proses dimulai dengan pembentukan graph, selanjutnya dilakukan pencarian jalur. Pencarian dimulai dimulai dari titik awal yang disebut root. Selanjutnya pencarian dilakukan dengan mencari semua titik yang terhubung dengan titik awal (root) tersebut yang disebut titik anak. Titik anak yang pertama kali ditemukan digunakan terlebih dahulu sebagai kandidat sebagai kunci pencarian berikutnya.Tahapan berikutnya dilakukan pemberian beban pada setiap segmen jalur alternatif. Segmen jalur yang telah diberi beban selanjutnya dicari nilai total untuk setiap jalur. Total untuk setiap jalur diurutkan dan ditampilkan dalam jumlah tertentu. Sistem informasi ini menghasilkan informasi jalur alternatif terbaik secara online dengan preferensi pengguna. Pengujian terhadap sistem yang telah dibuat dilakukan dengan percobaan sebanyak 15 kali menggunakan 44 simpul yang terbagi menjadi 94 segmen. Pengujian ditinjau dari kebenaran atau ketepatan jalur yang dihasilkan serta kecepatan dalam menampilkan jalur alternatif. Hasil pengujian pada smartphone BlackBerry™ 9300 3G menunjukkan bahwa ketepatan pencarian jalur alternatif mencapai 93%, dengan waktu pemrosesan rata-rata sebesar 7,3 detik. Kata kunci— mobile, graph, BlackBerry™, Top-k Query
I.
kepada pengguna jalan. Banyak faktor yang mempengaruhi pengolahan informasi lalu lintas diantaranya yang adalah panjang jalan, kepadatan, lajur jalan serta permasalahan insidentil misalnya banjir. Sehingga faktor tersebut perlu digunakan dalam menentukan informasi jalur alternatif yang akan dilewati. Pada penelitian sebelumnya dibuat modul sistem pemantau kondisi lalu lintas berdasarkan tingkat kepadatan sehingga menghasilkan informasi yang dapat diakses secara online oleh pengguna dengan perangkat mobile yang mempunyai sistem operasi Android[1]. Informasi kondisi lalu lintas yang dihasilkan modul pemantau kondisi lalu lintas tersebut tidak disertai informasi tentang saran jalur alternatif terlancar yang sebaiknya ditempuh oleh pengguna jalan. Sistem tersebut juga belum menyertakan partisipasi pengguna dalam menentukan preferensi terhadap faktor panjang jalan, kepadatan, perbaikan jalan dan banjir. Pembuatan sistem yang mengolah data lalu lintas berupa panjang jalan, kepadatan, perbaikan jalan dan banjir menjadi informasi jalur alternatif terlancar diajukan sebagai suatu solusi. Pengolahan data lalu lintas tersebut dilakukan dengan menyertakan preferensi pengguna. Informasi jalur alternatif dapat diakses secara online oleh pengguna melalui perangkat mobile terutama smartphone BlackBerry™. Sistem dibuat dengan masukan berupa data panjang jalan, kepadatan, perbaikan jalan dan banjir. Data panjang jalan, data kepadatan lalu lintas, data perbaikan jalan, dan data banjir diperoleh dari sistem lain yaitu Real Time Traffic Information System (RTTIS). Pencarian kemungkinan jalur dalam hal ini dengan mengabaikan cycle path (bagian jalur yang berulang) dalam sebuah jalur. Cakupan wilayah yang digunakan dalam pencarian jalur alternatif yaitu wilayah Surabaya Timur. Peta yang digunakan berasal layanan peta online (Online Map Service) CloudMade.
PENDAHULUAN II.
A. Latar Belakang Salah satu upaya mencegah bertambahnya tingkat kemacetan adalah dengan pemberian informasi jalur rawan macet yang dilakukan oleh petugas pengatur lalu lintas
PERANCANGAN SISTEM
A. Kedudukan Sistem Sistem informasi jalur alternatif yang dikerjakan pada tugas akhir ini mempunyai hubungan dengan sistem lain.
Sistem lain yang dimaksud adalah Real Time Traffic Information System (RTTIS) dan Sistem Penyedia Layanan Peta Online (Online Map Service). Kedudukan sistem informasi jalur alternatif terhadap Real Time Traffic Information System (RTTIS) dan Sistem Penyedia Layanan Peta Online diilustrasikan oleh Gambar 1. Gambar 1 menunjukkan ruang lingkup sistem informasi jalur alternatif dibatasi oleh suatu persegi dengan sudut tumpul. Sistem informasi tersebut terdiri atas tiga komponen utama, yaitu database, aplikasi web, dan aplikasi J2ME.
Gambar 1 Kedudukan Sistem Informasi Jalur Alternatif
Database yang digunakan oleh sistem informasi jalur alternatif berasal dari informasi yang dihasilkan oleh Real Time Traffic Information System (RTTIS). Setiap ada perubahan (update) informasi yang dihasilkan RTTIS, akan dijadikan acuan oleh admin aplikasi web untuk mengupdate database sistem informasi jalur alternatif. Komponen kedua dari sistem informasi jalur alternatif adalah aplikasi web. Aplikasi web di sini berfungsi sebagai mesin pemroses pencarian jalur alternatif. Sebagai mesin pencarian, aplikasi web dilengkapi dengan peta dari lokasi yang akan dicari. Peta tersebut diambil dari sistem layanan peta online. Hal yang harus dilakukan untuk memperoleh peta dari sistem layanan peta online yaitu pengiriman koordinat peta oleh aplikasi web menuju sistem peta online. Sistem layanan peta online menanggapi permintaan peta (peta yang dilengkapi koordinat peta) oleh aplikasi web dengan memberikan tampilan visual peta yang diinginkan kepada aplikasi web. Aplikasi J2ME sebagai komponen ketiga dari sistem informasi jalur alternatif berfungsi sebagai program pemanggil aplikasi web. Aplikasi web tersebut yang nantinya mengolah permintaan jalur alternatif serta menghasilkan informasi jalur alternatif pada perangkat smartphone BlackBerry™. B. Model Preferensi dan Beban Preferensi pengguna yang dimaksud dalam penelitian ini adalah adanya partisipasi pengguna dalam perencanaan jalur
yaitu berdasarkan keinginan dari setiap individu untuk memilih jalur dengan faktor beban. Tingkat preferensi mempunyai tiga tingkatan yaitu penting, biasa dan kurang penting. Nilai yang diberikan kepada tiga tingkatan tersebut secara berurutan yaitu 3,2 dan 1. Sebagian besar pengguna cenderung mengutamakan panjang jalan. Oleh karena itu, setiap nilai preferensi terhadap panjang selalu ditambah 1.Faktor beban tersebut diinformasikan dari sistem kepada pengguna untuk kemudian pengguna sendiri yang akan memilih faktor mana yang menurutnya lebih penting. Beban panjang jalan, kepadatan, perbaikan jalan maupun banjir dimodelkan sebagai berikut. 1) Panjang Panjang jalan yang dijadikan beban jalur alternatif diurutkan dari yang paling panjang sampai dengan yang paling pendek. Setelah diurutkan, kemudian dilakukan normalisasi dengan memberi nilai dengan batas bawah adalah nol dan batas atas adalah satu. Jadi jalan yang panjangnya paling besar akan diberi nilai nol, jalan yang panjangnya paling kecil diberi nilai satu, sedangkan yang lain diberi nilai diantara nol dan satu. 2) Kepadatan Kepadatan jalan berupa banyaknya pengguna jalan yang melintas pada suatu area jalan tertentu bersifat dinamis, dalam artian kondisi suatu jalan suatu saat tingkat kepadatannya bisa naik maupun turun. Oleh karena itu nilai beban kepadatan jalan selalu berubah. Jalan dengan tingkat kepadatan tertinggi akan diberi nilai nol, sedangkan jalan dengan tingkat kepadatan paling rendah akan diberi nilai satu. 3) Perbaikan Jalan Ada kalanya suatu jalan atau ruas jalan dikenakan perbaikan jalan. Hal tersebut tentu mempengaruhi arus lalu lintas yang melewati jalan tersebut. Suatu jalan yang dikenakan perbaikan jalan dengan panjang jalan yang paling tinggi diberi nilai nol, sedangkan jalan yang tidak terdapat perbaikan terhadapnya diberi nilai satu. 4) Banjir Kondisi suatu wilayah tertentu dengan fasilitas saluran air yang kurang baik, akan menyebabkan genangan air yang bisa mengganggu arus lalu lintas. Hal tersebut biasa terjadi sewaktu turun hujan pada kota-kota besar dengan kepadatan lalu lintas yang tinggi. Kondisi jalan dengan tidak ada genangan air diberi beban nol. Beban sebesar satu diberikan untuk jalan dengan genangan air yang tidak bisa dilewati oleh kendaraan pribadi roda empat. Sedangkan beban sebesar 0,5 diberikan untuk kondisi jalan dengan genangan air yang masih bisa dilewati oleh kendaraan pribadi roda empat. C. Fungsi Skor Hal mendasar dalam suatu Top-k query adalah cara melakukan agregasi skor terhadap multi atribut (kolom) [2]. Sebelum dilakukan agregasi nilai dari masing-masing atribut diubah dulu ke bilangan diantara 0 dan 1, setelah itu baru digunakan fungsi skor. Untuk mengintegrasikan empat faktor
beban dengan preferensi pengguna[3], dalam pelaksanaanya digunakan persamaan : . . . .
F(x)=
∑
............................. (1)
Keterangan : F(x) = fungsi kombinasi yang menghasilkan skor jalur alternatif; , , , = derajat kepentingan pengguna terhadap faktor beban dimana bernilai paling rendah 1 dan paling tinggi 3 (kurang penting, biasa dan penting); 1 menunjukkan preferensi terhadap panjang ditambah 1. =skor untuk faktor beban panjang jalan; = skor untuk faktor kepadatan; = skor untuk faktor perbaikan jalan; = skor untuk faktor banjir. Sebuah Top-k query dalam sebuah kalimat basisdata Structured Query Language (SQL) dinyatakan sebagai : SELECT * FROM R ORDER [k] BY Scoring_Function ......... (2)
Dari pernyataan 2 di atas, R mewakili relasi atau tabel, k mewakili jumlah baris hasil yang diinginkan, sedangkan Scoring_function merupakan fungsi skor dari kiteria (kolom) tabel R. Secara sederhana, dalam sistem basisdata relasional hasil dari suatu query adalah suatu himpunan baris. Sedangkan, hasil dari Top-k query adalah himpunan baris terurut berdasar kriteria tertentu, dimana pengurutan mencerminkan bagaimana pendekatan tiap baris sesuai dengan query yang diberikan[4]. D. Pemrosesan Top-k Query Pemrosesan Top-k query terdiri dari beberapa langkah seperti terlihat pada Gambar 2. Gambar 2 menunjukkan tahapan pemrosesan Top-k query yang dapat dijelaskan sebagai berikut.
2. Menentukan skor dari setiap faktor beban untuk setiap jalur yang diperoleh. Skor yang didapatkan berada dalam rentang 0 sampai dengan 1 untuk setiap jalur. Skor dari setiap segmen kemudian dijumlah sebanyak jumlah segmen dalam setiap jalur alternatif. 3. Memasukkan skor dari setiap faktor beban ke dalam fungsi kombinasi dengan preferensi pengguna. Jumlah skor untuk setiap faktor beban dari setiap segmen, dimasukkan ke dalam fungsi kombinasi dengan preferensi pengguna. 4. Menyeleksi hasil pencarian berdasarkan skor yang terurut dari yang tertinggi sampai yang terendah sebanyak k jalur. III.
PENGUJIAN
A. Peralatan Yang Digunakan Peralatan yang digunakan penulis dalam penelitian pencarian jalur alternatif, yaitu: 1) Perangkat Server • Prosesor : Intel(R) core(TM)2 Duo CPU T5870 @ 2,00 GHz. • Memori : 2,04 GB. • Sistem Operasi :Windows XP Professional Service Pack 2. 2) Perangkat Klien BlackBerry™ 9300 smartphone 3G Platform 6.6.0.212. 3) Koneksitas USB Modem EVDO Rev.A Smartfren CE682. Rancangan sistem diimplementasikan dengan membuat aplikasi yaitu web desktop dan smartphone BlackBerry™. Web desktop ditujukan untuk pengguna yang berada pada lingkungan yang tidak bersifat mobile. Sedangkan aplikasi pada smartphone BlackBerry™ berfungsi mengakomodasi lingkungan yang bersifat mobile[6] . B. Hasil Yang Diperoleh Percobaan dilakukan di smartphone BlackBerry™ dari suatu wilayah yang dipetakan menjadi 44 simpul yang terbagi menjadi 94 segmen. Sebagai contoh kasus, dari Gambar 3 diketahui bahwa seorang pengguna melakukan pencarian dengan preferensi pengguna sebesar 2 untuk semua faktor beban menghasilkan empat buah jalur alternatif dengan beban yang tertera pada Tabel 2. Tabel 2: Beban Awal Jalur Alternatif
Panjang Jalan(m) 6358.78
Kepadatan (m) 713
Perbaikan Jalan (m) 219
Banjir
1.
Id Jalur 0
2. 3. 4.
1 2 3
11182.25 7216.45 12039.92
1214 918 1419
770 521 1072
7.5 4.5 9
No
3
Gambar 2 Tahapan Pemrosesan Top-k Query
1. Menentukan semua kemungkinan jalur yang ada dari lokasi awal pencarian sampai lokasi tujuan. Pencarian jalur alternatif dilakukan dengan menggunakan pencarian Depth First Search[5].
Beban yang tertera pada Tabel 2 merupakan beban dalam kondisi belum normal. Beban tersebut kemudian dinormalkan seperti yang tertera pada Tabel 3.
(,)*)
= =0,75 Id Jalur =3 Skor= F(x)=
. . . . ∑
.0.0.0.0 = + =
=0 Hasil akhir informasi tiga jalur alternatif terlancar diperlihatkan pada Tabel 4. Nilai diurutkan dari yang tertinggi sampai yang terendah, dan diambil 3 nilai tertinggi.tertinggi adalah satu. . Tabel 4: Informasi Jalur Alternatif Gambar 3 Pencarian Jalur Alternatif
Gambar 3 menunjukkan peta wilayah Surabaya. Peta diambil dari layanan peta online CloudMade yang kemudian diintegrasikan dengan sistem informasi jalur alternatif pada penelitian ini. Sedangkan Tabel 3 menunjukkan nilai normal untuk faktor beban. Nilai normal beban berada diantara 0 dan 1. Tabel 3: Normalisasi beban Jalur Alternatif
No 1.
Id Jalur 0
2. 3. 4.
1 2 3
Panjang Jalan(m)
Kepadatan (m)
Perbaikan Jalan (m)
Banjir
1 0,151 0,849
1 0,290 0,709
1 0,354 0,646
1 0,250 0,750
0
0
0
0
Untuk menghitung skor jalur alternatif, yaitu dengan memasukkan tingkat preferensi pengguna ( , , , dan ) serta nilai normal total faktor beban tiap jalur ke dalam persamaan (1), sehingga diperoleh hasil sebagai berikut. Skor= F(x)=
. . . . ∑
.... = =
=1
=
Awal
Tujuan
Didapat
Benar
1
Jl.KenjeranN1
Jl.TempurrejoN7
3
3
2
Jl.R. GubengN13
3
3
3
Jl.KenjeranN5 Jl.Kjaya Indah N25
2
2
4
Jl.SulawesiN21
3
3
5
Jl.R. GubengN18
3
3
6
Jl.Kd CowekN2
Jl.Kr.JawaN19 Jl.D.Hus. Indah T.N30 Jl.R.Kjaya IndahN27 Jl.Ngagel Jaya S.N33
3
3
7
Jl.Kjaya N23
Jl.R. TengahN44
1
1
Jl.TempurrejoN7
Jl.KenjeranN1
2
2
Jl.R. GubengN13
Jl.KenjeranN5
3
3
. . . .
10
2
2
11
Jl.SulawesiN21
3
3
Jl.R. GubengN18
3
3
13
Jl.Kr.JawaN19 Jl.D.Hus. Indah T.N30 Jl.R.Kjaya IndahN27 Jl.Ngagel Jaya S.N33
Jl.Kaya IndahN25
∑ .0,151.0,290.0,354.0,250
Jl.Kd CowekN3
3
3
14
Jl.R. TengahN44
1
1
15
Jl.D.HusadaN16
Jl.KjayaN23 Jl.R Industri R.N42
2
2
,
12
Id Jalur =2
=
No
8
= =0,249
Skor= F(x)=
Tabel 5: Hasil Pengujian Ketepatan Jalur Alternatif
9
Id Jalur =1 Skor= F(x)=
Pengujian terhadap kebenaran jalur alternatif yang diperoleh, dilakukan dengan melakukan percobaan sebanyak 15 kali yang dirangkum pada Tabel 5.
. . . . ∑ .0,849.0,709.0,646.0,750
Tabel 5 mempunyai kolom No, kolom awal, kolom tujuan, kolom jalur yang diperoleh (Didapat), serta kolom Jalur Benar (Benar). Kolom No diisi dengan nomor urut segmen.Kolom awal dan tujuan menyatakan lokasi pencarian. Kolom jalur yang yang diperoleh (Didapat) diisi dengan jumlah jalur yang didapatkan dari hasil pencarian jalur alternatif. Sedangkan kolom (Benar) diisi dengan jumlah jalur yang setelah dicek dengan melihat peta. Hasil dari lima belas kali percobaan diperoleh jalur alternatif dengan tingkat kebenaran yaitu : = ( + + + + + + ++++ + + + + ) / 15
IV. PENUTUP A. Simpulan Pengujian terhadap sistem yang telah dibuat dilakukan dengan percobaan sebanyak 15 kali menggunakan 44 simpul yang terbagi menjadi 94 segmen. Pengujian ditinjau dari kebenaran atau ketepatan jalur yang dihasilkan serta kecepatan dalam menampilkan jalur alternatif. Hasil pengujian pada smartphone BlackBerry™ 9300 3G menunjukkan bahwa ketepatan pencarian jalur alternatif mencapai 93% dengan waktu pemrosesan rata-rata sebesar 7,3 detik.
≈ 93 % Percobaan 15 kali dengan jumlah segmen sebanyak 64 segmen menghasilkan jalur alternatif dengan tingkat kebenaran mencapai 93%.Sedangkan waktu yang diperlukan untuk memproses jalur alternatif ditunjukkan oleh Tabel 6.
B. Saran
Tabel 6: Hasil Pengujian Waktu Pemrosesan Jalur Alternatif
No
Waktu (detik)
Awal
Tujuan
1
Jl.KenjeranN1
Jl.TempurrejoN7
2
Jl.KenjeranN5
Jl.R. GubengN13
5,25
3
Jl.Kjaya Indah N25
7,19
4
Jl.SulawesiN21
Jl.Kr.JawaN19 Jl.D.Hus. Indah T.N30
5,47
5
Jl.R. GubengN18
Jl.R.Kjaya IndahN27
8,17
6
Jl.Kd CowekN2
Jl.Ngagel Jaya S.N33
5,06
7
Jl.Kjaya N23
Jl.R. TengahN44
4,47
8
Jl.TempurrejoN7
Jl.KenjeranN1
10,95
6,72
9
Jl.R. GubengN13
Jl.KenjeranN5
7,21
10
Jl.Kr.JawaN19
Jl.Kaya IndahN25
7,69
11
Jl.D.Hus. Indah T.N30
Jl.SulawesiN21
8,52
12
Jl.R.Kjaya IndahN27
Jl.R. GubengN18
6,34
13
Jl.Ngagel Jaya S.N33
Jl.Kd CowekN3
8,14
14
Jl.R. TengahN44
Jl.KjayaN23
8,45
15
Jl.D.HusadaN16
Jl.R Industri R.N42
7,31
Waktu rata-rata yang diperlukan untuk pengolahan jalur alternatif dari simpul awal ke simpul tujuan yaitu: =(6,72+5,25+7,19+5,47+8,17+5,06+4,47+10,95 +7,21+7,69+8,52+6,34+8,14+8,45+7,31) / 15 +(, = * x 1 detik = 7,3 detik.
Berikut ini merupakan saran yang dapat diberikan untuk pengembangan sistem. 1) Dalam rangka mempercepat pencarian, implementasi sistem dapat digunakan bahasa pemrograman lain seperti C dan sejenisnya untuk mendukung kinerja PHP. 2) Pencarian dibuat lebih interaktif dan menarik, dengan mengupayakan adanya visualisasi lokasi pencarian (baik awal pencarian dan tujuan pencarian). REFERENSI [1] Suherman, M.Y., “Sistem Penyaji Real Time Traffic Information System”, Institut Teknologi Sepuluh Nopember, Surabaya, 2011. [2] Manalu, E. F., “Analisis Terhadap Skyline Query Dan Top-k Query Pada Context Preference Service Aware Service”, Makalah IF1305 Strategi Algoritmik, Institut Teknologi Bandung, Bandung, 2009. [3] Balke,W.T., Kieβling, W., Unbehend, C.,” A Situation-aware Mobile Traffic Information System”, Proceedings of the 36th Hawaii International Conference on System Sciences, 2002. [4] Theobald, Martin, ”Efficient and Versatile Top-k Query Processing for Text, Structured, and Semistructured Data”, Institut für Informatik, 2009. [5] Sjukani, Moh., “Algoritma & Struktur Data 2 dengan C dan C++”, Mitra Wacana Media, Jakarta, 2010. [6] Riyanto, “Membuat Sendiri Aplikasi Mobile GIS Platform Java ME, BlackBerry & Android”, Andi Offset, Yogyakarta, 2010.
