需求可拆分车辆路径问题(the Split Delivery Vehicle Routing Problem, SDVRP)是带容量限制车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)的变形,SDVRP放松了CVRP模型中一个客户的需求只能由一辆车提供服务的限制。为了解决SDVRP,本文提出一种多起点的迭代局部搜索(multi-restart iterated local search, MRSILS)算法。首先使用GENIUS算法求解出一个大的旅行商问题(Travelling Salesman Problem, TSP)解,然后以车辆的容量为标准,分割大的TSP解,使分割后的路径满足车辆的容量限制,作为MRSILS算法的初始解。迭代局部搜索算法是针对客户节点进行的,节点的局部搜索顺序按照其删除节约代价从大到小进行。通过将节点从当前解中删除然后将此节点重新插入到其在当前解中的最优位置。提出了一个适用于SDVRP问题模型的贪婪的节点重新插入算法,尝试通过这个简单的重新插入算法来优化当前解。在寻找最优位置时,考虑节点的需求可拆分这一策略,即考虑需求可能被一个或多个车辆提供服务。如果经过一定次数的连续的局部搜索,并且在这个过程中,当前解的质量均未得到提升,我们对当前解进行扰动,然后从扰动得到的解出发,继续进行局部搜索。为了在扩大搜索空间的同时保证重新开始局部搜索解的质量,我们设计了一个精英解缓冲池策略,将一组得到最优解可能性较大的精英解放入这个池中,从这个解中挑选进行扰动的解。本文的优化目标是最小化所有路径的总长度。对扰动界限的设置和MRSILS算法框架中精英解缓冲池大小的设置进行了实验分析,为它们设置合理的参数值。分析了本文中提出的对节点进行排序算法对实验结果的影响,实验证明了它的合理性。最后,MRSILS算法在标准数据集上得到的实验结果与当前SDVRP问题领域最先进的算法的对比实验表明MRSILS算法是具有竞争力的。