A memetic algorithm for a vehicle routing problem with backhauls
A memetic algorithm for a vehicle routing problem with backhauls
复制标题
DOI：
10.1016/j.amc.2006.01.059
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
R. Tavakkoli-Moghaddam;Alireza Saremi;Mohammad Sadegh Ziaee
中科院分区：
文献类型：
--
作者：
R. Tavakkoli-Moghaddam;Alireza Saremi;Mohammad Sadegh Ziaee
本文研究了一类带回程的车辆路径问题（VRPB）的推广。在这个问题中，一组客户分为两个子集组成的线路和回程客户。每个线路运输客户都要求从车辆段交付其需求。此外，指定数量的产品应该从回程节点拾取到仓库。VRPB问题是一个著名的强NP-难问题，人们提出了许多算法来近似求解这样一个难题。本文提出了一种模因算法（MA），它使用不同的局部搜索算法来解决VRPB。利用模因算法的优势，将路由节点间和路由节点内的交换作为进化算法的一部分。大量的计算测试的一些例子，从文献中揭示了所提出的算法的有效性。
This paper considers an extension of a vehicle routing problem with backhauls (VRPB). In this problem, a set of costumers are divided in two subsets consisting of linehaul and backhaul costumers. Each linehaul costumer requires delivering its demands from the depot. In addition, a specified quantity of products should be picked up from the backhaul nodes to the depot. The VRPB is a well-known NP-hard problem in strong sense and a number of algorithms are proposed for approximate solutions of such a hard problem. In this paper, a memetic algorithm (MA) is proposed which uses different local search algorithms to solve the VRPB. Exploiting power of memetic algorithm, inter and intra-route node exchanges are used as a part of this evolutionary algorithm. Extensive computational tests on some instances taken from the literature reveal the effectiveness of the proposed algorithm.