On the analysis of last-mile relief delivery on a tree network: Application to the 2015 Nepal earthquake

The last mile delivery in humanitarian relief supply often happens on a tree or an almost-tree network allowing split deliveries. We present a relief delivery model incorporating a tree network for last mile delivery. We developed a mixed integer programming (MIP) formulation with the goal of minimizing the unsatisfied demand of the population. For better computational performance, we reformulated the MIP exploiting the tree network structure and found that this gave an order of magnitude reduction in computational time. To further improve computational efficiency, we developed a heuristic solution method based on a decomposition scheme applied to the tree network formulation. This led to the Capacitated Vehicle Routing Problem on trees with split deliveries, for which we derived a closed-form solution. This decomposition scheme resulted in a further order of magnitude reduction in computation time. To demonstrate the application of our approach we applied our model to the humanitarian logistics relief operation encountered in the 2015 Nepal earthquake.