다 경로 오리엔티어링 문제를 위한 우선순위규칙 기반의 발견적 기법

Abstract

단일 경로 오리엔티어링 문제가 확장된 다 경로 오리엔티어링 문제는 각 지점까지 걸리는 거리나 시간이 주어진 모든 지점 중 하나인 출발지점에서 종착지점까지의 각 차량 별 경로를 결정하는 문제이다. 각 차량의 경로들은 위의 주어진 지점들을 방문해야 하며 각 지점에는 서로 다른 각각의 점수가 주어져 있다. 본 문제의 목적은 방문한 지점들에서 얻은 점수의 합을 최대화 하는 것이다. 이러한 다 경로 오리엔티어링 문제는 '오리엔티어링' 이라는 야외 스포츠 경기, 가정용 유류의 배달을 위한 다 경로 차량문제, 대학 축구팀에서 고등학교 선수들을 모집하기 위한 설명회의 경로 결정문제와 가전제품의 출장 수리를 위한 수리 기사들의 경로를 결정하는 문제 등 많은 실질적인 사례들이 있다. 지금까지 다 경로 오리엔티어링 문제에서 다루어져 왔던 최적화 문제나 발견적 기법들은 실질적으로 크기가 큰 상황에서는 사용할 수 없는 문제가 있었기 때문에 우리는 우선순위규칙들을 사용한 간단하고 빠른 알고리듬들을 제안하였다. 이러한 빠른 기법들의 성능을 보여주기 위하여 100개의 지점까지 선정되어 있는 기존의 성능평가 기준 문제와 임의적으로 생성한 1000개까지의 잠재지점들로 구성된 문제로 실험을 해 보았다. 또한, 본 연구에서 제안하고 있는 알고리듬들을 기존에 발표된 발견적 기법의 해와도 비교 하였다.; Team orienteering, an extension of single-competitor orienteering, is the problem of determining multiple paths from a starting point to a finishing point for a given allowed time or distance limit fixed for each of the paths while maximizing the total collected score. Each path is through a subset of nodes, each of which has an associated score. The team orienteering problem has many applications such as home fuel delivery, college football players recruiting, service technicians scheduling, military operations, etc. Unlike the previous optimal and heuristic algorithms that are not suitable for practically very large-sized instances, we suggest two types of fast heuristics - serial and parallel ones - in which all nodes are listed in an order using a priority rule and then the paths are constructed according to this order. To show the performances of the fast heuristics, computational experiments were done on the small-to-medium sized benchmark instances up to 100 nodes and randomly generated large-sized test instances up to 1000 nodes, and the results show that some of the heuristics give reasonable quality solutions within very short computation time.