Multiobjective optimization of MPLS-IP networks with a variable neighborhood genetic algorithm

• A multiobjective genetic algorithm is proposed for packet routing in MPLS IP networks.
• The proposed GA, called VN-MGA, employs operators that work on two different solution neighborhoods, resembling the VNS metaheuristics.
• The solutions delivered by VN-MGA are compared with the ones delivered by the exact solutions provided by an ILP solver, for medium-sized problem instances. The VN-MGA was found to be able to find most of the exact Pareto-optimal solutions, leaving a small gap in the other cases.
• The VN-MGA has been statistically compared with a pure VNS strategy, outperforming that algorithm.
• Since the ILP approach is not applicable to large problem instances, the VN-MGA can be considered a suitable alternative for those problems.

This paper presents a Genetic Algorithm for the optimization of multiple indices of Quality of Service of Multi Protocol Label Switching (MPLS) IP networks. The proposed algorithm, the Variable Neighborhood Multiobjective Genetic Algorithm (VN-MGA), is a Genetic Algorithm based on the NSGA-II, with the particular feature that solutions are encoded defining two different kinds of neighborhoods. The first neighborhood is defined by considering as decision variables the edges that form the routes to be followed by each request, whilst the second part of solution is kept constant. The second neighborhood is defined by considering the request sequence as decision variable, with the first part kept constant. Comparisons are performed with: (i) a VNS algorithm that performs a switch between the same two neighborhoods that are used in VN-MGA; and (ii) the results obtained with an integer linear programming solver, running a scalarized version of the multiobjective problem. The results indicate that the proposed VN-MGA outperforms the pure VNS algorithm, and provides a good approximation of the exact Pareto fronts obtained with Integer Linear Programming (ILP) approach, at a much smaller computational cost. Besides potential benefits of the application of the proposed approach to the optimization of packet routing in MPLS networks, this work raises the theoretical issue of the systematic application of variable encodings, which allow variable neighborhood searches, as generic operators inside general evolutionary computation algorithms.