Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
ANALISIS RUTE DAN JALAN TERPILIH UNTUK SUATU PERJALANAN DI DALAM BATAS JALANLINGKAR YOGYAKARTA BERBASIS SISTEM INFORMASI GEOGRAFIS Petrus Paryono dan Wilson Universitas Kristen Duta Wacana - Yogyakarta e-mail :
[email protected],
[email protected];
[email protected]
ABSTRACT Road network is a vital infrastructure for transportation either for people which travels from one place to another place, or for consumer goods distributions. People usually choose a certain route which is suitable for himself/herself when he/she planned to go to some place. Actually, there are another routes which can be taken for a same destination. Whenever there is a detour for a closed road or a change in direction (one way or two way) he/she can still take the other routes. This situation will be oke if there is only few people uses the roads. Unfortunately there are many people uses the same roads and perhaps the same routes. This will lead to traffic jams in several roads and cause problems for transportation. This study used modified generate and test algorithm to analyse the possible routes and which roads are passed more frequent. This algorithm is based on directed graph from graph theory. The algorithm is implemented to a real spatial data (georeferenced digital roads) and used Geographical Information System application script (ArcView Avenue) for the analysis. The area for these study is bounded by ringroads (north, east, south, and west) in Yogyakarta Province. The experiments was conducted for several conditions, i.e. close one road, change two-way into one-way road and applied to several start and finish selections. These experiments gave good results and with simple interpretation, information of vital roads rank when they are closed or changed in directions can be viewed.
Keywords: route, road, geographical information system
D ‐ 1
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
PENDAHULUAN Latar Belakang Jalan merupakan sarana transportasi yang sangat vital karena menghubungkan suatu tempat tertentu ke tempat lain. Dengan adanya sarana ini, manusia dapat berpindah dari satu tempat ke tempat lain. Barang-barang komoditas juga dapat dipindahkan atau didistribusikan lewat sarana jalan ini. Untuk pergi ke tempat pekerjaannya, manusia juga memerlukan sarana jalan. Demikian pula untuk melakukan aktivitas lainnya. Namun demikian, ada jalan dengan kondisi baik dan ada pula jalan dengan kondisi buruk atau rusak. Ada yang lebar, halus, ada penerangan di waktu malam, tetapi juga ada yang dengan kondisi sebaliknya. Hal-hal ini menjadi pertimbangan manusia ketika harus menentukan atau memilih rute yang harus dilewati ketika akan bepergian ke suatu tempat. Seseorang tentu memilih jalan yang menurutnya paling nyaman. Kenyamanan ini bisa berarti jaraknya dekat, atau bebas hambatan seperti misalnya hanya ada sedikit lampu lalu-lintas yang dilewati. Dengan memperhitungkan kenyamanan inilah, maka orang akan menentukan rute yang akan dilewati ketika ia harus bepergian. Bila hanya ada satu orang yang mempergunakan jalan yang tersedia, rute manapun yang dipilih tentu tak menjadi masalah. Masalah akan timbul jika ternyata ada banyak orang yang memiliki kepentingan yang sama, yaitu memilih rute yang sama. Jalan menjadi macet dan akibatnya kenyamanan menjadi berkurang. Selain kemacetan karena banyak orang memilih jalan atau rute yang sama, pengalihan rute dengan penutupan jalan atau membuat jalan menjadi satu arah, karena sesuatu alasan, juga akan menimbulkan banyak masalah dalam hal transportasi.
Rumusan Masalah Sebagai sarana yang vital, jalan-jalan yang tersedia haruslah dimanfaatkan sebaik-baiknya untuk kepentingan manusia dengan segala aktivitasnya. Pengalihan rute dengan penutupan jalan atau membuat jalan menjadi satu arah, akan berdampak pada kelancaran transportasi. Dengan memperhatikan dampak tersebut, perlulah dilakukan suatu analisis rute dan jalan terpilih ketika seseorang akan melakukan suatu perjalanan.
Batasan Masalah Penelitian ini membatasi masalah dengan: (a) daerah penelitian berada dalam batas jalanlingkar (utara, timur, selatan, dan barat) dalam Daerah Istimewa Yogyakarta, (b) pencarian rute perjalanan tidak memperhitungkan panjang jalan, lebar jalan, waktu tempuh, rambu-rambu dan lampu-lampu lalu lintas, serta kondisi jalan, dan (c) memungkinkan adanya penentuan satu arah atau dua arah, serta penutupan jalan.
D ‐ 2
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
Tujuan Penelitian Tujuan penelitian ini adalah untuk (a) menghitung kemungkinan rute atau jalan yang mungkin dipilih oleh seseorang dalam melakukan perjalanan dengan menggunakan algoritma generate and test termodifikasi, (b) memvisualisasikan secara riil rute atau jalan tersebut dengan memanfaatkan aplikasi Sistem Informasi Geografis ArcView, dan (c) menganalisis dampak pengalihan rute dengan melakukan penutupan jalan.
LANDASAN TEORI Pada penelitian ini, digunakan Algoritma Generate & Test termodifikasi untuk pencarian semua rute yang mungkin. Pada prinsipnya algoritma ini merupakan penggabungan antara Depth First Search dengan pelacakan mundur (Backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan tertentu. Nilai pengujian berupa jawaban ‘ya’ atau ‘tidak’ (Dewi dan Purnomo, 2005). Algoritmanya adalah sebagai berikut : Misalkan awal adalah “Start” dan akhir adalah “Finish”, maka : 1. Pada langkah pertama adalah masukan node yang dijadikan sebagai “Start”(node awal), pada suatu tampungan data berupa Stack atau tumpukan, selanjutnya diberi nama Stack1. 2. Kemudian pada langkah kedua ambil node dari Stack1, kemudian dijadikan sebagai Node Awal. •
Jika tidak ada node yang dapat dijadikan sebagai Node Awal, maka berhenti dari pencarian, karena Stack1 kosong.
•
Jika ada, lanjut ke langkah tiga.
3. Kemudian pada langkah ini adalah melakukan pengecekan dari setiap node yang merupakan kemungkinan solusi selanjutnya. •
Jika didapatkan node yang merupakan solusi selanjutnya, simpan node tersebut di dalam Stack1. Jika tidak, lakukan backtracking sampai pada node pada Stack2. Jika Stack2 kosong, maka lakukan langkah pertama. Jika tidak, lanjut ke langkah empat.
•
Jika jumlah node yang ditemukan lebih dari 1, simpan Node Awal pada tempat tampungan data berupa tumpukan, selanjutnya diberi nama Stack2. Jika tidak lanjut ke langkah empat.
4. Pada langkah keempat dilakukan pengujian untuk melihat apakah node tersebut benarbenar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
D ‐ 3
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
•
Jika solusi ditemukan, (sama dengan node “Finish”), simpan hasil di tabel tampung, kemudian lakukan backtracking sampai pada node yang ada pada Stack2. Ulangi langkah kedua
•
Jika tidak, lakukan langkah 2.
Contoh Penerapan: Misalkan ada segmen jalan berarah (directed) yang terlihat pada Gambar 1, jika A terpilih sebagai “Start” dan J sebagai “Finish”. Pertanyaannya rute mana saja yang mungkin dilalui dari A untuk menuju J, dengan kondisi jalan tersebut?
Gambar 1. Contoh Kasus 1
Penyelesaiaan dari contoh kasus 1 adalah sebagai berikut : •
Pertama-tama semua node dalam kondisi “False(F)”, kemudian pada jalan A, dipilih node 1 sebagai kondisi awal (Start), dan pada jalan J dipilih node 8 sebagai kondisi akhir (Finish). Kemudian menyimpan node yang terpilih sebagai Start (node 1) ke dalam tumpukan (diberi nama Stack1) dan siapkan tumpukan satu lagi, kemudian disebut Stack2.
•
Ambil node dari Stack 1, kemudian node tersebut dijadikan sebagai Node Awal. Berilah status “True(T)” pada node ini, untuk menandakan bahwa node ini telah dilalui.
•
Cari semua node yang bersambungan langsung dengan node 1 dan didapat node 2 dan node 3. Simpan node 2 dan node 3 ke dalam Stack1. Karena node 1 mempunyai sambungan lebih dari 1, maka simpan node 1 ke Stack2.
•
Pilih node baru yang akan dijadikan sebagai Node Awal dari Stack1. Node yang terpilih berdasarkan sifat tumpukannya, yakni last in first out (LIFO). Misalkan yang terpilih adalah node 3, maka yang tersambung dengan node ini adalah node 5 dari semua node yang ada. D ‐ 4
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
•
Kemudian simpan node 5 ke dalam Stack1, selanjutnya pilih node baru lagi yang dijadikan sebagai Node Awal, dan seterusnya sampai Node Awal merupakan node yang dijadikan Finish (node 8).
•
Jika Node Awal merupakan Finish, simpan hasil rute pada tabel penampungan, kemudian lakukan backtracking dari node 8 sampai node yang ada pada Stack2 (node 1), selanjutnya ambil node baru dari Stack1 (node 2) untuk dijadikan sebagai Node Awalnya, dan seterusnya. backtracking dilakukan dengan cara merubah status node dari T menjadi F sampai node tertentu. Tujuannya agar node tersebut dapat digunakan kembali oleh rute yang lain.
•
Jika Node Awal sudah tidak ada node yang dapat dihubungkan lagi, maka lakukan backtracking dari node tersebut sampai node dari Stack2, kemudian ambil node dari Stack1 untuk dijadikan Node Awal lagi, dan seterusnya dilakukan berulang-ulang sampai Node Awal kosong.
•
Jika Stack2 kosong, maka lakukan pengambilan node baru pada Stack1 tanpa melakukan backtracking, dan seterusnya. Jika Node Awal tidak dapat mengambil node dari Stack1, maka berhenti dari pencarian rute.
Hasil rute yang terpilih dari setiap langkah ditunjukkan pada Tabel 1
Tabel 1. Proses Pencarian Rute pada Contoh Kasus 1 Node (F)
Stac k1
Stack 2
Node Awal
Hasil Rute (T)
Gambar Hasil Rute
2, 3, 4, 5, 6, 7, 8
1
0
-
-
-
2, 3, 4, 5, 6, 7, 8
0
0
1
1
4, 5, 6, 7, 8
2, 3
1
1
1
4, 5, 6, 7, 8
2
1
3
1, 3
4, 5, 6, 7, 8
2, 5
1
3
1, 3
4, 6, 7, 8
2
1
5
1, 3, 5
D ‐ 5
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
4, 7, 8
2, 6
1
5
1, 3, 5
4, 7, 8
2
1
6
1, 3, 5, 6
4, 8
2, 7
1
6
1, 3, 5, 6
4, 8
2
1
7
1, 3, 5, 6, 7
8
2, 4
1
7
1, 3, 5, 6, 7
8
2
1
4
1, 3, 5, 6, 7, 4
-
2, 8
1
4
1, 3, 5, 6, 7, 4
-
2
1
8
1, 3, 5, 6, 7, 4, 8
ISSN : 1978 – 9777
Simpan hasil rute – backtracking dari node 8 sampai dengan node 1 3, 4, 5, 6, 7, 8
-
-
2
1, 2
3, 5, 7, 8
6, 4
2
2
1, 2
3, 5, 7, 8
6
2
4
1, 2, 4
3, 5, 7
6, 8
2
4
1, 2, 4
D ‐ 6
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007 3, 5, 7
6
2
8
ISSN : 1978 – 9777
1, 2, 4, 8
Simpan hasil rute – backtracking dari node 8 sampai dengan node 2 3, 4, 5, 7, 8
-
-
6
1, 2, 6
3, 4, 5, 8
7
-
6
1, 2, 6
3, 4, 5, 8
-
-
7
1, 2, 6, 7
3, 5, 8
4
-
7
1, 2, 6, 7
-
4
1, 2, 6, 7, 4
-
4
1, 2, 6, 7, 4
-
8
1, 2, 6, 7, 4, 8
3, 5, 8
3, 5
3, 5
-
8
-
Simpan rute – tidak melakukan backtracking, karena Stack2 kosong 3, 5
-
-
-
1, 2, 6, 7, 4, 8
Berhenti dari pencarian rute, karena Node Awal kosong
D ‐ 7
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
METODE PENELITIAN Data Spasial Data spasial (georeferenced) jalan-jalan di daerah penelitian diperoleh dari Badan Koordinasi Survei dan Pemetaan Nasional (Bakosurtanal). Data jalan yang tersedia kemudian dicek dengan kondisi di lapangan dengan menggunakan GPS (Global Positioning System), apakah koordinatnya sudah sesuai. Hanya data jalan yang representatif (tidak termasuk jalan kecil atau gang) yang kemudian dipakai dan diberi label nama jalan.
Uji Implementasi Algoritma Uji implementasi algoritma dilakukan dengan memilih area yang kecil, sehingga dapat terlihat secara visual, kemungkinan-kemungkinan rute yang terpilih. Uji ini juga dilakukan untuk memilih start dan finish dari arah utara ke selatan dan dari barat ke timur, dan dengan menentukan penutupan jalan, serta pengubahan arah jalan (dari satu ke dua dan sebaliknya).
HASIL DAN PEMBAHASAN Sebagai contoh, diambil perjalanan dengan start dari Jalan Sunaryo (segmen 2) dan finish di Jalan A. Jazuli (segmen 3). Banyak rute yang mungkin yang dihasilkan adalah 14, dan dari semua kemungkinan ini, ada jalan yang dilalui sebanyak 8 kali, 7 kali dan 6 kali (Gambar 2 a). Semakin banyak jalan tersebut dilalui (dengan nilai maksimum sebanyak rute-rute yang mungkin), berarti semakin vital jalan tersebut. Jadi segmen jalan yang dilalui sebanyak 8 kali merupakan jalan yang cukup vital dan misalnya terjadi penutupan pada jalan tersebut maka ada beberapa rute yang akan hilang. Gambar 2b menunjukkan adanya penutupan Jalan Nyoman Oka (segmen 3) yang mengakibatkan perubahan kemungkinan rute (menjadi 6) dan jalan-jalan yang dilalui (menjadi 6, 4, 3, dan 2 kali). Pada kondisi seperti ini, jalan yang cacah dilaluinya sebanyak rute yang mungkin (6) merupakan jalan yang paling vital dan bila ini ditutup, maka tak akan ada rute yang terbentuk.
(a)
(b)
D ‐ 8
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
Gambar 2. (a) Hasil pencarian rute-rute yang mungkin dan cacah pilihan jalan dari setiap rute, (b) kondisi dengan penutupan segmen jalan Secara prinsip penelitian ini dapat menghasilkan apa yang diinginkan, meskipun memerlukan interpretasi yang lebih lanjut dari hasil yang diperoleh. Selain itu, dalam pemrosesan dengan data spasial yang riil, masih ada kendala yaitu waktu yang relatif lama (dalam orde menit). Tampaknya masih dapat dicari lagi langkah-langkah pemrograman yang memanfaatkan memori komputer, agar proses dapat dilakukan lebih cepat. Dengan kondisi pemrosesan yang relatif lama yang digunakan pada penelitian ini, maka untuk mengurangi waktu proses, digunakan trik yaitu dengan membatasi area pencairan. Pembatasan ini dilakukan dengan menentukan lebar (width) pencarian dari jalur lurus awal sampai akhir. Manusia juga menggunakan teknik ini ketika harus menghindari jalan yang ditutup, yaitu berusaha tidak menyimpang terlalu jauh dari rute semula. Trik ini cukup efektif untuk menghemat waktu proses, sehingga eksperimen dengan berbagai kondisi jalan (satu/dua arah dan penutupan) dapat dilakukan dengan waktu yang relatif lebih cepat. KESIMPULAN Hasil penelitian ini menunjukkan bahwa (a) algoritma yang dipakai dalam menentukan ruterute yang mungkin untuk suatu perjalanan dapat diimplementasikan langsung pada data spasial yang riil, (b) hasil rute-rute yang terpilih serta cacah pilihan pada suatu jalan dapat dilihat secara visual, dan (c) pengguna dapat menganalisis secara visual dampak pengalihan jalan atau perubahan arah (satu ke dua, dan sebaliknya) dengan melihat pada informasi di layar monitor atau printout. Penelitian ini masih dapat dikembangkan baik dari segi pemrosesan data maupun cara menampilkan informasi untuk secara langsung memberikan petunjuk jalan-jalan yang langsung terkena dampak apabila ada perubahan kondisi di suatu jalan tertentu, sehingga tidak memerlukan interpretasi yang lama. DAFTAR PUSTAKA Dewi, SK dan Purnomo, H. (2005). Penyelesaian Masalah Optimasi Dengan Teknik-teknik Heuristik. Graha Ilmu, Yogyakarta. Deo, N. (1987). Graph Theory with Applications to Engineering and Computer Science. PrenticeHall of India, New Delhi. Paryono, P. (1994). Sistem Informasi Geografis. Andi Offset, Yogyakarta. Prahasta, E. (2005). Konsep-Konsep Dasar Sistem Informasi Geografis. CV Informatika, Bandung, Edisi Revisi, Cetakan kedua. Prahasta, E. (2005). Sistem Informasi Geografis: Tutorial ArcView. CV Informatika, Bandung, Cetakan ketiga.
D ‐ 9
Seminar Nasional Teknologi 2007 (SNT 2007) Yogyakarta, 24 November 2007
ISSN : 1978 – 9777
Prahasta, E. (2003). Sistem Informasi Geografis: ArcView Lanjut Pemrograman Script Avenue. CV Informatika, Bandung, Cetakan pertama. Wilson (2007). Analisis Frekuensi Rute Dengan Modifikasi Algoritma Generate & Test di Kota Yogyakarta Berbasis Sistem Informasi Geografis. Skripsi. Program Studi Teknik Informatika, Universitas Kristen Duta Wacana, Yogyakarta.
D ‐ 10
