Improved Shuffled Frog Leaping Algorithm and its multi-phase model for multi-depot vehicle routing problem |
| |
Affiliation: | 1. Research Institute of Computer Science, Technical University of Loja, San Cayetano alto, Loja, Ecuador;2. Department of Computing, Polytechnic University of Madrid, Boadilla del Monte, Madrid, Spain;1. School of Mathematical Science, Anhui University, Hefei, Anhui 230601, China;2. School of Business, Anhui University, Hefei, Anhui 230601, China;1. Institute for Infocomm Research, Singapore;2. University of Hong Kong, Hong Kong;3. Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Australia;1. Sobey School of Business, Saint Mary’s University, Halifax, NS B3H 2W3, Canada;2. Charlton College of Business, University of Massachusetts Dartmouth, Dartmouth, MA 02747, USA;1. Department of Information Technology, College of Computers and Information Technology, Taif University, Taif, Saudi Arabia;2. Department of Electrical and Computer Engineering, Concordia University, Montreal H3G 1T7, QC, Canada;3. The Concordia Institute for Information Systems Engineering (CIISE), Concordia University, Montreal H3G 1T7, QC, Canada |
| |
Abstract: | In the present work, an improved Shuffled Frog Leaping Algorithm (SFLA) and its multi-phase model are presented to solve the multi-depots vehicle routing problems (MDVRPs). To further improve the local search ability of SFLA and speed up convergence, a Power Law Extremal Optimization Neighborhood Search (PLEONS) is introduced to SFLA. In the multi-phase model, firstly the proposed algorithm generates some clusters randomly to perform the clustering analyses considering the depots as the centroids of the clusters for all the customers of MDVRP. Afterward, it implements the local depth search using the SFLA for every cluster, and then globally re-adjusts the solutions, i.e., rectifies the positions of all frogs by PLEONS. In the next step, a new clustering analyses is performed to generate new clusters according to the best solution achieved by the preceding process. The improved path information is inherited to the new clusters, and the local search using SFLA for every cluster is used again. The processes continue until the convergence criterions are satisfied. The experiment results show that the proposed algorithm possesses outstanding performance to solve the MDVRP and the MDVRP with time windows. |
| |
Keywords: | Evolutionary computation Vehicle routing problem Shuffled Frog Leaping Algorithm Extremal optimization |
本文献已被 ScienceDirect 等数据库收录! |
|