확률적 외판원 문제(Probability Traveling Salesman Problem)는 일반적인 외판원 문제 (Traveling Salesman Problem)와 확률적 경로(Stochastic Routing) 문제에서 중요한 연구 분야 이다. 확률적 외판원 문제의 목적은 모든 고객을 방문하는 평균 거리가 최소가 되는 선험적 경로(priori tour)를 찾는 것이며, 경로에서 고객이 방문을 요구하지 않을 경우 다음 고객으로 방문을 하게 된다. 확률적 외판원 문제는 고객을 방문하는 확률에 따라 확률이 동일한 (homogeneous) 문제와 동일하지 않은 (heterogeneous) 이종 확률 문제로 분류되며, 대부분의 이종 확률 문제를 위한 연구는 탐색(search)기반 알고리듬을 고려하고 있다. 본 논문에서 제안된 최소 평균 거리 삽입 알고리듬은 탐색기반이 아닌 간단한 구성(construction) 알고리즘으로서 고객을 방문하는 순서를 결정하는 과정에서 이미 결정된 두 고객 사이에 평균거리(expected length)가 가장 작은 고객을 선택, 삽입하여 선험적 경로를 구한다. 제안된 알고리즘은 고객 방문 확률이 동일하지 않고 평균 확률이 낮은 경우 최적해에 근접한 해를 도출함이 실험을 통하여 관찰되었다.

요약
 1. 서론
 2. 확률적 외판원 문제
  2.1 기호 및 목적함수
  2.2 최소 평균 거리 삽입 알고리듬
 3. 수치적 실험
  3.1 실험 설계
  3.2 결과 분석
 4. 결론 및 향후과제
 참고문헌

• 김승모(한국외국어대학교 산업경영공학부) | Seung Mo Kim
• 최기석(한국외국어대학교 산업경영공학부) | Ki-Seok Choi