본 연구에서는 no-depot minmax mTSP를 해결하는 SlGi 휴리스틱을 제안한다. SlGi 휴리스틱은 구성 단계와 개선 단계로 구성된다. 각 단계에 사용되는 k-slice method 알고리즘과 SAG-insertion 알고리즘을 ...
http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
https://www.riss.kr/link?id=A108924926
2023
Korean
KCI등재
학술저널
516-529(14쪽)
0
상세조회0
다운로드국문 초록 (Abstract)
본 연구에서는 no-depot minmax mTSP를 해결하는 SlGi 휴리스틱을 제안한다. SlGi 휴리스틱은 구성 단계와 개선 단계로 구성된다. 각 단계에 사용되는 k-slice method 알고리즘과 SAG-insertion 알고리즘을 ...
본 연구에서는 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 휴리스틱은 외판원의 수가 증가할수록 알려진 최적해와의 차이가 감소하며, 실행 시간 또한 줄어든다. 따라서 외판원의 수가 더 많은 경우에 더욱 준수한 성능을 보일 것으로 예상된다.
다국어 초록 (Multilingual 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 ...
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.
볼록 사각형의 Macbeath inconic과 볼록 사각형의 Orthic inconic에 대한 연구
너비 우선 탐색 기반 비재귀 트리 탐색 알고리즘의 효율적 구현과 성능 비교
확장된 블로토 대령 게임에서 최적 전략의 수학적 분석과 시각화
진화학, 인지심리학, 뇌과학 연구프로그램으로 본 정서 기반 창의성과 영재교육