LONTAR KOMPUTER VOL. 1 NO.1 DESEMBER 2010 ISSN: 2088-1541

PENEMUAN RUTE TERPENDEK PADA APLIKASI

BERBASIS PETA

Putu Wira Buana

Staf Pengajar Teknologi Informasi, Fakultas Teknik, Universitas Udayana E-mail : [email protected]

Abstrak

Salah satu bidang Graphical Information System (GIS) yang banyak digunakan adalah pemodelan jaringan dari dunia nyata ke dalam basis peta. Beberapa persoalan yang telah banyak dimodelkan adalah jaringan lalu lintas jalan raya, jaringan irigasi dan jaringan listrik mulai dari gardu induk sampai ke pelanggan. Hasil akhir penelitian ini akan dapat dimanfaatkan untuk pencarian rute terpendek untuk berbagai keperluan masyarakat yang saat ini dihadapkan kepada berbagai kesulitan transportasi seperti kemacetan jalan raya. Hasil pengujian dengan membuat beberapa rute dan perbandingan perhitungan telah menunjukkan hasil rute yang tepat sesuai dengan kondisi di lapangan.

Kata kunci: GIS, peta, rute terpendek, jalan raya

Abstract

Graphical Information System (GIS) is a widely used network modeling of real world into the base map. Some of the issues modelled are highway network traffic, irrigation networks and power grids ranging from substations to customers. The final results of this study will be used to search the shortest route for variety public purposes that are currently faced with the difficulties of transportation such as highway congestion. The test results by using some different routes and comparison calculations have shown the right route compared with the conditions in the field.

Keywords: GIS, maps, shortest route, highway

  • 1.    PENDAHULUAN

Salah satu bidang Graphical Information System (GIS) yang banyak digunakan adalah pemodelan jaringan dari dunia nyata ke dalam basis peta. Beberapa persoalan yang telah banyak dimodelkan adalah jaringan lalu lintas jalan raya, jaringan irigasi dan jaringan listrik mulai dari gardu induk sampai ke pelanggan. Untuk melengkapi model agar dapat dipakai sebagai mesin pengambil keputusan, aplikasi harus dilengkapi dengan algoritma yang memungkinkan untuk melakukan tracing (penelusuran dengan syarat tertentu). Salah satu contohnya adalah penerapan model tracing untuk menemukan rute terpendek dari berbagai alternatif rute yang tersedia. Sistem akan menentukan rute mana yang harus dilalui untuk mendapatkan rute terpendek ataupun waktu tempuh tercepat berdasarkan beberapa parameter seperti standar kecepatan setiap ruas, lebar jalan, kondisi jalan dan faktor hambatan seperti lampu merah.

Tracing merupakan sebuah model algoritma untuk penyelesaian berbagai masalah jaringan di dunia nyata. Penelitian tentang tracing sudah banyak dikembangkan oleh lingkungan universitas maupun lingkungan industri. Salah satu hasil pengembangan yang paling dikenal

adalah ditemukannya network analyst yang dirilis oleh ESRI (Environmental Systems Research Institute) . Aplikasi terbarunya dimunculkan dalam ESRI ArcGIS.

Penelitian ini akan memanfaatkan ESRI ArcGIS sebagai tool untuk pemodelannya dalam basis desktop. Hasil akhirnya akan dapat dimanfaatkan untuk pencarian rute terpendek untuk berbagai keperluan masyarakat yang saat ini dihadapkan kepada berbagai kesulitan transportasi seperti kemacetan jalan raya.

  • 2.    KAJIAN PUSTAKA

    • 2.1.    Graph

Graph dapat digambarkan dengan menggambar garis yang menghubungkan dua buah titik. Titik-titik yang terhubung disebut sebagai node dan garis yang menghubungkan antar dua buah titik disebut sebagai edge.

Gambar 1. Graph (undirected)


Terdapat dua macam graph berdasarkan arahnya, yaitu directed graph dan undirected graph (digraph). Directed graph adalah graph yang memiliki arah tertentu dan biasanya digambarkan dengan menambahkan tanda panah pada ujung edge. Undirected graph adalah graph yang tidak memiliki arah tertentu. Artinya pergerakan diijinkan dari satu node ke node yang lain atau sebaliknya.



Gambar 2. (a) directed graph. (b) undirected graph

Jenis dan bentuk graph dalam dunia nyata yang paling mudah ditemui adalah jalan raya dan sungai. Jalan raya dapat berupa directed atau undirected graph sedangkan sungai pada umunya adalah directed graph.

  • 2.2.    Algoritma Dijkstra

Anggap titik awal mulai sebagai starting node dan jarak Y merupakan jarak antara starting node dengan node Y.

  • a.    Tetapkan nilai jarak tentatif dari setiap node, nol untuk starting node dan infinite (tak terbatas) untuk node lain.

  • b.    Tandai semua node selain starting node sebagai node yang belum dikunjungi dan kelompokkan dalam kelompok tertentu.

  • c.    Dari node yang sedang aktif, kunjungi semua node lain yang terkait dan hitung jarak tentatif-nya (total masing-masing jarak node aktif dengan node lainnya). Jika jarak node yang diuji lebih rendah dari jarak sebelumnya, gunakan jarak tersebut sebagai jarak terpendek.

  • d.    Tandai node yang telah dikunjungi setelah semua node terkait dikunjungi.

  • e.    Node selanjutnya, adalah node yang memili jarak terpendek.

  • f.    Jika kelompok node yang belum dikunjungi habis, berarti algoritma telah selesai. Jika tidak, kembali ke langkah (c).

  • 2.3.    GIS

GIS atau Graphical Information System di definisikan sebagai kumpulan hardware (komputer), software, dan data geografis yang digunakan untuk memperoleh, meng-update, memanipulasi, menganalisa dan menampilkan semua referensi informasi geografis. Pada intinya, GIS merupakan media penyimpanan dan analisa data geograis yang diperoleh dari berbagai sumber. Developer dapat mengimplementasikan informasi yang diperoleh dalam bentuk theme dan layer, melakukan analisa data, dan kemudian menampilkannya dalam bentuk grafik.

  • 2.4.    Penentuan Rute Terpendek dengan ArcGIS

ArcGis Network Analyst merupakan salah satu extention yang disediakan pada software ArcGis yang memiliki kemampuan untuk melakukan analisa jaringan, dimana dalam melakukan analisa jaringan Network Analyst akan menemukan jalur yang paling kecil impedansinya. Yang termasuk jaringan pada Network Analyst disini yaitu seperti: jaringan jalan, jaringan kabel listrik, jaringan sungai, jaringan pipa.

Network Analyst ArcGis memiliki kemampuan untuk membuat network dataset dan melakukan analisa pada jaringan tersebut. Extention ini dibuat dengan menggunakan beberapa bagian aplikasi dari ArcGis yaitu ArcCatalog untuk membuat network dataset, ArcMap untuk melakukan analisis dan ArcToolbox untuk melakukan proses geogrosesing.

Network dataset wizard di dalam ArcCatalog akan memudahkan untuk membuat sebuah dataset dari sebuat geodatabase atau shapefile, wizard ini akan membantu untuk mengidentifikasi feature class yang akan digunakan, menetapkan aturan di dalam jaringan dan mengidentifikasi atribut di dalam jaringan (ESRI, 1998)

Network Analyst ArcGis dapat menemukan jalan terbaik dari satu lokasi ke lokasi lain atau menemukan jalan terbaik untuk mengunjungi beberapa lokasi. Lokasi dapat ditentukan secara interaktif dengan menempatkan titik-titik pada layer, dengan memasukkan alamat atau dengan menggunakan titik dalam fitur yang ada pada fitur kelas.

  • 2.5.    Database dan Aplikasi

Menurut Kadir (2001), database adalah kumpulan data dengan susunan tertentu dan telah dikelola oleh mesin database yang dikenal dengan DBMS (Database Management System). Secara umum, dikenal dua jenis database yaitu database berbasis atribut dan spatial.

Aplikasi merupakan bentuk penyajian data kepada pemakai awam dengan pendekatan user friendly sehingga mudah dipakai. Aplikasi mampu menyajikan proses-proses yang rumit ke dalam tampilan menu yang mudah dimengerti.

  • 3.    PENGEMBANGAN SISTEM

    • 3.1    Digitasi Jalan

Digitasi adalah pengambilan data dengan cara menelusuri peta yang telah ada dengan menggunakan meja gambar yang disebut Digitizer Tablet atau mengikuti gambar hasil scanner/penyiaman di layar monitor. Dengan digitasi maka obyek–obyek di peta digambarkan ulang dalam bentuk digital menggunakan peralatan meja digitasi atau bantuan mouse dan monitor.

Gambar 3. Hasil digitasi peta

Dari peta terdigitasi dibuat suatu jalan dalam bentuk garis atau disebut dengan polyline. Jalan atau polyline ini yang nantinya akan digunakan untuk melakukan analisis objek.

(a)

(b)

Gambar 4. (a) Polyline peta terdigitasi. (b) Layer jalan

Jarak dari jalan yang telah terbentuk dihitung dengan bantuan Field Calculator. Panjang jalan dihitung dengan menggunakan

Dim pCurve as ICurve

Set pCurve = [shape]

dblLength=pCurve.length

Waktu tempuh dalam menit dan detik serta kecepatan yang dihasilkan dihitung dengan

minutes = [shape_leng] / [speed]

minutes = [shape_leng]*60 / [speed]

speed=[shape_leng]/[travel_s]

Penetapan perhitungan di atas akan menghasilkan data-data yang diperlukan untuk melakukan analisa rute terpendek.

FID

Shape *

Id

Layer

speed

speed_ms

ShapeJeng

travel_s

travel_m

FNODE

TNODE

►

7

Polyline

0

Arteri Primer

7

0.116667

0.681829

5.844248

0.097404

0.097404

0.097404

O

Polyline

0

Arteri Primer

7

0.116667

28.691678

245.92867

4.098811

4.098811

4.098811

8

Polyline

0

Arteri Primer

7

0.116667

76.149081

652.706409

10.87844

10.87844

10.87844

4

Polyline

0

Arteri Primer

8

0.133333

125.560635

941.704763

15.695079

15.695079

15.695079

3 I

Polyline

0

Arteri primer

7

0.116667

124.331914

1065.702124

17.761702

17.761702

17.761702

6

Polyline

0

Arteri Primer

7

0.116667

135.595198

1162.244552

19.370743

19.370743

19.370743

5

Polyline

0

Arteri Primer

7

0.116667

226.586695

1942.171673

32.369528

32.369528

32.369528

2

Polyline

0

Arteri Primer

7

0.116667

476.715654

4086.134173

68.102236

68.102236

68.102236

1

Polyline

0

Arteri Primer

8

0.133333

731.823465

5488.675984

91.477933

91.477933

91.477933

  • Gambar 5. Data hasil pengolahan atribut

  • 3.2    Network Data Set

Pembuatan network dataset yang akan digunakan dalam analisa network analyst dilakukan pada aplikasi ArcCatalog, network dataset dapat dibuat dari data jaringan dengan format shapefile (*shp), personal geodatabase (*mdb), geodatabase (gdb) ataupun ArcSDE geodatabase. Syarat utama jaringan supaya dapat digunakan untuk membuat network dataset yaitu minimal ada satu field pada tabel atribut yang akan digunakan sebagai impedansi misalnya pada jaringan jalan atribut yang dapat digunakan yaitu panjang masing-masing ruas jalan.

  • 3.3    Analisa Rute

Analisa yang dapat dilakukan dengan menggunakan ekstensi Network Analysis pada ArcGIS adalah route analysis, untuk menentukan rute optimal terdapat dua atau lebih titik yang harus dilewati. Penentuan rute optimal tersebut dapat berdasarkan jarak, waktu, ataupun indikator-indikator lainya.

Gambar 6. Point of interest dan junction

Point of interest merupakan titik-titik lokasi yang sekiranya dapat digunakan sebagai acuan pembantu untuk menentukan titik asal maupun tujuan. Gambar 6 merupakan point of interest yang telah dibuat sebelumnya dan tersusun atas beberapa layer berbeda. Layer tersebut antara lain adalah layer jalan, layer junction, dan layer daerah wisata atau rumah sakit. Layer junction merupakan layer yang berisi persimpangan jalan dan merupakan salah satu layer penting dalam penentuan rute terpendek.

Gambar 7. Contoh hasil pemilihan rute

  • 4.    PENGUJIAN

Pengujian dilakukan dengan menggunakan dua buah titik sebagai nilai pembanding, yaitu titik A dan titik B. Titik A disimbulkan dengan warna Hijau (bawah) dan titik B dengan warna Merah (atas).

(a)                                      (b)                                   (c)

Gambar 8. (a) Rute alternatif 1; (b) Rute alternatif 1; (c) Rute alternatif 1

Tabel 1 merupakan perbandingan hasil jarak tempuh dari titik A ke titik B antara Network Analyst dengan metode Manual.

Tabel 1. Jarak tempuh. Network Analyst vs Manual

Jarak Tempuh

Route 1

Route 2

Route 3

Network Analyst

5742,67

5669,16

5070,25

Manual

5689,92

5585,23

5050,37

Tabel 2 merupakan perbandingan waktu tempuh dari titik A ke titik B antara Network Analyst dengan metode Manual.

Tabel 2. Waktu tempuh. Network Analyst vs Manual

Waktu Tempuh

Route 1

Route 2

Route 3

Network Analyst

34,67

33,53

34,55

Manual

34,36

33,01

34,36

5. KESIMPULAN

Berdasarkan pembahasan di atas diperoleh beberapa kesimpulan sebagai berikut :

  • 1.    Untuk pengembangan aplikasi tracing rute terpendek, dapat dilakukan dengan pentahapan berikut ini

  • a.    pembuatan shape file terutama untuk jalan termasuk pemberian bobot jarak dan kecepatan standar setiap rusa jalan

  • b.    Penyiapan network dataset untuk menjamin konektivitas network dengan menentukan salah satu field pada atribut jalan sebagai impedans

  • c.    Tracing rute dengan Network Analyst

  • 2.    Output dari aplikasi ini adalah berupa urutan rute dan estimasi waktu tempuh.

  • 3.    Hasil pengujian dengan membuat beberapa rute dan perbandingan perhitungan telah menunjukkan hasil rute yang tepat sesuai dengan kondisi di lapangan.

6. DAFTAR PUSTAKA

ESRI, 2008, ArcGis 9. http://webhelp.esri.com/arcgisdestop/9.2/pdf/Nework Analyst Tutorial.pdf

Galati, Stephen R., 2006. “Geographic Information Systems Demystified”. London: Arctec House.

Puntodewo,A., Dewi,S., Tarigan, J., 2003, “Sistem Informasi Geografis untuk Pengelolaan Sumber Daya Alam”, Center for International Forestry Research (CIFOR)

Kadir,A., 2002, “Perancangan Database”, Andi Offset

Demers M.N., 1997, “Fundamentals of Geographic Information Systems”, New York: Jhon Wiley & Sons

ESRI, 1998, “Arcview Network Analyst”, http://www.esri.com/library/whitepapers/ pdfs/ana0498.pdf

Penemuan Rute Terpendek Pada Aplikasi Berbasis Peta

8