Paralelisasi Algoritma Multi-Objective A* untuk Pencarian Rute Optimal Pada Jaringan Jalan Kota Surabaya

Triwanto, Triwanto (2026) Paralelisasi Algoritma Multi-Objective A* untuk Pencarian Rute Optimal Pada Jaringan Jalan Kota Surabaya. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5002221070-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (16MB) | Request a copy

Abstract

Perencanaan rute optimal multi objektif pada sistem transportasi cerdas digunakan agar kendaraan otonom dapat bergerak lebih efisien dan aman. Algoritma perencanaan rute multi objektif pada berbagai penelitian sebelumnya masih terbatas pada pendekatan berbasis pembobotan tunggal (weighted-sum) dan algoritma yang kurang efisien secara komputasi. Penelitian ini mengimplementasikan framework paralelisasi CPU pada algoritma pencarian rute multi objektif untuk menyelesaikan permasalahan optimasi rute kendaraan otonom pada jaringan jalan Kota Surabaya guna meningkatkan efisiensi komputasi. Dataset primer yang digunakan dalam penelitian ini adalah SurabayaMOSPNet (Surabaya Multi Objective Shortest Path Network), yang disusun dari data jaringan jalan Kota Surabaya menggunakan OpenStreetMap (OSM), data elevasi dari Shuttle Radar Topography Mission (SRTM), dan data waktu memanfaatkan API TomTom. Dataset ini mencakup lima komponen biaya yaitu jarak, elevasi, konektivitas,jumlah persimpangan, dan waktu tempuh dalam empat skenario waktu kepadatan lalu lintas. Eksperimen dilakukan dengan membandingkan versi paralel dan sequential dari algoritma terhadap berbagai pasangan asal tujuan untuk menilai efisiensi waktu komputasi. Hasil penelitian menunjukkan bahwa penerapan paralelisasi algoritma MOA* pada dataset SurabayaMOSPNet mampu meningkatkan efisiensi pencarian rute multi kriteria melalui peningkatan speed up hingga 4.56× dan penyelesaian seluruh pasangan node uji. Sehingga berpotensi menjadi dasar bagi pengembangan sistem navigasi pada kendaraan otonom di Kota Surabaya.
=================================================================================================================================
Multi-objective optimal route planning in intelligent transportation systems is essential for enabling autonomous vehicles to operate in a safe and efficient manner. However, existing studies on multi-objective route planning algorithms remain largely limited to single-weighting (weighted-sum) approaches and algorithms that exhibit relatively low computational efficiency. To address these limitations, this study implements a CPU-based parallelization framework for a multi-objective route planning algorithm to solve the route optimization problem for autonomous vehicles on the Surabaya road network, with the objective of improving computational performance. The primary dataset proposed in this research is SurabayaMOSPNet (Surabaya Multi-Objective Shortest Path Network), which was constructed using road network data from OpenStreetMap (OSM), elevation data obtained from the Shuttle Radar Topography Mission (SRTM), and travel time information acquired through the TomTom API. The dataset incorporates five cost components, namely distance, elevation, connectivity, number of intersections, and travel time, across four traffic congestion scenarios. Experimental evaluations were conducted by comparing the parallel and sequential implementations of the algorithm over multiple origin–destination node pairs to assess improvements in computational efficiency. The experimental results show that applying the parallelized MOA algorithm to the SurabayaMOSPNet dataset significantly improves the efficiency of multi-criteria route planning, achieving a speedup of up to 4.56× while successfully solving all tested source–destination node pairs. Consequently, the proposed approach demonstrates its potential as a foundational framework for the development of navigation systems for autonomous vehicles in the City of Surabaya.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Parallelized Multi-Objective A* Search, sistem navigasi, short path problem,Surabaya Parallelized Multi-Objective A* Search, navigation system, shortest path problem, Surabaya
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA336 Artificial Intelligence Q Science > QA Mathematics > QA402.6 Transportation problems (Programming) Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.84 Heuristic algorithms. T Technology > TL Motor vehicles. Aeronautics. Astronautics > TL152.8 Vehicles, Remotely piloted. Autonomous vehicles.
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Triwanto Triwanto
Date Deposited:	29 Jul 2026 02:45
Last Modified:	29 Jul 2026 02:45
URI:	http://repository.its.ac.id/id/eprint/139382

Actions (login required)

View Item