Application of an ant algorithm for layout optimization of tree networks

Abstract

This article presents an application of the ant algorithm to the layout optimization of tree networks. Two different formulations are used to represent the layout optimization problem of tree networks in the proper form required for the application of the ant algorithm. In the first formulation, each link of the base graph, from which the optimum layout is to be selected, is considered as the decision points of the problem. The ants are then required to choose from two options of zero and one, available at each decision point, where the zero option represents the no pipe option for the link. This formulation leads to a very large search space dominated by the infeasible solutions. In the second approach, the network nodes are considered as the decision points of the problem at which the ants are required to choose any of the available links which are provided by a tree-growing algorithm. This formulation leads to a very small search space compared to the first algorithm as each ant is now forced to create a feasible solution. This approach fully exploits the sequential nature of the ant algorithm in building solutions, which is believed to be one of the main advantages of ant algorithms compared to other general heuristics. The proposed methods are applied to find the optimal layout of three benchmark examples in the literature and the results are presented and compared to the existing results. The results clearly reveal the superiority of the ant algorithm and in particular the second formulation to other global optimization methods including genetic algorithms (GAs) for the problems considered.