A Biogeography-Based Optimization with a Greedy Randomized Adaptive Search Procedure and the 2-Opt Algorithm for the Traveling Salesman Problem

Cheng Hsiung Tsai, Yu Da Lin, Cheng Hong Yang, Chien Kun Wang, Li Chun Chiang, Po Jui Chiang

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

We develop a novel method to improve biogeography-based optimization (BBO) for solving the traveling salesman problem (TSP). The improved method is comprised of a greedy randomized adaptive search procedure, the 2-opt algorithm, and G2BBO. The G2BBO formulation is derived and the process flowchart is shown in this article. For solving TSP, G2BBO effectively avoids the local minimum problem and accelerates convergence by optimizing the initial values. To demonstrate, we adopt three public datasets (eil51, eil76, and kroa100) from TSPLIB and compare them with various well-known algorithms. The results of G2BBO as well as the other algorithms perform close enough to the optimal solutions in eil51 and eil76 where simple TSP coordinates are considered. In the case of kroa100, with more complicated coordinates, G2BBO shows greater performance over other methods.

Original languageEnglish
Article number5111
JournalSustainability (Switzerland)
Volume15
Issue number6
DOIs
Publication statusPublished - 2023 Mar

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Geography, Planning and Development
  • Renewable Energy, Sustainability and the Environment
  • Environmental Science (miscellaneous)
  • Energy Engineering and Power Technology
  • Hardware and Architecture
  • Computer Networks and Communications
  • Management, Monitoring, Policy and Law

Fingerprint

Dive into the research topics of 'A Biogeography-Based Optimization with a Greedy Randomized Adaptive Search Procedure and the 2-Opt Algorithm for the Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this