순회 왼판원 문제를 위한 지역 탐색의 그리디 기반 이웃해 생성 방법
Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
순회 외판원 문제는 가장 유명한 조합 최적화 문제 중 하나이다. 지금까지 이 문제를 해결하기위해 많은 메타휴리스틱 탐색 알고리즘들이 제안되어 왔으며, 그중의 하나가 지역 탐색이다. 지역탐색에 있어서 매우 중요한 요소 중 하나가 이웃해 생성 방법으로 주로 역전(inversion)과 같은 무작위 기반 이웃해 생성 방법들이 사용되어 왔다. 본 논문에서는 4가지의 새로운 그리디 기반 이웃해 생성 방법들을 제안한다. 3가지 방법은 그리디 삽입 휴리스틱을 기반으로 하는데, 선택된 도시들을 하나씩 차례로 현재 가장 좋은 위치로 삽입한다. 나머지 하나는 그리디 회전을 기반으로한다. 제안된 방법들은 대표적인 지역 탐색 알고리즘인 first-choice 언덕 오르기 탐색과 시뮬레이티드 어닐링에 적용된다. 실험을 통해 제안된 그리디 기반 방법들이 기존의 무작위 기반 방법들보다 성능이 우수함을 확인하였다. 또한 일부 그리디 기반 방법들은 기존의 지역 탐색 기법들보다 더 우수함을 확인하였다.
Abstract
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.
참고문헌 (13)
- S. P. Tiwari, "A Survey of Metaheuristic Algorithms for Travelling Salesman Problem", International Journal Of Engineering Research & Management Technology, 1(5) (2014)
- R. A. Palhares, "Vehicle Routing:Application of Travelling Salesman Problem in a Dairy", 2018IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pp.1421~1425 (2018)
- G. Wang, "Robot Path Planning Based On The Travelling Salesman Problem", Chemical Engineering Transactions, 46, pp.307~312 (2015)[DOI]
- A. Roy, "A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique", Decision Making. Applications in Management and Engineering, 2(2), pp.100~111 (2019)
- W. Gao, "New Ant Colony Optimization Algorithm for the Traveling Salesman Problem", International Journal of Computational Intelligence Systems, 13(1), pp.44~55 (2020)
- M. A. Rahman, "Repetitive Nearest Neighbor Based Simulated Annealing Search for Traveling Salesman Problem", Open Access Library Journal, 8(6), pp.e7520~ (2021)
- S. Hore, "Improving variable neighborhood search to solve the traveling salesman problem", Applied Soft Computing, 68, pp.83~91 (2018)
- 황준하, "순열 기반 조합 최적화를 위한 지역 탐색의 이웃해 생성 전략", 한국컴퓨터정보학회논문지, 26(10), pp.27~35 (2021), 한국컴퓨터정보학회[DOI]
- F. Glover, "Tabu Search: A Tutorial", Interfaces, 20(4), pp.74~94 (1990)
- R. A. Rutenbar, "Simulated annealing algorithms: An overview", IEEE Circuits and Devices magazine, 5(1), pp.19~26 (1989)
- D. Abramson, "Simulated Annealing Cooling Schedules for the School Timetabling Problem", Asia Pacific Journal of Operational Research, 16, pp.1~22 (1999)
- Heuristics for the Traveling Salesman Problem, "C. Nilsson", Linköping University, ~ (2003)
- "TSPLIB"[URL]