Applications of the ant colony optimization algorithm in combinatorial optimization

Ant colony optimization (ACO) is a metaheuristic algorithm, originally developed for the traveling salesman problem. The main idea of ACO came from the ants' communicative behavior. Ants communicate with each other through pheromone, which is a kind of chemical substance in insects. An important behavior of ant colonies is the foraging behavior. Ants deposit some amount of pheromone during their trip from their nest to a food source. Deposited pheromone forms a pheromone trail. Ants prefer to choose paths with higher pheromone. This simple behavior allows them to find the shortest path between their nest and a food source when many paths exist. Inspired by such behavior, the ACO algorithm has been successfully used to solve the traveling salesman problem and other NP-hard combinatorial optimization problems such as vehicle routing and scheduling.;In this research, ant colony optimization is applied to solve three well-known NP-hard problems: the Steiner tree problem in an undirected graph, the Steiner arborescence problem in a directed graph, and the job-shop scheduling problem with the makespan objective.;Although the ACO algorithm has achieved success in solving various combinatorial optimization problems, it has not been applied to solve the two well-known NP-hard problems: the Steiner tree problem in an undirected graph (STP) and the Steiner arborescence problem in a directed graph (SAP). The first part of this research uses the ACO algorithm to solve large-scale versions of STP and SAP. The objective of both STP and SAP is to find the shortest tree containing a subset of nodes, called terminal nodes. For STP, a proposed two-phase procedure solves the problem. In the first-phase, existing graph reduction rules decrease the size of the original graph. The second-phase, based on the ACO algorithm, iteratively attempts to generate improved trees by adjusting the pheromone values of edges to generate an optimal or nearoptimal solution. The ACO algorithm finds the best known solutions for 56 out of 78 test problems. Moreover, this algorithm provides better results in the test problems than other metaheuristic algorithms. For SAP, a similar two-phase procedure is developed. The ACO algorithm obtains the best known solutions for all test problems.;In the case of the job-shop scheduling problem, the ACO algorithm has been applied to for job-shop scheduling problems (JSSP) with the makespan objective, but with results not as satisfactory as other metaheuristic algorithms. This algorithm has produced good solutions in various application areas, but they have not succeeded in certain cases due to a stagnation situation in which the same solutions are repeatedly generated. In 2004, Blum and Dorigo proposed a max-min ant colony optimization (MMACO) to prevent the stagnation of the general ACO algorithm. This research uses a max-min ant colony strategy to solve the JSSP with the objective of minimizing makespan. Moreover, in order to find near optimal or optimal solutions efficiently, the Storer et al.'s methodology which is known to be the one of the best heuristic algorithms is implemented in the framework of the MMACO algorithm. The MMACO with use of the Storer et al.'s methodology finds better solutions than the best known solutions for 6 test problems. In the 73 test problems, the average relative error from the best known solutions is 1.14%.