The Multi-Profit Orienteering Problem and Its Variants

Abstract

오리엔티어링 문제(orienteering problem, OP)는 야외 스포츠인 오리엔티어링으로부터 영감을 얻은 조합 최적화 문제이다. 이는 출발 지점, 도착 지점, 그리고 방문 지점(checkpoint)들로 구성된 지형에서 행하는 스포츠이다. 각 지점을 방문할 경우, 그 지점에 할당된 이익(profit)을 얻을 수 있다. 각 참가자들은 지도와 나침반을 이용하여 출발 지점에서부터 도착 지점까지 정해진 시간 내에 최대의 이익을 얻기 위해 여러 지점들을 방문하게 된다. 이 때, 지점들을 방문하여 얻은 이익의 합이 가장 큰 선수가 우승을 하게 된다. OP는 최근 많은 연구자들에 의해 관심을 받고 있다. 이는 선택적 외판원 문제(selective traveling salesman problem, STSP)라고도 알려져 있는데, 차량이 이동 제한 시간 내에서 고객으로부터 수집된 이익을 최대화하는 문제이다. OP의 변형 문제들로는 팀 오리엔티어링 문제(team orienteering problem, TOP), 시간 창이 있는 오리엔티어링 문제(orienteering problem with time windows, OPTW), 시간 창이 있는 팀 오리엔티어링 문제(team orienteering problem with time windows, TOPTW), 이익이 감소하는 팀 오리엔티어링 문제(team orienteering problem with decreasing profits, DP-TOP) 등이 있다. OP와 그의 변형 문제들은 도시 교통, 물류 등과 같은 실질적인 경로 최적화 문제에 필수적인 요소이다. 도시 교통에는 학교 통학버스나 셔틀버스 노선 문제, 관광 투어 가이드, 폐기물 수거 문제 등이 있다. 물류 문제로는 연료 유통계획 등이 대표적인 예이다. 본 박사논문은 최근에 도입된 다중이익 오리엔티어링 문제(multi-profit orienteering problem, MPOP)라는 OP의 변형을 다룬다. MPOP에서는 고객 지점마다 시간 의존적인 이익이 있기 때문에 해당 위치의 방문 시각에 따라 그 가치가 달라진다. MPOP의 목적은 이동 시간 제한 제약을 충족하면서 고객 지점에서 수집된 총 이익을 최대화하는 것이다. 최대한 많은 이익을 얻기 위해, 어떤 고객 지점들을 방문할 지를 결정하는 것과 더불어 각 고객 지점의 방문 시간을 신중하게 선택해야 한다. MPOP는 공연장과 방문시각을 정하여 콘서트 프로모션을 극대화하는 콘서트 프로모션 문제로부터 영감을 얻어 제안한 문제이다. MPOP의 응용분야로는 선거운동, 게릴라 콘서트, 관광 투어 가이드 등이 있다. 선거운동의 경우, 효과를 극대화하기 위해 선거 관리자가 유동인구를 고려해 후보 지역의 방문 우선순위와 방문 시각을 결정해야 한다. 또한, 관광 투어 가이드에서는 관광객이 선호하는 여행지들을 모두 방문하는 것은 불가능하기 때문에 관광객들의 만족도를 극대화하기 위해, 어떤 장소들을 선택하고, 어느 시간대에 방문할 지 결정을 해야 한다. 본 박사 논문의 구성은 다음과 같다. 제 1절에서는 본 논문에서 연구한 주제를 선정하게 된 배경과 연구한 문제들과 해결하기 위한 방법론에 대해 간략하게 소개한다. 박사 논문과 관련된 문헌들에 대해 제 2절에서 소개한다. 제 3절과 4절에서는 MPOP를 해결하기 위해 개발한 휴리스틱 알고리즘들(heuristic algorithms)과 최적 알고리즘들(exact algorithms)을 제안하였다. 제 5절에서는 MPOP의 변형 문제인 다중이익 팀 오리엔티어링 문제(multi-profit team orienteering problem, MPTOP)를 소개하고, 이를 해결하기 위한 branch-and-price(B&P) 기반의 최적 알고리즘들(exact algorithms)을 제안하였다. 본 연구의 주요 결과와 기여에 대한 요약과 향후 연구에 대하여 제 6절에서 논의한다. 제 3절에서는 OP에 대한 벤치마크 데이터 세트(benchmark data set)을 활용하여 MPOP에 대한 벤치마크 데이터 세트를 생성했다. 또한 MPOP를 해결하기 위해 혼합 정수 선형 프로그래밍(Mixed integer linear programming model, MILP) 형태의 수학적 모델(Mathematical model)을 개발하고, MPOP를 효과적으로 해결하기 위해 휴리스틱 알고리즘을 제안하였다. 제안하는 휴리스틱 알고리즘 “SA+VTOA”은 고객 지점들의 시퀀스(sequence)를 결정하는 알고리즘과 주어진 시퀀스에 대한 최적의 방문 시각을 설정해주는 알고리즘으로 구성된 하이브리드 접근 방식이다. 고객 지점들의 시퀀스를 바꿔가며 결정하는 부분에는 simulated annealing(SA) 알고리즘을 사용하고, 최적의 방문 시각을 결정해주는 부분에는 방문 시각 최적화 알고리즘(visiting-time optimization algorithm, VTOA)를 개발하여 사용하였다. 제안된 “SA+VTOA” 알고리즘의 평균 계산 시간은 8,7초이며, MPOP의 수학적 모델을 CPLEX를 통해 1시간 동안 계산하여 얻은 결과 대비 평균적으로 12.7% 더 좋은 결과를 제공하였다. 또한, 객관적인 성능 비교를 위해 MPOP의 특수한 문제(special case)인 OP의 벤치마크 인스턴스에 대해 실험을 한 결과, 89개의 인스턴스 중 64개에 대해 가장 잘 알려준 솔루션을 찾을 수 있었다. 제 4절에서는 MPOP에 대해 동적 계획법(dynamic programming, DP) 기반의 최적 솔루션 접근법(exact solution approach)을 제안하였다. 최적 솔루션 접근법 혹은 알고리즘 (exact solution approach or exact algorithm)은 해를 구할 수 있는 경우 그 해가 최적해임을 보장하는 알고리즘이다. 최종 제안된 알고리즘 “DP + SA + ng-route + update incumbent”은 동적 계획법(dynamic programming: DP), ng-route relaxed DP, 해 생성 알고리즘 (초기해 생성, incumbent solution 업데이트), 그리고 지배 규칙(dominance rule)을 결합한 알고리즘이다. 기본적인 DP는 기하급수적으로 많은 state를 가지기 때문에 계산 시간의 부담이 있다. 기본 DP 계산의 부하를 극복하기 위해 ng-route relaxed DP와 지배 규칙을 사용하여 탐색해야 할 state수를 줄일 수 있다. ng-route relaxed DP는 제안하는 DP 기반의 알고리즘의 incumbent solution과 state의 목적 값(objective value)의 상한 값(upper bound)을 업데이트 하는 데 사용된다. ng-route relaxed DP는 incumbent solution과 state의 상한 값의 관계를 활용하여 탐색이 불필요한 state들을 가지를 쳐 냄으로써(pruning) DP 알고리즘을 가속화한다. 또한 SA 기반 초기해 생성 알고리즘을 활용할 경우, 얻어진 초기해를 통해 불필요한 state들을 일찍 가치지기 할 수 있기 때문에 알고리즘의 성능을 향상시켜준다. 최종적으로 제안된 DP 기반의 최적 알고리즘 “DP + SA + ng-route + update incumbent”은 이전에 해결되지 않은 MPOP 벤치마크 인스턴스 33개에 대해 최적해를 보장해주고, 23개의 인스턴스에 대하여 최상의 해(best-known solution)를 업데이트 하였다. 제안하는 DP기반의 알고리즘을 객관적으로 비교하기 위해 시간 창이 있는 OP인 OPTW의 벤치마크 인스턴스에 대해 실험을 진행하였다. 제안하는 DP기반의 알고리즘 “DP + SA + ng-route + update incumbent”은 모든 인스턴스에 대해 최적의 솔루션을 찾는 등, OPTW 문제에 대해서도 우수한 성능을 보였다. 제 5절에서는 여러 대의 차량이 있는 문제인 MPTOP에 대해 소개한다. MPOP와 마찬가지로 고객 지점마다 여러 개의 시간 간격이 있으며, 방문 시각에 따라 얻을 수 있는 이익이 달라진다. 각 고객 지점마다 이익이 한 번만 발생하기에 여러 대의 차량이 같은 고객 지점을 방문할 필요가 없다. MPTOP는 방문 고객이 많아 복수의 차량을 관광에 운행하거나 2일 이상의 관광 일정을 만들 때 활용되는 문제이다. MPTOP의 목적은 시간 제한 제약 내에 운행하는 차량들로부터 얻는 총 수익을 극대화하도록 노선을 디자인하는 것이다. 본 논문에서는 MPTOP를 위한 147개의 벤치마크 인스턴스를 생성하고, MPTOP를 해결하기 위한 branch-and-price(B&P) 기반의 방법론을 제안한다. B&P 기반의 방법론은 column generation(CG)과 branch-and-bound(B&B) 방법의 조합이다. 제안하는 B&P 기반의 방법론의 성능을 평가하기 위해 베이스라인으로 MILP 형태의 수학적 모델인 [Basic MPTOP]를 개발하였다. [Basic MPTOP] 모델은 147개의 인스턴스 중 81개의 인스턴스에 대한 최적의 솔루션을 찾았지만, 제안된 B&P 기반의 알고리즘은 벤치마크 인스턴스의 98%에 해당하는 144개의 인스턴스에 대해 최적의 솔루션을 발견할 수 있었다. 또한 제안하는 B&P 기반 알고리즘의 객관적인 성능 평가를 위해, special case인 TOP 벤치마크 문제에 대해서도 실험을 진행하였다. 제안하는 B&P 기반의 알고리즘은 대부분의 TOP 벤치마크 인스턴스에 대해 최적의 솔루션을 찾을 수 있었다.

The orienteering problem (OP), which is a selective version of the traveling salesman problem, has been widely studied by many researchers in recent years. The purpose of the OP is to maximize profits collected from customers in a limited time period, during which all customers cannot be visited. There are many OP variants such as team orienteering problem (TOP), orienteering problem with time windows (OPTW), team orienteering problem with time windows (TOPTW), set orienteering problem (SOP), time-dependent orienteering problem (TD-OP), team orienteering problem with decreasing profits (DP-TOP), orienteering problem with variable profits (OPVP), and others. OP and its variants are essential elements in practical routing issues such as urban transportation, humanitarian logistics, and others. There are school or shuttle bus routing problems, tourism tour design, and waste collection problems in urban transportation. A representative example of humanitarian logistics is fuel distribution planning. This dissertation handles a recently introduced type of OP variant called the multi-profit orienteering problem (MPOP). In the MPOP, each customer vertex has a time-dependent profit such that its value varies on the basis of visiting time. The purpose of the MPOP is to maximize the total profits collected from vertices while satisfying the travel time limit constraint. To maximize the total profit, a vehicle should carefully select both the customer vertices to visit and their visiting time. The benchmark problem set for the MPOP is introduced, and this dissertation proposes a mathematical model, a hybrid heuristic algorithm, and exact solution approaches to solve it. The proposed hybrid heuristic algorithm consists of a vertex sequence setting algorithm and an optimal visiting-time setting algorithm for a given sequence. A simulated annealing (SA) algorithm is used for the first part, and a visiting-time optimization algorithm (VTOA) is used for the second part. Experimental results demonstrate that the proposed algorithm can solve most of the instances well within a reasonable time. The proposed exact solution approaches are the first dynamic programming (DP)-based algorithms for the MPOP. The final proposed exact algorithm combines DP, ng-route relaxed DP, incumbent solution generation algorithms, and bounding rules. Because a basic DP may have exponentially many states, its computational burden is impractical. In order to overcome the load in the computation of the basic DP, ng-route relaxed states and bounding rules are utilized to reduce the number of states to be searched. The ng-route relaxed states are used to update the incumbent solution and upper bounds of states in the proposed DP approach. The ng-route relaxed states accelerate the DP algorithm to fathom states utilizing the relationship between the incumbent solution and upper bounds of states. Besides, an SA-based initial solution generation algorithm is applied to start with a suitable incumbent solution because it can be beneficial to fathom some states in the early stages. The proposed DP-based exact algorithm can solve 33 previously unsolved benchmark instances optimally and update the best solution of 23 benchmark instances for the MPOP. The proposed DP-based algorithm—designed for a more general MPOP—can find optimal solutions for all instances and performs well on the OPTW problems, even when compared with specialized algorithms for the OPTW problems. If there are multiple vehicles, the problem becomes the multi-profit team orienteering problem (MPTOP). As in the MPOP, each customer vertex has several time slots, and the associated profit varies based on visiting time. Each customer vertex can be visited by at most one vehicle and one time slot, so the profit of each customer can be collected by at most once. The goal is to determine multiple routes and maximize these routes’ total profit within the travel time limit constraint. Each vehicle selects the vertices to visit as well as determines the visit sequence and visit times optimally. In this dissertation, the benchmark problem set for the MPTOP is introduced, and we propose a branch-and-price (B&P) approach to solve the MPTOP. The branch-and-price is a combination of the column generation method and branch and bound method. While the basic mathematical model [Basic MPTOP] found optimal solutions for 81 instances out of 147 instances with 1 h computation time limitation for each instance, the proposed B&P-based algorithm could discover optimal solutions for 144 instances, 98.0% of the benchmark instances. The proposed B&P-based algorithms can find optimal solutions for most instances and performs well on the TOP problems even though the proposed B&P-based algorithms are designed for a more general MPTOP. The proposed algorithms for the MPOP and the MPTOP can be applied to variants of the capacitated OP with slight modifications. The multi-profit capacitated orienteering problem (MPCOP) is the MPOP with vehicle capacity constraints. Its goal is to maximize the total collected profit within the travel time limit, and within the vehicle capacity constraints. The multi-profit capacitated team orienteering problem (MPCTOP) is the MPTOP with vehicles capacity constraints. Its purpose is to maximize the total profits collected from the vehicles while satisfying the travel time limit and vehicles’ capacity constraints.