Article Preview
Top2. 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.