@article{ART002768399},
author={Junha Hwang},
title={Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2021},
volume={26},
number={10},
pages={27-35},
doi={10.9708/jksci.2021.26.10.027}
TY - JOUR
AU - Junha Hwang
TI - Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization
JO - Journal of The Korea Society of Computer and Information
PY - 2021
VL - 26
IS - 10
PB - The Korean Society Of Computer And Information
SP - 27
EP - 35
SN - 1598-849X
AB - Local search has been used to solve various combinatorial optimization problems. One of the most important factors in local search is the method of generating a neighbor solution. In this paper, we propose neighbor generation strategies of local search for permutation-based combinatorial optimization, and compare the performance of each strategies targeting the traveling salesman problem. In this paper, we propose a total of 10 neighbor generation strategies. Basically, we propose 4 new strategies such as Rotation in addition to the 4 strategies such as Swap which have been widely used in the past. In addition, there are Combined1 and Combined2, which are made by combining basic neighbor generation strategies. The experiment was performed by applying the basic local search, but changing only the neighbor generation strategy. As a result of the experiment, it was confirmed that the performance difference is large according to the neighbor generation strategy, and also confirmed that the performance of Combined2 is the best. In addition, it was confirmed that Combined2 shows better performance than the existing local search methods.
KW - Neighbor generation;Local search;Permutation-based combinatorial optimization;Traveling salesman problem;Simulated annealing
DO - 10.9708/jksci.2021.26.10.027
ER -
Junha Hwang. (2021). Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization. Journal of The Korea Society of Computer and Information, 26(10), 27-35.
Junha Hwang. 2021, "Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization", Journal of The Korea Society of Computer and Information, vol.26, no.10 pp.27-35. Available from: doi:10.9708/jksci.2021.26.10.027
Junha Hwang "Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization" Journal of The Korea Society of Computer and Information 26.10 pp.27-35 (2021) : 27.
Junha Hwang. Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization. 2021; 26(10), 27-35. Available from: doi:10.9708/jksci.2021.26.10.027
Junha Hwang. "Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization" Journal of The Korea Society of Computer and Information 26, no.10 (2021) : 27-35.doi: 10.9708/jksci.2021.26.10.027
Junha Hwang. Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization. Journal of The Korea Society of Computer and Information, 26(10), 27-35. doi: 10.9708/jksci.2021.26.10.027
Junha Hwang. Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization. Journal of The Korea Society of Computer and Information. 2021; 26(10) 27-35. doi: 10.9708/jksci.2021.26.10.027
Junha Hwang. Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization. 2021; 26(10), 27-35. Available from: doi:10.9708/jksci.2021.26.10.027
Junha Hwang. "Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization" Journal of The Korea Society of Computer and Information 26, no.10 (2021) : 27-35.doi: 10.9708/jksci.2021.26.10.027
