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.

How to cite this paper

 Singamsetty, P & Thenepalle, J. (2021). Designing optimal route for the distribution chain of a rural LPG delivery system.International Journal of Industrial Engineering Computations , 12(2), 221-234.

Refrences

Ahmed, N., Das, S., & Purusotham, S. (2012). The oil tankers dispatching problem. Opsearch, 49(4), 366-385.
Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702.
Archetti, C., Doerner, K. F., & Tricoire, F. (2013). A heuristic algorithm for the free newspaper delivery problem. European Journal of Operational Research, 230(2), 245-257.
Belik, I., & Jörnsten, K. (2016). A new Semi-Lagrangean Relaxation for the k-cardinality assignment problem. Journal of Information and Optimization Sciences, 37(1), 75-100.
Bhavani, V., & Murthy, M. S. (2006). Truncated M-travelling salesmen problem. Opsearch, 43(2), 152-177.
Bianchessi, N., & Righini, G. (2007). Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 34(2), 578-594.
Chen, J. F., & Wu, T. H. (2006). Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5), 579-587.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96.
Gensch, D. H. (1978). An industrial application of the traveling salesman's subtour problem. AIIE Transactions, 10(4), 362-370.
Giardini, G., & Kalmar-Nagy, T. (2011). Genetic algorithm for combinatorial path planning: the subtour problem. Mathematical Problems in Engineering, 2011.
İnanlı, A., Ünsal, B., & Türsel Eliiyi, D. (2015). Route optimization for the distribution network of a confectionary chain. Promet-Traffic &Transportation, 27(6), 497-503.
Kalayci, C. B., & Kaya, C. (2016). An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 66, 163-175.
Katagiri, H., Hayashida, T., Nishizaki, I., & Guo, Q. (2012). A hybrid algorithm based on tabu search and ant colony optimization for k-minimum spanning tree problems. Expert Systems with Applications, 39(5), 5681-5686.
Keshtkaran, M., Ziarati, K., Bettinelli, A., & Vigo, D. (2016). Enhanced exact solution methods for the team orienteering problem. International Journal of Production Research, 54(2), 591-601.
Kumar, T., & Purusotham, S. (2018). The degree constrained k-cardinality minimum spanning tree problem: a lexi-search algorithm. Decision Science Letters, 7(3), 301-310.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
Montané, F. A. T., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595-619.
Murthy, M. S. (1976). A bulk transportation problem. Opsearch, 13(3-4), 143-155.
Polat, O., Kalayci, C. B., Kulak, O., & Günther, H. O. (2015). A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. European Journal of Operational Research, 242(2), 369-382.
Privé, J., Renaud, J., Boctor, F., & Laporte, G. (2006). Solving a vehicle-routing problem arising in soft-drink distribution. Journal of the Operational Research Society, 57(9), 1045-1052.
Sharma, S. K., Routroy, S., & Yadav, U. (2018). Vehicle routing problem: recent literature review of its variants. International Journal of Operational Research, 33(1), 1-31.
Stetsyuk, P. I. (2016). Problem statements for k-node shortest path and k-node shortest cycle in a complete graph. Cybernetics and Systems Analysis, 52(1), 71-75.
Subramanian, A., Drummond, L. M. D. A., Bentes, C., Ochi, L. S., & Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11), 1899-1911.
Subramanian, A., Uchoa, E., Pessoa, A. A., & Ochi, L. S. (2011). Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39(5), 338-341.
Subramanian, A., Uchoa, E., Pessoa, A. A., & Ochi, L. S. (2013). Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optimization Letters, 7(7), 1569-1581.
Tarantilis, C. D., & Kiranoudis, C. T. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of food Engineering, 50(1), 1-9.
Tarantilis, C. D., & Kiranoudis, C. T. (2002). Distribution of fresh meat. Journal of Food Engineering, 51(1), 85-91.
Tasan, A. S., & Gen, M. (2012). A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers & Industrial Engineering, 62(3), 755-761.
Thenepalle, J. K., & Singamsetty, P. (2018). Bi-criteria travelling salesman subtour problem with time threshold. The European Physical Journal Plus, 133(3), 1-15.
Volgenant, T., & Jonker, R. (1987). On some generalizations of the travelling-salesman problem. Journal of the Operational Research Society, 38(11), 1073-1079.
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122.
Wassan, N. A., Wassan, A. H., & Nagy, G. (2008). A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, 15(4), 368-386.
Xu, H., Li, Q., Wang, J., Luo, G., Zhu, C., & Sun, W. (2018). An optimization routing algorithm for green communication in underground mines. Sensors, 18(6), 1950.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2009). A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Systems with Applications, 36(2), 1070-1081.