Multi Objective Optimization of Multiple Depot Vehicle Routing Problem Using Swarm Intelligence Techniques

Abstract

The VRP refers to one of the combinatorial optimization problems in which clients are to be served by several vehicles. Multi-depot vehicle routing solution using swarm technique basically allocated to one of many depots, and then a vehicle from that depot is dispatched to service a specific group of customers along with a predetermined routing pattern that helps to solve the existing problems. newlineThe present work studied and implemented two Swarm Intelligence (SI) methods Ant Colony Optimization (ACO) and Intelligent Water Drop (IWD) to solve the multi-objective multiple depot vehicle routing problem. For solving these problems two algorithms, ACO and IWD algorithms have been developed. The algorithms are implemented and simulated using MATLAB version 15. Parallel methods are also implemented and simulated on MATLAB cluster of 8 nodes, for both the algorithms to achieve the speed of optimization. newlineThe ACO is based on the ants behavior to find the shortest route from one location to another, and their collective work for finding good solutions for the problems. This property has been imitated to construct solutions for ACO algorithm. Similarly, IWD algorithm inherits the properties of natural water drops to optimize the solutions efficiently. Both of the algorithms, ACO and IWD, are able to produce optimal set of solutions in reasonable time. newlineThe eACO and eIWD algorithm have been tested and verified on the standard benchmark problems datasets related to multiple depot vehicle routing problems (MDVRP). The results are compared with the best-known solutions and with the results of other existing heuristics/metaheuristics. From the results it is found that the eACO is improving many best-known solutions in reasonable time. The performance of enhanced IWD is also remarkable; it is improvingfew best-known solutions, and for other instances the results obtained is near optimal. newlineThe results verifies the effectiveness of both the algorithms and confirms them as better solution optimizing methods MDVRP problems, in comparison to the traditional SI methods and other heuristics. Hence, results indicate that the proposed methods are good alternative to solve MDVRP variants. newline newline