An ant colony optimization algorithm for the bi-objective shortest path problem

Multi-objective shortest path problem (MOSP) is an extension of a traditional single objective shortest path problem that seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. MOSP is one of the most important problems in network optimization with wide applications in telecommunication industries, transportation and project management. This research presents an algorithm based on multi-objective ant colony optimization (ACO) to solve the bi-objective shortest path problem. To analyze the efficiency of the algorithm and check for the quality of solutions, experimental analyses are conducted. Twosets of small and large sized problems that generated randomly are solved. Results on the set problems are compared with those of label correcting solutions that is the most known efficient algorithm for solving MOSP. To compare the Pareto optimal frontiers produced by the suggested ACO algorithm and the label correcting algorithm, some performance measures are employed that consider and compare the distance, uniformity distribution and extension of the Pareto frontiers. The results on the set of instance problems show that the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems. (C) 2009 Elsevier B. V. All rights reserved.