毕业设计（论文）-基于改进蚁群算法的物流配送路径优化.docx

中国矿业大学2014届本科生毕业论文 第33页目 录第一章 第一章 绪论21.1研究背景21.2 本文研究目的和意义31.2.1本文研究目的31.2.2本文研究的意义41.3本论文的主要工作5第二章 路径优化研究现状与分析62.1研究现状62.2研究方法7第三章 各种智能优化算法介绍73.1 智能优化算法73.1.1禁忌搜索算法73.1.2 模拟退火算法83.1.3遗传算法93.1.4 粒子群优化算法93.1.5 神经网络算法10第四章 基于蚁群算法系统开发基本思想104.1物流配送的问题描述104.2数学模型的建立114.3约束条件114.4优化目标124.5优化配送路线的蚁群算法124.5.1基本思想124.5.2 算法实现134.6TSP问题概述144.7基于蚁群算法求解旅行商问题（TSP）的基本流程144.8 VRP相关问题论述17第五章 蚁群算法的改进185.1问题描述185.2最大最小蚁群算法195.3蚁群算法的其他改进策略20第六章 软件实现246.1 功能要求246.2总体设计246.3 软件架构256.4 测试文档25第七章 总结语26参考文献28摘要：本文所要探讨的物流配送路径优化问题，是基于改进蚁群算法的物流最优路径选择系统，算法实际上是正反馈原理和启发式算法相结合的一种算法。该软件采用C+语言编写，用Qt做界面，可在Win7下运行。在选择路径时，蚂蚁利用了路径上的信息素，不断叠加，最终产生最优路径。本系统提供给合乎用户需求的优化路径策略，如路径最短、时间最短等进行配送路线规划方案。结合网上已有资源及多次实验计算，从而证明合理的使用蚁群算法进行路径线路，能够高效、快速的得到问题的最优解或接近最优解。关键词：基本蚁群算法；最大最小蚁群算法；物流配送；蚁群系统；路径优化； 第一章 绪论1.1研究背景在美国，物流产业链被人们形象地比作“尚未开发的价值400亿美元的金矿。数据显示，仅在每年物流成本上的支出，美国工业界就需要支付达到4000亿美元。如此庞大的数字，我们如果仅仅将它降低10，一年就可以节约近400亿美元。在我国，2004年后，随着网络时代的极速发展，带动了网购即电子商务的发展，相应地我国对物流的需求也愈发增大。商务部公布的数据显示，去年我国物流总额将近384亿元，仅仅过了一年，增幅较往年就到到了29个百分点，物流业的经济产出可见一斑。然而，就目前物流业发展可见，其发展己经成为经济发展过程中必须有效管理的问题。数据显示我国GDP中物流所占比持续偏高，甚至高于发达国家。如此可见，物流业经济的迅猛增长已经是势不可挡。然而通过观察以往的研究可以发现，我国现阶段物流配送的发展依旧十分落后，只配不送的尴尬现状造成物流配送中出现低效率、高成本、服务差等诸多问题，这已经严重影响到了电子商务在未来市场的长足发展，要知道，电子商务在网络时代中占据着极其重要的经济地位。高成本、低效率的物流配送使得在网上瞬间完成的电子商务所节约的时间、费用已变得毫无意义。试想一下，用户花费较少的支出买了商品，却需要在商品配送上另花费更多的时间和金钱，这本身就是一个不合理的现象。因此该如何实现高效、迅捷的配送是企业经营急需解决的问题。鉴于此，研究运用科学方法，合理建立一个高效率、低成本的物流配送系统来支持电子商务在物流业的发展己成为当务之急。1.2 本文研究目的和意义1.2.1本文研究目的物流配送网络是指物流过程中相互联系的设施及组织的集合。多种不同的物流节点和联结各点的线路构成了整个物流网络。其中节点包括仓库以及配送中心等，按规定进行物流配送运营的路线和航线则构成了物流线路。物流配送路径优化需要解决的根本问题就是从生产区域到消费区域的空间转移过程中对实现物品移动(运输)途径的优化。由于配送路径问题求解演算是属于NPHard（非确定性多项式）的问题，问题往往复杂性较高。此类问题的解决方法有不少，传统方法包括启发式算法和精确算法。实际解决中采用精确算法确实可得最优解，弊端则是求解时间会随着问题规模的增大而指数增长。一旦需要解决的节点过多往往需要花费很多时间，因此在大数据的问题解决中运用很少。相比之下，启发式算法就要合适的多，它通常可以根据问题的特性而将其化为多个小问题，以较为直观的方式来求解各个支问题。这是该方法的优势所在。可是以往的研究成果表明，尽管运用启发式算法可以针对VRP（车辆路线问题）问题获得比较满意的解，但是同样的，当问题规模变大时，最优解的产生往往会超出计划计算时间，收敛速度极其缓慢，甚至算法会直接进入停滞状态。因此，本文研究的目的是：1、通过对各种智能算法的介绍比较，找出它们的区别和优缺点，以及实际应用中的可行度，讨论出较为合适的算法。在此基础上引出蚁群算法，将会重点阐述该算法的可行性和实用性，并作出改进，使得算法能有在全局搜索和收敛速度上更具优势。2、在以往研究的基础上，建立适合实际物流配送网络路径优化的模型，并选择使用有效的算法，为物流配送网络路径优化问题的研究和实践提供理论依据和实际方法。3、根据论文选题要求，结合论文中选择的优化算法，开发出物流配送路径优化系统，要求该系统要严格遵守选题要求，可适当做出改进和拓展，作为论文的实践研究。本论文最终要求开发出满足实际应用的软件，能够在windows系统上运行，随机数据生成后（位置坐标），可以在符合约束条件的情况下，付出较小代价给出合理的路径优化解时间最短路径、距离最短路径。该解可允许有误差，但误差必须在可以接受的范围内。1.2.2本文研究的意义根据Ronald HBallo的观点，运输决策包括四种：运输方式的选择、对运输路线的规划、车辆调度以及集中运输等。运输成本降低的重点在于对运输路径进行合理规划，即优化运输路径。这就需要考虑到时间、财务、环境三方面的因素，即时间上的准时性以及快速响应；财务上则是各种运输费用的节省；环境上要考虑行驶时间、交通问题以及各种环境污染问题。这些问题往往可以通过改进运输方式、优化线路规划等加以改善。其中，运输问题不属于本文探讨的范围。而运输的线路规划主要是利用各种技术以最低的运营成本、最快捷的响应速度、最短的配送运输时间，把货物运至用户手中，达到节约费用和节省客户时间双赢的目的。实际中的物流配送尤其是从事城市配送的汽车货运工作往往需要考虑的问题更复杂，比如货运节点的多寡、物品种类是否繁杂、当地交通网络是否畅通等等，甚至运输服务地区内运输网点分布不均匀都会直接影响配送工作的进行。因此，实际应用中需要考虑的是如何设计合理、高效的配送方案以及减少车辆数量和配送里程数。高效率的物流中心配送作业具体而言就是：从配送中心使用多辆车向多个目的地送货，假设每个需求点的位置和供量确定，车辆载重一定，需要解决的就是合理安排车辆路线，以达到预定的目标(即最少费用，最短路径，最少时间，最少车辆使用等)。为了便于问题的研究，规定遵守的条件有：要求车辆载重大于该路径需求点的需求量；该路径长度不得超过一次配送中最大行驶距离；单位需求点有且只由一辆车送货。针对以往路径优化方案的研究，本文将建立该问题的数学模型，以蚁群算法为主要算法，建立出较为合适的路径优化系统，最终达到减少配送支出，提高对客户服务质量等目的，从而有效提高利润率，相应的缓解交通压力。本文的研究对城市的配送研究可起一定的借鉴作用，追求高利润、低成本，降低社会经济物流总成本，并有效的提高车辆运输效率，强化服务质量，提高更快更好的需求相应，无论是城市物流本身，亦或是针对客户群都是具有重要的参考价值。1.3本论文的主要工作 物流配送路径优化问题简称VRP，本论文将重点就城市车辆路径优化问题作为研究对象，针对目前路径优化研究的复杂性以及各类算法的使用，着重以蚁群算法为主要算法，在蚁群算法基础上结合最大最小蚁群算法对其进行改进，从而是整个系统的寻优速度更快、结果更准确。 本论文的研究工作主要包括： 第一章绪论部分主要以论文研究背景和目的方面为主，阐述了由国内国际实际物流发展而产生的问题，引出本论文研究的必要性和重要性。 第二章会就路径优化研究的国内外现状为例展开分析，指出现阶段路径优化问题的主要研究方法，由此引出下章针对这些研究方法的详细讨论。 第三章是几种智能优化算法的简单介绍，主要包括禁忌搜索算法、遗传算法、模拟退火算法、粒子群优化算法和人工神经网络算法。针对五中算法的基本思路、优缺点、以及实际应用中产生的问题与思考。第四章基于蚁群算法系统开发基本思想，主要对研究的数学模型、约束条件以及基本蚁群算法的的原理、实现方式展开论述。第五章主要是针对基本蚁群算法，结合最大最小蚁群算法进行改进，提高算法的收敛速度，以及全局搜索能力。后面也会给出蚁群算法的其他改进方式，以减少最优解的误差。第六章属于对路径优化系统的描述，主要有总体设计、功能要求以及界面的相关方面。此章的所述以及最后的软件部分都将作为论文的实物支持。最后一章是对本论文的总结和展望，重点对本论文中的优点和功能做出总结，同时就论文的不足结合现实技术做出进一步的展望。第二章 路径优化研究现状与分析2.1研究现状物流配送路径规划问题的研究现状：车辆优化调度问题及物流配送路径选择是整个物流配送体系优化中很重要的环节，也是电子商务活动不可或缺的内容。由于这一问题的理论涉及多学科，而且应用前景可观，所以很快引起了应用数学、物流学、运筹学、计算机应用图论与网络分析、交通运输工程、管理科学与工程等学科的专家、工程技术人员的极大关注。因此一度成为组合优化领域和运筹学的前沿研究热点，各学科专家针对此类问题进行了大量的学术探讨和试验分析，并取得了很大进展。近二十年来国内外对物流配送路径优化问题的研究给予了极大的关注。随着市场经济的进步和物流技术专业化水平的不断提高，物流配送业得到了快速发展。配送路径的选择是否合理，直接决定了配送速度是否迅捷、服务质量能否有所提高、配送成本能否减少以及整个经济块的利益能否最大化。配送路径的优化问题是物流配送体系的一个重要问题，物流配送路径的优化根本在于以最短的配送运输时间、最低的运输成本、最迅速的响应把货物运至客户手中，最短时间和最快速度两者本身与最低运输成本相制约，严格地来说这一个多目标的优化问题。2.2研究方法路径优化的方法很多，常用的有分区配送算法、旅行商法、扫描法、动态规划法、节约法等。但这些方法往往存在各种问题，例如节约法很难做到组合点整齐、组合边缘点的问题，且扫描法无法做到渐进优化等。如何针对物流配送路径优化问题的特点，建立运算复杂度低、寻优性能优良的启发式算法，也是很多人深入研究的课题。近年来流行的遗传算法、禁忌搜索算法等都在这方面取得了不同的成就。但根本性问题依旧存在，例如在搜索能力上遗传算法局部搜索能力很弱，总体上可行解的质量也不高，禁忌搜索算法如果没有一个比较合适的初始解其可行性也很低。诸如此类。第三章 各种智能优化算法介绍3.1 智能优化算法常见的用于解决路径优化问题的方法有不少，例如遗传算法、禁忌搜索算法、模拟退火算法、粒子群优化算法等，但往往方法各有不足。蚁群算法的优势在于它利用并行计算机制，可以很好的与其他算法结合，鲁棒性特点尤为突出。本章将会对智能优化算法做简单介绍。为下一章会针对蚁群算法概念、算法思想、优化步骤和相关数学模型等的进一步详解做铺垫。3.1.1禁忌搜索算法 1986年，由Glover提出的禁忌搜索算法（tabu search，TS）经过后来学者的不断完善，形成了一种比较完整的优化算法。禁忌搜索算法的基本工作原理是利用记忆存储，并对其系统化使用，从而使搜索过称顺利进行下去。记忆存储包括短期和长期记忆存储。长期记忆存储通过引用其他解进行邻域扩充；短期记忆存储则不同，它是将当前解的邻域限制到一个子集中来，子集含于这个邻域。禁忌搜索的过程实际上就是一个局部搜索过程，将所有的局部最优解用一张禁忌表记录，然后在一周的搜索中，从这些最优解中选择或禁止。出于对防止算法可能返回重复解的考虑，TS可以将近期访问过的最优解进行显式保存或者直接禁止这些解。但这就造成了算法很难向着那些未访问过的解移动。为防止这种情况出现，TS提出了新概念“渴望标准”来覆盖某些移动的禁忌状态，使得算法向比目前最优解更优的解移动。实际应用中，搜索过程的短期记忆是TS运用最广的特征，称为“简单禁忌搜索”。3.1.2 模拟退火算法 模拟退火算法的出现最早是由Metropolis在1953年提出的，严格意义上来说，属于局部算法的延伸，1983年，该算法成功的应用于组合优化问题，尤其在NP-head问题中运用更多。模拟退化算法的基本原理是基于一般优化问题与物理中的物质退火的相似性，即温度上升到一定程度的自由运动粒子，随着温度的下降（下降速度保持足够慢），那么最终整个系统将会达到其自身最低状态，称为基态状态。此时的基态可视为函数的全局最小点。组合问题的优化过程类似于此，它的迭代过程分为三个步骤生成新解、判断该解、是否接受/放弃，并且迭代过程中遵循随机接受准则，这个准则将会接受所有恶化解，使得得到恶化解的概率降低并无限接近零，最大程度上使得退火算法跳出局部极值，最终找出最优解。 遵循上述准则的模拟退火算法已经脱离了局部搜索算法范畴，成为了一种全局寻找最优解算法。此算法的优势在于，中间解可以一定程度上脱离局部极小点，最终在退火温度下找到最优解。3.1.3遗传算法 遗传算法是最初是由美国Michigan大学的J.Holland教授在1975年提出的，其基本思想是将自然界优胜劣汰的自然法则与组合优化及其他机器学习等问题结合。六十年代时这个算法还处于萌芽状态，算法相对简单的多；直到七十年代遗传算法得到了发展探索，当时的算法主要用于解决两类问题：（1）建立出一种寻找特定问题解的系统；(2)理解如何求解这些问题的过程。发展到九十年代，遗传算法的研究运用在各方面得到深入。 遗传算法的原理是基于初始种群的，即在当前种群中使用选择策略选择个体，其中该策略的标准是针对与适应值比例的，随着一代代的杂交和变异，直到最终的期待条件出现为止。对于旅行商问题（TSP），遗传算法中的杂交方式一般是将染色体标记为序列，其中包含所有需求点。这种方式的缺点在于方向的不确定性，最终产生的结果无法保证是有意义的。所以需要保证旅行商问题杂交算子编码的有效性。 遗传算法的主要步骤为：（1）编码；（2）生成初始群体；（3）检测与评估适应值；（4）选择使用/放弃；（5）交换，即信息交换；（6）变异。变异是新个体产生的主要方式。3.1.4 粒子群优化算法 粒子群优化算法（PSO）是由两位美国博士Kennedy（社会心理学博士）和Eleberhart（电子工程学博士）在观察鸟类觅食过程中收到启发而提出的。例子群优化算法同样是起源于生物社会系统的模拟。最开始的设想是基于单个个体组成的群体与环境和个体之间的反馈行为。 与其他算法相似之处在于粒子群优化算法同样是关于群体的迭代关系的算法，而不同之处则在于该算法并没有设定交叉、复制和变异等算子，而是将群体中的个体微化成无质量无体积的粒子。值得注意的是，例子算法是一种共生合作的算法。 粒子群算法之所以会受到各界不同程度的关注，最重要在于针对复杂非线性问题，该算法具有比较强的寻优能力，且简单通用，鲁棒性强。在函数优化领域以及车间调度方面粒子群算法都用应用 然而粒子群算法并不是完美的一种算法，它的缺点也是显而易见，例如该算法的高搜索能力是建立在参数的合理程度之上的，也就是说，没有一个合理的参数选择，该算法的搜索性能很低；其次它的局部搜索能力同样不高，搜索精度很低，这就导致了算法无法最终寻得全局最优解。3.1.5 神经网络算法 神经网络算法（ANN）起源已经很难考证了，其基本原理是模拟生物神经系统的一种人工智能的简化，系统主要由三部分组成：系统功能、组织结构和处理方式。应用优点在于它可以获得全局最优解，相应的算法无法避免局部极小问题，收敛对初值敏感以及收敛速度慢等问题。第四章 基于蚁群算法系统开发基本思想4.1物流配送的问题描述一般配送路径问题可描述如下：已知条件：需求点（客户）数量为L；需求点数量和坐标；预计可出现故障的路段；要求： a：系统可根据使用者选择的路径规划策略，如路径最短、时间最少等方式进行配送路线规划b：模拟车辆由仓库出发，沿着规划的配送路线行进，最后返回仓库c：在配送过程中可模拟前方行进路线堵车事件，系统能够绕开堵车路段动态规划配送路线d：需要满足的几个约束条件：1) 每条线路上的客户点需求量之和不超过汽车载重量；2) 每条配送路径的总长度不超过汽车一次配送的最大行驶距离；3) 每个客户点的需求必须且只能由一辆汽车来完成。4.2数学模型的建立符号的定义L：需求点总数；qi：需求点i的货物需求量，其中i=1，2，L；dij：从需求点i到需求点j的距离。注：当i=j=0时，表示起始地， K：车辆数量Qk：车辆k的最大载重，其中k=1，2，KDk：车辆k的最长行驶距离，其中k=1，2，Knk：车辆k需要配送的需求点总数，nk=0时，表示该车没有进入线路。k=1，2，KRk：车辆k配送的需求点的集合。当nk=0时，Rk=；当nk0时，4.3约束条件根据前文对路径优化的描述，需要注意的约束条件如下：1)线路上的需求点需求量之和不可以超过汽车载重量：，nk02)每条路径的总长度不超过汽车一次配送的最大行驶距离：， nk03) 每个需求点的需每次有且只能由一辆汽车来完成：，k1k24) 配送路径遍历所有需求点：4.4优化目标根据需优化目标，列出所要优化目标的数学形式：4.5优化配送路线的蚁群算法4.5.1基本思想蚁群算法的出现是根据自然界生物中蚂蚁的觅食行为启发而产生的“自然”算法。蚁群算法的最显著的特点在于蚁群中的蚂蚁是以“信息素”（pheromone）为介质的间接异步联系方式。蚂蚁的行为（寻找食物或者寻找回巢的路径），会在其走过的途中释放一些化学物质（即我们所说的“信息”）。同一蚁群会发现这些信息素，信息素作为一种特有信号影响蚁群的行动（具体表现为后者选择走这些具有“信息”的路径的可能性要大于选择其他路径的可能性），而后到者会继续在该“信息素”基础上进行加强，如此往复循环。这样，该路径走过的蚂蚁越来越多，“信息素”也越来越多，后来者选择此路径的可能性也更大（因为残留的信息浓度较大的缘故）。这样，在单位时间内此路径持续被更多的蚂蚁选择访问，信息素积累增多，直到最后，几乎所有的蚂蚁都选择这条最短的路径。4.5.2 算法实现我们用人工蚂蚁代替车辆对需求点点进行“配送”，蚂蚁在i需求点选择的下一个需求点j时，主要考虑两方面因素，一是i，j两需求点之间关系的亲密程度（即可见度），记为hij；另一点则需要考虑由目前的循环所得路径优化方案体现出来的由i到j的可行性（即信息素浓度），记为tij。在算法的初始时刻，将m只蚂蚁随机地放到 n 座城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此时各路径上的信息素量相等，设ij(0) = C（C 为一较小的常数）在t时刻蚂蚁k由需求点i转移到需求点j的概率：（2.1）其中，Jk(i)= 1，2，n- tabuk表示蚂蚁 k 下一步允许选择的城市集合。蚂蚁 k 当前走过的城市都记录在列表tabuk。当每一座城市都加入到tabuk中时，蚂蚁 k 便完成了一次循环，此时蚂蚁 k 所走过的路径便是 TSP（旅行家问题） 的一个可行解。(2. 1)式中的ij 表示一个启发式因子，代表蚂蚁从需求点i 转移到需求点 j 的期望程度。在 AS 算法中，ij 通常取需求点 i 与需求点j 之间距离的倒数。和分别表示信息素和启发式因子的相对重要程度。当所有蚂蚁完成一次循环后，信息素根据式（2. 2）更新。 (2. 2) (2. 3)其中(0 1)是路径上信息素的蒸发系数，1- 表示信息素的持久性系数；ij表示本次迭代边 ij 上信息素的增量。kij表示第 k 只蚂蚁在本次迭代中留在边ij 上的信息素量。如果蚂蚁 k 没有经过边 ij，则kij的值为零。kij表示为： (2. 4)其中，Q 为正常数，Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度。M. Dorigo 提出了 3 种 AS 算法的模型 ，式(2.4)称为 ant-cycle，另外两个模型分别称为 ant-quantity 和 ant-density，其差别主要在 (2. 4) 式，即：在 ant-quantity 模型中为： (2. 5)在 ant-density 模型中为： (2. 6)AS算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。AS 算法的时间复杂度为(NC*n2*m) 算法的空间复杂度为S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次数，n 为城市数，m为蚂蚁的数目。4.6TSP问题概述TSP问题是旅行商问题的简称，简而言之，说的是从前有一个商人，要从自己家开始出发，途径一些要求必须经过的城市，最后回到家乡，而且经过的城市不能有所重复。旅行商要做的就是找到一条最短路径达到目的地。该问题在图论下又叫做哈密顿圈问题，最早是由一个叫Euler研究出其雏形。4.7基于蚁群算法求解旅行商问题（TSP）的基本流程作为一个经典的路径寻优问题，TSP问题的理解并不难，但事实上至今也没有准确地答案。我们用一个带权完全图G=（N,A）来阐述，N是所有目标城市点的集合，A是所有边（路径模型）的集合。首先对蚂蚁数量、信息素等进行初始化，同时将迭代次数初始化为零。禁忌表是为了记录遍历城市的一个表，算法开始前其值为零，表示未访问任何城市。随着算法的进行，蚂蚁会选择城市出发并留下信息素，此时禁忌表值发生改变，同时信息素也会更新，当超出最大迭代次数时，程序将会终止，否则迭代继续，直至满足条件。 具体流程如下：设带权图G=（N，A），N=（1，2，3，4，5,n）表示城市的结点集合，各点的坐标信息和距离dij已知。设Xij=1(当（i,j）在最优回路上时)；Xij=0（其他条件时）因此可得旅行商问题的数学模型如下：?这里我们规定丨S丨表示s中G的所有顶点数量。上述约束条件中，a、b两个约束条件的作用就是限制每个点仅有一条边进和一条边出；而约束条件c则保证搜索过程中不会出现回路解。满足上述三个条件的所有解的回路就是哈密顿回路。同时出现新概念对称型TSP，即满足条件dij=dji。总结其数学模型下TSP问题的步骤为：Begin 对蚁群初始化Loop 构造蚂蚁路径； 对某一个蚂蚁进行局部搜索法； 信息素更新； 未达到迭代次数，继续转loop； 找到最优解并输出；End从TSP问题的数学模型可以看出，需要特别注意两个步骤：构造蚂蚁路径以及信息素更新。蚁群算法之所以优于其他算法，是因为每一次迭代中，信息素的期望值往往会低于其初始值，其计算公式如下：式中，m表示蚂蚁数量，Cnm代表路径长度。选择该初始值的初衷是因为，一旦信息素初始值过小，搜索区域往往受到限制，大多搜索会过于集中在初始有限的路径中，即我们所说的陷入局部搜索中，很难找到最优解。相反地，如果让信息素的初始值过大，就会无法发挥蚁群算法初始的多次迭代优势，这种效果会一直持续到信息素蒸发到很小的程度，此时更新的信息素才会指引搜索偏向性。我们从构建路径个信息素更新两方面剖析该问题：1、构建路径在蚁群算法中，我们设初始有m只蚂蚁参与TSP路径的构建。将所有蚂蚁随机的选中的需求点中。在构建路径过程的每一步中，蚂蚁会在规则概论下选择其下个访问需求点，其选择概论如下：上式中，是一个初始的启发式信息，和在前几章解释过，前者主要是影响信息素的产生，后者为启发式信息的重要参数，allowedk表示蚂蚁们未访问过的需求点，换而言之，就是蚂蚁下一个需要到达的点。我们分别对和取零值，可以发现，当为0时，此时会最大概论选出离i点最近需求点，这满足贪心算法的定义。而当=0时，此时对于概论P来说，能够改变它的只有信息素的放大系数，换句话说，信息素并没有发挥它该发挥的作用，即信息素没有使用任何启发式偏向性。此时的蚁群算法相对与其他智能算法没有任何优势可言，甚至不如其他算法，尤其是大于1时，AS将会越来越缓慢，直至停滞运行。此时的算法依旧会给出一条路径，也就是多数蚂蚁选择的路径，但其实已经没有任何研究的意义了，此路径甚至算不上一个可行解。在前几章我们针对几种智能算法做介绍的时候，提到过记忆储存这个概念，其包括短期储存和长期储存，事实上，在蚁群算法中，同样有记忆储存的概念。我们用Mk来表示蚂蚁们共同维护的这个记忆储存，类似与禁忌表，记忆储存里面会给出已经被访问过的需求点集合，并且这些需求点都是严格按照先后顺序被存储。可以发现，无论是Mk，还是Nik，都与访问路径有关，事实上后者往往需要以前者Mk给出的构造规则来定义概论P。除此之外，在计算构造路径Tk的总长度时，同样要使用到记忆存储。我们用两种方式可以实现可行解的构建：第一种是并行构建，也就是说每一只蚂蚁都可以随时从当前需求点出发向下个需求点；与之相反的一种方式称为顺序构建，我们可以理解为单线程的构建，即只有当一直蚂蚁完成从所在点向下一个点构建完整路径后，第二只蚂蚁才被允许开始它的构建。两种方式没有特别明确的界限，二者从根本上并没有改变蚁群算法的特征。2、信息素的更新信息素的更新会在全部的蚂蚁将路径构建好之后完成。起初，路径上的信息素会按照一个常量减少，也就是信息素蒸发。当减少到某个值时，此时到达的蚂蚁会重新在走过的路径上释放信息素。信息素的蒸发满足下式：式中，表示信息素蒸发率，其取值范围为（0,1。该参数的重要性在于可以抑制信息素的无限积累，而且也可以使算法舍弃已选择过的差解。蚁群算法最重要的特点在于蚂蚁迭代每一条路径时释放信息素，后面的蚂蚁又根据信息素继续选择该路径，继而再次释放信息素，如此往复直到所有的蚂蚁都选择信息素最大的那条，也就是我们需要的最优路径。所有蚂蚁在其选择的路径上释放信息素为： 根据上式不难总结出，在迭代次数允许的范围内，该路径的构建阅合适，信息素的释放也越多。在后一章有关蚁群算法的改进会提到有关选取合适参数以减少可行解误差的论述，此处给出基本ACO的相关合理参数：=1，（2，5），=0.5。4.8 VRP相关问题论述物流配送优化问题的研究中，最常用也是最关键的问题是车辆路径问题，简称VRP。该问题的研究往往不是单一的只针对某一个领域的研究，而是结合许多相关学科前沿和热点，比如计算机科学，物流科学，数学，运筹学等。该问题的具体论述如下：在满足某些给定条件（约束条件和需求条件）的前提下，从某一确定原点出发，目的地为多个需求点组成的集合，需要解决的是在诸多路径中找出最优的那个解（时间最短路径、距离最短了路径），满足条件：1、 每一个需求点只允许访问一次；2、 要求每一辆车从原点出发，最终也必须回到原点；3、 根据实际情况，某些特殊需求点需要接受限制，即约束条件。实际情况中需要考虑的约束条件如下：1、 限制容量。客户的要求或者说需求量有大有小，有时候受到车辆本身的条件所限，是没有办法一次性全部装载的，也就是说，车辆的要求负重不能大于车辆本身的最大载重。这种限制称为CVRP。2、 路长限制。车辆不可能无限制的一直跑下去，其行驶总路长受到油耗和油量的限制，即车辆的行驶路长需要设定为一个合适的常数。这种针对行驶路程限制或者说时间的限制称为DVRP。3、 时间窗。需求点不可能在车辆为访问的情况下一直等下去，这就需要给车辆一个时间限制。我们称这种限制为VRPTW。4、 带回程取货。有些需求点会有无用货物产生，需要从该点运回原点，此时就可以搭“顺风车”，减少成本支出。这种限制称为VRPB。5、 时间窗带回程取货。也就是结合了时间窗和回程取货限制，需要将无用货物在规定时间内运回原点。这种限制称为VRPBTW。再次强调，本文的研究都是基于CVRP的情况下的讨论。第五章 蚁群算法的改进5.1问题描述我们将具有容量限制的车辆路径优化问题（VRP）称为CVRP，即车辆所负重的需求量不得超过其最大容量。以下我们所要研究的问题都将以此为前提进行。蚁群算法中，我们往往会发现，随着越来越多的蚂蚁选择同一条路径不断的进行下去，这条路上的信息素将会急剧升高，更多的信息素吸引更多的蚂蚁走该路径，愈演愈烈，直到造成堵塞或者停滞。使用第四章所述的基本蚁群算法解决VRP或者CVRP问题会发现容易出现收敛速度慢、易陷入局部最优的问题。这个时候通常有两个方法解决：1、选择较为合适的和值使得最优解的误差控制在可以接受的范围内；2、结合其他算法来改进蚁群算法。通常情况下第一种方法无法直接判定选值是否最合适，本章将着重介绍结合其他算法改进后的蚁群算法，选择算法为最大最小蚁群算法。5.2最大最小蚁群算法本算法是在基本蚁群算法上做了如下几项改进。首先，对最优路径开发做出强化，具体做法为：只有在路径优化中那只最优蚂蚁，或者是遍历需求点过程中构建出最优路径的那只蚂蚁，才可以被允许释放信息素，但问题就出现了：这样会使信息素单一方面的增多最终导致路径堵塞，也许有人会说：这样的路径不正是好的路径吗？因为有大量的蚂蚁走。其实不是，这样的路径只能称作较好的路径而非最优路径。这个时候就有了第二个改进方式：将信息素限定在一个范围区间内Imin，Imax。其次，对信息素的初始值进行设定，并将其定为范围区间的上限值，同时与较小的那个信息素蒸发速率结合，原因是这样可以使算法在开始的搜索中向着更多的可能最优路径出发。最后，当出现以下条件：系统信息素增多导致系统堵塞，或者在迭代过程中不再出现优化路径，此时将会对信息素值初始化。最大最小蚁群算法的具体改进如下：（1）更新信息素当蚂蚁成功的构建完成一条路径时，根据信息素蒸发规则，最大最小蚁群算法将更新信息素。新的信息素如下：其中，。信息素释放的对象由至今最优的蚂蚁进行释放，此时；或者由当前迭代最优的蚂蚁进行释放，此时。其中Lib指的是目前最优路径的长度。（2）限制信息素改进后的最大最小蚁群算法中规定，每一条边的信息素都在区间Imin，Imax中，这样可以有效的防止停滞状态的发生。最重要的是这种限制可以使得需求点i蚂蚁选择去需求的j的概率保持在区间pmin,pmax内。当且仅当蚂蚁只剩下唯一选择时才有pmin=pmax=1。未更新信息素之前，信息素范围区间极值定义式如下： I更新信息素后极大值如下：（3）初始化和重新初始化信息素算法开始前，会对信息素进行初始化，设定原则为信息素极大值之上的一个估算值。由于该方式可以连同一个信息素蒸发参数，导致各边上的信息素差异的增加相对缓慢，因此在算法初期，该算法极具探索性。我们知道，蚁群算法在运行中对某些路径的探索概论很小，为了解决这个问题，就需要在达到某些条件时对信息素进行重新初始化。一般来说，重新初始化的条件有两个：算法达到或接近停滞，或者在达到迭代次数上限前依然没有找到最优路径。 5.3蚁群算法的其他改进策略在引入最大最小法对蚁群算法进行改进后，无论是算法的收敛速度，还是其全局搜索能力上都有很大的提高。这是从算法本身出发而做出的改进。有时候我们还可以从算法参数、需求点选择策略出发对其进行改进，这样可以提高算法的自适应性。（1）信息素传递参数r的选取在基本蚁群算法中，r是一个常量，通过对其定义式的研究发现，随着r不但变大，当达到某个临界值后，算法对那些未被搜索过路径的选择概率会相对减小，从全局搜索的角度来说，这是有缺陷的。相反，如果选择的r值过小，收敛速度会减少。因此如何在算法初期对r进行适当改进调整，可以帮我忙更快的找到最优路径，达到目的。在算法初期算法找到都属于次优解，如果r值要比较大，需要对信息浓度进行增大调整，加快收敛速度；如果算法进入停滞阶段，我们要减小r值，进而使信息素对蚁群的影响达到最小，加大对全局的搜索以避免局部最优。上式中，r表示连续没有进化的循环的次数，rmax为常数，l(0,1)也属于一个常量，控制r衰减速度，rmin是r的最小值，防止r过小影响收敛速度。当r达到预先设置的一个数值rmax时，我们就减小r，r重新计数，如此反复，直至r达到预设最小值rmin为止。（2）确定性搜索和探索性搜索的选则当算法在初期找到较优解后，需要加快收敛速度，尽快进化，从而得到更优解。蚁群算法属于一种启发式算法，要想使得算法进化就必须不断进行遍历搜索；但是不断的搜索又会限制算法的收敛速度，进而反过来导致加长了最优解的寻找时间，甚至忽略了最优解。举个例子，当蚁群算法得到较优解时，且此解有进化为最优解的可能，此时算法会在更大的空间搜索，范围大了，对该解对应的路径选择概论就会减少，信息素浓度会逐渐减少直至此路径被遗忘。为此我们引入一个常量：q00,1)，每当蚂蚁在选择路径之前，都会先产生一个q0,1)，k号蚂蚁选择规则如下： 由上式可以看出，当qq0时，将会使用基本蚁群算法进行搜索；当qq0时，是从已经得到的结果中，找出最大概论的路径作为选择，属于确定性搜索。确定性搜索解决了探索性搜索受限于收敛速度的问题，通过调整合适的q0，使探索性搜索和确定性搜索合理搭配，从而加快蚁群算法的收敛速度。通过对q0的取值进行调整，我们发现：当qq0时，算法会选择采用确定性搜索，此时蚂蚁以概率q0选择最短路径；而当qq0时，算法会选择采用探索性搜索，此时蚂蚁以概率l- q0进行随机路径选择。在算法迭代的初期，q0需要选择较大的初始值，且确定性搜索以较大的概率进行，这样做的目的是为了加快寻找局部较优路径的速度；在算法的中期q0的值会以较小为准，增大探索性搜索的概率，继而加大搜索空间；直到算法的后期，恢复q0的初始值，加快收敛速度。结合最大最小算法改进后的蚁群算法，得到的基于改进后蚁群算法的物流配送路径优化问题的算法流程图：开始G=0，初始化信息C，设置进化代数G_MAX，对每只蚂蚁初始化车辆序列G=G_MAX吗随机产生q0,1)tabu满了吗更新最佳路径，清空tabu，G=G+1，更新q0，若连续未进化代数r=rmax，r=MAXlr，rmin得到最优路径，输出结果结束NYNY更新tabuY返回物流中心，选择下一辆车结束得到最优路径，输出结果更新最佳路径，清空tabu，G=G+1，更新q0，若连续未进化代数r=rmax，r=MAXlr，rmintabu满了吗随机产生q0,1)G=G_MAX吗G=0，初始化信息C，设置进化代数G_MAX，对每只蚂蚁初始化车辆序列开始 图1 算法流程图第六章 软件实现本章就会展示基于改进后蚁群算法的物流配送路径优化系统。6.1 功能要求（1）生成客户数据 用户可以在软件界面上随机标注仓库与客户的地址(不少于10个客户)；客户的地址表示采用Window设备坐标系。客户地址间的距离采用设备坐标像素间距模拟，坐标之间行驶速度采用随机算法生成。（2）动态路线规划软件可根据用户选择的路径规划策略，如最短路径、最少时间等进行配送路线规划。模拟车辆从仓库出发，沿着规划的配送路线行进，最后返回仓库。在配送过程中可模拟前方行进路线堵车事件，软件能够绕开堵车路段动态规划配送路线。6.2总体设计本系统是基于蚁群算法的路径优化设计，主要作用是根据6.1所述的功能要求设计，在给出随机需求点的坐标数据后，输入约束条件（即事故路段），通过数据计算，最终系统根据计算结果得出优化后的路径（长度最短、时间最短）。数据图如下：6.3 软件架构在B2C农产品电子商务物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。本软件可以在配送之前根据客户的配送地址间线路间距、经验路况做分析计算出一条最优配送路径。而且，事先通知系统拥挤路段后，系统可以选择避开该路段的最优路径。软件界面分为左右两栏，左栏控制部分有produce data、route shortest、time shortest、Drive、exit五个按钮，分别用于产生随机数据、选择路线最短的路径、选择时间最短的路径、模拟汽车行进、退出软件。显示部分可以显示最优路径以及相应路径的代价。具体的，右栏可以显示仓库和客户区位置（此软件设置客户区为14个）并且根据相应的操作描绘出最佳路线并模拟汽车行进。编程实现上，自定义两个类，class WuLiu、class Ant，其中WuLiu类用于实现软件的外观；Ant类用于实现算法。6.4 测试文档测试方法：软件运行后，点击Produce Data按钮可以生成随机测试数据，如果数据不理想，可以继续点击该按钮；点击Route Shortest按钮，右侧栏会描绘最优路径，同时左栏会显示路径中从仓库出发依次经过的客户区，同时显示此条路径的代价；对于时间最短的测试与上面类似；点击Drive，模拟汽车行进；点击Exit，退出软件。测试中可能出现的问题：对于同一批数据，两次点击Route Shortest按钮生成的最优路径会有所不同，这是由于算法陷入局部最优导致。对于时间最短路径可能会出现的问题也是如此。虽然会出现陷入局部最优的情况，但是，测试发现由此造成的误差会限制在一定范围内，这中误差往往是可以接受的，另外可以通过选择合适的alpha、beta值使得误差进一步减小。第七章 总结语本文的核心研究是基于改进蚁群算法的物流配送路径优化问题。针对该问题，将今年来市场以及研究中运用过的其他智能算法相应做了对比和简述。论文中，通过结合最大最小蚁群算法对基本蚁群算法做出改进，解决了基本蚁群算法收敛速度缓慢，优化结果差等问题，同时基于改进后的算法本身也可以做到避免陷入局部搜索、算法停滞等问题。在信息素方面无论是信息素初始化更新，还是迭代时的重新初始化更新方面，改进算法都具有优势，相应的提高算法收敛速度和全局寻优能力。本文在验证方面选取的是经典问题旅行商问题（TSP），为了使得论文研究更具实际价值，在车辆路径问题（VRP）的基础上做出进一步扩充在容量方面做出基于现实的限制，也就是CVRP。本文的所有研究都是基于该前提条件进行的研究，实际应用方面更具考究。在最终的软件设计方面，完全满足论文选题对软件的技术要求，在随机生成需求点坐标后，软件可以快速的做出响应，给出满足条件的优化路径，包括最短时间优化和最短距离优化，同时在软件中也可以实现针对某事故路段而做出路径的重新优化，以及该优化结果相应路径的代价。并且给出了优化路径的数字表达，更直观也更加满足在现实环境中的路径解决需要。本论文主要工作如下：1、 开题介绍了论文研究的背景、目的、意义，以及对国内外相关物流发展现状和问题展开讨论。2、 对相关的智能算法做了部分简介，包括各种智能算法的演绎基本原理、发展优势及实际应用中产生的问题和不足。3、 进入本论文重点需要应用和介绍的部门对基本蚁群算法的基本原理、数学模型和约束条件等做了论述，同时相应介绍TSP、CVRP等问题，为后面的改进蚁群算法章节做了铺垫。4、 主要介绍改进后的最大最小蚁群算法，列出在基本蚁群算法改进的步骤、注意点，结合相关研究得出改进后蚁群算法的优势所在。5、 针对以上研究对基于QT界面制作的软件部分做出相关介绍，包括软件的总体设计、制作原理和功能要求。6、 对论文中算法的优势以及软件部分的优缺点进行总结，同时对未来物流的发展进行展望，也提出了针对本论文可以改进的地方。结合论文部分做出的基于改进蚁群算法的物流配送路径优化系统，在适用性和功能性都较高，能够在较短时间、花费较小代价的前提下给出最优路径或者接近最优路径的解，符合论文选题的要求。研究展望如上所说，本文能够在选题的要求下做出较为合适的系统，最终得出最优解或者近似最优。然而，本论文也是一些不足之处。比如，路径选择都是直线行走，而实际生活中的路线不可能都是直线，当然，这是技术层面上的问题，相对来说，需求点的顺序走向是没有太大差异。所以，在时间和技术允许的情况下，还可以做出一下几个方面的研究拓展：1、 GPS导航技术的支持。这会使得该系统更加完善，配送车辆在某一点时随时可以根据具体情况改变方案。2、 在系统中可以加入一个需求紧急度，即将客户的需求分类，哪些需要重点、迅速的配送，哪些相对时间不急，这样的安排更具人性化。3、 建立真实情况下客户资源数据库。4、 可以细化软件模块，比如添加用户注册模块、用户登录模块甚至系统管理模块等等。5、 动态设计更优化。本系统是可以避开事故路段重新规划路径的，然而这还是不够的，如果进一步对其动态设计，还可以添加在行驶途中遭遇问题的规划。技术革新的脚步从没有停止过，不断的创新才是发展的根本。正如论文对基本蚁群算法的改进一样，今后也一定会出现更好、更快的算法，我们要做的就是把这些运用到实际中，让物流业的发展更进一步。作者在技术和经验上还有诸多不足，论文中难免有些许错误，往各位老师能够指正，不胜感激。参考文献1Bernd Bullnheimer, Richaxd F Hartl, Chri