带硬时间窗的车辆路径问题求解算法研究

发布时间：2020-10-21 17:56

　　 随着现代经济飞速发展,尤其是电子商务平台的快速崛起,使物流配送成为其不可或缺的一部分,人们对物流配送服务的需求也日益增加,而车辆路径规划问题作为物流配送行业的重要问题,自提出以来就吸引了运筹学和组合优化等领域工作者的广泛研究。随着客户日趋严格的及时交付要求,带硬时间窗车辆路径问题越来越突出,而该问题的研究由于自身的复杂性目前还没有得到很好的解决。因此,本文基于此开展研究,具体研究内容如下:1.针对带硬时间窗车辆路径问题提出了一种改进型烟花算法进行求解,该算法能够利用信息交互进行资源分配。首先在传统烟花算法的基础上结合构造算法产生初始烟花和路径解决方案,然后对传统烟花算法的爆炸算子进行改进,使得烟花种群中适应度值最优烟花的爆炸搜索半径能够根据个体适应度值自适应地调整,增强算法后期局部搜索能力,再利用交叉重组完成爆炸火花的邻域搜索,并通过变异操作来增强种群多样性,最后通过烟花算法的分布式信息共享机制来避免算法早熟。2.针对改进型烟花算法在求解客户聚类测试集时存在行驶总距离较长问题,提出了一种基于模因算法的求解方法。考虑到初始解的好坏影响算法的收敛速度,首先通过模糊聚类生成初始可行解以保证种群多样性和算法后期的收敛性,然后对进化模块的进化算子进行改进,采用边缘交叉重组算子进行全局搜索以产生更多较优个体,最后在局部优化模块采用节点交换和k-opt作为模因算子,对较优个体进行局部优化以快速收敛到最优解。3.Solomon标准测试集作为当前国际通用的车辆路径规划问题参考标准,方便各算法的集中比较,本文基于该测试集对上述主要研究方法开展相关实验研究,对所获结果与当前已公布最优解进行比较,以验证所提算法的有效性和可行性。4.最后,以顺丰快递兰州集散中心为各营业点配送快递为例,本文基于Flexsim仿真软件进行仿真实验研究,实验结果表明所提出的算法对求解带硬时间窗车辆路径问题具有一定的理论意义和应用价值。
【学位单位】：兰州理工大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：U463.6
【部分图文】：

节约算法示意图

带硬时间窗的车辆路径问题求解算法研究8图 2.1 节约算法示意图图 2.2 节约算法求解路径图2.2.2 插入启发式算法插入算法(Insertion Heuristic)作为典型的构造启发式算法，主要分为顺序插入和并行插入两类。顺序插入算法是每一次只构建一条路径，开始时随机选择一个客户构建一条路径，然后将未安排的客户迭代地插入到当前路径中，直到满足车载容量或违反时间窗约束，算法的核心在于确定下一个被插入到路径的客户和客户插入的最佳位置。并行插入算法是同时构造几条路径，在插入之前首先确定插入的路径数量，然后构建几条初始路径，计算将待插入客户插入到现有路径位置后产生的距离增加值，最后按照距离增加值递增顺序依次插入客户直到所有客户都被插入可行路径。选取 Solomon25 个客户的 R101 测试数据集对并行插入算法进行测试，过程如图 2.3 所示。种子客户首先构建两条初始路径，路径外的点代表未安排的客户，然后根据距离增加值将未安排的客户依次插入到初始路径中，最后在满足车载容

图 2.3 插入算法示意图通过上述测试与分析发现：构造启发式算法将客户插入到初始路径中时，在插入前均需对约束进行检验，插入效率较低；当客户违反约束条件不能插入时则会构建新的路径，并且问题规模增加变复杂后，容易产生冗余路径。2.3 经典元启发式算法简介相比构造启发式算法，经典元启发式算法在算法设计上比较复杂，并且参数设置对算法性能影响较大，但采取全局搜索方式可以跳出局部最优并获得满意解。2.3.1 遗传算法遗传算法是由美国的 J.Holland 教授和他的学生于 1975 年借鉴生物界物竞天择适者生存的进化规律提出的一种随机化搜索方法，算法具体流程如下图 2.4 所示。遗传算法广泛应用于组合优化、信号处理和自适应控制等领域，其主要特点是可以直接对对象进行操作；具有良好的并行性和全局寻优能力；概率化的寻优
【相似文献】

相关期刊论文 前10条

1 欧阳普仁,杨叔子;一种改进的Marple算法[J];南京理工大学学报(自然科学版);1988年01期

2 黄小蓓;隆永红;;分布式数据库管理系统中的並发控制——算法及其性能分析[J];计算技术与自动化;1988年02期

3 冯成进;;0—1规划新算法的改进[J];曲阜师范大学学报(自然科学版);1988年02期

4 曾秀;魏振华;;猴群算法及其改进综述[J];电脑知识与技术;2017年32期

5 许灿英;;算法合谋反竞争问题初探[J];合肥工业大学学报(社会科学版);2019年02期

6 段艳明;肖辉辉;林芳;;新授粉方式的花授粉算法[J];计算机工程与应用;2018年23期

7 肖海军;王芬艳;卢常景;曹颖;;一种有效的多峰优化鸟群算法[J];中南民族大学学报(自然科学版);2018年04期

8 覃远年;梁仲华;;蚁群算法研究与应用的新进展[J];计算机工程与科学;2019年01期

9 肖辉辉;段艳明;;基于改进花授粉算法的移动机器人路径规划研究[J];软件导刊;2018年11期

10 莫海淼;赵志刚;曾敏;石静;温泰;;具有自适应步长与协同寻优的蝙蝠烟花混合算法[J];小型微型计算机系统;2019年07期

相关博士学位论文 前10条

1 张代雨;多学科优化算法及其在水下航行器中的应用[D];西北工业大学;2017年

2 钟林峰;复杂网络中关键节点的挖掘算法研究[D];电子科技大学;2018年

3 邱实;多光谱卫星遥感影像云及云阴影精准检测算法研究[D];电子科技大学;2018年

4 孙宁;人工免疫优化算法及其应用研究[D];哈尔滨工业大学;2006年

5 陆楠;关联规则的挖掘及其算法的研究[D];吉林大学;2007年

6 胡铟;基于单目视觉的运动目标检测与跟踪算法研究[D];南京理工大学;2008年

7 王珏;生物地理学优化算法的研究及应用[D];哈尔滨工程大学;2013年

8 黄松;面向多应用场景的粒子群优化算法研究[D];江南大学;2017年

9 安琦;信号侦收中的识别与分类理论与算法研究[D];电子科技大学;2017年

10 周瑞红;基于群智能优化理论的聚类改进方法及应用研究[D];吉林大学;2017年

相关硕士学位论文 前10条

1 朱昌龙;面向三维游戏场景的动态寻路算法的研究与应用[D];武汉工程大学;2018年

2 刘晓红;改进的AP-SVM算法研究及其在字母识别的应用[D];厦门大学;2017年

3 何逸凡;基于深度学习的视频动作时空检测算法研究[D];北京邮电大学;2019年

4 林婉莹;图书推荐系统中提升Top-N列表多样性算法研究[D];北京邮电大学;2019年

5 董静;基于主题模型和聚类算法的网络热点话题发现[D];河北大学;2019年

6 牛群;带硬时间窗的车辆路径问题求解算法研究[D];兰州理工大学;2019年

7 李佩茜;一种高效的基于教与学的社区发现算法的研究[D];厦门大学;2018年

8 裴华欣;自适应密度峰划分聚类算法研究及应用[D];浙江工业大学;2018年

9 朱炎亮;基于深度学习的人员异常操作视觉检测算法[D];浙江工业大学;2018年

10 曾辰子;改进差分进化算法及其收敛性分析[D];武汉理工大学;2018年

本文编号：2850426