Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem

详细信息    查看全文

• 作者：Ehsan Teymourian^a ; Vahid Kayvanfar^b ; ^{v.kayvanfar@aut.ac.ir" class="auth_mail" title="E-mail the corresponding author} ; GH.M. Komaki^c ; M. Zandieh^d
• 关键词：Vehicle routing problem ; Hybrid meta-heuristic ; Intelligent water drops ; Cuckoo search ; Local search
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 March 2016
• 年：2016
• 卷：334-335
• 期：Complete
• 页码：354-378
• 全文大小：2336 K

文摘

The capacitated vehicle routing problem (CVRP) is investigated in this research. To tackle this problem, four state-of-the-art algorithms are employed: an improved intelligent water drops (IIWD) algorithm as a new swarm-based nature inspired optimization one; an advanced cuckoo search (ACS) algorithm; and two effective proposed hybrid meta-heuristics incorporating these methods, called local search hybrid algorithm (LSHA) and post-optimization hybrid algorithm (POHA). Both IIWD and ACS algorithms introduce new adjustments and features which improve the effectiveness of the proposed algorithms so as to optimize the CVRP. The hybrid methods, LSHA and POHA, take advantage of the merits of ACS and IIWD in exploring the solution space. These algorithms are enhanced to control the balance between diversification and intensification of the search process. Two well-known benchmark instances in the literature are solved so as to evaluate the proposed techniques. Experimental results are compared to the best obtained consequences previously reported in the literature. To present a comprehensive comparison between our proposed meta-heuristics and other state-of-the-art algorithms, some critical statistical test is employed; where the quality of our algorithms’ performance in terms of average results is also determined. It is shown that the LSHA and POHA algorithms can effectively cope with such problems, where in most of instances LSHA can yield the best gained solutions in the literature. Specifically, in 92.9% of cases of Christofides benchmark and in 50% of cases of Golden benchmark, the best obtained solutions in the literature are achieved.