基于带时间窗车辆路径问题的改进人工蜂群算法的研究

发布时间：2020-06-22 20:55

【摘要】：带时间窗车辆路径问题(Vehicle Routing Problems Wih Time Windows,简称VRPTW)是在基本车辆路径问题(Vehicle Routing Problems,简称VRP)基础上增加时间窗约束衍生而来的组合优化问题。由于VRPTW已被证明是一个NP难问题,因此如何有效求解VRPTW是一个研究难点。人工蜂群算法(Artificial Bee Colony Algorithm,简称ABC算法)是一种模仿蜜蜂采蜜觅食等行为的群智能优化算法,在求解NP难问题中有非常不错的效果。本文围绕车辆数和车辆行驶距离这两个目标基于VRPTW对ABC算法做了大量改进以及研究,主要工作如下:本文首先探讨了ABC算法的理论基础,根据VRPTW的特点将标准ABC算法离散化。本文设计了一种新的数据结构,采用两个方向的单链表,使用二维编码方式表示每个解,重新定义了蜂群在对食物源进行邻域变换时的编码更新公式,给出了建立初始种群以及产生侦查蜂的方法。由于标准离散ABC算法求解精度很差,本文对标准离散ABC算法做了改进,提出了改进离散ABC算法。结合二维编码的结构,算法在蜂群做邻域搜索时采用了路径间和路径内两种搜索方向,并提出了一种最优插入策略以提高插入操作的成功率。在侦查蜂阶段本文引入了限制变量,设计了新的淘汰机制,增加产生新解的迭代次数以提高新解的竞争力。本文设置了公告栏,通过更新公告栏记录全局最优解,防止最优解在迭代过程中被抛弃。通过与标准离散ABC算法、其他启发式算法、数据库中最优解做对比,改进离散ABC算法在能找到最佳车辆数的情况下保持很高的精度。为了进一步探索改进离散ABC算法种群收敛能力,本文从方差和熵两个方面研究了该算法在求解VRPTW中的种群多样性。通过实验数据证明改进离散ABC算法在整个迭代过程中种群分布较广,空间搜索能力很强,一直维持一个比较高的种群多样性。
【学位授予单位】：武汉轻工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18
【图文】：

第二章 理论基础第 章 理论基础本章是论文的理论基础，介绍了 VRPTW 和 ABC 算法的基础知识，为究做理论准备。VRPTW 理论基础本文研究的是单车场、单时间窗、硬时间窗、非时变的 VRPTW。如图，该问题可描述为：从配送中心派送若干相同载重量的车辆，车辆在满点时间窗约束、客户服务唯一性约束、自身载重量约束等其他约束条件完所有客户点之后，最后回到配送中心，使得所需车辆数最少和所有车总路程最短。二

图 4.1 标准蜂群算法和改进蜂群算法收敛对比结果分析，从图 4.1 中我们可以看出，无论是标准离散 ABC 算法，还是改进离散 ABC 算法，在求解 VRPTW 问题上的收敛速度都特别快，在很短的时间内都可以搜寻到一个局部满意解，这也是 ABC 算法的一大优势，从两个算法的收敛对比中我们可以发现改进离散 ABC 算法的搜索深度和局部搜索能力都比标准离散 ABC 算法更强，更容易跳出局部最优，在解空间中继续寻找更好的解，直至找到全局最优解。下面我们根据不同的算例来对比分析标准离散 ABC 算法和改进离散 ABC算法，见表 4.1。表 4.1 标准离散 ABC 算法和改进离散 ABC 算法求解 VRPTW 结果比较标准 ABC 算法 改进 ABC 算法算例车辆数 最优值 平均数 车辆数 最优值 平均数C101.100 17 1351.6 1415.6 10 828.9828.9C102.100 15 1266.2 1341.5 10 828.9830.7

【相似文献】

相关期刊论文 前10条

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

2 黄小蓓;隆永红;;分布式数据库管理系统中的N&发控制——算法及其性能分析[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];电子测量与仪器学报;2019年07期

10 梁昔明;高超;龙文;;基于速度越界处理与高斯扰动的改进蝙蝠算法[J];数学的实践与认识;2019年19期

相关会议论文 前10条

1 苗强;刘晓琳;王仲奇;;随机球重叠判断算法改进研究工作进展[A];中国原子能科学研究院年报 2013[C];2014年

2 殷凡;王海斌;李超;;改进蝙蝠算法在DOA估计中的应用[A];2019年全国声学大会论文集[C];2019年

3 李超;余昭平;;基于矩阵的Apriori算法改进研究[A];第二届全国信息检索与内容安全学术会议（NCIRCS-2005）论文集[C];2005年

4 王蓬;宋明玉;张林芳;王新远;;广义自适应相干累积算法改进及其在线谱增强中的应用[A];中国声学学会2007年青年学术会议论文集（上）[C];2007年

5 孙迪峰;方厚林;梁旭斌;赵天青;张亮永;;宽带MUSIC算法中同步干扰研究[A];2019年全国声学大会论文集[C];2019年

6 郝红星;吴玲达;宋汉辰;;一种残损图像修补算法改进与实现[A];第18届全国多媒体学术会议（NCMT2009）、第5届全国人机交互学术会议（CHCI2009）、第5届全国普适计算学术会议（PCC2009）论文集[C];2009年

7 解迎刚;王志良;郑珊山;;基于LANDMARC及其算法改进的RFID室内定位研究[A];第二十九届中国控制会议论文集[C];2010年

8 王笃侠;冷晟;周燕飞;;单件小批生产模式下的MRP算法改进[A];全国先进制造技术高层论坛暨第七届制造业自动化与信息化技术研讨会论文集[C];2008年

9 邹锦峰;;水面仿真研究及算法改进[A];全国首届数字（虚拟）科技馆技术与应用学术研讨会论文集[C];2007年

10 林关成;李亚安;;一种支持向量机训练集选取算法改进[A];2009’中国西部地区声学学术交流会论文集[C];2009年

相关重要报纸文章 前2条

1 记者 宛霞;风云卫星云导风算法改进[N];中国气象报;2018年

2 记者 陈姝;深企为大桥定制人脸识别方案[N];深圳商报;2018年

相关博士学位论文 前10条

1 周凌云;几种典型群智能算法及其更新机制研究[D];武汉大学;2018年

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

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

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

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

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

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

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

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

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

相关硕士学位论文 前10条

1 毛振平;云平台下医疗大数据的FP-Growth算法的优化研究[D];华北水利水电大学;2019年

2 陈晨;面向林业小班的坡度、坡向及坡位提取算法研究[D];浙江农林大学;2019年

3 杨闰;改进TLBO算法及其在天线优化设计中的应用[D];杭州电子科技大学;2019年

4 李文静;改进花授粉算法及其在社交网络中的应用研究[D];江西理工大学;2019年

5 陈朝威;基于密度的聚类算法研究[D];北京交通大学;2019年

6 李桃;智能算法及其在图像处理中的应用[D];西华师范大学;2019年

7 赵冠宇;基于进化计算的车联网路侧单元部署优化方法研究[D];吉林大学;2019年

8 陈婧文;基于链接改进的BIRCH算法的研究与应用[D];吉林大学;2019年

9 吕桂新;基于改进多标记分布学习算法的评分预测[D];吉林大学;2019年

10 彭国雯;基于深度学习的场景文字检测算法的融合技术研究[D];河南大学;2019年

本文编号：2726231