A Branch-Cut-and-Price Approach for the Asymmetric Vehicle Routing Problem

본 연구는 비대칭차량경로문제의 개선된 경로분할모형을 소개한다. 기존 모형과 달리 본 모형은 차량과 독립적인 분할경로를 사용하며, 절단면을 사용해서 경로의 실행가능성을 확보한다. 모형에 수많은 열과 행이 있기에, 각 분지문제에서 열생성과 행생성과정을 반복하는 분지-열/행생성 알고리듬을 통해 최적화를하며, 두 가지의 branching 전략을 채택한다. 벤치마킹문제를 사용한 실험연산에서 본 알고리듬의 결과를 기존 문헌의 결과와 비교하여 유효성을 확인한다.

We introduce an updated route-splitting model for the asymmetric vehicle routing problem. In this model, variables are vehicle-independent and the feasibility of routes is sought by the rounded capacity cuts. To deal with the exponentially large number of columns and rows in the model, a branch-cut-and-price algorithm is developed for optimization. Two complementary branching strategies are adopted. The overall approach is tested on the benchmark test problems and compared with earlier results in the literature.