一种通信故障设备物流建模的DA算法研究

彭金明 黄大巧 陈胜君 张奇

摘 要：随着LTE的商用，无线网络规模越来越大，网络设备越来越复杂，运营商为了网络故障的响应效率，投入了大量成本进行网络运维，然而网络运维仅仅注重管理流程上和工具软件方法上的改进，却忽视了基站故障物流处理能力，而这个方面往往是提高基站响应速度的最佳手段，考虑到基站维保需要固定的检测周期，移动基站的分布分散的特征，本文采用了一种通信故障设备物流建模的DA算法，通过对基站退服设备的信息挖掘，制定最优的收集机制，大大提高的基站维保的响应速度。使无线网络更加具有竞争力，使运营商在得到更加快速的备件服务、更加快速的故障响应以及更加贴近的IT服务的情况下，减少企业的运营成本。

关键词：无线维护；通信设备；物流建模；迪克斯拉特（Dijkstra）算法

1 背景

对于无线网络维护来说，基站是通信系统中很重要的一个节点，一旦某个基站出现退服，则该基站天线覆盖范围内信号会中断或者严重变弱，会严重影响到覆盖范围内客户的正常通话。对于基站代维的我们来说，保证基站的正常运行是我们日常维护的重中之重，但是有些时候基站退服是不可避免的，所以只有增强代维人员的技术水平，降低退服处理历时，才能保证移动公司在激烈的市场竞争中立于不败之地。将会引起网络调整和网络容量的排除或者更换设备都需要上站，为了提高基站故障的处理能力，对于基站维保单位来说，需要出门收集故障设备，但是由于故障问题设备并不是集中在一起的，这就需要驱车赶往每个基站点进行收集工作，所以就要求有一个较好的行车路线，使得其在取到所有的设备的同时，行进的路线最短，耗时最少，这样既可以节约成本，又可以提高劳动效率。

2 算法介绍及问题建模

2.1 算法介绍

利用计算机计算效率快以及现有的资源，我们将利用迪克斯拉特（Dijkstra）算法以及电子地图为我们方案提供支持。我们首先电子地图获取点与点之间的最短的距离，之后再利用迪克斯拉特（Dijkstra）算法寻找出一个较好的行车路线。同时考虑为了不消耗过多的计算机资源，同时对迪克斯拉特（Dijkstra）算法进行了优化，找到最优的路径。

2.2 应用建模

无线通信设备维保物流面临的问题主要针对地图上收取设备的站点非常多的情况，因为只有在这种情况下，算法的优越性才能体现出来，而当点比较少的时候，不同路径的距离差异并不明显。综合迪克斯拉特（Dijkstra）算法，对较多收取设备站点的情况进行路径规划。实际问题如图所示，我们需要从圆点处移动到剩下的每一个标记点处，最后再返回到圆点处的标记点。

此时，站点在几十个以内，假设车的容量足够大，可以考虑把情况表示如下图2：

圆点代表出发点，三角形代表站点，则首先按照大致方位进行分区，使得每个区内的数量在10个以内，以减少每个区的运算量。然后分别对每个区用迪克斯拉特算法计算最短路径（此时每个区的起点取为离上一个区最近的点，而终点取为离下一个区最近的点），如上图中，从圆点首先到达1，然后1到2的路径采用迪克斯拉特算法，即可走完此区域。这样依次按图中箭头，即可在每个区域内都按照迪克斯拉特算法算出的路径走完，最终回到圆点。

当站点点数进一步增加，分的区域也变得更多的时候，区域与区域之间的路径也应考虑在内，如下图，此时可把区域看成点，然后用迪克斯拉特算法规划出区域与区域之间的最优路径，此时，起点取为圆点点（车辆出发点），终点取为离圆点最近的区域。这样，车辆行驶的距离，一方面从区域到区域之间是最短的，另一方面，在每一个区域内部也是最短的。

如果车辆的容量并非足够大，则需要先统计地图中设备的量，假设为X，假设车辆的容量为M，那么车辆需要运的次数为T=（[X/M]+E）

这时候我们先将地图纵向或者纵向分成 个区域，调整边界，保证前面每一块区域的数量尽量接近S=K*N

接下来再调整其剩下的方向，保证前面划出的区域数量尽量接近于汽车容量M。

3 算法应用效果分析

以杭州市某运营商无线基站维保物流为例，进行算法建模与传统方式比较。以比较算法在应用中的优劣和效果。图4是我们假设的一次收取设备的过程，我们按着一般的经验选择路线，在图上，我们可以看到，路线可以说是按照我们一般平常车辆习惯的路线执行，而总共我们走的路程为20.1公里。

将上图化简，并编号得到下面的图

接下来我们要得到每两个点之间的最短距离

利用迪克斯拉特（Dijkstra）算法我们可以得到最短路径为0→1→5→3→2→4→6→7→0

总的距离为15.8公里，相对最初的选择提高了21.4%的效率，时间节省了26.7%。

4 结论

结合迪克斯特拉（Djikstra）算法和复杂的无线基站物流的新的发展，提出了一种通信故障设备物流建模的DA算法，应用实践说明了按照该算法设计的路线，对提高整个网络维保的经济型，时效性、安全性、沟通性和方便等性能都取得了较好的效果。当结点就比较多，求解的复杂度就会很大对于路径规划问题，通过划分区域，并分别在区域间和区域内应用该算法，使得整体和局部的路径都得到优化，从而可以达到省时省力、高效快捷的目的。

[参考文献]

[1]Wikipedia.Dijkstra's algorithm.

[2]Rosen K H，Krithivasan K.Discrete mathematics and its applications[M].New York：McGraw-Hill，1999.P652.

[3]Rosen K H，Krithivasan K.Discrete mathematics and its applications[M].New York：McGraw-Hill，1999.P653.