이종 확률적 외판원 문제를 위한 최소 평균거리 삽입 및 집단적 지역 탐색 알고리듬

• 영문명: A Minimum Expected Length Insertion Algorithm and Grouping Local Search for the Heterogeneous Probabilistic Traveling Salesman Problem
• 발행기관: 한국산업경영시스템학회
• 저자명: 김승모(Seung Mo Kim) 최기석(Ki-Seok Choi)
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2010년 하계학술대회 논문집, 1~8쪽, 전체 8쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2010.08.30

영문 초록

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 (MELI) 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 MELI algorithm generates better solutions when the average probability is low and the customers have different visiting probabilities. We also suggest a local search method which improves the initial solution generated by the MELI algorithm.

목차

1. 서론

2. 확률적 외판원 문제

3. 최소 평균거리 삽입 알고리듬

4. 지역탐색 기법을 적용한 최소평균삽입 알고리듬

5. 결론

키워드

Probabilistic Traveling Salesman Problem Priori Tour 2-p-opt Local Search