需求可拆分车辆路径问题的迭代局部搜索算法研究

摘要

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

目录

声明

致谢

摘要

1 引言

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1 车辆路径问题的分类

1．2．2 CVRP的研究现状

1．2．3 SDVRP的研究现状

1．2．4 VRP的求解目标

1．3 研究内容和目标

1．4 论文组织结构

2 相关理论知识

2．1 SDVRP数学模型和求解目标

2．2 SDVRP问题复杂性和最优解的特性

2．2．1 时间复杂度

2．2．1 最优解特性

2．3 启发式算法

2．3．1 传统启发式算法

2．3．2 元启发式算法

2．4 基于局部搜索的元启发式算法

2．4．1 迭代局部搜索算法

2．4．2 禁忌搜索算法

2．4．3 基于属性的爬山者算法

2．5 SDVRP邻域算子

2．6 好的启发式算法的特点

2．7 本章小结

3 多起点迭代局部搜索算法

3．1 基本定义

3．2 构造初始解

3．3 多起点迭代局部搜索算法

3．3．1 算法思想

3．3．2 算法框架

3．4 邻域算子

3．4．1 算法思想

3．4．2 算法框架

3．5 扰动算法

3．5．1 被扰动解的选择

3．5．2 扰动策略和扰动界限描述

3．6 算法分析

3．7 本章小结

4 实验结果

4．1 实验数据集及环境介绍

4．2 实验参数设置

4．2．1 扰动界限参数设置

4．2．2 精英解缓冲池大小的参数设置

4．3 局部搜索节点排序策略

4．4 实验结果对比

4．5 本章小结

5 总结与展望

5．1 论文总结

5．2 研究展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集