Efficient Heuristics for Large-Scale Vehicle Routing Problems Using Particle Swarm Optimization

Efficient Heuristics for Large-Scale Vehicle Routing Problems Using Particle Swarm Optimization

A. Chandramouli (National Institute of Technology, Tiruchirappalli, India), L. Vivek Srinivasan (Velammal Engineering College, India) and T. T. Narendran (Indian Institute of Technology, Madras, India)
Copyright: © 2012 |Pages: 17
DOI: 10.4018/jgc.2012070103
OnDemand PDF Download:
No Current Special Offers


This paper addresses the Capacitated Vehicle Routing Problem (CVRP) with a homogenous fleet of vehicles serving a large customer base. The authors propose a multi-phase heuristic that clusters the nodes based on proximity, orients them along a route, and allots vehicles. For the final phase of determining the routes for each vehicle, they have developed a Particle Swarm Optimization (PSO) approach. Benchmark datasets as well as hypothetical datasets have been used for computational trials. The proposed heuristic is found to perform exceedingly well even for large problem instances, both in terms of quality of solutions and in terms of computational effort.
Article Preview

2. Literature Review

A variety of approaches based on heuristics and meta-heuristics are reported for the Capacitated Vehicle Routing Problem and its variants. Bullnheimer et al. (1999) developed an improved Ant System algorithm for the VRP with one central depot and identical vehicles. Baker and Ayechew (2003) considered the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), where customers, are served from a single depot. In this work, the vehicles were subject to a weight limit and the distance travelled. Berger and Barkaoui (2003) proposed a new genetic algorithm for the CVRP. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem was developed by Prins (2004). Osman et al. (2005) investigated the application of genetic algorithms to solve multi-objective routing problems. The proposed model eliminated the use of weight factor of each objective.

A new hybrid approximation algorithm based on discrete particle swarm optimization (DPSO) and simulated annealing (SA) was developed by Chen et al. (2006) to solve the CVRP. The algorithms combined global search and local search to search for the optimal results. Tavakkoli-Moghaddam et al. (2006) presented a linear integer model of CVRP with the independent route length to minimize the heterogeneous fleet cost and maximize the capacity utilization. The proposed model was solved by a hybrid simulated annealing (SA) based on the nearest neighborhood. A computational-efficient VRPTW algorithm, which was based on the principles of PSO, was developed by Zhu et al. (2006). Yu et al. (2008) proposed an Improved Ant Colony Optimization (IACO), which had a new strategy to solve the VRP.

Duhamel et al. (2009) addressed the Capacitated Location-Routing Problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The proposed solution method was a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS). Pop et al. (2010) proposed an effective metaheuristic algorithm for a Generalized Vehicle Routing Problem (GVRP) based on genetic algorithms. The GVRP consisted of designing optimal delivery or collection routes, subject to capacity restrictions, from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets. Marinakis et al. (2010) developed a hybrid PSO for the VRP which combines a PSO algorithm, the multiple phase neighborhood search–greedy randomized adaptive search procedure (MPNS–GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path re-linking (PR) strategy.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 1 Issue (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 1 Issue (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing