Finding a solution to the Multi-Criteria Minimum Spanning Tree (mc-MST) problem has direct benefit on real world problems. The Multi-objective Evolutionary Algorithm (MOEA) called NSGA-II (Non-Dominated Sorting Genetic Algorithm) has demonstrated to be the most promising approach to tackle mc-MST problem because of their efficiency and simplicity of implementation. However, it often reaches premature convergence and gets stuck at local optima causing the non-diversity of the population. To tackle this situation, the use local search strategies together with MOEAs has shown to be a good alternative. In this paper, we investigate the potential of local search methods to improve the overall effectiveness of NSGA-II to settle the mc-MST problem. We evaluate the performance of three general purpose local searches (Pareto Local Search, Tabu Search and Path Relinking) adapted to the multi-objective approach. Experimental results show that using Pareto Local Search (PLS) into the NSGA-II offers a better performance in terms of diversity and search space covered to settle the mc-MST problem.
