1. 서 론

Vehicle Routing Problem with Pickup and Delivery(VRPPD) 는 고객으로부터 물품을 수령하고 동시에 요구하는 물품을 배달하는 차량의 최적 경로를 결정하는 문제이다[6]. VRPPD 는 고려하는 목적함수, 차량의 용량, 차고의 수, 시간 제한 (time window), 대상 물품의 제약 등에 따라 다양하게 변 형된 문제가 생성된다. 자원 재배치(Vehicle Routing with Resource Repositioning) 차량 경로 문제는 VRPPD의 특 별한 변형으로 한 종류의 재사용 가능한 자원을 대상으 로 배달양의 합과 수령양의 합이 같은 경우에 해당하는 것으로 정의할 수 있다.

대표적인 자원 재배치 차량 경로계획에 속하는 문제는 트럭을 이용한 공공 자전거 정적 재배치이다. 재배치는 수 요가 적은 대여소에 있는 여유 자전거를 수요가 많은 대여 소로 이동시켜 이용자의 서비스 수준을 향상시키는 것이 다[9]. 정적 재배치는 자전거 이용이 정지되어 있는 정해 진 시간에만 재배치를 한다. 일반적으로 하루 중 사용자가 없는 야간 시간대에 차량을 이용하여 각 대여소의 목표 재고량을 만족시키기 위한 정적 재배치를 수행한다. 목표 재고수준과 현 재고수준을 입력으로 정적 재배치를 위한 두 가지 의사결정인 차량 경로와 대여소에서의 상하차 수 량을 결정하는 연구에서는 다양한 MILP(Mixed Integer and Linear Problem) 문제가 정의되었다. 모든 문제들은 공 통적으로 차량의 운행시간 최소화를 기본 목적으로 하지 만 제한조건은 상황에 따라 여러 형태로 정의된다. 문제의 단순성을 위해 각 대여소는 한 번만 방문하도록 하는 문제 [5, 12, 13]가 있는 반면, 다수의 차량이 여러 번 방문하는 것을 허용하는 문제[3, 10]도 있다. 또한, 대여소에서의 목 표 재고수준을 필히 만족하여야 하는 문제[3]가 있는 반 면, 불만족을 허용하는 문제[2, 5, 11, 13] 또는 목표 재고 수준의 범위를 설정한 문제[14]가 있다. 목표 재고수준을 꼭 맞추기 위한 제한 조건은 매우 엄격한 조건에 속하여 이를 만족하는 유효 해를 구하기가 쉽지 않다. 이보다는 목표 재고수준과 재배치 후 달성되는 재고수준의 차이를 최소화하는 문제가 더 현실적일 수 있고, 해를 보다 쉽게 구할 수 있는 장점을 갖는다. 목표 재고 수량의 불만족을 허용하는 경우, 가중치를 이용하여 불만족도를 목적함수 에 포함하는 것이 일반적이다[5, 11, 13]. Rainer-Bach et al.[10]의 연구에서는 운행시간에 대한 가중치를 목표 재 고 수량의 불만족도에 대한 가중치의 1/100000로 하였지 만 단일 목적함수에 사용된 가중치의 설정이 현실적으로 어려울 뿐만 아니라 문제에 대한 하나의 근사 최적해는 제한된 정보에 속한다.

본 연구에서는 자원 재배치를 위한 차량 경로계획 문제 에서 단일 목적함수 보다는 목표 재고수준 미달성도와 차 량의 운행시간의 두 가지 목적함수를 최소화하는 다목적 최적화 문제를 다룬다. 자원 재배치 차량 계획에 대한 기 존 연구에서는 다목적 최적화 문제에서의 파레토 최적해 를 구하기 위한 노력을 찾아보기 어렵다. 그러나 파레토 최적해는 의사 결정자에게 보다 풍부한 정보를 제공할 수 있는 장점을 갖는다. 이에 따라 본 연구에서는 자원 재배 치 차량 경로계획의 다목적 최적화 문제에 대한 파레토 최적해를 효과적으로 제공할 수 있는 방법을 모색한다. 논 문의 구성은 다음과 같다. 제 2장에서는 본 논문에서 다루 는 자원 재배치 경로계획의 다목적 최적화 문제를 정의한 다. MILP에서와 같은 정의보다는 차량 경로를 순열로 표 현한 해를 이용하여 함축적으로 문제를 설명한다. 제 3장에 서는 다목적 최적화 기법 중 우수한 성능을 가진 SPEA2 (Strength Pareto Evolutionary Algorithm 2)를 자원 재배치 차량 경로계획 문제에 적용하는 방법을 설명하고, 두 목 적함수가 선형 결합된 단일 목적함수에서 가중치의 다양 화를 이용한 다목적 최적화 방법을 설명한다. 제 4장에서 는 표준 실험 데이터를 이용하여 실험한 결과를 설명하고, 제 5장에서 실험 결과 시사점과 향후 개선 방향을 논한다.

2. 자원 재배치 경로계획 문제

네트워크 G(V,A)에서 V = {0, 1, 2, ⋯, n}는 노드 집 합이고, A = {(i, j) : i≠j}는 아크 집합으로 노드 0는 차 고(depot), 나머지 노드들은 수요처를 나타낸다. 노드 i에 는 수요량 d_i , 아크 (i, j)에는 차량의 운행시간 t_ij가 설 정되어 있다. 현재 용량 C_k (k = 1, ⋯, m) 를 갖는 m개의 빈 차량이 차고에 위치하고 있다.

노드 i에서의 수요는 보유하고 있는 과다 자원을 덜기 위한 회수(d_i < 0)이거나 또는 부족 자원을 보충하기 위 한 보급(d_i > 0) 중의 하나이다. 차량은 방문하는 수요처 에서 이동이 요구되는 자원을 싣거나 또는 필요로 하는 자원을 내린다. 자원 재배치는 모든 노드에 대한 수요의 합이 0이 되는 경우로 회수된 모든 자원은 남김없이 보 급되어야 한다. 이러한 상황에서 모든 노드의 수요를 만 족하기 위한 차량의 경로 중 가장 빠른 시간 내에 운행 을 종료할 수 있는 경로를 결정하는 것이 자원 재배치를 위한 차량 경로계획 문제이다.

위 문제의 해를 나타내는 차량 경로 집합 R = { r 1 , r 2 , ⋯ , r m } 은 m개의 경로로 구성되고, 각 경로는 차량의 노드 방문 순서로 r k = ( υ k , 1 , υ k , 2 , ⋯ , υ k , n k ) , υ k , j ∈ V − { 0 } 이다. 각 차량의 운행은 차고에서 출발하여 차고에서 종료되고, 각 수요처는 한번만 방문 된다. 모든 차량이 운행을 종료 하는 시각을 최소화하기 위한 목적함수는 식 (1)을 최소화 하는 것이다.

식 (1)은 차고에서 출발한 각 차량이 경로상의 모든 노드들을 차례대로 방문한 후 다시 차고로 돌아올 때 까 지의 운행 시간 중 가장 긴 운행시간을 의미한다.

차량은 방문하는 노드의 수요를 만족시켜야 한다. k번 째 차량이 j번째 방문 노드 υ_kj에 도착했을 때 차량에 싣 고 있는 보유 자원 양을 Q라고 하자. 만약 노드의 수요량 d(υ_kj) 이 음수라면 - d(υ_kj) 만큼을 차량에 실어야 하므로 차 량의 여유 용량이 수요량을 초과하여야 한다(즉, Q - d(υ_kj) ≤ C_k). d(υ_kj) > 0인 경우에는 차량에 있는 자원에서 수요 량을 내 주어야 하므로 d(υ_kj) ≤ Q이어야 한다. 차고를 출발하는 빈 차량이 경로상의 J번째 노드를 떠날 때 싣고 있는 자원의 수량은 − ∑ j = 1 J d ( υ k j ) 이다. 따라서, 차량 경로 에 속한 노드의 수요량과 차량의 용량 간에 다음 조건이 만족되어야 한다.

조건 1)

운행을 마친 차량은 비어 있어야 하므로 다음 조건이 만족되어야 한다.

조건 1)과 2)는 매우 엄격한 조건에 속하여 이를 만족 하는 유효한 해의 수는 제한적일 수 있다. 또한, 어렵게 구한 유효한 해의 목적함수 값은 현실적으로는 인정할 수 없을 정도의 매우 큰 값을 가질 수 있다. 보다 실용적 인 대안은 모든 노드의 수요량을 가급적 만족하면서 허 용 가능한 시간 내에 종료될 수 있는 차량 경로를 구하 는 것이다. 각 노드에서의 수요량을 100% 만족하지 않는 경우를 허용한다면 수요량 만족 조건 대신에 수요량 불 만족 정도의 최소화를 목적함수로 설정할 수 있다. 수요 량 불만족 정도는 식 (4)와 같이 각 수요처에서의 수요량 과 차량 경로에 의해 실현된 양의 차이에 대한 절대값의 합으로 정의될 수 있다. 따라서, 식 (4)를 최소화하는 차 량의 경로를 구하는 두 번째 목적함수를 정의할 수 있다.

차량 운행 결과인 노드 i에서의 상태 y_i (R)은 전적으 로 차량 경로 R = { r 1 , r 2 , ⋯ , r m } 에 의해 결정된다. 현재 Q_k개의 자원을 싣고 있는 용량 C_k인 k번째 차량이 노드 i에 도착하여 떠날 때 Q′_k 개의 자원을 싣고 있다고 하자.

즉, 수요량이 양수인 경우 수요처에 내주는 양은 차량 보유량에 제약을 받는다. 만약 수요량이 보유량을 초과 한다면 수요처는 보유량만큼만 받을 수 있어 부족량이 발생한다. 수요량이 음수인 경우에는 수요량의 절대값에 해당하는 자원을 차량에 실어야 하지만 차량의 여유 용 량 이상을 실을 수 없어 잔여량이 수요처에 남아 있을 수 있다.

본 연구에서 다루는 차량 경로계획 문제는 위에 정의 된 두 목적함수 Z₁ (R)과 Z₂ (R)을 최소화하는 다목적 최 적화 문제이다. 두 함수는 트레이드 오프 관계를 가지고 있다. 수요 만족도를 증가시키기 위해서는 차량의 운행 시간이 길어질 수밖에 없고, 차량의 운행시간을 짧게 하 기 위해서는 수요의 만족도가 떨어질 수밖에 없게 된다. 이러한 경우 다양한 수요의 만족도와 차량 운행 시간을 포함하는 파레토 최적해의 제공이 의사결정자들에게 도 움을 줄 것이다.

3. 다목적 해 탐색 알고리즘

3.1 SPEA2

2000년 대 이후 근사적인 파레토 해를 효과적으로 구하 기 위한 다목적 최적화 알고리즘들이 개발되어 왔다. 대부 분의 알고리즘들은 유전자 알고리즘(Genetic Algorithm : GA), 입자 군집 최적화(Particle Swarm Optimization : PSO) 와 같은 군집을 이루는 개체 기반의 메타 휴리스틱에 기초 하고 있다. 우수한 성능을 가진 것으로 알려진 NSGA2 (Non-dominated Sorting Genetic Algorithm 2)[4]와 SPEA2 [17]는 GA에 기초하고 있고, SMPSO(Speed-constrained Multiobjective PSO)[9]은 PSO에 기초하고 있다. 참고문헌[8]은 GA 기반 다목적 최적화 방법에 대한 세부적인 설명을 포 함하고 있다.

SPEA2는 우세(dominance)기반의 적응값 할당 정책, 다 양성을 확보하기 위한 근접 이웃해 생성, 우수 개체를 저장 하기 위한 어카이브의 3가지 주된 방법을 사용하고 있다. SPEA2를 차량 경로계획 문제에 적용하기 위해서는 유전 자 알고리즘에서와같이 해의 표현 방법이 중요하다. 본 연구에서는 해를 순열 형태로 표현하고, 특별히 고안된 휴리스틱 기반의 디코딩 방법에 의해 유효한 차량 경로로 변환하였다.

기본적으로는 순열 형태의 해를 m개의 경로로 분리하 기 위하여 m = 1개의 컷 포인트(c p 1 , c p 2 , ⋯ , c p m − 1)를 이 용한다. 이들 컷 포인트의 위치를 왼쪽 또는 오른쪽으로 한 칸 이동시키는 연산을 정의할 수 있다. L (k)는 k번째 컷 포인트를 왼쪽으로 한 칸 이동시키는 연산이고, 반면, R (k)는 오른쪽으로 한 칸 이동시키는 연산이다. 연속적 인 두 컷 포인트에 대해 연산을 동시에 수행할 수 있다. 예를 들어, {L (k), R (k + 1)}은 k번째 컷 포인트를 왼쪽으 로 한 칸 이동시키는 동시에 k + 1번째 컷 포인트를 오른 쪽으로 한 칸 이동시킨다. 컷 포인트에 의해 분리된 한 경 로에 대해 8 경우의 컷 포인트 이동을 고려할 수 있다. 예 를 들어, 순열 형태로 표현된 해를 다음과 같이 두개의 컷 포인트 cp₁(= 4), cp₂(= 8)로 분리하여 3개의 경로를 생성 하였다고 하자.

3, 5, 1, 2 | 7, 8, 10, 4 | 6, 9, 12, 11

두 번째 경로를 구분하는 두 컷 포인트를 이동시킨다 고 하자. 다음의 8가지 이동을 고려할 수 있다.

이러한 컷 포인트 이동을 이용하여 순열 형태의 해를 경로로 변환하는 알고리즘은 다음과 같다.

Algorithm : Decoding using cut-point movement

초기의 컷 포인트들은 m개의 경로에 가급적 동일한 수의 노드들이 포함되도록 선택된다. 이들 컷 포인트들에 대해 컷 포인트 이동을 반복 수행하여 최종적인 컷 포인 트들을 확정하고, 이에 따라 순열의 해를 경로로 변환한 다. 제안된 디코딩 방법은 순열 표현의 해를 m개의 경로 로 분리하기 위해 목적함수 Z₁의 최소를 가져오는 부분 최 적해를 생성하는 향상적 휴리스틱 방법에 속한다.

3.2 가중치를 이용한 단일 목적함수

정의된 식 (1)과 식 (4)의 두 목적함수에 가중치 w₁ , w₂ 로 선형 결합된 하나의 목적함수를 다음과 같이 정의할 수 있다.

합이 1인 두 가중치의 값을 변화시키면 다양한 해 집 합을 구할 수 있고, 이들 중 파레토 해에 해당하는 해를 선별할 수 있다. 이 방법은 하나의 목적 함수 만을 대상 으로 하므로 주어진 문제에 대한 우수한 해를 생성할 가 능성이 크다. 그러나, 우수한 파레토 최적해를 생성하기 위해서는 다양한 가중치 값을 고려하여야 한다. 가중치 값이 다양할수록 우수한 파레토 해를 구할 가능성이 커 지지만 실행시간은 증가된다. 따라서, 실행시간과 해의 질 사이의 균형을 고려하여야 한다.

본 연구에서는 하나의 목적함수 값을 대상으로 해를 구 하는 방법으로 유전자 알고리즘과 VNS(Variable Neighborhood Search)[7]를 고려하였다.

4. 실험 및 결과

4.1 데이터 및 실험 방법

VRP의 벤치마크 문제들을 이용하여 자원 재배치를 위한 다목적 최적화 방법의 성능 평가를 위한 실험을 수 행하였다. Uchoa 등[15]이 제안한 VRP 문제들은 100부 터 1000까지의 노드를 포함하는 100개 문제로 구성되어 있다. 이 중 노드 수 120, 214, 308의 3가지 문제를 대상 으로 하였다.

제시된 문제들은 노드 간의 거리, 차량 수가 제공되지 만 자원 재배치 문제에 적합하기 위해서는 차량의 용량 과 노드의 수요에 대한 추가 자료가 필요하다. 각 노드에 서의 수요는 <Table 1> 에서와 같은 총 자원 이동량을 만족시키기 위해 전체 수요합이 0이 되도록 임의로 생성 하였고, 차량의 용량은 30으로 설정하였다.

SPEA2에서는 예비 실험을 통해 우수한 결과를 가져 오는 파라미터 값을 선정하였다. 교배 연산자로는 외판 원 문제에서 우수한 성능을 가져온다고 알려진 OX(order crossover)를 사용하였고, 돌연변이 연산자로는 순열 표 현 해에서 임의의 두 위치 사이의 값을 반전시키는 연산 자를 사용하였다.

가중치를 이용한 방법에서는 w₁의 값을 0.01부터 0.99 까지 0.01씩 증가하여 총 99개의 가중치를 할당하였다. GA에서는 SPEA2에서와 같은 파라미터 값을 사용하였 다. 즉, <Table 2>에서 GA 에서는 필요 없는 archive size 를 제외하고 나머지 파라미터에 대해 동일한 값을 사용 하였다.

VNS는 기존 연구[16]의 알고리즘을 사용하였고, 초기 해의 쉐이킹(shaking) 방법으로 서로 다른 경로에 속한 두 노드의 위치를 교환하는 연산자를 사용하였다. 부분 최적 화 방법인 VND(Variable Neighborhood Descent)는 한 경 로의 노드를 동일한 경로의 다른 위치 또는 다른 경로로 이동시키는 재위치(relocate) 연산자와 서로 다른 경로의 두 노드 위치를 바꾸는 교환(exchange) 연산자를 사용하였 다. VNS의 부분 최적화에서는 최우수 선택(Best Accept) 정책[1]을 채택하였다.

최적화 방법들은 자바로 프로그래밍 되어 인텔 i-7 3.6 GHz PC에서 SPEA2는 10분, GA와 VNS는 한 가중치 인 스턴스에 대해 30초 동안 실행하였다. 따라서, 가중치를 이용한 방법은 총 50분 동안 실행되었다.

4.2 성능 비교

<Figure 1>에서 <Figure 3>은 <Table 1>의 문제에 대해 SPEA2, GA, VNS에 의해 생성된 해에 대해 식 (1)과 식 (4)에서 정의된 두 목적함수 값을 나타낸 것이다. 모든 문 제에서 SPEA2와 GA의 해들은 VNS에 의한 해들에 의해 지배되어 VNS의 해가 매우 우수한 파레토 근사해를 생 성함을 보인다. SPEA2와 GA의 경우 수요를 완전히 만족 하는 해(Z₂ = 0)를 생성하지 못한 반면, VNS는 다수의 해 를 생성한다. 이는 VNS에서 수요 불만족도에 대한 가중 치를 1에 가깝게 했을 때 단일 목적함수 값을 최소화하는 부분 최적화 방법의 우수한 성능에 기인한다. 더욱이 최 대 운행시간인 Z₁에서는 VNS가 월등히 우수한 성능을 보인다.

3가지 방법 중 SPEA2의 성능이 가장 뒤떨어진다. 이는 GA, VNS에 비해 1/5의 실행시간이 주어진 이유도 있지만 SPEA2를 포함한 일반적인 다목적 최적화 방법이 채택하 고 있는 여러 목적 함수의 트레이드 오프를 감안한 새로 운 이웃해 생성방법에 기인하는 것으로 판단된다. 반면, 가중치 변화에 따른 단일 목적함수에서는 목적함수 간의 트레이드 오프를 배제하기 때문에 GA가 SPEA2보다 우 수한 해를 구할 수 있는 것으로 분석된다. 부가적으로 SPAE2에서는 10분 실행시간으로 충분한 안정상태에 도 달하였기 때문에 더 이상의 실행시간 연장이 해의 질에 영향을 미치지 못하였다.

4.3 VNS 복잡성

VNS는 부분 최적화 방법을 포함하므로 적지 않은 실행 시간을 필요로 한다. VNS를 이용한 단일 목적함수 최적 화에서 실행시간을 감소시키기 위한 방법으로 가중치의 수를 줄이는 것을 고려해 볼 수 있다. 그러나, 가중치 수 를 줄이면 파레토 해의 수는 감소하여 의사결정을 위한 충분한 정보를 제공하지 못할 수 있다. 파레토 해의 수와 실행 시간 간의 균형을 맞추는 작업이 필요하다.

추가적인 실험에서 가중치를 0.1부터 0.9까지 9개로 줄 이고, 한 가중치 인스턴스에 대해 30초의 두배인 60초 동안 실행하여 총 9분으로 VNS의 해들을 구하였다. <Figure 4> 에서 <Figure 6>은 3 문제에 대해 9개의 가중치와 99개의 가중치에 대한 두 목적함수 값을 나타낸다. 그림은 99개 가중치에 비해 실행시간의 감소에도 효과적인 해를 생성 함을 보여준다. 9개 가중치로 구한 해는 이전의 99개 가중 치로 구한 해에 비해 약 18%의 실행시간이 소요되었지만 99개 해 중 지배하는 해의 비율은 30% 이상을 나타낸다 (<Table 3> 참조). 이 같은 결과는 가중치의 수를 줄이는 반면 한 가중치에 대한 실행시간을 증가시키면 효율적으 로 우수한 근사 파레토 해를 생성할 수 있음을 의미한다.

5. 결 론

공공 자전거 정적 재배치 문제로 대표되는 자원 재배 치 차량 경로계획 문제는 차량 운행 시간을 최소화하는 동시에 각 수요처에서 요구하는 자원의 요구량과 반납양 의 만족도를 최대화하는 다목적 최적화 문제로 정의될 수 있다. 자원 재배치를 위한 차량 경로계획에 실제적인 지 원을 위해서는 하나의 최적해보다는 다수의 파레토 최적 해를 제공하는 것이 의미가 있다. 본 연구에서는 우수한 파레토 최적해를 구하는 방법을 제안하였다. 문제에 파레 토 근사 최적해를 구하기 위해서는 SPEA2 등의 다목적 최적화 알고리즘을 이용하는 것이 일반적이다. 이와 별도 로 두 목적함수를 선형 결합한 단일 목적함수에서 가중치 를 변화시킨 다수의 문제에 대한 최적해를 구하여 이들을 파레토 근사해로 간주할 수 있다. 단일 목적 함수의 최적 화는 매우 우수한 해를 구할 수 있는 장점이 있지만, 문제 의 수가 커지면 많은 실행시간이 필요로 하는 단점을 갖 는다. VRP의 대표적 벤치마크 문제에 대해 실험한 결과 VNS로 구한 단일 목적함수의 해들이 SPEA2에 의한 해 들을 완전히 지배하여 우수한 파레토 근사 최적해를 형성 하였다. SPEA2를 비롯한 범용의 다목적 최적화 방법은 목적함수 간 트레이드 오프의 균형을 맞추는 해들을 생성 하는 이유로 자원 재배치 다목적 최적화 문제에는 우수한 해를 생성하지 못하였다. 반면, 부분 최적화에 기반을 둔 VNS 알고리즘에서는 목적함수 간 트레이드 오프를 배제 하기 때문에 보다 우수한 해를 생성할 수 있었다. 단일 목적 함수에 의한 파레토 해들을 구하는 실행시간을 줄이기 위해 서는 가중치의 수를 감소시킴으로써 문제의 수를 적게 할 수 있다. 이때 각 문제에 대한 실행시간은 증가시켜 보다 우수한 해를 구함으로써 파레토 집합에 포함된 해의 수와 해의 우수성 사이의 균형을 맞추는 작업이 필요하다.