American Journal of Applied Sciences

Optimization of Capacitated Vehicle Routing Problem by Nested Particle Swarm Optimization

Karuppusamy Kanthavel and Paruchuri Prasad

DOI : 10.3844/ajassp.2011.107.112

American Journal of Applied Sciences

Volume 8, Issue 2

Pages 107-112

Abstract

Problem statement: Vehicle routing problem determines the optimum route for each vehicle as a sequence of visiting cities. The problem has been defined as NP-hard and exact solution is relatively difficult to achieve for real time large scale models. Though several attempts to solve the problem were made in the literature, new approaches may be tried to solve the problem to further reduce computational efforts. Approach: In this context this study focuses on maximum utilization of loading capacity and determines the optimum set of vehicle routes for Capacitated Vehicle Routing Problem (CVRP) by a Nested Particle Swarm Optimization (NPSO) technique. The algorithm is implemented as Master PSO and slave PSO for the identification of candidate list and route sequence in nested form to optimize the model. Results: Benchmarking data set of capacitated vehicle routing is considered for the evaluations. The total distance of set vehicle route obtained by the new approach is compared with the best known solution and other existing techniques. Conclusions/Recommendations: The NPSO produces significant results and computational performance than the existing PSO algorithms. This newly proposed NPSO algorithm develops the vehicle schedule without any local optimization technique.

Copyright

© 2011 Karuppusamy Kanthavel and Paruchuri Prasad. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.