시간 및 비용 제한이 주어진 유지보수 출장경로 탐색

Abstract

주어진 그래프에서 최소 비용으로 모든 노드를 한번 씩 방문하는 경로를 찾기 위한 외판원 문제는 여행 및 출장 경로를 찾는 응용문제에서 많이 활용이 되어왔다. 그러나 현실의 응용 문제에서는 여행 예산이 한정된 경우, 그리고 모든 노드를 방문하지 않아도 되는 경로를 찾아야 하는 경우가 발생한다. 본 논문에서는 제품의 고장 신고가 들어온 지역을 방문하기 위해 정해진 하루 예산 (i.e., 시간, 비용 등)을 만족하는 출장 경로를찾기 위한 출장 경로 최적화 문제를 다룬다. 또한 최적의 출장경로는 방문한 지역의 총 효용성으로 판단한다. 보다 현실적인 가정을 위해 외판원 문제와 달리 모든 지역을 방문할 필요가 없으며 하루 예산안에서 효용성을 높일 수 있다면 같은 지역을 두 번 방문하여도 관계없는 것이 차이이다. 본 연구에서는 이를 해결하고자 탐욕적(Greedy) 알고리즘을 제안하였으며, 실제 A/S 접수, 방문 날짜와 주소가 기록된 데이터를 기반으로 제안된 알고리즘의 성능을 비교 검증하였다. 그리고 실험을 통해 제안 알고리즘이 실제 A/S 수행에서 사용 된 예산보다 더 적은 예산을 사용하며 더 많은 도시를 방문하는 순회 경로를 찾아내는 것을 확인하였다.

Traveling salesperson problem has been utilized for finding minimum-cost cycle touring all nodes with the smallest cost for a given graph and utilized for traveling path or business trip. However, for the real-world application, business budget is limited, and it is not needed to cover all cities. This paper deals with finding optimal business route problem with constraints which are limited budget. i.e., time, costs, etc. In addition, the optimal path is evaluated by the summation of value of visited cities. For more realistic assumption, in distinction from traveling salesperson problem, this problem is not required to visit all cities, and to maximize the total value of the cities, one city can be visited twice. To address this problem, this research suggests greedy algorithm and be evaluated with real maintenance trip data which consists of customer’s request, visit date and address. In conclusion, by the experiments, we verify that this algorithm obtains optimal path which utilizes less cost and more number of cities than real business trip data.