Multiple criteria minimum spanning trees

Abstract

The NP multiple criteria minimum spanning tree as several applications into the network design problems. In this paper, we rst introduce some properties than can help to characterize the problem, as well as to produce heuristics to solve it in a more e cient way. In the second part, we propose an application of the Multiple Objective Network optimization based on the Ant Colony Optimization (MONACO) algorithm to nd out an approximation to the set of the non- dominated solutions of the problem. The MONACO algorithm uses as many pheromone trails as the number of criteria and some local operators to increase the speed of the process and the quality of the results.