Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem

Abstract

Traveling salesman problem (TSP) is an optimization problem in determining the optimal route of a number of nodes that will only be passed once with the initial node as the final destination. One method for solving TSP is the Ant Colony Optimization (ACO) Algorithm. ACO is inspired by ant behaviour in searching for food, where ants produce pheromones to find food sources and make a route from the colony to food that will be followed by other ants. However ACO has not been considered as the optimal method for resolving TSP. This is because ACO has several shortcomings in the computational process. Comparisons between pheromones are not yet clear, and slow computing time causes the results of ACO to be not optimal. To correct these deficiencies, modifications will be made to the ACO. Modifications are made by changing some values in the ACO, such as adjusting the number of ants by the node automatically, changing the value in the pheromone renewal, and adding value to the construction of the solution. The outcome of this research is the modification of ACO did not provide shorter computing time with a more accurate final value, thus did not provide an optimal solution. The test results in this study found that the average computation time for the last iteration of each test was 0.54 second, and for the 10 iteration computation time obtained an average of 5.54 second for four tests. The amount of memory used in four tests in this study was 440.11 mb for 10 iterations.