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

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

국문 초록

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

목차

1. 서론

2. 확률적 외판원 문제

3. 수치적 실험

4. 결론 및 향후과제

키워드

이종확률 외판원문제 구성 알고리듬