A Genetic clustering algorithm for Multi Depot vehicle Routing Problem

Authors

  • Abubakar Aminu Muazu Umaru Musa Yaradua university,katsina, katsina state
  • Amina Nura Umaru Musa Yaradua University

DOI:

https://doi.org/10.56471/slujst.v2i1.74

Abstract

Multi Depot Vehicle Routing Problem (MDVRP) is a well-known real-life problem with many real life applications in the areas of transportation, distribution, and logistics. MDVRP is an extension of classical Vehicle Routing Problem (VRPs) with more than one depot, applicable to organizations which have several branches and each branch aimed at delivering goods or services to their customers simultaneously. This research work is aimed at proposing an efficient clustering algorithm for Clustering customers to an appropriate depot and was implemented in a classical MDVRP in order to quantify how travel distance and time are minimized. Genetic Algorithm (GA) was used to optimize the overall process because of its stochastic nature, efficiency, parallelism feature in solving combinatorial optimization problems. The main difference between the existing algorithm and the proposed algorithm is seen clearly in the rule 1 and 2 of the algorithm, the existing algorithm identified The closest depot to the customer and make an assignment then the closest depot to the closest neighbor node while the proposed algorithm identified closest customer, assign it to the depot and, then assign closest customer to the last assign customer. A simulation model for the algorithm was developed using MATLAB R2007b. The manual summation of the whole 33 benchmark instances of the result was conducted in order to obtain the optimal route for the existing algorithm which gives a total travelled distance of 80831.84 km and travelled time of 8635.1s; while total travelled distance for the proposed Genetic Clustering Algorithm was 75312.39 km and travelled time of 7340.8s. The result obtained from the Genetic Algorithm shows that travelled distance and traveled time were minimized when compared with existing results, the ability of Genetic Algorithm to diversify solution proved its effectiveness.

References

Abraham A. N. (2006). Evolutionary computation: from genetic algorithms to genetic programming.Stud.Comput.Intel.http://www.springerlink.com/content/l646l37m787 , 13, 1-20.

Alinaghian, M.; Shokouhi, N.(2018) Multi-Depot Multi-Compartment Vehicle Routing Problem, Solved By AHybrid Adaptive Large Neighborhood Search. Omega, 76, 85–99.

Braekers B, Ramaekers K, and Van Nieuwenhuyse I,(2016) “The vehicle routing problem: state of the art classification and review,” Journal of Computers & Industrial Engineering, vol. 99, pp. 300–313.

Chakraborty, R. (2010, June 01). www.myreaders.info/html/artificial_intelligence.html. Retrieved feb 01, 2017, from www.Myreaders.info.

Contardo C. and Martinelli R. (2014). A new exact algorithm for the multi depot vehicle routing problem under capacity and route length constraints,” in Discrete Optimizatio. 129-146.

Cordeau J. F., Gendreau M., and Laporte G. (2012). A tabu search heuristic for periodic and Multi Depot Vehicle Routing Problems. Wiley subscription Services, 105 - 119.

Eiben A., Smith J. (2015). Introduction to Evolutionary Computing. Springer-Verlag, Berlin Heidelberg.

Emir ˇZ. Dˇzenana Ð.and Emir B.(2020) An Adaptive Data-Driven Approach to Solve Real-World Vehicle Routing Problems in Logistics. published at Hindawi Complexity Volume 2, Article ID 7386701, 24 pages, https://doi.org/10.1155/2020/7386701

Fitriana R, Moengin P and Kusumaningrum U. Improvement Route for Distribution Solutions MDVRP (Multi Depot Vehicle Routing Problem) using Genetic Algorithm Published at IOP, IOP Conf. Series: Materials Science and Engineering528 (2019) 012042, doi:10.1088/1757-899X/528/1/012042

Hashim A., Muhammad H., Fazl H. Ahmadullah, Salman,Yasir S., (2016). Solving Traveling Salesman Problem through Optimization Techniques Using Genetic Algorithm and Ant Colony Optimization. Journal of Applied Environmental , 55-62.

Karakati S. and Podgorelec V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing. Applied soft computing , 1-14.

Li, Y.; Soleimani, H.; Zohal, M.(2019) An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. J. Clean. , 227, 1161–1172.

Mauro B., Franco M., Roberto B. (2008). Reactive Search and Intelligent Optimization (http:/ / reactive-search. org/ thebook). Springer Verlag.

Montoya-Torres J. R., Franco J. L., Isaza S. N., Jimenez H. F., Herazo-Padila N. (2015). A literature review on the vehicle routing problem with multiple depots. Journal of Computers and industrial Engineering , 115-129.

Subramanian A., Penna P. H. V., Uchoa E. and Ochi LS. (2013). Meta Heuristic Procedure for MDVRP and MDVRP with pick up and Delivery. Journal of Operational Research, Vol 221, no. 2, pp 285295.

Soonpracha K., mungwattana A., Janssens G. K. and Tharinee (2014). Heterogeneous VRP Review and Conceptual Framework. Proceedings of the International MultiConference of Engineers and Computer Scientists (pp. 1-8). Hong Kong: International MultiConference of Engineers and Computer Scientists. vol II, IMECS march 12-14, 2014, Hong Kong.

Surekha P and Sumathi S. (2011). Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms. World Applied Programming , 118-131.

Oliveira F.B., Enayatifar R. Sadaei H.J., Guimaraes F.G., Potvin J.Y. (2015). A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem. Journal of Expert Systems with Applications. Elsevier , 1-14.

Vidal T., Crainic T.G., Gendreau M., Prins C. (2010, 2011). Framework for Family of Vehicle Routing Problem. Journal of Transportation and Loguistics .

Yanjun S., Lingling L., Fanyi H., and Qiaomei H.( 2020). A Heuristic Solution Method for Multi-Depot Vehicle Routing-Based Waste Collection Problems. Published: 1 April 2020, Journal of Applied . Science.10, 2403, doi:10.3390/app10072403, www.mdpi.com/journal/applsci

Published

2021-01-23