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

《蚁群算法在车辆路径优化中的应用毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、蚁群算法在车辆路径优化中的应用毕业论文目录摘要2ABSTRACT3第1章绪论61.1研究目的和意义61.2国内外研究现状71.2.1国外研究现状71.2.2国内研究现状81.3本文研究内容9（1）基本蚁群算法9（2）蚁群算法的优化9（3）蚁群算法在TSP问题中的应用91.4开发环境与工具91.5论文的组织结构10第2章蚁群算法102.1蚁群算法简介102.2蚁群算法的原理112.2.1蚂蚁觅食规则122.2.2蚂蚁移动规则122.2.3蚂蚁避障规则122.2.4蚂蚁撒信息素规则122.3蚁群算法的特点及优缺点132.3.1蚁群

2、算法的特点132.3.2蚁群算法的优点142.3.3蚁群算法的缺点14342.5蚁群算法的核心函数15（1）初始化15（2）选择下一个城市，返回城市编号15（3）更新环境信息素17（4）检查终止条件18（5）输出最优值182.6蚁群算法的参数分析192.6.1蚂蚁数量N_ANT_COUNT192.6.2启发因子192.6.3期望启发因子202.6.4信息素挥发度202.6.5总信息量（DBQ）21第3章改进的蚁群算法213.1轮盘赌选择223.1.1轮盘赌选择基本思想223.1.2轮盘赌选择工作过程223.2MAX_MINAC

3、O243.2.1MAX_MIN算法的框架结构243.2.2MAX_MIN算法流程图26第4章蚁群算法在车辆路径问题中的应用284.1车辆路径问题简介284.1.1车辆路径问题定义284.1.2车辆路径问题分类294.2车辆路径问题的求解算法294.2.1精确算法294.2.2启发式算法304.3蚁群算法解决车辆路径问题314.4数值实验结果及分析334.4.1轮盘赌选择优化前后数据对比334.4.2MAX_MIN算法改进前后数据对比3434第5章总结与展望36参考文献36第1章绪论TSP问题是一种特殊的车辆路径问题，是作为所有

4、组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。传统解法对小搜索空间的TSP问题适用，而且有的算法获得精确解的性质也正是人们所期望的。于是，许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法（AC）是由意大利学者MacroDorigo等人在20世纪90年代提出来的[1]，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并

5、且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是

6、目前蚁群算法研究的又一个热点。1.1研究目的和意义物流是供应链中最重要的组成部分，是商品从生产者经过各流通环节最终到达消费者手中的过程。物流业这是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着巨大的商机。物流业被誉为经济发展动脉的“加速器”和商业结果演变的“润滑剂”，现代企业的“第三利润源泉”。通过提高物流管理水平和效率，降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际竞争力。因此，国家和各地政府纷纷定制了各种有利于物流发展的政策和计划。在国家“十一五规划”中讲“34

7、大力发展现代物流”作为今后重点发展的领域，明确提出“十一五”结束即2010年，全社会物流成本要比2004年的计策上下降2—3个百分点。合理使用优化运输路线，降低企业物流成本，是物流管理的很重要内容。针对物流管理中对运输车辆路径优化调配的要求，1959年由Dantzig和Ramser首先提出了车辆路径问题的数学模型。车辆路径问题已经是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究一个热点问题，并且在通讯、身长、国防、生物计算机应用等领域得到了广泛的应用。1.2国内外研究现状车辆路径问题的研究有着现实的经济意

8、义和学术意义。自从VRP被Dantzig和Ramser于1959年提出之后，很快就引起了运筹学、应用数学、物流科学、计算机科学等各个学科专家学者与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿问题和研究热点。许多学者对该问题进行了大量的理论研究及实验分析，目