PBIL算法求解车辆路径优化问题

发布时间：2017-09-16 13:02

  本文关键词：PBIL算法求解车辆路径优化问题

  更多相关文章： 车辆路径问题 PBIL算法 全局搜索 局部搜索

【摘要】：物流产业是国民经济发展的第三重要源泉,特别是进入21世纪以来,大力提倡发展现代物流产业,而车辆路径问题是现代物流的关键环节,对车辆路径问题的研究具有重要的理论及经济意义。1959年Dantzing和Ramser首次提出车辆路径问题(Vehicle Routing Problem, VRP),自提出以来,VRP问题一直是众多专家在运筹学、应用数学及计算机应用等学科领域的研究热点。根据约束条件的不同可以将VRP问题划分为多个调度问题。研究最早的是非对称TSP问题(Asymmetric Traveling Salesman Problem, ATSP);研究较多是的带容量约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP);研究中与实际结合紧密的是带软时间窗约束车辆路径问题(Vehicle Routing Problem with Soft Time Windows, VRPSTW)。VRP问题已经被证明具有NP-hard属性,在应用和理论上都有较高的研究意义。传统的精确算法不能对大规模的此类问题求解,因此需要用智能算法求得较优解。种群增量学习算法(Population-based Incremental Learning Algorithm, PBIL)是分布估计算法(Estimation of Distribution Algorithms,EDA)的一种,其特有的概率模型可以引导算法在优质解空间中的细致搜索。本文主要用种群增量学习算法对ATSP、CVRP、VRPSTW问题进行求解。(1)针对ATSP问题,提出了一种新的PBIL算法,将传统PBIL算法中的二进制编码方式改进为十进制的编码方式,减少编码的转换过程,设计新的学习概率矩阵更新方式,提高了算法的搜索效率。(2)针对带容量约束的问题,改进(1)中PBIL算法里的学习概率矩阵更新方式,使得全局搜索更加精确有效,和局部算法相结合,增强了算法的鲁棒性。(3)针对软时间窗问题,将(2)PBIL算法中融入均匀分布和轮盘赌两种选择方式,并加入2-opt和Insert局部搜索,将概率矩阵设计为三维,平衡全局搜索和局部搜索,提高算法的有效性和高效性。本文最后都用仿真实验和算法比较的方式,证明了上述所提出算法的有效性。
【关键词】：车辆路径问题 PBIL算法 全局搜索 局部搜索
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U116.2;F252
【目录】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 绪论11-25
• 1.1 车辆路径优化问题背景及意义11
• 1.2 车辆路径问题描述11-18
• 1.2.1 车辆路径问题构成与分类11-14
• 1.2.2 车辆路径问题数学模型描述14-15
• 1.2.3 车辆路径优化问题国内外研究现状15-18
• 1.3 求解车辆路径优化问题算法概述18-22
• 1.3.1 精确算法18
• 1.3.2 启发式算法18-22
• 1.4 本文主要的研究工作22-25
• 第二章 PBIL算法求解非对称TSP问题25-35
• 2.1 引言25-26
• 2.2 ATSP的数学模型26
• 2.3 NPBIL算法26-31
• 2.3.1 解的表示26-27
• 2.3.2 学习概率矩阵简介27
• 2.3.3 解的生成27-28
• 2.3.4 学习概率矩阵的更新28-29
• 2.3.5 NPBIL的局部搜索29-30
• 2.3.6 NPBIL的算法步骤30-31
• 2.4 实验仿真与比较31-32
• 2.4.1 实验设置31
• 2.4.2 NPBIL算法与其他算法的比较31-32
• 2.5 本章小结32-35
• 第三章 PBIL算法求解带容量约束的VRP问题35-49
• 3.1 引言35-36
• 3.2 带容量约束VRP问题的模型36-37
• 3.3 混合的PBIL算法37-44
• 3.3.1 解的表示37-38
• 3.3.2 学习概率矩阵模型38
• 3.3.3 解的生成38-40
• 3.3.4 学习概率矩阵的更新40
• 3.3.5 HPBIL的局部搜索40-42
• 3.3.6 HPBIL的算法步骤42-44
• 3.4 实验仿真与比较44
• 3.4.1 实验设置44
• 3.4.2 HPBIL算法与其他算法的比较44
• 3.5 本章小结44-49
• 第四章 PBIL算法求解带软时间窗的VRP问题49-61
• 4.1 引言49-50
• 4.2 带软时间窗的VRP问题模型50-52
• 4.3 改进的PBIL算法52-56
• 4.3.1 解的编码52
• 4.3.2 全局搜索52-55
• 4.3.3 局部搜索55
• 4.3.4 IPBIL的算法步骤55-56
• 4.4 仿真实验与比较56-57
• 4.5 本章小结57-61
• 第五章 总结与展望61-63
• 5.1 论文总结61-62
• 5.2 研究展望62-63
• 致谢63-65
• 参考文献65-71
• 附录A 攻读硕士期间研究成果71

【相似文献】

中国期刊全文数据库 前10条

1 高丽萍;彭敦陆;邓桂英;陈庆奎;;面向企业应用的“算法设计与分析”课程建设改革探索[J];中国电力教育;2011年20期

2 姜枫;;“算法设计与分析”课程教学改革探索[J];中国电力教育;2013年26期

3 苏安婕;吴志刚;;关键步分解法在算法设计与描述中的应用[J];成组技术与生产现代化;2011年03期

4 雷小园;;排列组合的算法设计与C++实现[J];中国新技术新产品;2010年10期

5 肖建华,何宏,陈展,欧阳湘江;算法中数学策略的应用与研究[J];湖南工程学院学报(自然科学版);2004年02期

6 余嵘华,张霆,张云;票证结存算法设计[J];合肥工业大学学报(自然科学版);2000年S1期

7 冯平;黄名选;;由频繁项集生成关联规则的算法设计和实现[J];广西工学院学报;2007年01期

8 王卿;路晓伟;;高等院校学分制教学排考问题算法设计[J];上海理工大学学报;2007年06期

9 刘永广;叶梧;冯穗力;庄宏成;;基于蚁群算法的无线Mesh网公平路由算法[J];华南理工大学学报(自然科学版);2009年01期

10 邢春峰,柳重堪;联想记忆系统的学习算法设计(I)[J];北京联合大学学报;1998年03期

中国重要会议论文全文数据库 前10条

1 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

2 杨盘洪;朱军祥;赵建安;杨静;;机动目标跟踪的模糊变结构交互多模算法[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

3 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

5 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

6 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

7 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

8 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

9 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

10 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

中国重要报纸全文数据库 前1条

1 ;算法设计的策略[N];电脑报;2003年

中国博士学位论文全文数据库 前10条

1 江立辉;基于干扰对齐的多用户无线传输优化方法研究[D];哈尔滨工业大学;2015年

2 史亚;多核学习算法与应用研究[D];西安电子科技大学;2015年

3 薛菲;基于蝙蝠算法的启发式智能优化研究与应用[D];北京工业大学;2016年

4 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

5 龙海侠;进化算法及其在生物信息中的应用[D];江南大学;2010年

6 谭跃;具有混沌局部搜索策略的粒子群优化算法研究[D];中南大学;2013年

7 尤海峰;求解隐式目标优化问题的交互式进化算法研究[D];中国科学技术大学;2011年

8 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

9 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

10 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

中国硕士学位论文全文数据库 前10条

1 李欣园;基于选择偏好的组合聚类算法研究与实现[D];内蒙古大学;2015年

2 杨潇;界约束非线性最小二乘问题的无导数算法[D];上海交通大学;2015年

3 王晓璐;基于Zynq的LS-SVM算法加速器设计[D];哈尔滨工业大学;2015年

4 楼磊磊;医疗保险数据异常行为检测算法和系统[D];浙江大学;2015年

5 齐海龙;基于改进人工蜂群算法的非线性系统辨识方法研究[D];北京化工大学;2015年

6 蔡平梅;结构化稀疏信号的恢复算法研究[D];上海大学;2015年

7 赵晨阳;基于蚁群算法的高阶图匹配方法研究[D];西安电子科技大学;2014年

8 苟清松;多目标粒子滤波检测前跟踪算法研究[D];电子科技大学;2015年

9 李枝勇;蝙蝠算法及其在函数优化中的应用研究[D];上海理工大学;2013年

10 李莲;基于蜂群和粗糙集的聚类算法研究[D];长沙理工大学;2014年

，

本文编号：863189