蚁群算法在车辆路径优化中的应用毕业论文.doc

蚁群算法在车辆路径优化中的应用毕业论文 目录 摘 要 2 ABSTRACT 3 第1章 绪论 6 1.1 研究目的和意义 6 1.2 国内外研究现状 7 1.2.1 国外研究现状 7 1.2.2 国内研究现状 8 1.3 本文研究内容 9 （1） 基本蚁群算法 9 （2） 蚁群算法的优化 9 （3） 蚁群算法在TSP问题中的应用 9 1.4 开发环境与工具 9 1.5 论文的组织结构 10 第2章 蚁群算法 10 2.1 蚁群算法简介 10 2.2 蚁群算法的原理 11 2.2.1 蚂蚁觅食规则 12 2.2.2 蚂蚁移动规则 12 2.2.3 蚂蚁避障规则 12 2.2.4 蚂蚁撒信息素规则 12 2.3 蚁群算法的特点及优缺点 13 2.3.1 蚁群算法的特点 13 2.3.2 蚁群算法的优点 14 2.3.3 蚁群算法的缺点 14 2.5 蚁群算法的核心函数 15 （1）初始化 15 （2）选择下一个城市，返回城市编号 15 （3）更新环境信息素 17 （4）检查终止条件 18 （5）输出最优值 18 2.6 蚁群算法的参数分析 19 2.6.1 蚂蚁数量N_ANT_COUNT 19 2.6.2 启发因子 19 2.6.3 期望启发因子 20 2.6.4 信息素挥发度 20 2.6.5 总信息量（DBQ） 21 第3章 改进的蚁群算法 21 3.1 轮盘赌选择 22 3.1.1 轮盘赌选择基本思想 22 3.1.2 轮盘赌选择工作过程 22 3.2 MAX_MIN ACO 24 3.2.1 MAX_MIN算法的框架结构 24 3.2.2 MAX_MIN 算法流程图 26 第4章 蚁群算法在车辆路径问题中的应用 28 4.1 车辆路径问题简介 28 4.1.1 车辆路径问题定义 28 4.1.2 车辆路径问题分类 29 4.2 车辆路径问题的求解算法 29 4.2.1 精确算法 29 4.2.2 启发式算法 30 4.3 蚁群算法解决车辆路径问题 31 4.4 数值实验结果及分析 33 4.4.1 轮盘赌选择优化前后数据对比 33 4.4.2 MAX_MIN算法改进前后数据对比 34 第5章 总结与展望 36 参考文献 36 第1章 绪论 TSP问题是一种特殊的车辆路径问题， 于是，许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法（AC）是由意大利学者Macro Dorigo等人在20世纪90年代提出来的[1]，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。 蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。 另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。 1.1 研究目的和意义 物流是供应链中最重要的组成部分，是商品从生产者经过各流通环节最终到达消费者手中的过程。物流业这是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着巨大的商机。物流业被誉为经济发展动脉的“加速器”和商业结果演变的“润滑剂”，现代企业的“第三利润源泉”。 通过提高物流管理水平和效率，降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际竞争力。因此，国家和各地政府纷纷定制了各种有利于物流发展的政策和计划。在国家“十一五规划”中讲“大力发展现代物流”作为今后重点发展的领域，明确提出“十一五”结束即2010年，全社会物流成本要比2004年的计策上下降2—3个百分点。 合理使用优化运输路线，降低企业物流成本，是物流管理的很重要内容。针对物流管理中对运输车辆路径优化调配的要求，1959年由Dantzig和Ramser首先提出了车辆路径问题的数学模型。车辆路径问题已经是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究一个热点问题，并且在通讯、身长、国防、生物计算机应用等领域得到了广泛的应用。 1.2 国内外研究现状 车辆路径问题的研究有着现实的经济意义和学