Multi-Phase Meta-Heuristic for Multi-Depots Vehicle Routing Problem
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.
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.
Cite this paper
J. Luo, X. Li and M. Chen, "Multi-Phase Meta-Heuristic for Multi-Depots Vehicle Routing Problem," Journal of Software Engineering and Applications, Vol. 6 No. 3, 2013, pp. 82-86. doi: 10.4236/jsea.2013.63B018.
J. Luo, X. Li and M. Chen, "Multi-Phase Meta-Heuristic for Multi-Depots Vehicle Routing Problem," Journal of Software Engineering and Applications, Vol. 6 No. 3, 2013, pp. 82-86. doi: 10.4236/jsea.2013.63B018.
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.
[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.