The Team Orienteering problem (TOP) is a variant of the Vehicle Routing Problem.
In the TOP, a set of nodes (customers) is given, each with a reward. The objective is to determine a fixed number of tours, limited in travel time, that visit some nodes and maximize the collected rewards. In this study, we propose the greedy method to construct of the tours, and then improvement steps are applied. The algorithm is compared with the other heuristics of the literature and applied on a large problem set.
다경로 오리엔티어링 문제는 차량경로설정 문제의 하나로서 전통적인 차량경로 설정문제와 가장 큰 차이점은 모든 고객을 방문할 필요가 없다는 것이다. 이때 목적은 가용한 차량의 대수와 차량별 운행시간을 갖고, 각 고객이 갖고 있는 보상의 합을 최대화 하는 것이 된다. 각 고객이 갖고 있는 보상이란, 해당 고객에 대해 서비스를 지원하였을 때 얻을 수 있는 잠재적 이익이나 긴급함의 정도로 고려될 수 있다.
예를 들면, 지역내 고등학교에 대한 대학 홍보의 경우 일정기간 내에 모든 고등학교를 방문하는 것이 불가한 경우가 있다. 이때 각 고등학교에서 대학에 올 수 있는 잠재적 능력을 보상으로 고려하여 대학홍보일정을 수립하는 경우가 다경로 오리엔티어링의 실제문제 상황이라 볼 수 있다. 본 연구에서는 일반적인 팀 오리엔티어링 문제상황과 마찬가지로 각 경로의 제한시간과 경로의 수를 제외한 추가적인 제약사항은 없는 것으로 간주하였다.
대학의 홍보 이외에도 일정 기간동안 사용 가능한 차량의 수가 고정되어 있고, 각 차량의 하루당 사용 가용시간이 제한된 경우 필요한 모든 고객에 대한 서비스가 불가능 할 경우가 발생할 수 있다. 이 경우에 차량 경로설정은 각 고객에게 서비스를 제공했을 때 얻을 수 있는 회사의 이익을 최대화 하도록 설계되어야 할 것이다.
특히, 군에서 상급부대의 이동정비는 가용한 기간내에 전 예하부대에 대한 서비스가 불가한 경우가 대부분으로 본 문제의 특성과 유사하다고 볼 수 있다.
이러한 문제는 NP-hard 문제로 알려져 있기 때문에 그동안 많은 휴리스틱 방법들이 제안되어 왔다. 본 연구에서는 그리디 해법을 적용한 휴리스틱 방법과 추가적인 성능향상 방안을 제안하였다. 일반적인 그리디 방법은 개념이 단순하고 알고리즘을 구현하기가 간편한 반면, 최적 해를 찾을 수는 없는 것으로 알려져 있다. 하지만 팀오리엔티어링 문제에서 초기 투어에 다양한 씨앗노드를 지정함으로써 그리디 해법의 성능을 개선할 수 있음을 알 수 있었다. 본 연구에서는 제안된 그리디 휴리스틱의 효율성을 확인하기 위해 그 동안 연구되었던 다른 휴리스틱과 동일한 문제 set을 가지고 결과값을 비교해 보았다.
