水电站电缆敷设算法优化的研究和探讨

黄志澎

（中国电建集团成都勘测设计研究院有限公司数字工程分公司，四川 成都 610072）

水电站的厂区覆盖面积大，桥架空间布置错综复杂，电缆数量一般达到上万数量级，电缆敷设是电气设计中最为复杂的环节。水电站电缆敷设路径的优化具有重大的意义，包括节约电缆及敷设材料、降低电缆损耗和减少火灾的发生及电缆的损坏等。在电缆敷设设计时，优化设计工艺设备及电气设备的布置，优化配置电器设备，优化电缆敷设路径，减少电缆敷设长度，减少工程投资。电缆长度缩短，相应减少了电缆中的电量或信号损耗等。

当前的电缆敷设软件，在软件平台、行业特点各有侧重。基于REVIT 软件开发了CableSmart 电缆敷设设计系统，在求解水电站全厂大规模的桥架网、电缆路径计算中效率较低，通过优化电缆敷设路径算法提高系统性能，并成功应用在大渡河猴子岩等水电站工程，取得了显著成效。

1 国内外关于路径优化的研究

电缆敷设规划过程中，满足条件下获取最优路径是核心问题，需要不断优化寻路算法，提高自动敷设效率，缩短自动敷设的时间。最短路径算法重要的应用有计算机网络路由算法、机器人探路、交通路线导航、人工智能等。

最短路径计算分为静态最短路计算和动态最短路计算，静态最短路计算是外界环境不变计算最短路径，主要有Dijkstra 算法、A*算法；动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下最短路计算，典型的有D*算法。电缆敷设在敷设过程中，由于容积率等属性改变，桥架网是个动态网络，所以属于动态路径最短路计算。

国内外涉及到路径优化的研究很多，主要的研究方向都是针对特定环境下对算法的限制条件进行修改，其中罗建国等人在设计电缆敷设路径时，将所有的电缆路径抽象为复杂网络，不考虑每一段路径内具体敷设几条电缆，基于此，作者采用了树状、网状搜索算法对多条电缆敷设进行设计。张志广在求解电缆敷设最短路径的过程中，运用了改进的F-D算法，在对多条电缆进行敷设时将电缆按照长度进行排序来确定敷设顺序，为电缆敷设路径优化提供了一种新的思路。

A*、蚁群等启发式算法都有共同的特点，从随机的可行初始解出发，采用迭代改进的策略去逼近问题的最优解，但局部最优问题、参数设置问题和收敛速度的问题都是影响蚁群或启发式算法的重要因素。

2 Dijkstra 基本算法简介

Dijkstra 算法是典型的最短路算法，用于计算一个节点到其他所有节点的最短路径，主要特点是以起点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法由荷兰计算机科学家提出，使用了广度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法的输入包含了一个有权重的有向图G，以及G中的一个源点S，以V表示G中所有顶点的集合，每个图中的边都是由两个顶点所形成的有序元素对。（u，v）表示从顶点u到v有路径相连；以E表示G中所有边的集合，而边的权重则由权重函数定义，因此，就是从顶点u到顶点v的非负权重，任何两点间路径的权重，就是该路径上所有边的权重总和。已知有V中顶点s及t，Dijkstra 算法可以找到s到t的最低权重路径，也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

3 使用改进算法的实现

本项目中综合考虑编程复杂度、优化的效率等方面的需求，采用优先级队列对Dijkstra 算法优化。在本项目中，电缆的网络结构是无向的，并且由于电缆敷设的特性，偏向于稀疏图，因此本项目中采用邻接表的方式在存储图结构设计中。此外需要对Dijkstra 算法和优先级队列进行封装，形成算法类，该类的主要输入参数为图结构和起点、终点，在本项目中接受的是邻接表表示的图，输出为从起点到终点的不经过任何设备节点的最短路径，在实际项目中，需要求解成千上万条路径，就需要不断调用该算法类，每次调用计算出来一条当前状态下的最短路径，并更新当前路径的容积率，等待下一条路径计算。

算法的主体包括两部分，即找路过程和容积率更新过程。找路过程：通过Dijkstra 算法不断进行，迭代式松弛，搜遍全图，即可覆盖目标终点，使用parent[]数组来记录每次到达该节点最近的父节点，parent[i]=j，则从j到i的线路是最近的。容积率更新过程：通过parent[]数组倒序找到从终点到起点的最优路线，该路线可以保证容积率满足的条件下路径最短，在全局的table[]数组中更新线路上所有起点 终点的容积率。

使用邻接矩阵实现的dijkstra 算法的复杂度是O（V2）。使用邻接表的话，更新最短距离只需要访问每条边一次即可，因此这部分的复杂度是O（E）。但每次要枚举所有的顶点来查找下一个使用的顶点，因此最终复杂度还是O（V2）。在|E|比较小时，大部分的时间都花在了查找下一个使用的顶点上，因此需要使用合适的数据结构进行优化。

不采用最小优先级队列优化，时间复杂度为O（|V2|），其中|V|为图的顶点个数，通过斐波拉契堆实现的Dijkstra 算法时间复杂度为0（|E|+|V|log|V|），其中|E|是边数。对于不含负权的有向图，这是目前已知的最快的单源最短路径算法。

在寻找最短路径的过程中，难点在于数据结构要求是动态的。因为有向图的子图G'之外的点的集合在不断缩小，因此每次弹出一个节点之后都需要维护这个数据结构，使得下一次找最小值的开销依然会很低. 优先队列可以进行插入、弹出和维护操作。

优先队列有不同的实现方法，比如堆、二项堆、Fibonacci堆等。不同的数据结构对不同操作的时间代价不同，有优有劣。把每个顶点当前的最短距离用堆来维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要用的顶点。这样堆中的元素共有O（V）个，更新和取出的操作有O（E）次，因此整个算法的复杂度是O（ElogV）。

算法流程：通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作。初始时，原点s的路径权重被赋为0（d[s]=0）。如果对于顶点s存在能直接到达的边（s，m），则把d[m]设为w（s，m），同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示暂时没有通向这些顶点的路径，当算法结束时，d[v]中存储的便是从s到v的最短路径，或者路径不存在的话是无穷大。

边的拓展是Dijkstra 算法的基础操作，如果存在一条从u到v的边，则从s到v的最短路径可以通过将边（u，v）添加到尾部来拓展一条从s到v的路径，这条路径的长度是d[u]+w（u，v）。如果这个值比目前已知的d[v]的值要小，可以用新值来替代当前d[v]中的值。算法维护两个顶点集合S和Q，集合S保留所有已知最小d[v]值的顶点v，而集合Q则保留其他所有顶点，集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点，当一个顶点u从Q中转移到S中，算法对u的每条外接边（u，v）进行扩展。算法流程如图1所示。

图1 Dijkstra 算法流程图

考虑弹出最小值和更新节点这两个操作的话，时间代价最低的是 Fibonacci 堆。早在 1987年，UCSD 的教授 MICHAEL F 和TARJAN（Tarjan 算法的发明者）合作了一篇文章“Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms”，首创性地提出了Fibonacci 堆，并用它优化了一系列的算法，其中包括Dijkstra 算法。Fibonacci堆是满足最小堆属性的树的集合，也就是说，子节点的值总是大于或等于父节点的值，这意味着最小的值始终是其中一棵树的根，斐波那契堆的简单结构如图2所示。

图2 简单斐波拉契堆结构

斐波拉契堆可以在常数时间内进行插入、合并、减少关键字等操作，但删除搜索等操作并不是其专长。斐波拉契堆并没有太多需要时刻保持的属性，这使得对于插入、合并、减少关键字等操作变得容易。实际上它将很多工作留在了提取最小元素时来完成，所以这个操作实现起来复杂，运行起来耗时。

二叉堆是一个近似完全二叉树的结构，并同时满足堆结构的性质，即子节点的键值或索引总是小于（大于）它的父节点，那么二叉堆上最大值（最小值）就是根节点。在本项目中，使用数组的索引来表示元素在二叉堆中的位置，有以下规则：①元素k的父节点所在的位置为[k/2]；②元素k的子节点所在的位置为2k和2k+1。根据以上规则，可以使用数组的索引来表示二叉堆，通过二叉堆，可以实现插入和删除都达到O（logn）的时间复杂度。

对于堆来说，最小元素已经位于根节点，那么删除操作就是移除并返回根节点元素，这时候二叉堆就需要进行调整；当插入新元素的时候，也需要重新排列二叉堆以满足二叉堆的定义。

优先队列有以下几种基本操作：① Makeheap（ ）建立一个新的堆H； ②Insert（H，x）插入一个值域为x的元素；③Extractmin（H）返回优先队列H的最小值，并删除；④Decreasekey（H，x，k）把H中的某个值域为x的元素的值改成k；⑤ Union（H1，H2）；⑥把H1和H2中的元素合并一个新的优先队列。

斐波拉契堆与二叉堆主要操作的时间复杂度对比如表1所示。

表1 时间复杂度对比表

从表1可以看到基于二叉堆的优先队列的性能低于斐波拉契堆的性能，数量级级别不大时，两者的性能比较接近。斐波拉契堆的复杂性和常数因子比较大，因此除了管理某些大数据的应用，一般情况下使用二叉堆在实现上会更加方便。本项目中考虑到水电站桥架网节点数据量在100 000 以下，图也是稀疏图的客观条件，并没有使用复杂的斐波拉契堆来实现，采用二叉堆来实现。

4 运行性能测试

在算法性能测试中采用C#中的System.Diagnostics. Stopwatch 函数进行程序计时，其中计时起点为Main 函数的入口为所有程序开始之前，计时终点为所有程序完成，包括数据读取、数据规格化、路径计算、输出规格化和验证逻辑。所测试的硬件环境为Intel（R）Core（TM）i5-4200U CPU@ 1.60 GHz，2.30 GHz，8 GB，Win7X64。

目前的测试数据中，边表中存储63 211 条边，即存在63 211 个不同类型桥架，其中节点数为50 694，即存在50 694个不同类型的节点，包括设备节点和网络节点；设备节点中存在1 683 个节点，即网络中存在1 683 个设备节点，剩下的节点为网络节点；在电缆表中存在4 104 条电缆。对代码连续运行10 次，分别记录每一次路径计算的用时情况，以此来衡量算法的性能。根据10 次运行的时间绘制折线图，运行中的平均耗时为36 527 ms，可以看出，算法性能比较稳定，波动较小。算法用时折线图如图3所示。

图3 算法用时折线图

5 工程应用和验证

在大渡河流域的猴子岩电站数字化设计中，采用本院自主开发的CableSmart 电缆敷设设计系统开展了电缆敷设设计，如图4和图5所示。该系统是基于Revit 软件进行二次开发，通过优化电缆敷设算法，提高了电缆自动敷设的效率，大幅缩短了敷设路径计算时间，自动敷设时间从2 h 缩短为20 min 以内；提高了电缆优化敷设的效率，缩短了规则检查与优化敷设时间。

图4 油罐室空压机设备及桥架

图5 辅助和指导现场电缆敷设工作

6 结语

本项目中综合考虑编程复杂度、优化的效率等方面的需求，采用优先级队列优化Dijkstra 算法优化，实现了对动态桥架网的最短路径的快速求解，并应用在猴子岩电站的电缆设计工作中，取得了显著的成效。