A Multi-Objective Ant Colony Optimization Algorithm for Infrastructure Routing

Abstract

An algorithm is presented that is capable of producing Pareto-optimal solutions for multi-objective infrastructure routing problems: the Multi-Objective Ant Colony Optimization (MOACO). This algorithm offers a constructive search technique to develop solutions to different types of infrastructure routing problems on an open grid framework. The algorithm proposes unique functions such as graph pruning and path straightening to enhance both speed and performance. It also possesses features to solve issues unique to infrastructure routing not found in existing MOACO algorithms, such as problems with multiple end points or multiple possible start points. A literature review covering existing MOACO algorithms and the Ant Colony algorithms they are derived from is presented. Two case studies are developed to demonstrate the performance of the algorithm under different infrastructure routing scenarios. In the first case study the algorithm is implemented into the Ice Road Planning module within the North Slope Decision Support System (NSDSS). Using this ice road planning module a case study is developed of the White Hills Ice road to test the performance of the algorithm versus an as-built road. In the second case study, the algorithm is applied to a raw water transmission routing problem in the Region C planning zone of Texas. For both case studies the algorithm produces a set of results which are similar to the preliminary designs. By successfully applying the algorithm to two separate case studies the suitability of the algorithm to different types of infrastructure routing problems is demonstrated.