DP를 이용한 외판원문제에 대한 발견적 해법

서병규 漢陽大學校 1993 국내석사

Pr¨ufer수를 이용한 외판원문제의 유전해법

이재승 한양대학교 1997 국내석사

이종 확률적 외판원 문제를 위한 최소 평균 거리 삽입 알고리듬

김승모 韓國外國語大學校 大學院 2010 국내석사

The Probabilistic Traveling Salesman Problem (PTSP) is an important topic in the study of traveling salesman problem and stochastic routing problem. The goal of PTSP is to find a priori tour visiting all customers with a minimum expected length, which simply skips customers not requiring a visit in the tour. There are many existing researches for the homogeneous version of the problem, where all customers have an identical visiting probability. Otherwise, the researches for the heterogeneous version of the problem are insufficient and most of them have focused on search base algorithms. In this paper, we propose a simple construction algorithm to solve the heterogeneous PTSP. The Minimum Expected Length Insertion algorithm is a construction algorithm and consists of processes to decide a sequence of visiting customers by inserting the one, with the minimum expected length between two customers already in the sequence. Compared with optimal solutions, the proposed algorithm generates better solutions when the average probability is low and the customers have different visiting probabilities.

PCB 조립공정에서 부품 랙 할당과 배치순서 결정 방법의 연구

임승환 東亞大學校 大學院 2000 국내박사

전자산업에 속하는 생산업체들은 기업간의 과다 경쟁으로 인해 높은 생산성과 정밀한 작업을 수행할 수 있는 자동화된 설비를 필요로 하고 있다. 특히 전자제품 생산에서 중요한 부분을 차지하고 있는 PCB(인쇄회로기판) 생산공정의 여러 하부공정들에서는 PCB상에 다양한 종류의 부품들을 배치 및 삽입할 수 있는 자동화된 설비들로 대부분 교체되었다. 또한 여러 하부공정 중에서 표면탑재방식의 부품 자동 삽입기는 정밀화되고 소형화된 고밀도의 전자부품들을 PCB상에 배치할 수 있는 설비로서, 많은 시간을 점유하고 있으므로 이 설비를 효율적으로 운영할 수 있는 알고리즘의 개발이 중요한 과제로 대두되고 있다. 이러한 종류의 부품 자동 삽입기는 크게 각 부품종류들이 장착되는 랙과 부품을 집고 배치시키는 헤드, 그리고 PCB를 고정하고 배치지점으로 이동시키는 테이블로 나누어 볼 수 있으며, 현재에는 더욱 확장된 랙과 복수 개의 헤드를 가지도록 발전되고 있다 따라서 효율적 운영을 위한 분석이 더욱 복잡해지고 있으며, 이를 운영하는 알고리즘의 효율성에 따라 생산량의 차이가 발생한다. 표면탑재방식의 부품 자동 삽입기에 대한 분석은 일반적으로 랙에 대한 부품할당문제와 PCB상에 부품배치순서를 결정하는 문제로 나누어볼 수 있으며, 이 두 가지 문제는 이차할당문제와 순환외판원문제로 다루어질 수 있다. 위의 두 문제는 전형적인 NP-hard문제로서 근사-최적해를 구할 수 있는 휴리스틱들이 제안되어지고 있다. 하지만 기존의 여러 연구에서는 부품할당문제를 경험적인 방법에 의존하고 있으며, 배치순서를 결정함에 있어서도 전체 배치지점들을 하나의 경로로 구성하여 운영함으로써 그 효율성을 떨어뜨리고 있다. 본 연구에서 제시한 경로구성방법은 먼저 PCB상의 모든 배치지점들을 하나의 경로로 구성하여 배치순서를 결정하지 않고, 적절한 크기의 여러 개의 그룹으로 나누어 그룹별로 경로를 구성함으로서 문제의 크기에 따라 유연성을 부여하였다. 우선 4개의 칸을 하나의 그룹으로 설정하여 랙의 이동에 따른 비효율성을 최소화할 수 있는 방안을 개발하였으며, 나아가 랙의 그룹 수를 n개로 확장한 일반적인 모형도 개발하였다. 본 연구에서 제시한 또 다른 방안의 특징으로는 그룹을 형성하는데 있어 각 부품종류들에 대한 근접도를 평가하여 이를 랙의 할당에 적용한 것을 들 수 있다. 이는 각 배치지점에 대하여 서로 근접한 부품종류들의 수준을 수치로서 나타내는 것이며, 따라서 그룹화에 따른 랙의 칸에 대한 부품종류의 적절한 할당이 가능하게 하였다. 또한 그룹별로 최적의 부품배치순서를 결정할 수 있도록 하였다. 본 연구를 통하여 개발한 방법에 따라 PCB 상의 부품배치 및 삽입을 해 나갈 때의 효율성을 점검하기 위해 문헌에서 찾아진 방법과 부품자동 삽입기 제작회사에서 제공하는 방법 두 가지를 프로그램화하여 그 효율성을 비교 분석하였다. 다양한 경우의 시뮬레이션 결과 최근 문헌상의 방법에 비하여 x-y테이블 단위당 이동거리의 크기 w를 20과 35㎜로 설정한 경우 각각 8.2%와 12%의 단위 이동거리가 감소하는 효과를 나타내었다. 또한 기계와 함께 제공되는 방법보다도 45.6%와 41%의 단위 이동거리가 감소되는 효과를 나타내었다. Factory automation equipments which perform better for productivity and precision tasks are highly demanded due to extreme competition in electronic industries. Especially factory automation equipments which can handle various components are replaced with old machines in current PCB production lines. Surface mounters which pick, place and insert small sized components are the most important equipment in the production line. It is valuable to develop algorithms which can operate surface mounters efficiently to increase productivities. A surface mounter has racks(loading the components), heads(picking and placing components), and χ-y table(moving components placing point to the head). Some of surface mounters have multi-heads and racks. Because of the multi-heads and racks, it is very complicated to find efficient operation methods for the surface mounters. To develop an algorithm a surface mounter must be considered on two aspects, which are component assignment for racks and component placement ordering on PCB. These are basically QAP and TSP, however, there is a difference on the approach solving both at the same time. Currently, a simple heuristic is supplied with surface mounters, but the performance is not acceptable. Most of the companies who own surface mounters develop head moving sequences on a PCB and rack assignment by manual. However, it takes about a few man days and the result can not be expected as an efficient one. In this study, a heuristic is developed to find an efficient sequence on a PCB and rack assignment by component grouping. As setting up 4 reels in a group, the distance of rack movement is minimized. In addition, a generalized model for more than 4 reels in a group is developed. It is found that the performance of this heuristic is better than the P&S heuristic. The good performance is obtained by designing this heuristic according to the components placement data of the given PCB. Through the simulation study, the suggested heuristic is about 8.2 and 12% better than the P&S algorithm, and 41% and 45.6% better then the supplied algorithm with mounters respectively.

비대칭 외판원 문제를 위한 새로운 분지기법

지영근 한양대학교 대학원 1996 국내석사

변형된 순외판원문제와 시간분할을 통한 차량운송경로계획에 관한 비교

윤성원 연세대학교 대학원 2008 국내석사

Solving Methods of Traveling Salesman Problem : 巡廻外販員問題에 대한 解法

배강수 木浦大學校 大學院 2004 국내박사

본 논문은 순회외판원문제에 대한 몇 가지 해법을 소개하고 순회외판원문제의 효과적인 근사해를 구하기 위하여 새로운 알고리즘을 제공하고자 한다. 주어진 알고리즘이 효과적인 알고리즘인지 과학적으로 판단하기 위해서는 최악의 실행시간뿐만 아니라 평균 실행시간까지 조사해야하지만 본 논문에서는 최악의 실행시간으로만 한정하기로 한다. 제안된 새로운 알고리즘은 다음과 같은 4단계로 시행된다. 1단계 : 각 도시간 비용을 크기 순으로 정열한 후 비용이 작은 r개의 도시를 제외한 (n-r)개의 도시만 선택 2단계 : (n-r)개의 도시를 최근거리인접점 알고리즘을 이용하여 초기해를 구한다. 3단계 : 초기해에 분지한계법을 이용하여 부분최적해를 구한다. 4단계 : 부분최적해와 제외한 r개의 도시로 근사해를 구한다. 최악의 실행시간으로 한정하여 비교·분석한 결과 제안된 알고리즘의 실행시간은 O((n-r)!)로 분지한계법보다는 실행시간이 더 빠르지만 최근거리인접점 알고리즘이나 k-optimal 알고리즘보다는 더 느린 것으로 나타났다. We introduce the traveling salesman problem and survey several solving methods for it. And we suggest the new algorithm of solving methods for the traveling salesman problem. To observe efficiency with scientific exactitude of this algorithm, we compare and analyze not only the worst-case running time but also average-case between suggested algorithm and other, but we restrict only the worst-case running time in this paper and compute it. The algorithm for an approximate solution of the TSP is following steps: Step 1. The number of costs of all cities, that is n^(2), is sort in the order of their (small) size by Merge sort. And choose n-r cities among n cities, where r(<n)) is the number of cities with small cost among costs sort. Step 2. Initial assignment with n-r cities : Find the initial solution using nearest neighbor algorithm. It is unnecessary that the initial solution is tour at this place. Step 3. Find partial optimal solution using Branch and bound algorithm for n-r cities. Step 4. Find approximate solution from partial optimal solution for n-r cities and r cities. Running time of suggested algorithm is O((n-r)!) in the worst-case. From a point of view of worst-case running time, O((n-r)!) is faster than that of branch and bound, but slower than that of nearest neighbor and k-optimal.

시간제약이 있는 외판원 문제 해결을 위한 회피 가능한 경로 패턴을 이용한 제약 프로그래밍

이현진 인하대학교 대학원 2010 국내석사

시간제약이 있는 외판원 문제는 외판원이 본사를 발하여 시간제약이 있는 모든 고객을 방문하고 돌아오는 최소비용의 경로를 선정하는 문제이다. 본 논문에서는 시간제약이 있는 외판원 문제의 해결을 위하여 회피 가능한 경로 패턴을 활용한 제약 프로그래밍 기반의 탐색 전략을 제안한다. 본 탐색 전략은 높은 비용을 구성하는 해의 집합에서 발생하는 경로의 패턴을 추출하여 해당 패턴이 나타나는 탐색 공간을 사전에 제거하는 탐색 전략이다. 제약 프로그래밍에 의한 최적 알고리즘은 제약조건의 수에 의존하여 성능이 결정된다. 따라서 본 논문에서는 회피 가능한 경로 패턴을 제약조건에 추가하는 전략을 사용하였다. 추가적으로 본 탐색 전략을 발견적 알고리즘 수준의 속도 유지를 위하여 도메인 제거 기법을 추가적으로 제안하였다. 제안하는 탐색 전략의 성능 평가를 위하여 TSPTW 벤치마크 자료를 사용하였으며, 최적해를 산출해내는 기준 아래 다른 최적 알고리즘보다 속도 측면에서 향상된 결과를 확인할 수 있었다. 도메인 제거 기법을 추가적으로 적용한 탐색 전략의 경우 다른 발견적 알고리즘과 동등하거나 그 이상의 해를 발견해 낼 수 있었다. Traveling salesperson problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. This paper presents a search strategy for solving the TSPTW that merges constraint programming propagation algorithms. This search strategy removes bad path patterns in advance. As a result, we can reduce the size of search space. Performance of exact algorithms using the constraint programming depends on the number of constraints. Therefore we improved the performance of proposed search strategy by exploiting avoidable path patterns as constraints. We also added domain reduction phase in the search strategy for keeping up search speed with other heuristics. Computational tests performed on TSTPW benchmark problem instances show that the proposed search strategy generates optimal or near-optimal solutions in most cases. The proposed method results much faster than other exact approaches. In addition, it generates more qualitative solutions than other heuristics.

Reinforcement learning-based TSP problem solving with diffusion model

김주왕 Graduate School, Yonsei University 2024 국내석사

The Traveling Salesman Problem (TSP) is a cornerstone challenge in combinatorial optimization, recognized as an NP-hard problem. The rapid evolution of advanced artificial intelligence technologies has inspired a myriad of novel strategies to tackle this enduring issue. In this paper, we introduce an innovative approach that synergizes reinforcement learning (RL) with diffusion models to solve the TSP. This method employs a latent variable to generate an adjacency matrix, thus bridging the methodologies of image and graph learning in a unified RL framework. Our approach leverages a pre-trained diffusion model, utilizing it as a source of prior knowledge, which enhances computational efficiency and fosters remarkable generalization capabilities. We present experimental results on TSP datasets comprising various numbers of cities, where our method consistently surpasses existing solutions. This achievement not only deepens our comprehension of complex AI technique integration but also establishes a new benchmark for efficiently resolving NP-hard problems through cutting-edge artificial intelligence. 외판원 문제(TSP)는 조합 최적화 분야의 주요 과제로, NP-완전 문제로 인정받고 있다. 첨단 인공지능 기술의 급속한 발전은 이 오랜 문제를 해결하기 위한 다양한 새로운 전략들을 고안해냈다. 본 논문에서는 강화학습(RL)과 확산 모델을 통합하여 TSP를 해결하는 혁신적인 접근 방식을 소개한다. 이 방법은 잠재 변수를 사용하여 인접 행렬을 생성함으로써 이미지 학습과 그래프 학습 방법론을 단일 RL 프레임워크에서 통합한다. 본 접근법은 사전 지식의 원천으로 활용되는 사전 훈련된 확산 모델(Diffusion Model)을 활용하여 계산 효율성을 높이고 뛰어난 일반화 능력을 갖추고 있다. 다양한 도시 수를 포함하는 TSP 데이터셋에 대한 실험 결과를 제시하며, 본 방법이 기존 솔루션을 꾸준히 능가함을 보여준다. 이러한 성과는 복잡한 AI 기술 통합에 대한 이해를 심화시킬 뿐만 아니라, 첨단 인공지능을 통해 NP-완전 문제를 효율적으로 해결하는 새로운 기준을 수립한다.

(An) Efficient Algorithm for Uniform Coverage Path Planning on Surfaces

최현웅 서울대학교 대학원 2020 국내석사

Coverage path planning (CPP) is widely used in numerous robotic applications. With progressively complex and extensive applications of CPP, automating the planning process has become increasingly important. This thesis proposes an efficient CPP algorithm based on a random sampling scheme for spray painting applications. We have improved on the conventional CPP algorithm by alternately iterating the path generation and node sampling steps. This method can reduce the computational time by reducing the number of sampled nodes. We also suggest a new distance metric called “upstream distance” to generate reasonable path following given vector field. This induces the path to be aligned with a desired direction. Additionally, one of the machine learning techniques, support vector regression (SVR) is utilized to identify the paint distribution model. This method accurately predict the paint distribution model as a function of the painting parameters. We demonstrate our algorithm on several types of analytic surfaces and compare the results with those of conventional methods. Experiments are conducted to assess the performance of our approach compared to the traditional method. 본 논문에서는 2차원 표면의 균일 커버리지 경로 계획을 설명하고 이를 효율적으로 푸는 알고리즘을 제시한다. 우리는 경로 계획 문제를 두 개의 하위 문제로 분리하여 각각 푸는 기존의 방식을 보완하여 두 개의 하위문제를 한 번에 풀면서 계산시간을 줄이는 방법을 제시하였다. 또한 경우에 따라 주어진 벡터 필드와 나란한 방향으로 경로가 생성될 필요가 있는데 이를 위해 거스름 거리(upstream distance)의 개념을 제시하였으며 여행 외판원 문제(Traveling Salesman Problem)를 풀 때 이를 적용하였다. 우리는 차량 도장 응용분야에 균일 커버리지 경로 계획법을 적용하였으며 도장 시스템을 고려하여 균일한 페인트 두께를 보장하는 방법을 같이 제시하였다. 네 가지 타입의 2차원 곡면에 대해 시뮬레이션을 진행하였으며 기존의 방법에 비해 더 적은 계산시간을 요구하면서도 합리적인 수준의 페인트 균일도를 달성함을 검증하였다.