Pengembangan Sistem Rekomendasi Rute Paling Optimum dengan Algoritme Voronoi Continuous K Nearest Neighbor (VCKNN), Progressive Incremental Network Expansion (PINE), Voronoi-Based Network Nearest Neighbor (VN3), Berbasis WebGIS

Wicaksono, Fajar Krisna (2018) Pengembangan Sistem Rekomendasi Rute Paling Optimum dengan Algoritme Voronoi Continuous K Nearest Neighbor (VCKNN), Progressive Incremental Network Expansion (PINE), Voronoi-Based Network Nearest Neighbor (VN3), Berbasis WebGIS. Sarjana thesis, Universitas Brawijaya.

Abstract

Dalam kesehariannya, masyarakat di Kota Malang sering melakukan perjalanan dari satu tempat ke tempat lain dengan mempertimbangkan efesiensi waktu perjalanan. Kecamatan Lowokwaru adalah salah satu kecamatan yang cukup padat di Kota Malang, dengan pertumbuhan penduduk yang relatif cepat. Oleh karenanya, sering terjadi kemacetan di titik-titik tertentu dan pada waktu tertentu. Pencarian jalur dapat menjadi salah satu solusi dalam menangani kemacetan pada waktu-waktu tertentu di Kota Malang. Beberapa diatara algoritme untuk menyelesaikan masalah pencarian rute, yakni Voronoi-Based Continuous k Nearest Neighbor (VCKNN), Progressive Incremental Network Expansion (PINE), Voronoi-Based Network Nearest Neighbor (VN3). Setiap algoritme memiliki langkah-langkah perhitungan serta model data yang berbedabeda, hal ini berpengaruh kepada waktu komputasi pada setiap algoritme yang mempengaruhi response time dari sistem. Pada penelitian ini menggunakan algoritme VCKNN, PINE dan VN3, pada algoritme tersebut sudah menggunakan poligon vororoi untuk melakukan pengelompokan data, sehingga perhitungan jaringan jalan lebih efisien. Pada algoritme VCKNN, PINE dan VN3, proses pencarian rute dibagi menjadi 2 tahap, yang pertama mencari tetangga voronoi untuk menyaring data berdasarkan poligon voronoi, setelah itu mencari rute pada poligon voronoi tersebut. Penelitian ini dilakukan untuk mengetahui berapakah response time, jumlah node yang dilalui serta hubungan antara response time dengan jumlah node yang dilalui sehingga diketahui algoritme yang paling efisien dalam masalah pencarian rute. Dari penelitian diketahui bahwa algoritme dengan response time tercepat yaitu algoritme VCKNN dengan response time 0.071 detik dan algoritme dengan jumlah node yang dilalui paling sedikit yaitu algoritme PINE dengan jumlah node yang dilalui 17 node. Pada perbandingan algoritme VCKNN dengan VN3 didapatkan hasil bahwa jumlah node yang dilalui mempengaruhi response time, sedangkan pada perbandingan VCKNN dengan PINE dan PINE dengan VN3 response time yang dilalui tidak mempengaruhi response time, hal ini dikarenakan terdapat proses untuk mencari move interval terlebih dahulu pada algoritme PINE. Dari keseluruhan hasil penelitan didapatkan algoritme yang paling efisien dalam penentuan rute optimum adalah algoritme VCKNN.

English Abstract

In daily life, people in Malang often travel from one place to another by considering the efficiency of travel time. Lowokwaru is one of the densely populated subdistricts in Malang City, with relatively fast population growth. Therefore, traffic jam often occurs frequently at certain time. Path searching is one of the solutions in handling traffic jam at certain time in Malang. There are several algorithms for solving route searching problems such as Voronoi-Based Continuous k Nearest Neighbor (VCKNN), Progressive Incremental Network Expansion (PINE), Voronoi- Based Network Nearest Neighbor (VN3). Every algorithm has different calculation steps and data models, it affects the computing time of every algorithm that affects the response time of the system. This research uses the VCKNN, PINE and VN3 algorithms, it already uses the voronoi polygon to perform data groupings, so the calculation of the road network is more efficient. In the VCKNN, PINE and VN3 algorithms, the route searching process is divided into two stages, the first stage is searching for the voronoi neighbor to filter the data based on the voronoi polygon, after that, it searches the route on the voronoi polygon. This research was conducted to find out the response time, the number of passed node and the relationship between response time and the number of passed node, so the most efficient algorithm in the problem of route searching was known. From this research it was known that the algorithm with the fastest response time was VCKNN algorithm with 0.071 seconds response time and the algorithm with the lowest number of passed node was PINE algorithm with the number of nodes passed by 17 nodes. In comparison of VCKNN and VN3 algorithm it was found that the number of passed node affects the response time, whereas in comparison of VCKNN with PINE and PINE with VN3, the passed response time did not affect the response time, it happened because there was a process to find the move interval first on the PINE algorithm. From the results of the research, the most efficient algorithm in determining the optimum route was the VCKNN algorithm.

Item Type: Thesis (Sarjana)
Identification Number: SKR/FTIK/2018/614/051808470
Uncontrolled Keywords: Sistem Rekomendasi Rute, Algoritme Voronoi Continuous K Nearest Neighbor (VCKNN), Progressive Incremental Network Expansion (PINE), Voronoi-Based Network Nearest Neighbor (VN3), WebGIS
Subjects: 300 Social sciences > 388 Transportation
Divisions: Fakultas Ilmu Komputer > Sistem Informasi
Depositing User: Budi Wahyono Wahyono
Date Deposited: 08 Apr 2019 03:13
Last Modified: 21 Oct 2021 06:03
URI: http://repository.ub.ac.id/id/eprint/161452
[thumbnail of Fajar Krisna Wicaksono.pdf]
Preview
Text
Fajar Krisna Wicaksono.pdf

Download (8MB) | Preview

Actions (login required)

View Item View Item