Serial and Parallel Solutions to Variants of Vehicle Routing Problem Using Swarm Intelligence Techniques

Abstract

The present work studied and implemented two Swarm Intelligence (SI) methods ACO and IWD to solve the variants of vehicle routing problem, i.e. capacitated vehicle routing problem (CVRP) and vehicle routing problem with time windows (VRPTW). For solving these problems two algorithms, viz, enhanced Ant Colony Optimization (eACO) and enhanced Intelligent Water Drops algorithms have been developed. Both the algorithms are modified and improved version of basic ACO and basic IWD algorithms. 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 eACO 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 eACO algorithm. Similarly, eIWD algorithm inherits the properties of natural water drops to optimize the solutions efficiently. Both of the algorithms, eACO and eIWD, 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 up to 250 dimensions, which comprised of total 138 instances of CVRP and VRPTW datasets. The results are compared with the best-known solutions and with the results of other existing heuristics. From the results it is found that the eACO is improving many best-known solutions in reasonable time. The convergence time of eACO is further reduced in parallel implementation. The performance of enhanced IWD is also remarkable; it is improving few best-known solutions, and for other instances the results obtained is near optimal. The computing time for eIWD is very close to eACO computation time. newlineThe results verifies the effectiveness of both the algorithms and confirms them as better solution optimizing methods for CVRP and VRPTW problems, in comparison to the traditional SI methods and other heuristics. Hence, results indicate that the proposed methods are a good alternatives to solve VRP variants. newline newline