基于蚁群算法的配送路径规划研究，本文主要内容关键词为：算法论文,路径论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
文章编号：1002-3100(2013)07-0045-03
关于物流配送路径规划一直是物流领域研究的热点和难点问题，从国外研究情况来看，1993年Ronald等人提出物流系统设计的四个核心战略规划区域模型(Four major strategic planning areas in logistics system design)，他认为四个核心区域为客户服务水平、选址决策、库存决策和运输决策(Customer service levels，Location decisions，Inventory decisions，Transport decisions)，对于配送中心选址方法可简单分为定性和定量两大类，定性方法主要是层次分析法和模糊综合评价相结合对各个方案进行指标评价，找出最优地址。定量方法包括重心法、运输规划法、Cluste法、CFLP法、Baumol-Wolfe模型、混合0—1整数规划法、双层规划法、遗传算法等。蚁群算法是一种新型的优化方法，该算法不依赖于具体问题的数学描述，具有全局优化能力。
本文提出了一种基于改进蚁群算法的物流配送路径规划方法，将物流配送中心看成一个聚类过程，再利用蚁群系统中蚂蚁通过信息素留存寻找最优路径的机制，结合蚂蚁使物体聚堆的行为模式，合理设计转移概率、禁忌列表及信息素更新方式，使系统配送中心的配送路径最短，从而确定配送中心的配送路径。
1 蚁群算法
仿生学家经过大量细致观察研究发现，蚂蚁个体之间通过一种称为外激素的物质进行信息传递，蚂蚁在运动过程中，能够在它所经过的路径上留下信息素，而且蚂蚁在运动过程中能够感知这种物质，并且以此指导自己的运动方向。受此启发，它由意大利学者Marco Dorigo于1991年在他的博士论文中引入，提出了一种基于蚂蚁种群的新型优化算法——蚁群算法。
蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，蚂蚁总能找到巢穴与食物源之间得最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取得基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。
1.1 研究目的
本研究拟通过学习蚂蚁觅食回巢的生物本能，对物流配送进行仿真模拟，找出优化的配送路径，提高物流配送的效率和效益。
1.2 研究的对象
先对6个同配送点的配送方案进行研究，然后延伸到100个配送点，并找出最佳路径。以上步骤均通过计算机编程进行演化分析。把研究的成果进行实际应用的演算和验证。
1.3 研究方法
本文使用蚁群算法，进行人工模拟配送路线，并用计算机编程进行模拟，就如同一只人工蚂蚁，背着背包，到若干个结点，搬运食物回蚁巢。
规则1 环境：人工蚂蚁所在的环境是一个虚拟的世界，有确定的路线桥，且两点间路线桥不相交；有信息素，信息素都同质(不区分，找到食物时分泌的信息素和回巢时分泌的信息素)，环境以一定的速率让信息素消失。
规则2 移动：人工蚂蚁只会沿着路线桥觅食，当走到结点(觅食点)，人工蚂蚁会判断是否有信息素及其浓度，优先选择信息素浓度大的路线桥为路径；同时会有一定的概率，随机选择别的路线桥；如路线桥上均无信息素则随机选择路线桥。
规则3 觅食：人工蚂蚁沿路线桥到各个结点觅食，当到达该觅食点后，为防止人工蚂蚁原地转圈，它会记住最近刚走过哪些点(禁忌表)，如发现下一个结点是已觅食过的结点，则会避开该点。
规则4 信息素：每只人工蚂蚁在遍历完各点后，系统会利用蚁周算法更新信息素，对总路径最短的路线进行精英激励，会大量增加该路线信息素；如果总路径较长则少量增加信息素；信息素在人工蚂蚁遍历完后，将会按一定速率自动挥发所有路线桥上的信息素。
2 研究步骤
2.1 初始化结点
各个结点进行坐标化，数据存入zuobiao(序号：X，Y)表中，见表1，然后构造成路线桥距离矩阵存入jiedian(序列：1，2，3，…，n)表中，见表2，此次研究拟选用zuobiao表中的结点和数据：
2.2 信息素表示
所有的路线桥上的信息素全部为0，并把信息素数据存入xinxisu(序号：1，2，3，….，n)表中，见表3，用0表示无信息素。
2.3 初始化禁忌表
人工蚂蚁比较聪明，当到达该觅食点后，它会记住已找到的结点，并把结点信息存入jinji(序号，禁忌，先后顺序)表中，其中0表示未用，1表示已用，详见jinji表，见表4。
第1只人工蚂蚁运行状态：人工蚂蚁从巢穴出发，判断与该结点连接的各个路线桥上的信息素的浓度，因信息素均为0，则用随机函数进行选择路线→在jinji表中把起点设置为1(已用)，先后顺序为1，离开起点→沿着该路线桥到达下一觅食结点，信息素为0，则用随机函数进行选择路线→同样在jinji表中把第1个觅食结点设置为1(已用)，先后顺序为2，离开第1个结点→沿着该路线桥到达下一觅食结点，判断信息素，随机函数选择路线桥→……→当6个觅食结点全部走完后，人工蚂蚁自动沿着路线桥回到巢穴结点，从而形成完整的闭合回路→计算总路线桥长度，用L1表示，同时更新xinxisu表，在路线桥闭合回路全部洒上强度为3的信息素。
第2只人工蚂蚁运行状态：人工蚂蚁从巢穴出发，判断与该结点连接的各个路线桥上的信息素的浓度，原则上沿着信息素浓度大的路线桥通往下一觅食结点，但也会有“叛逆”的情况，用随机函数产生这种小概率事件，如人工蚂蚁遇到小概率事件，则沿着小概率事件选择的路线桥爬行到下一觅食结点→在jinji表中把起点设置为1(已用)，先后顺序为1，离开起点→沿着该路线桥到达下一觅食结点，判断连接该觅食结点各个方向上的信息素浓度，正常是沿着信息素浓度大的方向移动，同时考虑小概率事件是否发生，如发生则沿着小概率选择的优先路线前进。→同样在jinji表中把第1个觅食结点设置为1(已用)，先后顺序为2，离开第1个结点→沿着该路线桥到达下一觅食结点，判断信息素浓度，并优先考虑小概率事件→……→当6个觅食结点全部走完后，人工蚂蚁自动沿着路线桥回到巢穴结点，从而形成完整的闭合回路→计算总路线桥长度，用L2表示，更新xinxisu表，判断该轮路线桥总长度是否是最短，如最短则在第2只蚂蚁走过的路线桥上全部洒上激励的信息素，其值为3，同时，在全部路线桥上按1个信息素/每轮的速率，挥发信息素。
2.4 总路线长度最优的判定
判断路线桥该轮路线桥总长度是否是最短，可分为如下三种情况。
L1＜L2 增加L2闭合回路上的信息素+1 把L1设为最短路径，用Lmin表示，后续人工蚂蚁的Ln均与Lmin比较
L1=L2 增加L2闭合回路上的信息素+3 把L2设为最短路径，用Lmin表示，后续人工蚂蚁的Ln均与Lmin比较
L1＞L2 增加L2闭合回路上的信息素+3 把L2设为最短路径，用Lmin表示，后续人工蚂蚁的Ln均与Lmin比较
后续n只人工蚂蚁和第2只蚂蚁一样觅食(n=80)，最终沿着信息素最浓的路线桥爬行各个觅食点，其路径桥为最短路线。
2.5 参数选取
(1)随机小概率为0.05，结点6个，信息素对精英蚂蚁奖励+3，对一般蚂蚁+1，信息素挥发速率为1/轮。
(2)人工蚂蚁选取80只(迭代80轮)。
(3)觅食结点的状态。其中第1只人工蚂蚁比较特殊，路线桥选择不是按信息素的浓度进行选择，而是人工赋予随机选择函数。在离开原点时选择概率为1/6，到第一个结点后选择概率为1/5，到第二个结点后选择概率为1/4，……，1/1回到巢穴。
2.6 进行演算
觅食结点的状态选取3种状态：离散型、聚合型、平均型；随机小概率事件按分形理论选取20个不同的参数，如下值：0.5、1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5、5、15、25、35、45、55、65、75、85、95；每轮蚂蚁选择80只；为了剔除异常收敛，每轮均进行10次演算求出平均值，作为该轮稳定的最短路径。综合考虑状态的聚合度、觅食结点个数、随机小概率事件，通过编程和建立数据库，模拟最优路线结果如下：
1→3→5→4→2→6→1 其中Lmin=45.2
3 实例分析
为了验证本算法的正确性，在Matlab平台上对其进行了仿真实验。建立如下数学模型，选取福州市某配送中心10个点进行配送，并且要求路径最短，如表5所示，10个点经过坐标化后是接近平均型分布，小概率事件选取0.5，人工蚂蚁选取80只，每轮进行10次迭代并取平均值。结合迭代运算，得出最优路径如下：
2→3→4→ 5→6→8→ 10→9→1→2
蚁群算法可以比较完美地解决配送路径问题，但也存在不足之处，特别是在信息不完全的情况下，比如两点之间有捷径，模拟最优线路与实际线路会有偏差，同时算法可能会陷入局部最优，可以通过控制收敛速度和加快趋向最优路径对蚁群算法进行优化。