Many research articles in the literature have dealt with the problem of finding an optimal tour such as the traveling salesman problem (TSP) and vehicle routing problem (VRP). They commonly assumed that "all" nodes on a given graph should be visited exactly once and only once. In this thesis, however, we deal with a multi-path orienteering problem (MPOP) that does not require visiting all the nodes. We want to find a set of paths for each vehicle that has to leave the distribution center and arrive at a specified destination. The objective is to maximize the total rewards collected by visiting as many customers as possible under a specified time limit. The manager of department store, and mineral water manufacturing and distribution company faces a similar problem during peak-sale periods. First, the problem is formulated in mathematical model. Then recognizing the difficulty in finding an optimal solution, a heuristic is developed that has three phases, i.e., construction phase, improvement phase, and balancing phase. To examine the validity of the algorithm, 450 problems are generated varying the numbers of nodes, the number of vehicles, and the time limit of each vehicle. Recognizing that some previous studies in the orienteering problem turn out to be a special case of MPOP, two heuristics, one for single path and the other for multiple paths, are adopted for the comparison purpose. The computational results show that the proposed heuristic tends to outperfonn the existing algorithms.
최근 고객의 만족도를 높이기 위해 물류의 중요성이 증대되고 있으며 많은 기업들이 고객이 구매한 제품을 직접 배달해 주는 택배 서비스가 점차 늘어나고 있는 추세이다. 기존의 차량의 경로를 찾는 많은 연구가 여러 산업 분야에 있어서 적용이 되어왔다. 하지만 기존의 연구에 있어서 모든 고객을 반드시 한번 방문해야 한다고 가정하고 있으며, 이는 특히 명절 혹은 크리스마스 시즌 때의 백화점이나 할인점의 상황이나 여름철의 생수회사의 경우와 같이 고객의 배달 주문이 한꺼번에 많이 몰리는 때에 주어진 시간과 차량을 가지고는 모든 고객의 수요를 만족시킬 수 없는 경우에는 적용하기 힘들다.
따라서 본 논문은 이와 같이 주어진 시간과 차량이 한정되어 있는 상황에서 방문해야 할 고객이 상대적으로 많은 경우, 어느 고객을 선택하여 어떻게 차량 경로를 찾을 것인가 하는 것을 다루고 있다. 본 연구에서 구하고자 하는 것은 주어진 시간 제약 하에서 최대한 많은 고객을 방문하여 그들로부터 얻는 이익을 최대화하도록 여러 대의 차량에 대한 최적의 차량경로를 구하고자 하였다.
현재 운용 중인 한 생수회사의 물류센터를 기반으로 본 연구의 모델이 세워졌다. 각 차량의 운전자가 작업이 끝난 후 각자의 집으로 퇴근을 하는 동안 주어진 초과작업시간만큼 퇴근하는 길에 고객에게 방문하여 배달을 하는 것을 문제 상황으로 하였다. 즉, 각 경로는 모두 같은 지점에서 출발하여 각자 정해진 지점에 주어진 시간 내에 도착하여야 한다.
본 논문에서는 위의 문제 상황에 맞는 수리적 모형을 제시하였고 본 문제가 수리적으로 해를 구하는 것이 힘든 것을 감안하여 경로의 구축 단계, 경로의 개선 단계, 여러 경로에 대한 조정단계의 세가지 단계로 구성되어 있는 발견적 해법을 개발하였다.
기존의 연구 중 우리가 다루는 문제의 특별한 경우에 해당하는 연구가 있었으므로, 이들 두 가지 발견적 해법을 가지고 우리가 개발한 발견적 해법과 실험을 통해 결과를 비교하였다. 총 450회의 문제를 가지고 실험한 결과 대부분의 문제에서 우리의 발견적 해법이 찾아낸 경로가 우수하다는 결과를 알 수 있었다.
