Penentuan Availability Path Planning Dengan Kombinasi Algoritma Djikstra dan Algoritma Ant Colony Optimization Untuk Shortest Path

Abstract

The search for the shortest path is the search for a path in a weighted graph that minimizes the sum of the weights of the edges forming the path. Determining the shortest path also really needs a path availability analysis which will also speed up the process of finding the shortest path. That way the resulting path is the path that has the least weight or distance. Now the search for the shortest path is needed by robot-based systems, where the shortest path search system allows the system to work quickly and precisely. One application of finding the shortest path is found in airline activities where the inter-city routes that it passes will form a directed and weighted graph. From this formed graph, it will be processed using Dijkstra's algorithm and Ant Colony to determine the shortest path from one city to another. In the Algorithm process, Dijkstra needs distance data for each city before starting the algorithm process. Whereas in the Ant Colony Algorithm, it does not require the distance for each city because in the Ant Colony the distance between cities is calculated after the ants have completed their journey. So that Dijkstra's Algorithm can only run if the distance of each city is known beforehand, whereas the Ant Colony Algorithm does not require the distance of each city to carry out the process. From the process results of the two algorithms, it is known that the paths produced by Dijkstra's algorithm are more consistent and precise than the Ant Colony algorithm which gives results that are not necessarily the same in each process. However, Dijkstra's algorithm requires distance data first, while the ant colony algorithm still takes a very long time to find the shortest route, so a combination of the two algorithms is needed.