基于改进蚁群算法的物流配送路径优化研究

1、    基于改进蚁群算法的物流配送路径优化研究    夏鹏+张玮摘要：本文首先通过对传统蚁群算法在物流配送路径优化问题中的研究，得出蚁群算法存在如收敛速度较慢、算法易陷于局部最优等缺点，进而对蚁群算法进行优化改进，使物流配送路径优化研究得到更好的解决。关键词：蚁群算法 物流配送路径 优化一、引言互联网在不断地发展，这一时代慢慢兴起，网购逐渐走进我们的生活大当中。伴随着网购而不断兴盛的就是物流行业。物流行业越来越繁荣，对物流配送路径进行优化也显得尤为重要，因为这直接关系到物流行业的成本控制、盈利水平及配送效率。调查显示，目前在我们国家物流行业的总成本一半以

2、上花费在运输当中，这一项花费远远高于西方的一些发达国家。在研究物流配送路径的时候，我们常将其归属于组合优化，即是一个np完全问题。研究过程中，针对路径优化人们经常会用到诸如方案评价法、动态规划法、遗传算法等各类方法。不过就目前的一些研究而言，这些算法都存在着一定程度的缺点，并不是特别完美，比如遗传算法局部搜索能力不强，蚁群算法容易呈现停滞征象，等等。现在的研究中，针对以往在物流配送路径优化方面的一些算法进行改进完善，以便于原有算法的所存在的缺点和不足之处能够得到弥补。近些年来，受到生物进化展现出来的先进特点的启发，部分学者研究发现了一些像遗传算法、蚁群算法等的智能算法，并常常将这些算法运用到一

3、些复杂优化问题中去。在进行物流配送路径问题研究的时候，遗传算法具有收敛到全局最优的优点，不过在描述所求问题的约束条件时，这一算法往往表现的不尽如人意，而物流配送路径优化又是一种多约束问题。和遗传算法一样，蚁群算法也是一种随机搜索算法，不过蚁群算法有其自身的优点，比如其能同时兼顾解的局部构造和整体性能， 适合用来求解具有复杂约束条件以及解的组成元素之间关联性较强的优化问题。二、蚁群算法与物流配送路径问题2.1 蚁群算法描述蚁群算法（ant colony optimization， aco）是由意大利的著名学者marco dorigo最先提出来的，它是一种随机搜索算法。这种算法是受到蚂蚁群体在寻找

4、食物时探索路径行为的启发，它是对日常蚂蚁群体进行较优路径搜寻这一过程的模拟，蚁群中的每一只蚂蚁分别独自地在候选解空间中去搜索一个解，蚂蚁会在每次搜索完成之后留下一些信息量在相应的解上面在。根据所选择的解的性能的差异，蚂蚁会有选择的留下信息量，当解的性能较好的时候，蚂蚁会留下较多的信息量，反之留下的信息量则会比较少，其中留下较多信息量的解也相应的更加容易被再次选择。在刚开始执行算法的时候，每个解上面的信息量都是相同的，当算法不断地往前推进，就相当于蚂蚁不断地寻找路径，较优解上面留下来的信息量就会渐渐变多，这样不同解上的信息量就逐渐被拉开，进而收敛得到最优解或者近似的最优解。在解决物流配送路径优化

5、问题上，蚁群算法凭借其自身的优点表现出极其强大的作用。不过这种算法仍然在一定程度上存在着一些不足之处，例如收敛速度较慢、算法易陷于局部最优、各个参数的设置还建立在实验和经验的基础上、理论支持不是特别的严谨等。与神经网络、遗传算法等一些其他的优化算法相比，蚁群算法的优点体现在它具有正反馈、分布式计算、较强的鲁棒性以及富于建设性的贪婪启发式搜索等特点。蚁群算法的这些不同于其他算法的特点，使得一些更加复杂的问题在求解方面难度有所降低。2.2 物流配送路径问题描述2.2.1 问题描述针对物流配送问题，我们一般可以进行如下描述：为满足某一配送目标，从物流配送中心发出若干车辆，选择一条比较合适的的运输路线

6、，在满足送货量、时间窗、车辆数量、载重量、行驶里程等条件下，完成配送目标，要求对形式路线作出合理安排，使运输总成本最小，并且还需要满足下列各项约束条件：（1）当配送中心为完成一次配送任务后从该中心发出一辆运输车辆，运输车辆在完成配送中心布置的任务之后重新返回到配送中心；（2）各条线路上的运输车辆的最大运输量应该大于或等于该路径上面各站点的一次配送需求量；（3）每条配送路径的长度需控制在运输车辆单次配送的最大行驶距离以内；（4）有且仅能有一辆运输车给每一位客户送货。2.2.2 数学模型在建立蚁群算法数学模型之初，我们要考虑设计出一条最优的配送路线，该线路要满足总的配送距离最短。现作出如下假设：某

7、一区域有一个配送中心，该配送中心服务n个目标客户，每个目标客户的需求量为，从配送中心发出的运输车辆的最大运输量为g，定义二值函数如下：根据假设作出如下数学模型：（1）（2）2.3 蚁群算法在配送路径问题中的应用描述根据以上建立起来的蚁群算法，我们用车辆去替代蚂蚁，从配送中心发出一辆车，为配送区域中的一个配送节点配送货物，如果从配送中心发出的车辆的货运量能够达到需配送的配送节点的需求量，就对货物进行配送，如否则返回配送中心重新装货，表示完成一次配送。从配送中心发出的一辆运输车辆在一个配送过程中完成了相應的配送任务之后，对每一条配送路径上的信息素进行更新。一趟任务接着一趟任务去完成，当每一辆从配送

8、中心发出的车辆完成了各目标客户的配送任务之后，表示一次迭代成功的完成了，比较其便利的路径长度并保存最短路径，然后进行下一次迭代。三、蚁群算法的改进与优化3.1 改进算法数学模型在2.2节建立的数学模型的基础上，结合实际的物流配送情况，对蚁群算法的数学模型进行改进与优化。优化之后的算法具体描述如下：全局信息素更新规则：基于增强蚂蚁全局搜索能力的目的，使得收敛这一现象不要发生的太快，每一只蚂蚁在相同的一条路径上通过的时候会留下相应的信息素，这些信息素对其他蚂蚁访问该路径有抑制作用。所以可以按照下述规则对t时刻在路径（i，j） 上的信息素进行相应调整： 在（6）式中，我们用表示信息素的持久化系数，其

9、取值范围为0到1；用 （t，n）表示蚂蚁在第n次迭代后留在路径（i，j）上的信息素增量；0，1为一个系数； 的含义是完成一次迭代后，蚂蚁在前面n-1次迭代中在路径（i，j）上留下的信息素增量之和；这样表示属于前面迭代中蚂蚁释放信息素加权抑制因子。式（7）中： 表示所有的蚂蚁第 n 次迭代后在路径（i，j） 上留下的信息量的总和， 的取值采用蚁周系统模型，值为：式（8）中：lk表示的是第k只蚂蚁完成一次循环过程经历的总的路径长度；q表示信息素强度。局部信息素更新规则：和蚁群算法相类似。在改进的蚁群算法当中，局部信息素更新的设置主要是为了根据路径爬行次数与总次数的比值来对该路径上信息素的大小进行进

10、一步的控制，然后来对蚂蚁选择该路径的概率进行影响。所以，当蚂蚁从由区域i行驶到区域j时，式（9）中：表示的是前n-1次迭代所有蚂蚁经过路径（i，j）的次数比上前 n-1迭代参与搜寻的蚂蚁总数得到的数值大小，（1-）反应了路径（i，j）的重要程度。2（0<2<1）是一个参数，而 路径上信息素最初始的浓度。3.2 改进后的算法流程以tsp为例，采用蚁周系统模型。改进蚁群算法的主要步骤如下：（1）对参数进行初始化设置。在刚开始运行算法的时候，给每一个参数设置一个初始值：迭代的次数为nc=0，最大的迭代次数是ncmax，蚂蚁数量为m，信息素强度初始值为q，最小信息素强度为 ，最大信息素强度

11、为 和 、 的参数值；（2）把禁忌表清空，且nc=nc+1；（3）根据式（1）的路径选择概率，将蚂蚁从原始位置运输到下一个城市，再对禁忌表进行修改，在该蚂蚁的禁忌表中增加该城市；（4）如果算法中的蚂蚁是在第一次迭代中，就按照步骤（3）与（4）循环执行，如果不是，那么根据式（7）进行局部信息素更新，一直到该算法中每一只蚂蚁都生成一条路径为止。（5）对第 k 只蚂蚁通过的总路径lk进行计算，当蚂蚁是第一次迭代时，根据（2）式更新全局信息素，否则蚂蚁根据式（ 8） 进行所有路径上的全局信息素更新。（6）當循环次数 时，结束该循环，输出蚂蚁走过的路径，此时的路径为最优路径，若不满足 ，则转至步骤（2）。参考文献：1王训斌，陆慧娟，陈伍涛，张火明.改进蚁群算法在物流配送路径中的应用j.中国计量学院学报，2008，19（4）：342-346.2段爱民，陈泽琳，陈海波.基于改进蚁群算法的物流配送路径优化j.计算机技术与发展，2011，21（12）：178-181.3王睿.物流智能配送系统集成一体化探讨j.电子测试，2