Solving the Joint Location-Allocation-Routing Problem with a Branch-and-Cut Algorithm

We present a new mixed-integer program for a multi-depot, multi-vehicle capacitated location-allocation routing problem (LARP). The model simultaneously selects the locations of facilities, allocates customers to the intermediate facilities, and identifies the optimal number of capacitated vehicles and routes necessary to transport goods to each depot. The proposed model can be solved efficiently with a branch-and-cut algorithm available in most commercial MIP solvers. Our model is a generalized formulation of LARPs in the literature. To demonstrate the practical viability of the approach, we tested the computational performance of our model on a pseudo-real problem of minimizing transportation costs in an industrial rubber plantation that adopts a bi-layer transportation system. The computational results suggest that the new model can solve larger and more complex problem instances than those documented in the literature to reasonable levels of optimality