蚁群算法在车辆路径优化中的应用毕业论文目录摘要 (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问题适用，而且有的算法获得精确解的性质也正是人们所期望的。

于是，许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。

而蚁群算法（AC）是由意大利学者Macro Dorigo等人在20世纪90年代提出来的[1]，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。

蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。

为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。

如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。

另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。

而由于蚁群算法中蚂蚁的个体行为具有在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。

如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。

1.1 研究目的和意义物流是供应链中最重要的组成部分，是商品从生产者经过各流通环节最终到达消费者手中的过程。

物流业这是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着巨大的商机。

物流业被誉为经济发展动脉的“加速器”和商业结果演变的“润滑剂”，现代企业的“第三利润源泉”。

通过提高物流管理水平和效率，降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际竞争力。

因此，国家和各地政府纷纷定制了各种有利于物流发展的政策和计划。

在国家“十一五规划”中讲“大力发展现代物流”作为今后重点发展的领域，明确提出“十一五”结束即2010年，全社会物流成本要比2004年的计策上下降2—3个百分点。

合理使用优化运输路线，降低企业物流成本，是物流管理的很重要容。

针对物流管理中对运输车辆路径优化调配的要求，1959年由Dantzig和Ramser首先提出了车辆路径问题的数学模型。

车辆路径问题已经是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究一个热点问题，并且在通讯、身长、国防、生物计算机应用等领域得到了广泛的应用。

1.2 国外研究现状车辆路径问题的研究有着现实的经济意义和学术意义。

自从VRP被Dantzig和Ramser于1959年提出之后，很快就引起了运筹学、应用数学、物流科学、计算机科学等各个学科专家学者与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿问题和研究热点。

许多学者对该问题进行了大量的理论研究及实验分析，目前己经产生出多种成熟的算法，取得了令人瞩目的成果，为后人的继续研究提供了极高的参考价值。

1.2.1 国外研究现状1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型。

1971年，Eilon提出将动态规划法用于固定车辆数的VRP，通过递归方法求解。

1974年，Wren Gillett等人提出扫描算法，将该算法应用于车辆调度问题，并和当时其它算法进行了比较，证明该算法所求得的解较优于其它方法。

1981年，Christofides等人提出了k度中心树和相关算法，对固定车辆数m 的m-TSP进行了进行k度中心树松弛。

后来，M.L.Fishe对这种方法做了进一步改进，可求解有134个客户的VRP。

1991年，Gendreau等人将禁忌搜索方法应用于VRP，它是比较好的启发式算法，可以成功地应用于许多经典的VRP。

1996年，wrence将遗传算法用于VRP的研究，有效的求解出带时间窗限制的VRP。

1.2.2 国研究现状在我国，有关车辆路径问题的研究是在20世纪90年代以后才逐渐兴起的，比国外相对落后。

随着顾客需求的变化，运输车辆的调度显得日益重要。

近年来，我国理论界逐渐开始关注车辆路径问题的研究，并已取得初步成果。

蚁群算法、启发式算法以及一些混合算法被学者们广泛的利用，代表了较近的研究思想。

启发式算法作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现已成为解决VRP问题的重要方法。

与传统的启发式算法相比，近年来所采用的一些新的启发式算法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的VRP 问题上可以获得较快的收敛速度和较高质量的全局解。

大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据。

钢铁学院大卫和东北大学姜大力等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。

崔雪丽、马良和炳全等人基于近年来出现的新型智能优化思想：人工蚂蚁系统给出了一种可快速求解VRP的蚂蚁搜索算法。

通过定义基本的人工蚂蚁状态转移概，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有使用意义和可操作性。

经一系列数据测试和验证，与若干已有的经典算法相比较，获得了较好的结果。

善林人等提出一种基于蚁群优化的混合算法来解决VRP。

首先提出一种ACO 算子，然后加入局部搜索机制并使用基于问题的特定启发信息——节约量来改进算法。

小峰等针对了蚁群算法存在的过早收敛问题引入节省量以及车辆载重利用率两种启发式信息对蚁群算法加以改进，并加入2.opt方法对问题求解进行局部优化，计算机仿真结果表明，这种混合蚁群算法对求解车辆路径问题有较好的改进效果。

1.3 本文研究容本文的研究容可以概括为三部分：蚁群算法的基础性理论、蚁群算法的优化以及蚁群算法在TSP问题中的应用：（1）基本蚁群算法了解基本蚁群算法的概念、原理以及代码如何实现。

（2）蚁群算法的优化根据蚁群算法的基本原理做出优化，避免蚁群算法的缺点，在迭代次数尽量少，迭代结果尽量趋近最优解的情况下做出优化。

本文主要讲解轮盘算法和max_min算法在蚁群算法中的优化。

（3）蚁群算法在TSP问题中的应用利用蚁群算法的特点以及蚁群算法的优化应用到TSP问题中。

1.4 开发环境与工具计算机：HP ProBook 4416S系统：Microft Windows XPProfessinal版本2002Service Pack3存：2G开发语言：C++运行环境：Microsoft Visual C++ 6.01.5 论文的组织结构第一章绪论主要是讲解本课题研究容、目的和意义，国外对蚁群算法的研究现状以及本系统开发环境的介绍；第二章蚁群算法主要是介绍什么是蚁群算法，蚁群算法的原理和思想以及蚁群算法的优缺点；第三章改进的蚁群算法主要是讲解在基本蚁群算法的基础上对蚁群算法做出优化（本文采用了轮盘选择和MAX-MIN两种优化方式）第四章蚁群算法在车辆路径问题中的应用第五章总结与展望第2章蚁群算法2.1 蚁群算法简介蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。

它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。

针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。

蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。

在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。

图（1）显示了这样一个觅食的过程。

图（1）蚂蚁觅食在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。