基于粒子群蚁群混合算法的物流车辆路径问题研究

发布时间：2017-06-08 11:19

  本文关键词：基于粒子群蚁群混合算法的物流车辆路径问题研究，由笔耕文化传播整理发布。

【摘要】：在经济全球化和信息化的大前提下,物流作为“第三利润源泉”成为拉动我国GDP增长和第三产业发展的重要因素。配送是从物流系统中衍生出来的重要环节。优化配送路线能够提高配送效率,降低配送成本,同时能够有效减少因物流配送引发的交通拥堵,空气、噪声污染等问题。因此研究如何有效的利用现有资源建立合理的配送方案,提高企业的经济效益,具有重要的现实意义。车辆路径优化问题(Vehicle Routing Problem, VRP)是物流配送优化中的核心问题。近些年来VRP问题已经成为运筹学、应用数学、图论以及计算机科学等学科领域关注的重点问题。由于该问题是一个复杂的组合优化问题,所以求解此问题的许多智能型启发式优化算法应运而生。粒子群算法和蚁群优化算法就是人类受自然界真实鸟类和蚂蚁的觅食行为启发而提出的智能优化算法。本文通过研究粒子群算法和蚁群优化算法的优点,提出了一种有效结合两种算法优势的融合算法(PSO-MMA)。通过将P SO-MMA算法应用于旅行商问题说明其在搜索解的精度上是一种比较优秀的算法,进一步将该算法应用于VRP问题的求解并验证了其有效性。本文的研究内容和完成的工作主要有以下几个方面：1.针对粒子群算法容易陷入局部最优的不足之处,提出了自适应变异和划分多粒子群的策略对该算法进行优化。2.由于蚁群算法在搜索初期信息素是均匀分布,因此具有搜索盲目性的缺点。本文使用优化后的粒子群算法求得问题的次优解来初始分布最大最小蚁群算法的信息素矩阵。之后利用蚁群算法,以国际库TSPLIB中旅行商问题(旅行商问题是一个经典组合优化问题,由于它的NP完全性,在国际上已经成为衡量算法优劣的标准)的标准算例为实验数据搜索问题的最优解。计算结果显示,PSO-MMA在搜索解的精确性上明显优于基本粒子群算法(PSO),最大最小蚁群算法(MMAS)和改进后的粒子群算法(IPSO),并且可以搜索到eil51和berlin52两个实例的最优解,说明本文提出算法的优越性。3.对车辆路径问题进行建模,并采用VRP数据库及其它文献中的实例对融合后的算法进行实验,仿真实验结果验证了粒子群蚁群融合算法求解带容量约束的车辆路径问题的有效性。
【关键词】：自适应变异 粒子群算法 蚁群算法 旅行商问题 车辆路径问题
【学位授予单位】：内蒙古农业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U116.2;TP18
【目录】：

• 摘要3-4
• abstract4-9
• 1 绪论9-15
• 1.1 研究背景和意义9-10
• 1.2 国内外研究现状10-12
• 1.2.1 粒子群算法的国内外研究现状10
• 1.2.2 蚁群算法的国内外研究现状10-11
• 1.2.3 车辆路径问题的国内外研究现状11-12
• 1.3 论文的研究内容12-13
• 1.4 论文的组织结构13-15
• 2 粒子群及蚁群算法的基础知识15-27
• 2.1 粒子群算法介绍15-21
• 2.1.1 粒子群算法的基本原理15-16
• 2.1.2 粒子群算法的流程16-17
• 2.1.3 粒子群算法的特点17-18
• 2.1.4 几种粒子群算法的改进方法18-20
• 2.1.5 粒子群算法的研究及应用20-21
• 2.2 蚁群算法介绍21-27
• 2.2.1 蚁群算法的基本原理21-23
• 2.2.2 蚁群算法模型的数学描述23-24
• 2.2.3 蚁群算法的实现步骤24
• 2.2.4 基本蚁群算法的特点24-27
• 3 粒子群蚁群混合算法求解旅行商问题27-36
• 3.1 粒子群算法的改进27-28
• 3.1.1 多粒子群竞争机制27
• 3.1.2 自适应变异策略27-28
• 3.1.3 算法步骤28
• 3.2 最大最小蚂蚁算法28-30
• 3.2.1 Max-Min Ant System28-29
• 3.2.2 算法步骤29-30
• 3.3 粒子群蚁群混合算法30-32
• 3.3.1 混合算法的思想30-31
• 3.3.2 算法流程31-32
• 3.4 旅行商问题32-33
• 3.4.1 旅行商问题概述32
• 3.4.2 旅行商问题的数学模型32-33
• 3.5 仿真实验33-36
• 4 粒子群蚁群混合算法在车辆路径问题中的应用36-50
• 4.1 车辆路径问题的研究36-38
• 4.1.1 车辆路径问题概述36
• 4.1.2 车辆路径问题的约束条件36-37
• 4.1.3 车辆路径问题的分类37-38
• 4.2 车辆路径问题的求解方法38-43
• 4.2.1 一般算法38-39
• 4.2.2 启发式算法39-43
• 4.3 粒子群蚁群混合算法求解车辆路径问题43-50
• 4.3.1 车辆路径问题的数学模型43-44
• 4.3.2 测试实例44-49
• 4.3.3 实验小结49-50
• 5 总结与展望50-52
• 5.1 总结50
• 5.2 展望50-52
• 致谢52-53
• 参考文献53-57
• 作者简介57

【相似文献】

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

1 方红远,王浩,程吉林;初始轨迹对逐步优化算法收敛性的影响[J];水利学报;2002年11期

2 徐红梅;陈义保;刘加光;王燕涛;;蚁群算法中参数设置的研究[J];山东理工大学学报(自然科学版);2008年01期

3 张倩;陈维荣;;电力系统优化算法综述[J];科协论坛(下半月);2008年03期

4 刘海霞;李新;;几何区间裁剪算法收敛性分析和比较[J];计算机辅助设计与图形学学报;2010年12期

5 孟庆春，，贾培发;关于Genetic算法的研究及应用现状[J];清华大学学报(自然科学版);1995年05期

6 朱勇;周国标;;一类改进的蚁群算法及其收敛性分析[J];兰州理工大学学报;2006年02期

7 吴墀衍;郑政谋;;奇异噪声环境下传统与稳健LMS算法的性能研究[J];深圳大学学报;1992年Z2期

8 李小平,王凤儒;优解保留遗传算法收敛性的研究[J];电机与控制学报;2000年01期

9 郑松;侯迪波;唐旭华;叶波;周泽魁;;一种改进蚁群算法及其在配方优化中的应用[J];江南大学学报(自然科学版);2008年04期

10 徐耀群;王长举;;一种万有引力优化算法及其收敛性分析[J];哈尔滨商业大学学报(自然科学版);2013年01期

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

1 任伟建;陈建玲;韩冬;王凤妤;;蚁群算法综述[A];2007中国控制与决策学术年会论文集[C];2007年

2 张丹;华红艳;邵丽红;;扰动蚁群算法中参数的优化选择[A];中国自动化学会中南六省（区）2010年第28届年会·论文集[C];2010年

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

1 王允良;飞行器总体参数优化的进化算法及其应用研究[D];西北工业大学;2006年

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

1 孟晓琳;蚁群算法的研究及其应用[D];西南交通大学;2015年

2 丁雪海;基于群智能的多目标关联规则挖掘算法应用研究[D];上海大学;2014年

3 陈贞贞;基于FPGA的压缩感知恢复算法的研究与实现[D];中国科学院研究生院(空间科学与应用研究中心);2015年

4 葛曼;基于稀疏表示的鲁棒相位恢复算法研究[D];燕山大学;2016年

5 胡瀛月;人工蜂群算法的改进及相关应用研究[D];中原工学院;2016年

6 高明芳;基于粒子群蚁群混合算法的物流车辆路径问题研究[D];内蒙古农业大学;2016年

7 周文明;基于智能算法的移动机器人路径规划研究[D];南京理工大学;2016年

8 陈振;混合型蝙蝠搜索优化算法及其应用研究[D];广西大学;2014年

9 宋锦娟;一种改进的蚁群算法及其在最短路径问题中的应用[D];中北大学;2013年

10 郭姗姗;基于改进粒子滤波的红外弱小目标检测前跟踪算法[D];哈尔滨工程大学;2012年

  本文关键词：基于粒子群蚁群混合算法的物流车辆路径问题研究，由笔耕文化传播整理发布。

本文编号：432393