Penerapan Algoritma Dijkstra yang Dimodifikasi untuk Pencarian Rute Terpendek pada Graf Hamiltonian

Gunawan, Nebula Labama (2024) Penerapan Algoritma Dijkstra yang Dimodifikasi untuk Pencarian Rute Terpendek pada Graf Hamiltonian. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5002201078-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (3MB)

Abstract

Penelitian ini bertujuan untuk mengembangkan dan menerapkan Algoritma Dijkstra yang dimodifikasi untuk pencarian rute terpendek pada graf Hamiltonian, dengan fokus pada rute pengiriman di Kabupaten Sidoarjo, Jawa Timur. Latar belakang penelitian ini didasarkan pada kebutuhan akan kecepatan pengiriman dalam layanan pengiriman barang, yang dapat dicapai melalui pencarian rute pengiriman terpendek. Metodologi yang digunakan meliputi pengembangan program dengan memodifikasi Algoritma Dijkstra dan penerapan Algoritma K-means untuk clustering graf dengan banyak simpul. Implementasi program dilakukan dalam beberapa tahap, termasuk pembuatan graf, clustering, pencarian rute terpendek intra-cluster dan inter-cluster,integrasi rute, dan visualisasi rute. Hasil penelitian menunjukkan bahwa Algoritma Dijkstra yang dimodifikasi dapat diterapkan dan mampu menghasilkan rute terpendek yang mampu menyelesaikan pencarian jalur terpendek pada graf Hamiltonian dibandingkan dengan Algoritma Dijkstra konvensional. Pembahasan dan hasil mencakup perbandingan jarak tempuh pada rute terpendek dan kelengkapan simpul yang dilewati antar dua algoritma. Kesimpulan dari penelitian ini adalah bahwa modifikasi Algoritma Dijkstra yang dikombinasikan dengan strategi clustering menggunakan Algoritma K-means mampu menyelesaikan pencarian rute terpendek pada graf Hamiltonian yang merepresentasikan rute pengiriman di Sidoarjo. Penelitian ini memberikan kontribusi bagi pengembangan teori graf dan algoritma dalam konteks pengiriman barang, serta dapat menjadi referensi bagi penelitian selanjutnya yang berfokus pada optimasi rute dan penerapan teknik clustering dalam berbagai bidang.
==============================================================================================================================
This research aims to develop and apply a modified Dijkstra’s Algorithm for shortest route search on Hamiltonian graphs, focusing on delivery routes in Sidoarjo Regency, East Java. The background of this research is based on the need for speed of delivery in goods delivery services, which can be achieved through finding the shortest delivery route. The methodology used includes program development by modifying Dijkstra’s Algorithm and applying K-means Algorithm for clustering graphs with many vertices. The program implementation is done in several steps, including graph generation, clustering, intracluster and intercluster shortest route search, route integration, and route visualization. The results show that the modified Dijkstra’s Algorithm can be applied and is able to produce shortest routes that are able to solve the shortest path search on Hamiltonian graphs compared to the conventional Dijkstra’s Algorithm. The discussion and results include a comparison of the travel distance on the shortest route and the completeness of the nodes passed between the two algorithms. The conclusion of this research is that the modification of Dijkstra’s Algorithm combined with the clustering strategy using the K-means Algorithm is able to solve the shortest route search on the Hamiltonian graph that represents the delivery route in Sidoarjo. This research contributes to the development of graph theory and algorithms in the context of goods delivery, and can be a reference for further research that focuses on route optimization and the application of the clustering technique in various fields.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Teori Graf, Rute Terpendek, Rute Pengiriman, Algoritma Dijkstra, Modifikasi Algoritma Dijkstra, K-means, Graph Theory, Shortest Route, Delivery Service Route, Dijkstra Algorithm, Modified Dijsktra Algorithm
Subjects:	T Technology > T Technology (General)
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Nebula Labama Gunawan
Date Deposited:	23 Aug 2024 04:35
Last Modified:	23 Aug 2024 04:35
URI:	http://repository.its.ac.id/id/eprint/115296

Actions (login required)

View Item