A hybrid approach to approximate the Pareto front of the MOST problem

This study introduces a hybrid NSGA-II algorithm with Multi-VNS for approximating the Pareto front of the multi-objective spanning tree (MOST) problem, building on recent approaches that have adapted NSGA-II combined with local search heuristics. By exploiting the property that a spanning tree is acyclic and that the addition of an edge generates a unique cycle, our mutation operator adds edges to a given spanning tree of a connected graph , thereby reducing the size of the MOST problem. By applying the exact mutation operator with low probability, this reduced problem is solved, producing a set of mutant solutions. The NSGA-II selection operator then approximates the Pareto front, which is further refined by a Multi-VNS metaheuristic to balance diversification and intensification. Comparative experiments with both exact and approximate methods demonstrate promising results.