CAJ | 학술논문

TSP（旅行商问题）作为一种解决组合优化问题的有效方法,在近几十年来受到了广泛的研究。理论证明它是一个典型的NP难问题,为了更快捷地求解,候选集方法在多种求解算法比如LKH算法中都有用到,一般是用于产生一个接近局部最优的初始解,较少用于寻路过程中。本文提出了一种新的简单的候选集方法,它采用一种新的距离度量,更好地符合了对称TSP的寻路规则。将其应用于最大最小蚁群算法（MMAS）的寻路过程中,实验结果表明针对对称TSP问题,该方法能比基本的MMAS取得更好的性能。这种候选集方法也可以用于其他求解对称TSP问题的进化计算。
TSP（여행상문제）작위일충해결조합우화문제적유효방법,재근궤십년래수도료엄범적연구。이론증명타시일개전형적NP난문제,위료경쾌첩지구해,후선집방법재다충구해산법비여LKH산법중도유용도,일반시용우산생일개접근국부최우적초시해,교소용우심로과정중。본문제출료일충신적간단적후선집방법,타채용일충신적거리도량,경호지부합료대칭TSP적심로규칙。장기응용우최대최소의군산법（MMAS）적심로과정중,실험결과표명침대대칭TSP문제,해방법능비기본적MMAS취득경호적성능。저충후선집방법야가이용우기타구해대칭TSP문제적진화계산。
As a typical NP problem and an effective solution to combinatorial optimization problems, TSP （traveling salesman problem） has been extensively studied in the last few decades. Candidate set is often used in many algorithms to limit the selecting range in the process of choosing a next traveling destination or to initialize a local optimum solution, such as in LKH algorithm. A novel simple generating method of candidate set is proposed in this paper and applied to MAX-MIN Ant System （MMAS） for symmetric TSP problems. Experiment results show that this new method outperforms MMAS. It can also be used in other algorithms for symmetric TSP problems.