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

다국어 초록 (Multilingual Abstract)

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.

목차 (Table of Contents)

• 1장 서론 1
• 1절 연구배경 1
• 2절 관련연구 및 연구목적 2
• 3절 논문구성 3
• 2장 확률적 외판원 문제 4
• 1절 확률적 외판원 문제 정의와 기호 4
• 2절 확률적 외판원 문제의 목적함수 5
• 3장 최소 평균 거리 삽입 알고리듬 7
• 1절 최소 평균 거리 삽입 알고리듬 7
• 2절 수치적 실험 9
• (2.1) 실험 설계 9
• (2.2) 실험 결과 분석 10
• 3절 최소 평균 거리 삽입 알고리듬 개선 12
• 4장 지역탐색 기법을 적용한 최소평균거리삽입 14
• 1절 2-p-opt 14
• 2절 집단적 지역탐색 기법 15
• (2.1) 집단 고객 교환 15
• (2.2) 개별 고객 교환 16
• 3절 수치적 실험 19
• (2.1) 실험 설계 19
• (2.2) 실험 결과 분석 20
• 5장 결 론 23
• 참고문헌 24
• ABSTRACT 25