Dr. Abubakar Muazu Aminu,.Amina Nura

Keywords: Genetic Algorithm, Multi Depot Vehicle Routing Problem, Optimization, Optimization Techniques Evolutionary algorithm

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.