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. 지역탐색 기법을 적용한 최소평균삽입 알고리듬
  4.1 2-p-opt
  4.2 집단적 지역탐색(Grouping Local Search)
   4.2.1 고객 집단 교환
   4.2.2 개별 고객 교환
   3.3 수치실험
 5. 결론
 참고문헌

• 김승모(한국외국어대학교 산업경영공학과, Department of Industrial and Management Engineering, Hankuk University of Foreign Studies) | Seung Mo Kim
• 최기석(한국외국어대학교 산업경영공학과, Department of Industrial and Management Engineering, Hankuk University of Foreign Studies) | Ki-Seok Choi