基于禁忌搜索和蚁群的混合智能算法解决VRP的研究

发布时间：2020-07-18 18:23

【摘要】：车辆路径问题作为车辆调度的重要环节,是目前优化领域的难点问题之一。经过国内外学者的不断研究已取得了丰富的研究成果和经验,并广泛运用于在工业生产、计算机科学等领域。根据车辆路径问题的问题特性和数学模型,怎样用科学算法在合理的时间内搜索到问题的最优路径依然是最优化问题的研究重点,突出了重要的理论价值和现实意义。由于精确算法在求解最优化问题时,时间会根据问题规模的大小逐级变长的重大缺陷,众多学者提出了人工智能算法,这为解决车辆路径问题提供了良好的选择空间和无限发散思维。虽然蚁群算法和禁忌搜索算法在求解车辆路径优化问题中的应用兴起已久,但其潜力还有待进一步挖掘,以下是本文的主要研究内容:(1)对基本禁忌搜索算法精度和效率差的问题提出了改进策略。考虑到基本禁忌搜索算法精度差,本文提出了两点改良:优化算法结构和丰富邻域搜索函数。改进算法在判断该候选解是否优于公告板中最优值这一过程做出调整。当然,改进算法是在保留了基本TS算法思想的基础上做出了修改。改进后的禁忌搜索算法使用多种邻域操作算子,极大地丰富了邻域函数。其次,针对禁忌搜索算法效率差这一劣势,本文合理设计禁忌表结构和选择禁忌对象。对比Solomon标准数据库中的算例数据,改进后的禁忌搜索算法与基本算法不论是在效率还是精度上都有明显的改善,说明禁忌搜索算法有很好的理论研究价值和意义;与其他算法对比的结果也显示了改进后的禁忌搜索算法也有较强的优势。(2)在众多智能优化算法中,蚁群算法拥有良好的全局搜索性能,但是局部搜索能力又很弱且整体搜索效率低,纵观其他算法,发现禁忌搜索算法刚好可以弥补蚁群算法这一缺点。然而禁忌搜索算法对初解有较强的敏感度,好的初始解能使算法快速收敛到最优解。因此有必要设法提出一种混合智能优化算法,使其相辅相成,实现更好的求解结果。蚁群算法研究进程已久,不管是理论研究还是实际应用上都取得了重大突破。在混合算法中蚁群算法使用自适应的期望启发因子,能够使信息素合理的迭代。此外,为了降低禁忌搜索对初始解的依耐性,本文先使用蚁群算法迭代出具有一定差异度的若干较优解,作为改进禁忌搜索算法的初始解,并保留信息素的信息来指导禁忌搜索算法快速迭代。混合算法有效利用了禁忌搜索算法较强的局部搜索能力和蚁群算法并行的全局搜索能力,力求在避免局部收敛到最优值和算法的收敛性能上有较大改善。对比单一蚁群算法和禁忌搜索算法以及其他人工智能算法,混合后算法在精度上有了提升,说明禁忌搜索算法和蚁群算法是有竞争力的;而且与标准数据库的已知最优解的差距缩小,说明混合算法在求解车辆路径问题上是有优势的。
【学位授予单位】：武汉轻工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：U491;TP18
【图文】：

VRP示意图

TS算法流程图

蚂蚁觅食原理示意图

【相似文献】

相关期刊论文 前10条

1 吴永杰;;基于多目标禁忌搜索算法的认知无线电频谱分配[J];中国新通信;2014年22期

2 赵月;胡玉梅;;求解可重入并行机调度的混合禁忌搜索算法[J];计算机应用;2012年09期

3 傅成红;符卓;;一种毗邻信息改进的车辆路径问题禁忌搜索算法[J];系统工程;2010年05期

4 廖飞雄;马良;王攀;;一种改进的禁忌搜索算法求解背包问题[J];计算机应用与软件;2009年03期

5 张国胜;方宗德;李爱民;庞辉;;基于混沌技术的连续禁忌搜索算法研究[J];计算机应用研究;2008年02期

6 汪嘉杨;李祚泳;倪长健;熊建秋;;基于混合禁忌搜索算法的水位流量关系拟合[J];系统工程;2006年06期

7 王宏;潘寒尽;;禁忌搜索算法在系统可靠性分配中的应用[J];电子产品可靠性与环境试验;2006年05期

8 黄明,闫淑娟,梁旭;遗传算法和禁忌搜索算法在车间调度中的研究进展[J];工业控制计算机;2004年02期

9 邓泽林,黄文奇,周立刚;求解车间作业调度问题的快速禁忌搜索算法[J];华中科技大学学报(自然科学版);2003年11期

10 方永慧,刘光远,贺一,邱玉辉;一种基于插入法的禁忌搜索算法[J];西南师范大学学报(自然科学版);2003年06期

相关会议论文 前10条

1 王鑫;彭绍雄;;基于改进的禁忌搜索算法求解旅行商问题[A];第三届中国指挥控制大会论文集（下册）[C];2015年

2 刘振刚;王道平;;一类单机调度问题的新邻域及其禁忌搜索算法[A];第二十九届中国控制会议论文集[C];2010年

3 李菊芳;贺仁杰;姚锋;谭跃进;;成像卫星集成调度的变邻域禁忌搜索算法[A];社会经济发展转型与系统工程——中国系统工程学会第17届学术年会论文集[C];2012年

4 黄金平;郑秉霖;;改进禁忌搜索算法在大规模资源分配问题中的应用[A];1997中国控制与决策学术年会论文集[C];1997年

5 王涛;蔡延光;张新政;;禁忌搜索在车辆路径问题中的应用[A];04'中国企业自动化和信息化建设论坛暨中南六省区自动化学会学术年会专辑[C];2004年

6 刘长石;;有时间窗车辆路径问题的一种改进禁忌搜索算法[A];人文科技发展与管理创新——湖南省管理科学学会2009年度学术年会论文集[C];2009年

7 吴超;姚宗含;林源;;高速公路通行卡调配路径算法研究[A];第十四届中国智能交通年会论文集[C];2019年

8 范静;唐国春;;同时收发运输路径问题的禁忌搜索算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

9 方华;;对于树枝形铁路专用线取送车顺序的探讨[A];第十八届站场与枢纽年会论文集[C];2017年

10 李磊;孙俊清;韩梅;;基于“作业面”的集装箱码头集卡路径优化的研究[A];第二十七届中国控制会议论文集[C];2008年

相关博士学位论文 前10条

1 符卓;开放式车辆路径问题及其应用研究[D];中南大学;2003年

2 段凤华;带软时间窗约束的开放式车辆路径问题及其应用[D];中南大学;2010年

3 李琳;电子商务环境下物流配送中若干优化问题的研究[D];东北大学;2010年

4 李坤;物流运作管理中的装载计划及物流调度[D];东北大学;2010年

5 徐开亮;生产任务加工时间可控条件下的生产调度问题研究[D];西安交通大学;2010年

6 蒋大奎;按单生产直达运输模式下的生产运输集成调度问题研究[D];天津大学;2012年

7 王佳;城市常规公交线网与发车频率优化设计[D];中南大学;2013年

8 马天义;低功耗软硬件划分算法研究[D];哈尔滨工业大学;2009年

9 杨晨凯;延迟优化的内容分发技术研究[D];中国科学技术大学;2016年

10 宁涛;混合量子算法在车辆路径问题中应用的研究[D];大连海事大学;2013年

相关硕士学位论文 前10条

1 付秦红;基于禁忌搜索和蚁群的混合智能算法解决VRP的研究[D];武汉轻工大学;2018年

2 刘敏丽;基于改进禁忌搜索算法的含分布式电源配电网规划研究[D];湖北民族大学;2019年

3 马永秀;基于时空网络的航班延误恢复问题建模及优化方法[D];中国民航大学;2017年

4 王岩;和声策略禁忌搜索算法[D];东北大学;2008年

5 马艳萍;基于禁忌搜索算法的图着色研究与实现[D];陕西师范大学;2011年

6 王玉晶;基于禁忌搜索算法的生理信号情感识别研究[D];西南大学;2008年

7 王明兴;连续禁忌搜索算法改进及应用研究[D];浙江大学;2005年

8 郭娜;基于节约算法和移动方向的禁忌搜索算法[D];大连理工大学;2009年

9 王民生;禁忌搜索算法及其混合策略的应用研究[D];大连交通大学;2005年

10 摄伟;基于禁忌搜索算法的区域电网无功优化[D];西安科技大学;2008年

本文编号：2761261