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

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.