This study deals with a variant of the orienteering problem faced by managers of some department stores during peak-sale periods. We want to find a set of paths to be traveled by each vehicle that leaves a department store and arrives at a specified destination after visiting customers. The problem is formulated into the mathematical model with the objective of maximizing the sum of the rewards collected by the vehicles within a given time limit and a given capacity constraint. Since the problem is known to be NP-hard, a heuristic algorithm and a priority-based Genetic Algorithm (pGA) are developed to find the solution. For small sized problems, the performances of the algorithms are compared with the optimum solutions obtained from CPLEX.
본 논문은 실제 백화점 배송문제에 대한 해법을 찾는 것으로, 추석이나 연말연시와 같이 고객의 배달요구가 최대가 되는 시점에도 배송부서의 인원을 늘리지 않고 제품을 제때 배송할 수 있게 도와주는 일종의 변형된 오리엔티어링 문제를 다루고 있다. 본 논문은 차량이 여러 대이고 각 차량의 도착지 및 운행시간이 다르며 차량마다 최대 적재용량이 주어져 있는 문제의 해법을 다루었다. 여러 대의 차량이 동시에 출발하여 각 차량의 목적지까지 가는 도중에 최대한 많은 reward를 모으는 것이 본 연구의 목적이다. 각 차량의 목적지와 운행시간이 다르며, 차량의 용량제약을 고려하고 있다는 점에서 기존의 연구들과 차별화 된다.
본 논문에서는 위 문제를 수학적 모델로 모형화 하였다. 이러한 문제는 NP-hard임이 알려져 있기 때문에, 문제의 특성을 이용한 휴리스틱 알고리즘과 메타 휴리스틱의 일종인 유전 알고리즘을 제안하였다. 본 논문에서 제안한 휴리스틱과 유전 알고리즘의 유효성을 검증하기 위해, 고객 수와 직원 수에 따른 새로운 데이터 세트를 만들고 문제의 크기가 작은 경우에 대해 CPLEX를 이용한 최적해와 비교하였다.
