Shortest path atau rute terpendek merupakan permasalahan yang dapat menemukan rute dalam graf dengan bobot sisi tertentu yang memiliki total bobot minimum, banyak algoritma yang dapat digunakan untuk mengatasi permasalahan rute terpendek ini salah satunya pada penelitian ini yang menerapkan algoritma Dijkstra dalam menentukan rute terpendek untuk kurir J&T Rungkut, Surabaya, dalam konteks Travelling Salesman Problem (TSP). Algoritma Dijkstra dipilih karena kemampuannya dalam menyelesaikan masalah rute terpendek pada graf berbobot dan berarah dengan bobot positif. Penelitian ini bertujuan untuk mengetahui berapa efisiensi Algoritma Dijkstra dalam menentukan rute terpendek, dengan menampilkan peta interaktif yang mempertimbangkan jarak tempuh sehingga berguna untuk mengoptimalkan pekerjaan kurir dalam mengantar barang. Hasil penelitian menunjukkan bahwa algoritma Dijkstra secara konsisten meningkatkan efisiensi jarak yang diambil oleh kurir, dengan tingkat efisiensi jarak yang bervariasi dari 1,4% pada skenario 1 kurir 9 yang merupakan efisiensi jarak terendah hingga efisiensi jarak tetinggi yaitu 48,6% pada skenario 3 kurir 10. Sehingga rata-rata dari semua skenario menghasilkan efisiensi jarak sebesar 21,82% jika menggunakan algoritma Dijkstra dalam mencari rute terpendek. Dalam tiga skenario yang dianalisis, algoritma Dijkstra menunjukkan potensi yang signifikan dalam memberikan solusi rute terpendek dibandingkan rute kurir itu sendiri. Oleh karena itu, pemilihan metode yang tepat harus mempertimbangkan kondisi spesifik untuk mencapai hasil yang optimal. Penelitian ini dapat memberikan kontribusi signifikan dalam petunjuk rute pengiriman bagi perusahaan jasa pengiriman dan dapat diimplementasikan secara luas.


Deskripsi Lain

The shortest path problem involves finding a route in a graph with specified edge weights that has the minimum total weight. Many algorithms can address this shortest path problem, one of which is the Dijkstra algorithm, used in this study to determine the shortest path for J&T couriers in Rungkut, Surabaya, within the context of the Traveling Salesman Problem (TSP). The Dijkstra algorithm is chosen for its ability to solve shortest path problems on weighted, directed graphs with positive weights. This study aims to evaluate the efficiency of the Dijkstra algorithm in determining the shortest path by presenting an interactive map that considers travel distances, thereby optimizing the courier’s delivery work. The results show that the Dijkstra algorithm consistently improves the efficiency of the distance traveled by couriers, with distance efficiency varying from 1.4% in Scenario 1 (courier 9), the lowest distance efficiency, to a maximum of 48.6% in Scenario 3 (courier 10). The average efficiency across all scenarios is 21.82% when using the Dijkstra algorithm to find the shortest path. In the three scenarios analyzed, the Dijkstra algorithm demonstrated significant potential in providing shorter routes compared to the couriers’ own routes. Therefore, choosing the appropriate method should consider specific conditions to achieve optimal results. This research can make a significant contribution to route guidance for delivery companies and can be implemented broadly.

• “Penentuan Jalur Terpendek Untuk Mempersingkat Waktu Dan Biaya Distribusi Dengan Menggunakan Metode Algoritma Ant Colony” ( Studi Kasus di CV. Citra Kencana Bakery )
• Penyelesaian Travelling Salesman Problem (TSP) Untuk Pendistribusian Barang Menggunakan Algoritma Particle Swarm Optimization (PSO) (Studi Kasus : PT. Lukindari Permata Sidoarjo)
• TRAVELLING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA DIJKSTRA (Studi Kasus J&T Rungkut, Surabaya)