PERBANDINGAN RUTE OPTIMUM HASIL PERHITUNGAN ALGORITMA DIJKSTRA DAN A* UNTUK SIRKULASI PAKET JASA EKSPEDISI JNE DI D.I. YOGYAKARTA

LATIEF ZAINULHAYAT, Dr. Taufik Hery Purwanto, M.Si.

2017 | Skripsi | S1 KARTOGRAFI DAN PENGINDRAAN JAUH

Meningkatnya aktivitas perdagangan antar daerah menuntut jasa pengiriman barang untuk memenuhi kebutuhan tersebut. Kondisi lalu lintas D.I Yogyakarta yang semakin padat menghambat Jalur Nugraha Ekakurir (JNE) sebagai salah satu penyedia jasa pengiriman paket terbesar di Indonesa untuk menjaga ketepatan waktu pengiriman. Penentuan rute optimum menggunakan Sistem Informasi Geografi merupakan solusi untuk mengatasi masalah tersebut. Proses dan hasil penentuan rute dipengaruhi algoritma yang bekerja di belakangnya. Penelitian ini bertujuan untuk mengetahui kemampuan algoritma Dijkstra dan A* (A-star) untuk menentukan rute optimum sirkulasi paket JNE di D.I Yogyakarta serta membandingkan proses dan hasil rute optimumnya. Perbandingan rute dilakukan secara kualitatif berdasarkan kenampakan spasial rute dan secara kuantatif berdasarkan waktu proses serta jumlah ruas jalan yang terpilih. Data jaringan jalan dikoreksi topologi agar konektivitas simpul tiap ruas jalan dan elemen jaringan yang lain saling terhubung. Implementasi algoritma pencarian rute Dijkstra dan A* dilakukan pada pengolahan basisdata menggunakan sistem basisdata PostgreSQL dan PostGIS untuk data spasial. Sebagai parameter impedansi, digunakan waktu tempuh rencana dari tiap ruas jalan yang memperkirakan waktu yang dibutuhkan untuk mencapai lokasi tujuan. Skenario rute yang dibuat semuanya dapat diselesaikan dengan baik oleh algoritma Dijkstra maupun A*. Rute optimum dari semua skenario dengan impedansi yang sama untuk setiap ruas dalam jaringan yang ada menunjukkan persamaan hasil dari algoritma Dijkstra dan A*. Namun perbedaan prinsip kerja keduanya menjadikan kecepatan proses perhitungan algoritma tersebut berbeda. Algoritma A* (best-first search) yang menggunakan koordinat setiap node untuk memperkirakan arah menggunakan waktu proses hingga 13% lebih cepat dibandingkan dengan algoritma Dijkstra (greedy) yang rakus dan tanpa pertimbangan spasial.

The inter-regional trade activity which is growing up today, has made linier impact for courier services company to support this activity. In PT. JNE outbound process, their pick-up drivers need optimum route to reach the warehouse based on schedule. GIS provide a solution to determine optimum route using network analyst and shortest-path finding. Optimum route calculation process and results based on shortest-path algorithm that works behind. This study aims to compare Dijkstra and A* (A-star) algorithm in finding optimum route calculations of PT. JNE pick-up-driver outbound process in D.I.Yogyakarta. Route comparisons conducted qualitatively by its spatial appearance and quantitatively based on processing time and the number of selected road segments. Topological correction was used for the road network data, so that each nodes and other network elements were connected. Dijkstra and A-Star algorithm was analyzed using PostGIS spatial database in PostgreSQL database system. Scenarios were made using travel-time scheme of each road network, defined as impedance parameter which estimates required time for pick-up-driver to reach warehouse as the destination from their agents location. All of the scenarios were solved by Dijkstra and A-star algorithm. Both of the algorithm have same optimum route results for each scenario. However, the methods between these algotihm is different especially in the processing time part. The A-star algorithm (best-first search) used each node�s coordinates to estimate the direction, so the processing time is +/-13% faster than Dijkstra's algorithm (greedy-algorithm) which is not using any spatial-considerations.

Kata Kunci : rute optimum, Dijkstra, A-star, JNE