KJCKorea
Journal Central

@article{ART002880930},
author={Junha Hwang and Yongho Kim},
title={Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2022},
volume={27},
number={9},
pages={69-76},
doi={10.9708/jksci.2022.27.09.069}

TY - JOUR
AU - Junha Hwang
AU - Yongho Kim
TI - Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2022
VL - 27
IS - 9
PB - The Korean Society Of Computer And Information
SP - 69
EP - 76
SN - 1598-849X
AB - The traveling salesman problem(TSP) is one of the most famous combinatorial optimization problem. So far, many metaheuristic search algorithms have been proposed to solve the problem, and one of them is local search. One of the very important factors in local search is neighbor generation method, and random-based neighbor generation methods such as inversion have been mainly used. This paper proposes 4 new greedy-based neighbor generation methods. Three of them are based on greedy insertion heuristic which insert selected cities one by one into the current best position. The other one is based on greedy rotation. The proposed methods are applied to first-choice hill-climbing search and simulated annealing which are representative local search algorithms. Through the experiment, we confirmed that the proposed greedy-based methods outperform the existing random-based methods. In addition, we confirmed that some greedy-based methods are superior to the existing local search methods.
KW - Neighbor generation;Greedy-based;Local search;Traveling salesman problem;Simulated annealing
DO - 10.9708/jksci.2022.27.09.069
ER -

Junha Hwang and Yongho Kim. (2022). Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 27(9), 69-76.

Junha Hwang and Yongho Kim. 2022, "Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem", Journal of The Korea Society of Computer and Information, vol.27, no.9 pp.69-76. Available from: doi:10.9708/jksci.2022.27.09.069

Junha Hwang, Yongho Kim "Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27.9 pp.69-76 (2022) : 69.

Junha Hwang, Yongho Kim. Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem. 2022; 27(9), 69-76. Available from: doi:10.9708/jksci.2022.27.09.069

Junha Hwang and Yongho Kim. "Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27, no.9 (2022) : 69-76.doi: 10.9708/jksci.2022.27.09.069

Junha Hwang; Yongho Kim. Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 27(9), 69-76. doi: 10.9708/jksci.2022.27.09.069

Junha Hwang; Yongho Kim. Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information. 2022; 27(9) 69-76. doi: 10.9708/jksci.2022.27.09.069

Junha Hwang, Yongho Kim. Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem. 2022; 27(9), 69-76. Available from: doi:10.9708/jksci.2022.27.09.069

Junha Hwang and Yongho Kim. "Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27, no.9 (2022) : 69-76.doi: 10.9708/jksci.2022.27.09.069