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

《需求可拆分车辆路径问题的迭代局部搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：密级：公开硕士学位论文需求可拆分车辆路径问题的迭代局部搜索算法研究作者姓名温真真学科专业计算机科学与技术指导教师于剑教授培养院系计算机与信息技术学院二零一五年三月硕士学位论文需求可拆分车辆路径问题的迭代局部搜索算法研究作者：温真真导师：于剑北京交通大学年月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。学校可以为存在馆

2、际合作关系的兄弟高校用户提供文献传递服务和交换服务。保密的学位论文在解密后适用本授权说明）签字日期：丨：年飞月，日签字曰期年月学校代码：密级：公幵北京交通大学硕士学位论文需求可拆分车辆路径问题的迭代局部搜索算法研究作者姓名：温真真学号：导师姓名：于剑职称：教授学位类别：工学学位级别：硕士学科专业：计算机科学与技术研究方向：人工智能北京交通大学年月致谢在毕业论文完成之际，衷心对在研究生学习期间为我提供无私帮助老师、同学和家人表示感谢。在研究生学习期间，于剑教授和林友芳教授他们渊博的知识开阔的视野给了我深深的启迪；他们严谨细致、一丝不苟的作风一直是我工作、学习中

3、的榜样；他们循循善诱的教导和不拘一格的思路给予我无尽的启迪。特别感谢董兴业副教授在论文算法思路方面和论文写作方面给予的无私指导，董兴业副教授在组合优化领域的专业知识为论文的推进工作给出了宝贵的指导意见，为最终算法的优化成型起到了相当重要的作用。也向教授向教授为数据集的搜集工作做出的大力支持表示衷心的感谢。在实验室的工作学习生活中，韩升老师都为我提供了许多无私的指导和帮助。实验室的师兄、师姐、师弟和师妹都给予了我热情的帮助。最后，对一直为我提供支持和关怀的家人表示感谢，他们一直都是我坚强的后盾和温暖的港湾，就是因为有他们的支持与理解我没有顾虑地走到今天。北京交

4、通大学硕士学位论文摘要摘要需求可拆分车辆路径问题（是带容量限制车辆路径问题（的变形，放松了模型中一个客户的需求只能由一辆车提供服务的限制。为了解决，本文提出一种多起点的迭代局部搜索（算法。首先使用算法求解出一个大的旅行商问题（解，然后以车辆的容量为标准，分割大的解，使分割后的路径满足车辆的容量限制，作为算法的初始解。迭代局部搜索算法是针对客户节点进行的，节点的局部搜索顺序按照其删除节约代价从大到小进行。通过将节点从当前解中删除然后将此节点重新插入到其在当前解中的最优位置。提出了一个适用于问题模型的贪婪的节点重新插入算法，尝试通过这个简单的重新插入算法来优化当

5、前解。在寻找最优位置时，考虑节点的需求可拆分这一策略，即考虑需求可能被一个或多个车辆提供服务。如果经过一定次数的连续的局部搜索，并且在这个过程中，当前解的质量均未得到提升，我们对当前解进行扰动，然后从扰动得到的解出发，继续进行局部搜索。为了在扩大搜索空间的同时保证重新开始局部搜索解的质量，我们设计了一个精英解缓冲池策略，将一组得到最优解可能性较大的精英解放入这个池中，从这个解中挑选进行扰动的解。本文的优化目标是最小化所有路径的总长度。对扰动界限的设置和算法框架中精英解缓冲池大小的设置进行了实验分析，为它们设置合理的参数值。分析了本文中提出的对节点进行排序算法

6、对实验结果的影响，实验证明了它的合理性。最后，算法在标准数据集上得到的实验结果与当前问题领域最先进的算法的对比实验表明算法是具有竞争力的。关键词：车辆路径问题；需求可拆分；元启发式算法；局部搜索；多起点北京交通大学硕士学位论文，，：北京交通大学硕士学位论文目录目录艘弓研究背景与意义国内外研究现状车辆路径问题的分类的研究现状的研究现状的求解目标研究内容和目标论文组织结构相关理论知识数学模型和求解目标问题复杂性和最优解的特性时间复杂度最优解特性启发式算法传统启发式算法兀启发式算法基于局部搜索的元启发式算法迭代局部搜索算法禁忌搜索算法基于属性的爬山者算法邻域算子好

7、的启发式算法的特点本章小结多起点迭代局部搜索算法基本定义构造初始解京交通大学硕士学位论文目录多起点迭代局部搜索算法算法思想算法框架邻域算子算法思想算法框架扰动算法被扰动解的选择扰动策略和扰动界限描述算法分析本章小结实验结果实验数据集及环境介绍实验参数设置扰动界限参数设置精英解缓冲池大小的参数设置局部搜索节点排序策略实验结果对比本章小结总结与展望论文总结研究展望参考文献作者简历及攻读硕士学位期间取得的研究成果独创性声明学位论文数据集北京交通大学硕士学位论文引言研究背景与意义采购，生产和分配是供应链的三个传统阶段。近年来，生产设施内部和外部之间材料和信息流的管理

8、己受到越来越多的关注。此外，运送货物和商品的成本占供