Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Mar 15;13(1):4267.
doi: 10.1038/s41598-023-31123-8.

Novel hybrid evolutionary algorithm for bi-objective optimization problems

Omar Dib  1
Affiliations

Novel hybrid evolutionary algorithm for bi-objective optimization problems

Omar Dib. Sci Rep. .

Abstract

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.

PubMed Disclaimer

Conflict of interest statement

The author declares no competing interests.

Figures

Figure 1
Figure 1
Illustration of single and bi-objective TSP graphs.
Figure 2
Figure 2
Illustration of the proposed method.
Figure 3
Figure 3
Illustration of Phase 1.
Figure 4
Figure 4
Illustration of neighborhood structures.
Figure 5
Figure 5
Taxonomy of multi-objective performance indicators.
Figure 6
Figure 6
Distribution of computation time of different algorithms for datasets (Lust and Teghem).
Figure 7
Figure 7
Distribution of coverage metric for datasets (Lust and Teghem).
See this image and copyright information in PMC

References

    1. Matai R, Singh SP, Mittal ML. Traveling salesman problem: An overview of applications, formulations, and solution approaches. Travel. Salesman Probl. Theory Appl. 2010 doi: 10.5772/12909. - DOI
    1. Alexandridis A, Paizis E, Chondrodima E, Stogiannos M. A particle swarm optimization approach in printed circuit board thermal design. Integrat. Comput. Aided Eng. 2017;24(2):143–155. doi: 10.3233/ICA-160536. - DOI
    1. Nalecz-Charkiewicz K, Nowak RM. Algorithm for dna sequence assembly by quantum annealing. BMC Bioinform. 2022;23(1):1–17. doi: 10.1186/s12859-022-04661-7. - DOI - PMC - PubMed
    1. Carpio, R. F., Maiolini, J., Potena, C., Garone, E., Ulivi, G., Gasparn, A. Mp-stsp: A multi-platform steiner traveling salesman problem formulation for precision agriculture in orchards. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp 2345–2351 (2021). 10.1109/ICRA48506.2021.9561023.
    1. Mosayebi M, Sodhi M, Wettergren TA. The traveling salesman problem with job-times (tspj) Comput. Oper. Res. 2021;129:105226. doi: 10.1016/j.cor.2021.105226. - DOI