蚁群算法在弱电管线路由优化中的应用研究

景艳龙，赵立君 俞必勇

(北京工商大学规划建设处，北京 100048) (北京工商大学网络中心，北京 100048)

蚁群算法在弱电管线路由优化中的应用研究

景艳龙，赵立君 俞必勇

(北京工商大学规划建设处，北京 100048) (北京工商大学网络中心，北京 100048)

基于蚁群算法，建立地下弱电管线优化模型，并将该模型应用于弱电管线路由优化设计中。结果表明，弱电管线路由优化后可以节省施工费用，说明该方法具有可行性，可以为弱电管线路由优化设计提供参考。

弱电管线；路由；优化；蚁群算法

近年来，弱电管线的规划越来越受到人们的重视，其中路由规划是一个重要研究方向。路由规划除要考虑符合设计规范、方便施工外，还要考虑节约建设成本，这是进行路由优化的主要目的。铺设弱电管线施工过程包括铺设PVC格栅管和沿PVC格栅管铺设弱电线缆2个阶段。目前对弱电管线路由优化的研究大多只限于其中1个阶段，而没有对上述2个阶段进行整体优化。为此，笔者在考虑铺设线路最短的基础上，利用蚁群算法，将铺设弱电管线施工阶段的总工程费最低作为优化目标，从而达到节约施工费用的目的。

1 蚁群算法概述

蚁群算法是一种新兴的模拟仿生算法，具有模拟生物界群体觅食的能力，并且能够在实际的路径搜索过程中对外界的影响作出动态响应，由于蚁群算法原型本身就是一个寻找最短路径的模型，因此它在路径优化方面有着天然优势[1]。

为了便于描述蚁群算法数学模型，引入如下变量：N表示路由中的节点数；M是蚁群中蚂蚁的数量；T表示循环次数；dij(i，j=1，2，…，N)表示节点i和节点j之间的距离；τij(t)表示t(0

(1)

式中，allowedk={N-tabuk}表示蚂蚁k下一步允许选择的节点；α和β为2个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性；ηij为启发函数，其表达式为：ηij(t)=1/(dij+dje)；dij为相邻两节点之间的距离；dje为下一步可选节点和终点之间的直线距离。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或完成一个循环后，要对残留信息进行更新，可以采用局部更新和全局更新相结合的更新方式。

当第k只蚂蚁完成一条搜索路径时，在其经过的边上按照局部更新规则对信息素浓度进行局部更新[3]：

(2)

当M只蚂蚁全部完成一次循环，则对本次循环中产生的全局最优路径上的边按照全局更新规则进行更新：

(3)

式中，Lgb为到目前为止找到的最优路径。

2 地下弱电管线优化模型的建立

在对弱电管线路由进行优化之前，首先要根据地上建筑情况和地下管线情况，确定可行的路由，在可行的路由基础上确定最优路径。

2.1弱电管线可行路由的规划

可行路由规划的原则包括以下几方面[4]：①为了方便施工和不影响交通，以及减少管线负荷，管线路由应设在道路两侧人行道上或绿地内。②为了方便管井的挖掘，管线路由应设在地上障碍物、地下管线较少的地段。 ③管线路由应考虑新旧管道衔接问题。④管线位置尽可能与现有弱电设备在路的同侧，便于连接。⑤管线位置的选择应方便出户入户。

2.2费用权值系数的确定

由于铺设弱电管线分为铺设PVC格栅管道和铺设弱电线缆2个阶段，因此铺设管线的总费用为线缆铺设费用与PVC格栅管道铺设费用之和：

(4)

式中，Cij表示从节点i到节点j段管线铺设总费用；Cl表示每段线缆铺设单价；Cd表示从每段PVC管道铺设单价；Cw表示管线所经路由中弱电井的造价；k′表示弱电井数量；dij表示从节点i到节点j段距离。

如果起点和终点不同的2条及以上线缆路由在某一路段可沿同一管沟铺设，即部分路由重合，则线缆费用为多条线缆的总费用，而管道费用为1条管道的费用。如果管道费用计入第1条线缆，则第2条及以上线缆管道的费用为0，则式(4)可以改写为：

(5)

式中，kij为加权系数，如果进行某条管线路由优化时，发现已有其他管线从本段路由经过，则kij取0，否则取1。

2.3优化的步骤及优化目标函数的确定

假设需要铺设的管线条数为m，将第1条进行最低费用优化的管线称为首选优化管线，确定的优化步骤如下：①任选出1条线路j′作为首选优化管线，利用蚁群算法进行优化；②在确定了首选优化管线的基础上，任选第2条管线进行优化；③重复步骤②，随机选第i′条管线，在前i′-1条路径已确定的条件下，进行管线路由优化；④当所有管线路由均优化后，将所有的管线费用求和，表示为：

(6)

由于第2条及以后的管线路由优化都在首选优化线路选定的基础上进行，首选优化线路不同会导致施工总费用不同，因而需要把m条管线中的每1条都作为首选优化线路进行优化并计算总费用，然后进行对比，从而找出费用最低的优化方案。

所以，最终优化的目标函数为：

(7)

3 应用实例

图1 规划的可行路由

为了验证优化模型的可行性，以北京工商大学阜成路校区西区架空线改造工程中7条光缆的铺设为例，进行了弱电管线路由优化设计。

3.1可行路由的规划

根据可行路由规划的原则，规划出架空线改造工程的可行路由(见图1)。

3.2Cl、Cd、Cw参数的确定

根据工程实际测算，7条管线线缆费用(Cl)的值分别为142.5、240、101.25、101.25、320、160和95元/m；管道铺设费用(Cd)为222.52元/m；弱电井工程费用(Cw)为3750元/个。

3.3运行结果

确定相关参数后,利用开发的软件和地理信息组件运行蚁群优化算法程序，使用ArcEngine的渲染方法对找到的最优路径进行显示(见图2)，图3为原设计路由。经过计算，原设计路由总造价为555882.11元，优化路由的总造价为526296.69元，施工总造价减少5.32%，说明笔者提出的优化方法是可行的，可以应用于弱电管线路由优化设计中。

图2 优化路由 图3 原设计路由

[1]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[2]Dorigo M，Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 21(1)：53-66.

[3]黄贵玲，高西全.基于蚁群算法的最短路径问题的研究与应用[J].计算机工程与应用，2007，43(13)：233-235.

[4]韦鹤平.最优化技术应用[M].上海:同济大学出版社,2000.

[编辑] 李启栋

10.3969/j.issn.1673-1409(N).2012.11.042

TP301 6

A

16731409(2012)11N13003