Analisis Perbandingan Algoritma Djikstra dan Algoritma Ant Colony Optimization dalam Optimasi Pencarian Rute Distribusi Barang (Studi Kasus: Toko Basmalah Region Jember)

Abstract

Traveling Salesman Problem is an optimization problem to find the shortest route for a salesman to visit all points exactly once and then return to the point of origin. One of the activities included in the traveling Salesman Problem is product distribution. PT. Sidogiri Mandiri Utama also carries out distribution activities for mineral water products. The high demand for mineral water makes the distribution process a very important activity for the company. In the interviews conducted, problems were found, namely the number of distribution routes that had to be chosen by a courier and congestion. For this reason, an optimal route is needed so that the distribution process can run efficiently in terms of time and cost by using the Dijsktra algorithm and the Ant Colony Optimization algorithm. The two algorithms will be compared to find out which has better in finding the optimal route in the following stages: 1. Data Collection; 2. Data Analysis; 3. Algorithm Implementation; 4. Calculation of Cost and Time; 5. Comparative Analysis. The data to be used in this research is product distribution route data at PT. Sidogiri Mandiri Utama headed to the Basmalah store located in Jember Regency, distribution vehicles, distribution routes, travel time, and distribution costs. This research also uses the Google Maps platform to get details on the location of the research object. The implementation of both algorithms uses graphs and mathematical calculations with predetermined parameters. This research produces the optimal distribution route by Dijsktra's algorithm over a distance of 242km. And the distribution route generated by the ACO calculation has a distance of 260km. The travel time for the Dijsktra algorithm distribution route takes 5 hours and 22 minutes, which is shorter than the travel time for the ACO algorithm distribution route, which is 5 hours and 45 minutes. The distribution costs incurred when taking the Dijsktra algorithm's optimal route are Rp. 334,267, while the ACO algorithm requires a distribution fee of Rp. 354,667. From the distance traveled, travel time, and costs required during the distribution process, it can be concluded that Dijkstra's algorithm is more optimal than the Ant Colony Optimization algorithm.