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 () and Po-Jui Chiang ()
Additional contact information
Cheng-Hsiung Tsai: Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 80778, Taiwan
Yu-Da Lin: Department of Computer Science and Information Engineering, National Penghu University of Science and Technology, Magong 88046, Taiwan
Cheng-Hong Yang: Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 80778, Taiwan
Chien-Kun Wang: Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 80778, Taiwan
Li-Chun Chiang: Department of Political Science, National Cheng Kung University, Tainan 701401, Taiwan
Po-Jui Chiang: Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 80778, Taiwan

Sustainability, 2023, vol. 15, issue 6, 1-14

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.

Keywords: BBO; TSP; 2-Opt; randomized greedy algorithm (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2071-1050/15/6/5111/pdf (application/pdf)
https://www.mdpi.com/2071-1050/15/6/5111/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:15:y:2023:i:6:p:5111-:d:1096569

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().