文章基本信息

标题：IMPROVED WATER FLOW-LIKE ALGORITHM FOR CAPACITATED VEHICLE ROUTING PROBLEM
本地全文：下载
作者：MOKHTAR MASSOUD KERWAD ; ZULAIHA ALI OTHMAN ; SUHAILA ZAINUDIN 等
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2018
卷号：96
期号：15
出版社：Journal of Theoretical and Applied
摘要：The capacitated vehicle routing problem (CVRP) has many applications in different domains seeking ways to minimize the total traveled distance. Although the CVRP has been widely investigated in the literature, it is facing ongoing operational challenges. Moreover, despite various metaheuristics that have been proposed to solve this problem, its optimal solution is still not achieved. Thus far, the water-flow-like algorithm (WFA) has obtained a reasonable solution for this problem, with room for further improvement. The WFA has strategies for diversification (in the precipitation operation). This study aims to enhance the WFA for solving the CVRP by providing a good solution in terms of diversity and quality. The basic WFA is capable of solving the CVRP, however, it has problems in terms of slow convergence and the tendency of being trapped in the local optimum. Therefore, an improved WFA (IWFA) is proposed in this study to overcome this weakness by increasing the diversity of solution search in the precipitation operation using constructive heuristics (i.e., nearest neighbor, random method, and greedy randomized adaptive search procedure). Constructive heuristics aim to construct new solutions instead of duplicating existing ones. Computational results show that the IWFA outperforms the basic WFA with a solution quality improvement of up to 76.92% and is better than other state-of-the-art methods by up to 74.55%. This finding indicates that the IWFA is a promising approach for solving instances of CVRP.
关键词：Capacitated Vehicle Routing Problem; Metaheuristics; Constructive Heuristics; Water-Flow-Like Algorithm.