APLIKASI GRAF DALAM PENCARIAN JALUR TERPENDEK MENGGUNAKAN ALGORITMA ANT COLONY OPTIMIZATION (ACO)

Traveling Salesman Problem (TSP) is one of the problems in the search for the shortest path (shortest Parth Problem). One method that can be used in problem solving Traveling Salesman Problem (TSP) is to use Ant Colony Optimization algorithm (ACO). The algorithm is composed of a number m of ants cooperate and communicate indirectly via pheromone communication. This research will be focused on finding the shortest path Traveling Salesman Problem (TSP) using the algorithm Ant System (AS) which is one part of the Ant Colony Optimization algorithm (ACO). Ant System (AS) is the first algorithm that tested its use in problem Traveling Salesman Problem (TSP) and the calculation is simpler than other algorithms in the ACO. Environment used in the algorithm Ant System (AS) is a graph that has nodes and arcs between vertices as well as fully connected (each node has an arc to the other nodes) and bidirectional (each path can be traveled back and forth two-way). Each arc has a weight that indicates the distance between two nodes that are connected by the arc. Results of studies have shown that the algorithm is Ant System (AS) can be used to find the shortest path problem Traveling Salesman Problem (TSP). The solution obtained by the AS algorithm is highly dependent on the determination of the parameters used. Among them is the intensity of ant trail