@article{ART003074063},
author={Yongho Kim and Junha Hwang},
title={A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2024},
volume={29},
number={4},
pages={1-8},
doi={10.9708/jksci.2024.29.04.001}
TY - JOUR
AU - Yongho Kim
AU - Junha Hwang
TI - A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2024
VL - 29
IS - 4
PB - The Korean Society Of Computer And Information
SP - 1
EP - 8
SN - 1598-849X
AB - The traveling salesman problem(TSP) is one of the well known combinatorial optimization problems.
Local search has been used as a method to solve TSP. Greedy Random Insertion(GRI) is known as an effective neighbor generation method for local search. GRI selects some cities from the current solution randomly and inserts them one by one into the best position of the current partial solution considering only one city at a time. We first propose another greedy neighbor generation method which is named Full Greedy Insertion(FGI). FGI determines insertion location one by one like GRI, but considers all remaining cities at once. And then we propose a method to combine GRI with FGI, in which GRI or FGI is randomly selected and executed at each iteration in simulated annealing. According to the experimental results, FGI alone does not necessarily perform very well. However, we confirmed that the combined method outperforms the existing local search methods including GRI.
KW - Greedy neighbor generation;Combined method;Local search;Traveling salesman problem;Simulated annealing
DO - 10.9708/jksci.2024.29.04.001
ER -
Yongho Kim and Junha Hwang. (2024). A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 29(4), 1-8.
Yongho Kim and Junha Hwang. 2024, "A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem", Journal of The Korea Society of Computer and Information, vol.29, no.4 pp.1-8. Available from: doi:10.9708/jksci.2024.29.04.001
Yongho Kim, Junha Hwang "A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 29.4 pp.1-8 (2024) : 1.
Yongho Kim, Junha Hwang. A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem. 2024; 29(4), 1-8. Available from: doi:10.9708/jksci.2024.29.04.001
Yongho Kim and Junha Hwang. "A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 29, no.4 (2024) : 1-8.doi: 10.9708/jksci.2024.29.04.001
Yongho Kim; Junha Hwang. A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 29(4), 1-8. doi: 10.9708/jksci.2024.29.04.001
Yongho Kim; Junha Hwang. A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem. Journal of The Korea Society of Computer and Information. 2024; 29(4) 1-8. doi: 10.9708/jksci.2024.29.04.001
Yongho Kim, Junha Hwang. A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem. 2024; 29(4), 1-8. Available from: doi:10.9708/jksci.2024.29.04.001
Yongho Kim and Junha Hwang. "A Combined Greedy Neighbor Generation Method of Local Search for the Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 29, no.4 (2024) : 1-8.doi: 10.9708/jksci.2024.29.04.001
2