Research Article Open Access

Optimization of Capacitated Vehicle Routing Problem by Nested Particle Swarm Optimization

Karuppusamy Kanthavel1 and Paruchuri Prasad1
  • 1 ,
American Journal of Applied Sciences
Volume 8 No. 2, 2011, 107-112

DOI: https://doi.org/10.3844/ajassp.2011.107.112

Submitted On: 24 January 2011 Published On: 28 February 2011

How to Cite: Kanthavel, K. & Prasad, P. (2011). Optimization of Capacitated Vehicle Routing Problem by Nested Particle Swarm Optimization. American Journal of Applied Sciences, 8(2), 107-112. https://doi.org/10.3844/ajassp.2011.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.

  • 1,525 Views
  • 3,460 Downloads
  • 9 Citations

Download

Keywords

  • Capacitated Vehicle Routing Problem (CVRP)
  • Nested Particle Swarm Optimization (NPSO)
  • Travelling Salesman Problem (TSP)
  • metaheuristic techniques
  • local optimization