Multi-Phase Meta-Heuristic for Multi-Depots Vehicle Routing Problem

Jianping Luo, Xia Li, Min-Rong Chen

College of Information Engineering, Shenzhen University, Shenzhen, 518060, China.

DOI: 10.4236/jsea.2013.63B018                

Abstract

In this work, we present a multi-phase hybrid algorithm based on clustering to solve the multi-depots vehicle routing problem (MDVRP). The proposed algorithm initially adopts K-means algorithm to execute the clustering analyses, which take the depots as the centroids of the clusters, for the all customers of MDVRP, then implements the local depth search using the Shuffled Frog Leaping Algorithm (SFLA) for every cluster, and then globally re-adjusts the solutions, i.e., rectifies positions of all frogs by the extremal optimization (EO). The processes will continue until the convergence criterions are satisfied. The results of experiments have shown that the proposed algorithm possesses outstanding performance to solve the MDVRP.

Keywords

Combinatorial Optimization; Vehicle Routing Problem; Shuffled Frog Leaping Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Eusuff M, Lansey K. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algo-rithm. Journal of Water Resources Planning and Man-agement 2003; 129 (3):10–25.
[2]	Luo Jian-ping, Li Xia, Chen Min-rong. A Novel Meta-heuistic for the Mul-ti-Depot Vehicle Routing Problem. Communications in Computer and Information Science 2012; 307:216-224.
[3]	Luo Jian-ping, Li Xia, Chen Min-rong. Improved Shuffled Frog Leaping Algorithm for Solving CVRP. Journal of Electronics & Information Technology 2011; 33(2): 30-434．
[4]	Crevier B, Cordeau J, Laporte G. The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research 2007; 176(2):756–773.
[5]	Villegas J G, Christian P. GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots. Engineering Applications of Artificial Intelligence 2010; 23(5):780–794.