No-depot minmax mTSP 문제를 위한 분할 및 가변 이웃 탐색 기반 휴리스틱

A Heuristic For The No-Depot Minmax Multiple Traveling Salesmen Problem Based on Clustering And Variable Neighborhood Search

본 연구에서는 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 휴리스틱은 외판원의 수가 증가할수록 알려진 최적해와의 차이가 감소하며, 실행 시간 또한 줄어든다. 따라서 외판원의 수가 더 많은 경우에 더욱 준수한 성능을 보일 것으로 예상된다.

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.