Novel hybrid evolutionary algorithm for bi-objective optimization problems

This work considers the Bi-objective Traveling Salesman Problem (BTSP), where two conflicting objectives, the travel time and monetary cost between cities, are minimized. Our purpose is to compute the trade-off solutions that fulfill the problem requirements. We introduce a novel three-Phase Hybrid Evolutionary Algorithm (3PHEA) based on the Lin-Kernighan Heuristic, an improved version of the Non-Dominated Sorting Genetic Algorithm, and Pareto Variable Neighborhood Search, a multi-objective version of VNS. We conduct a comparative study with three existing approaches dedicated to solving BTSP. To assess the performance of algorithms, we consider 20 BTSP instances from the literature of varying degrees of difficulty (e.g., euclidean, random, mixed, etc.) and different sizes ranging from 100 to 1000 cities. We also compute several multi-objective performance indicators, including running time, coverage, hypervolume, epsilon, generational distance, inverted generational distance, spread, and generalized spread. Experimental results and comparative analysis indicate that the proposed three-phase method 3PHEA is significantly superior to existing approaches covering up to 80% of the true Pareto fronts.

Automated summary

This work proposes a novel three-Phase Hybrid Evolutionary Algorithm (3PHEA) that incorporates the Lin-Kernighan Heuristic, Non-Dominated Sorting Genetic Algorithm, and Pareto Variable Neighborhood Search to solve the Bi-objective Traveling Salesman Problem (BTSP). The algorithm is compared with three existing approaches on 20 BTSP instances of varying difficulty and size, and evaluated using multiple performance indicators. Experimental results show that the 3PHEA method outperforms existing approaches by achieving over 80% coverage of the true Pareto fronts.