Computational Advances in Relief Distribution Models on Tree Graphs
MetadataShow full item record
A tragedy happened in Nepal in April 2015. A massive earthquake struck its capital, killing and injuring millions of people across the mountainous country. A large number of these people remained waiting for relief in remote and inaccessible regions in the mountains. To deliver relief items to these people the humanitarian logistics agencies setup an ingenious supply chain in which helicopters took the supplies to helicopter landing zones up to certain altitudes and the last mile delivery to the mountain villages was done by porters and pack animals traveling on mountain trails. In our study, we took up the challenge of optimizing this problem with the goal of minimizing the unsatisfied demand of the people in these villages and the cost of delivery. We developed two models for this problem. The first model is a multiperiod multimodal capacitated vehicle routing model. The second is a multiperiod multimodal capacitated vehicle routing model on trees also called the model with tree route formulation. The second model exploits the almost-tree shaped network of mountain trails in formulating the porter routing constraints. We solve both models by the branch-and-bound method. We show a considerable reduction in computation in the second method. The objective solution for the second model approximates well the solution of the first model as shown in the results. Furthermore, we develop a heuristic solution method for the second model. This method uses the multi-objective structure of our objective function to divide the model into multiple parts. It also takes advantage of the almost-tree shaped porter routing network. This method approximates the first model also as shown in the results. With this method, we show a further reduction in computation time of the solution.