No-depot minmax mTSP 문제를 위한 분할 및 가변 이웃 탐색 기반 휴리스틱
A Heuristic For The No-Depot Minmax Multiple Traveling Salesmen Problem Based on Clustering And Variable Neighborhood Search
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 연구에서는 no-depot minmax mTSP를 해결하는 SlGi 휴리스틱을 제안한다. SlGi 휴리스틱은 구성 단계와 개선 단계로 구성된다. 각 단계에 사용되는 k-slice method 알고리즘과 SAG-insertion 알고리즘을 제안한다. k-slice method와 선행연구에서 제시한 클러스터링 알고리즘을 비교한 결과, k-slice method가 여러 데이터에서 선행연구 알고리즘보다 뛰어난 성능을 보임을 확인하였다. 또한, SlGi 휴리스틱을 이용해 구한 minmax 거리와 ES, MILP 알고리즘을 이용한 minmax 거리, 최적 minmax 거리를 비교하였다. 그 결과, SlGi 휴리스틱이 선행연구 알고리즘 및 알려진 최적해와 비슷한 수준의 minmax 거리를 구하는 것을 확인하였다. SlGi 휴리스틱은 외판원의 수가 증가할수록 알려진 최적해와의 차이가 감소하며, 실행 시간 또한 줄어든다. 따라서 외판원의 수가 더 많은 경우에 더욱 준수한 성능을 보일 것으로 예상된다.
Abstract
In this study, we present the SlGi heuristic to address the no-depot minmax mTSP, comprising both construction and improvement stages. For each stage, we introduce a k-slice method algorithm and a SAG-insertion algorithm. Comparative analysis against clustering algorithms reveals the superior performance of the k-slice method across various data sets. Additionally, we compare minmax distances obtained using the SlGi heuristic with those from ES and MILP algorithms, as well as the optimal minmax distance. Results show that the SlGi heuristic achieves comparable minmax distances to algorithms in the literature and the known optimal solution. Notably, differences between the SlGi heuristic and the known optimal solution decrease with an increasing number of salesmen, accompanied by reduced execution time. Thus, the SlGi heuristic is expected to perfom better with a larger number of salesmen.
참고문헌 (28)
- 강래구, "최적의 TSP문제 해결을 위한 유전자 알고리즘의 새로운 집단 초기화 및 순차변환 기법", 한국정보통신학회논문지, 10(3), pp.622~627 (2006), 한국정보통신학회
- 유형선, "Large-Scale TSP 근사해법에 관한연구", 한국정밀공학회지, 9(3), pp.122~131 (1992)
- 윤여덕, "Extended Simulated Annealing 방법에 의한 확장된 TSP의 해결", 한국정보과학회 학술발표논문집, 16(2), pp.369~372 (1989)
- 이강구, "TSP에서 Union 연산자를 이용한유전자 알고리즘", 한국정보과학회 학술발표논문집, 21(1), pp.213~216 (1994)
- 조준현, "TSP 해결을 위한 Proximal Mapping 기법", 제어.로봇.시스템학회 논문지, 28(12), pp.1103~1108 (2022), 제어·로봇·시스템학회[DOI]
- 황숙희, "TSP 경로탐색을 위한 S-MINE 알고리즘", 정보처리학회 논문지, 18(2), pp.73~82 (2011), 한국정보처리학회
- Al-Omeer, M. A., "Comparative study of crossover operators for the MTSP", 2019International Conference on Computer and Information Sciences (ICCIS), pp.1~6 (2019), IEEE
- Combining 2-opt, 3-opt and 4-opt with k-swap-kick perturbations for the traveling salesman problem, "Blazinskas, A.", Kaunas University of Technology, Department of Multimedia Engineering, ~ (2011)
- Cheikhrouhou, O., "A comprehensive survey on the Multiple Traveling Salesman Problem : Applications, approaches and taxonomy", Computer Science Review, 40, pp.100369~ (2021)[DOI]
- Chen, X., "Ant colony optimization based memetic algorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems", IEEE Access, 6, pp.21745~21757 (2018)[DOI]
- He, P., "Hybrid search with neighborhood reduction for the multiple traveling salesman problem", Computers and Operations Research, 142, pp.105726~ (2022)[DOI]
- Johnson, D. S., "The traveling salesman problem : A case study in local optimization", Local search in combinatorial optimization, 1(1), pp.215~310 (1997)
- Karabulut, K., "Modeling and optimization of multiple traveling salesmen problems : An evolution strategy approach", Computers & Operations Research, 129, pp.105192~ (2021)[DOI]
- Kim, B. I., "Comparison of tsp algorithms", Project for Models in Facilities Planning and Materials Handling, 1, pp.289~293 (1998)
- Latah, Majd., "Solving multiple TSP problem by k-means and crossover based modified ACO algorithm", International Journal of Engineering Research and Technology, 5, pp.430~434 (2016)[DOI]
- Lin, S., "Computer solutions of the traveling salesman problem", Bell System Technical Journal, 44(10), pp.2245~2269 (1965)[DOI]
- Lloyd, S., "Least squares quantization in PCM", IEEE transactions on information theory, 28(2), pp.129~137 (1982)[DOI]
- Na, B., "Heuristic approaches for no-depot k-traveling salesmen problem with a minmax objective", Master’s, pp.2007
- Nagata, Y., "A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem", INFORMS Journal on Computing, 25(2), pp.346~363 (2013)[DOI]
- Narasimha, K. V., "An ant colony optimization technique for solving min–max multi-depot vehicle routing problem", Swarm and Evolutionary Computation, 13, pp.63~73 (2013)[DOI]
- Naznin, M., "A clustering heuristic by effective nearest neighbor selection", Midwest Instruction and Computing Symposium (2007)
- Oberlin, P., "A transformation for a multiple depot, multiple traveling salesman problem", Proceedings of the 2009Conference on American Control Conference, pp.2636~2641 (2009), IEEE Press
- Reinelt, G., "TSPLIB-A traveling salesman problem library", ORSA Journal on Computing, 3(4), pp.376~384 (1991)[DOI]
- Shuai, Y., "A new crossover approach for solving the multiple traveling salesmen problem using genetic algorithms", European Journal of Operational Research, pp.72~82 (2013)[DOI]
- Soylu, B., "A general variable neighborhood search heuristic for multiple traveling salesmen problem", Computers & Industrial Engineering, 90, pp.390~401 (2015)[DOI]
- Sundar, K., "Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems", Journal of Intelligent & Robotic Systems, 88, pp.513~526 (2017)[DOI]
- Wang, X., "The min-max multi-depot vehicle routing problem : heuristics and computational results", Journal of the Operational Research Society, 66(9), pp.1430~1441 (2015)[DOI]
- Zhou, H., "A comparative study of improved GA and PSO in solving multiple traveling salesmen problem", Applied Soft Computing, 64, pp.564~580 (2018)[DOI]