Designing optimal route for the distribution chain of a rural LPG delivery system

Abstract

A practical distribution system that arises in the context of delivering liquefied petroleum gas (LPG) through cylinders is considered in this study. To meet all the challenging constraints, the model is explicitly considered as a simultaneous pickup and delivery single commodity truncated vehicle routing problem with the homogeneous fleet of vehicles. The aim of this problem is to find the optimal routes for the set of vehicles locating at the distributing agency (DA), which offers simultaneous pickup and delivery operations over single commodity (i.e. LPG cylinders) to a fixed subset (need not serve all delivery centers) of delivery centers at rural level. The model is designed using zero-one integer linear programming. For proper treatment of the present model, an exact Lexi-search algorithm (LSA) has been developed. A comparative study is performed between the LSA and existing results for the relaxed version of the present model. Further, the efficiency of the LSA is tested through numerical experiments over small and medium CVRP benchmark test instances. The extensive computational results have shown that the LSA is productive and revealed that the real solutions have more consistent than the integral solutions in the presence of truncation constraint.