Abstract
When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.
Keywords : Shortest path; Vehicle routing; Dynamic programming; Column generation
Keywords : Shortest path; Vehicle routing; Dynamic programming; Column generation
Summary
추가적인 제약이 있는 VRP (Vehicle Routing Problem)는 CG (Column Generation)와 BnP (Branch-and-Price)를 사용해서 풀 수 있는데 솔루션 기법으로써 다이나믹 프로그래밍을 사용한다. 이 논문에서는 RCESPP (Resource Constrained Elementary Shortest Path Problem)를 exact하게 풀기 위한 방법으로 bounded bi-directional dynamic programming 을 제안한다. 3가지 유형의 VRP (CVRP, VRPDC, CVRPTW) 를 Solomon 데이터를 사용하여 실험하며 실험결과 기존의 mono-directional 알고리즘보다 우수한 성능을 가짐을 보인다.
본문 내용
VRP란 주어진 고객들을 모두 방문하는 차량 경로들의 집합을 구하는 문제다. 목적함수는 총 비용(거리)를 최소화하는 경로를 찾는 것이다. Column generation을 적용하기 위해 set covering 문제로 reformulation을 하는데 이렇게 하는 이유는 매우 타이트한 lower bound를 줄 수 있기 때문이다.
$$ \begin{align} \min \quad & \sum_{f \in \mathcal{F}} c_f z_f \notag \\ \text{s.t.} \quad & \sum_{f \in \mathcal{F}} x_if z_f \ge 1 \quad \forall i \in \mathcal{N} \\ & - \sum_{f \in \mathcal{F}} z_f \ge -V \\ & z_f \in \{0,1\}, \quad \forall f \in \mathcal{F} \end{align} $$
Righini, G., & Salani, M. (2006). Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, 3(3), 255-273. 논문 링크
여기서 모든 경로의 집합인 $\mathcal{F}$의 개수가 매우 많기 때문에 column generation에서 reduced cost가 음수인 경로만 찾아서 추가해야한다. 더 이상 reduced cost가 음수인 경로가 없으면 column 추가를 멈춘다. 이 논문에서는 2가지 bound를 사용하며 각각은 다음과 같다.
Fathoming unpromising states
Stopping the extension of the non-dominated states
Stopping the extension of the non-dominated states
첫 번째는 말 그대로 가망없는 상태는 고려하지 않는 것이고 두 번째는 지배되지 않는 상태의 확장을 멈추는 것이다. 즉, 더 이상 branching할 필요가 없다고 판단되는 상태를 일찍 파악해서 불필요한 branching을 줄이는 것이다.
(이 논문에서 reduced cost를 구할 때 $\lambda$를 2로 나누는 이유는 bi-directional이라 symmetry를 만들기 위함이다.)
앞서 3가지 VRP에 대해 실험한다고 했는데 각각은 CVRP (Capacitated vehicle routing probelm), VRPDC (vehicle routing problem with distribution and collection), CVRPTW (capacitated vehicle routing problem with time windows)이다. CVRP는 용량인 capacity만 고려하는 문제, VRPDC는 distribution과 collection을 고려하는 문제, CVRPTW는 capacity와 time windows를 고려하는 문제이다. 각각의 문제에 대해 제약을 만족하면서 완전한 경로가 되도록 state를 확장한다. 특히 dominance test는 이 알고리즘에서 굉장히 중요한 부분이다. 두 개의 레이블 $l_1 (S_1,R_1,C_1,i)$ 과 $l_2 (S_2,R_2,C_2,i)$에 대해 다음을 만족하면 $l_1$은 $l_2$를 지배한다. (여기서 $S$는 방문한 노드를 나타내는 벡터, $R$은 자원 소모를 나타내는 벡터, $C$는 cost를 나타낸다.)
$$ \begin{align} & S_1 \le S_2 \notag\\ & R_1 \le R_2 \notag\\ & C_1 \le C_2 \notag\\ \end{align} $$
위의 지배규칙을 적용하여 확장 가능한 노드로 계속 확장하면서 가능한 label의 집합을 구하는 다이나믹 알고리즘을 레이블링 알고리즘 (labeling algorithm) 이라고도 부른다. 더 이상 시행할 노드가 없을 때까지 반복한다. RCESPP의 mono-directional dynamic programming의 수도코드 (pseudocode)는 다음과 같다.
여기서 Extend 함수와 EFF 함수에서 다른 state로 확장시 자원 제약에 대해 확인하고 dominace test를 적용하여 state 추가 여부를 결정한다.
그러나 이러한 방법은 노드의 개수가 증가하면 label의 개수가 기하급수적으로 증가하기 때문에 계산시간이 급격하게 증가한다. 따라서 이 논문에서 bi-directional dynamic programming을 제안한 것이다. 고려해야할 state가 매우 많기 때문에 이를 절반으로 나누어 구하자는 생각이다. 즉, 시작노드와 끝노드에서 절반씩 경로를 구한 뒤 이를 합쳐 하나의 경로로 만드는 것이다. 이러한 방법은 기하급수적으로 많은 state를 다루지 않도록 해준다. Bi-directional dynamic programming의 수도코드는 다음과 같다.
mono-directional과 전체적으로 유사하며 Forward 와 Backward로 나누어 경로를 구하는 것이 다른 점이다. 여기서는 특정 방향 외의 다른 방향에서 path의 나머지 부분이 생긴다고 가정할 수 있다면 특정 방향으로는 확장을 하지 않아도 되고 optimal solution도 보장할 수 있음을 주장한다. 이를 위해 bounding에서는 optimal solution이 아닌 state를 알아내고 forward나 backward path의 확장을 멈추는 규칙을 적용한다. bi-directional 알고리즘에서 Join 함수의 수도코드는 다음과 같다.
이 알고리즘에서는 두 개의 path를 합치는 과정에서 중복된 솔루션이 포함될 수 있다. 중복된 솔루션이 생기면 계산적으로 비효율적이기 때문에 이를 방지하기 위해 Halfway를 고안하였다. 이는 forward와 backward로 결합된 path의 state가 half-way point에 가능한 가깝도록 하는 것이다. 즉, 가장 symmetry한 조합으로 두 개의 경로를 하나로 합치는 것이다.
실험결과 mono-directional에 비해 bi-directional이 확장되는 state의 총 개수도 적고 계산 시간도 더 빠른 편임을 보인다. 또한, 3600초 time-limit안에 mono-directional로 풀 수 없는 문제를 bi-directional으로 푼 경우도 있으므로 더 우수한 성능을 가졌다고 볼 수 있다.
여기서 Extend 함수와 EFF 함수에서 다른 state로 확장시 자원 제약에 대해 확인하고 dominace test를 적용하여 state 추가 여부를 결정한다. 그러나 이러한 방법은 노드의 개수가 증가하면 label의 개수가 기하급수적으로 증가하기 때문에 계산시간이 급격하게 증가한다. 따라서 이 논문에서 bi-directional dynamic programming을 제안한 것이다. 고려해야할 state가 매우 많기 때문에 이를 절반으로 나누어 구하자는 생각이다. 즉, 시작노드와 끝노드에서 절반씩 경로를 구한 뒤 이를 합쳐 하나의 경로로 만드는 것이다. 이러한 방법은 기하급수적으로 많은 state를 다루지 않도록 해준다. Bi-directional dynamic programming의 수도코드는 다음과 같다.
mono-directional과 전체적으로 유사하며 Forward 와 Backward로 나누어 경로를 구하는 것이 다른 점이다. 여기서는 특정 방향 외의 다른 방향에서 path의 나머지 부분이 생긴다고 가정할 수 있다면 특정 방향으로는 확장을 하지 않아도 되고 optimal solution도 보장할 수 있음을 주장한다. 이를 위해 bounding에서는 optimal solution이 아닌 state를 알아내고 forward나 backward path의 확장을 멈추는 규칙을 적용한다. bi-directional 알고리즘에서 Join 함수의 수도코드는 다음과 같다. 이 알고리즘에서는 두 개의 path를 합치는 과정에서 중복된 솔루션이 포함될 수 있다. 중복된 솔루션이 생기면 계산적으로 비효율적이기 때문에 이를 방지하기 위해 Halfway를 고안하였다. 이는 forward와 backward로 결합된 path의 state가 half-way point에 가능한 가깝도록 하는 것이다. 즉, 가장 symmetry한 조합으로 두 개의 경로를 하나로 합치는 것이다. 실험결과 mono-directional에 비해 bi-directional이 확장되는 state의 총 개수도 적고 계산 시간도 더 빠른 편임을 보인다. 또한, 3600초 time-limit안에 mono-directional로 풀 수 없는 문제를 bi-directional으로 푼 경우도 있으므로 더 우수한 성능을 가졌다고 볼 수 있다.
Cite
Righini, G., & Salani, M. (2006). Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, 3(3), 255-273. 논문 링크