论文部分内容阅读
【摘 要】本文以普遍应用的Dijkstra最短路径算法为基础，针对发电厂电缆敷设工作特点进行适应性修改，并在实践工作中进行了评估。
【关键词】最短路径；电缆敷设
1.前言
电缆敷设工作是发电厂电气设计中一项重要的工作内容，在计算机辅助设计普及的今天，利用计算机进行电缆敷设路径设计，寻找最短电缆路径，对提高工作效率和设计成果的经济可靠性均有极大的帮助。
本文依据应用广泛的Dijkstra算法，针对发电厂电缆敷设设计工作的特点进行适应性修改，经实践证明，取得了良好的效果。
2.算法设计
2.1电缆通道数据模型
在发电厂电气设计中，电缆通道是由电缆桥架、电缆沟道、直埋管线等构成的一个空间立体网格，在设计图纸中采用节点进行标识，如图：
为了对电缆通道进行恰当的描述，在计算机数据结构中，可以采用带权的无向图予以表示。所谓图，指的是有顶点集V和弧集R构成的数据结构，记为，且。其中，VR表示两个顶点之间的关系，表示从t到h的一条弧，定义了弧的意义[1]。
针对实际工作，顶点集V对应电缆通道各节点，弧集R对应各节点之间的通道，为了考量通道长度，加入集合L对其进行描述，若两节点之间连通，则即为通道实际长度，否则记。
2.2Dijkstra算法
Dijkstra算法是求解某源点到图内另一点最短路径的比较著名的算法，其基本思路是以源点作为最短路径点集合S的初始值，然后按照路径长度递增的顺序计算源点到各点的最短路径，并将最短路径顶点加入到集合S中，直至S=V。引入辅助变量D，用以记录源点到其余各点最短路径长度，引入辅助变量P（），记录最短路径点序列。
计算步骤描述如下：
初始化各变量。源点为k；
搜索k至其他各点j弧长，更新j至源点的最短距离；
将2）中求得的j加入最短路径序列P（），以j作为k代入步骤2）中继续运算，直至求得源点至各顶点最短路径长度。
上述计算步骤的通用计算机程序在各类文章中均有提及，此处不再赘述。
3.适应性改进及程序
3.1电缆通道容量控制
电缆敷设计算与一般的最短交通路径等计算不同，在实际的电缆敷设中，由于电缆桥架、电缆沟道等容量是一个有限值，所有的路径随着电缆经过，其容载能力都是逐步下降的，到一定数量电缆之后，会发生电缆通道满载，此时这条通道应视为关闭，或者截断。
对此，在程序中应纳入变量，记载各通道的容量情况，并随着电缆逐根敷设，各路由通道依照所敷设电缆的空间占用情况进行修正，当减小为一定值时，将弧长修改为无穷大，即标记为不连通，以便程序寻找其他通道。
3.2路径预筛除
在原始的算法中，步骤2）对图内每一个节点进行一次搜索操作，而在实际情况中，电缆通道的每个节点通常仅与其余有限的几个节点相连通，最多的连通数量一般不超过4个。因此，对于整个发电厂几百个节点而言，所有的节点之间存在大量的正无穷弧长，对这些不连通弧进行操作计算无疑浪费了大量的时间。
针对上述情况，可以在计算步骤2）中对弧长进行判断，筛除不连通弧，提高计算效率。
3.3参考路径应用
在发电厂电缆敷设中，存在电缆路径相同的情况，特别是大量的控制、测量电缆，这种情况更为普遍。因此，可以建立参考路径库，在每根电缆敷设之前，先在参考路径库中进行查找，如果命中，则可以直接省略复杂的计算过程，缩短敷设时间。
另一方面，考虑到电缆通道容量控制问题，需要在某电缆通道关闭时，将所涉及的参考路径自库中删除，以便程序寻找新的可达路径。
3.4实践效果
以上述算法为核心，补充数据录入与集中导入、文件保存与读取、电缆参考数据庫维护、数据导出与规范化出版等功能后，即可形成完整的电缆敷设软件。
通过在山西某两发电厂工程进行试验，除去原始数据的整理与导入时间，该计算方法从开始计算到完成格式化成品文件输出，平均每根电缆敷设时间约为13秒左右，在软件运行完毕之后即形成了满足出版要求的Excel表格文件，格式工整，数据准确，极大提高了工作效率。
参考文献：
[1]数据结构：C语言描述，方贤进，国防科技大学出版社，2010.9，ISBN978-7-81099-803-1.
[2]一种基于Dijkstra 算法的启发式最优路径搜索算法， 王景存/张晓彤，北京科技大学学报，第29 卷第3 期.
[3]动态网络中的最短路径改进算法，韩平阳/罗五明，军事运筹与系统工程，第21卷第1期.
[4]基于Dijkstra 算法的最短路径的实现，冯桂莲，青海大学学报（自然科学版），第25 卷第1 期.
[5]复杂网络中最短路径算法的研究及应用，罗飞/魏开平，电子测量技术，第30 卷第4 期.
[6]电力工程电气设计手册，电气一次部分，中国电力出版社.
作者简介：
谭李师（1978.02-）男，汉族，籍贯：河北省保定市，2000年毕业于华北电力大学电力工程系，现就职于中国核电工程有限公司河北分公司，高级工程师，从事核从事核电站电气设计工作。
解险峰（1970.09-）男，汉族，籍贯：河北省保定市，1992年毕业于华北电力大学电力工程系，现就职于中国核电工程有限公司河北分公司，高级工程师，从事核从事核电站电气设计工作。
【关键词】最短路径；电缆敷设
1.前言
电缆敷设工作是发电厂电气设计中一项重要的工作内容，在计算机辅助设计普及的今天，利用计算机进行电缆敷设路径设计，寻找最短电缆路径，对提高工作效率和设计成果的经济可靠性均有极大的帮助。
本文依据应用广泛的Dijkstra算法，针对发电厂电缆敷设设计工作的特点进行适应性修改，经实践证明，取得了良好的效果。
2.算法设计
2.1电缆通道数据模型
在发电厂电气设计中，电缆通道是由电缆桥架、电缆沟道、直埋管线等构成的一个空间立体网格，在设计图纸中采用节点进行标识，如图：
为了对电缆通道进行恰当的描述，在计算机数据结构中，可以采用带权的无向图予以表示。所谓图，指的是有顶点集V和弧集R构成的数据结构，记为，且。其中，VR表示两个顶点之间的关系，表示从t到h的一条弧，定义了弧的意义[1]。
针对实际工作，顶点集V对应电缆通道各节点，弧集R对应各节点之间的通道，为了考量通道长度，加入集合L对其进行描述，若两节点之间连通，则即为通道实际长度，否则记。
2.2Dijkstra算法
Dijkstra算法是求解某源点到图内另一点最短路径的比较著名的算法，其基本思路是以源点作为最短路径点集合S的初始值，然后按照路径长度递增的顺序计算源点到各点的最短路径，并将最短路径顶点加入到集合S中，直至S=V。引入辅助变量D，用以记录源点到其余各点最短路径长度，引入辅助变量P（），记录最短路径点序列。
计算步骤描述如下：
初始化各变量。源点为k；
搜索k至其他各点j弧长，更新j至源点的最短距离；
将2）中求得的j加入最短路径序列P（），以j作为k代入步骤2）中继续运算，直至求得源点至各顶点最短路径长度。
上述计算步骤的通用计算机程序在各类文章中均有提及，此处不再赘述。
3.适应性改进及程序
3.1电缆通道容量控制
电缆敷设计算与一般的最短交通路径等计算不同，在实际的电缆敷设中，由于电缆桥架、电缆沟道等容量是一个有限值，所有的路径随着电缆经过，其容载能力都是逐步下降的，到一定数量电缆之后，会发生电缆通道满载，此时这条通道应视为关闭，或者截断。
对此，在程序中应纳入变量，记载各通道的容量情况，并随着电缆逐根敷设，各路由通道依照所敷设电缆的空间占用情况进行修正，当减小为一定值时，将弧长修改为无穷大，即标记为不连通，以便程序寻找其他通道。
3.2路径预筛除
在原始的算法中，步骤2）对图内每一个节点进行一次搜索操作，而在实际情况中，电缆通道的每个节点通常仅与其余有限的几个节点相连通，最多的连通数量一般不超过4个。因此，对于整个发电厂几百个节点而言，所有的节点之间存在大量的正无穷弧长，对这些不连通弧进行操作计算无疑浪费了大量的时间。
针对上述情况，可以在计算步骤2）中对弧长进行判断，筛除不连通弧，提高计算效率。
3.3参考路径应用
在发电厂电缆敷设中，存在电缆路径相同的情况，特别是大量的控制、测量电缆，这种情况更为普遍。因此，可以建立参考路径库，在每根电缆敷设之前，先在参考路径库中进行查找，如果命中，则可以直接省略复杂的计算过程，缩短敷设时间。
另一方面，考虑到电缆通道容量控制问题，需要在某电缆通道关闭时，将所涉及的参考路径自库中删除，以便程序寻找新的可达路径。
3.4实践效果
以上述算法为核心，补充数据录入与集中导入、文件保存与读取、电缆参考数据庫维护、数据导出与规范化出版等功能后，即可形成完整的电缆敷设软件。
通过在山西某两发电厂工程进行试验，除去原始数据的整理与导入时间，该计算方法从开始计算到完成格式化成品文件输出，平均每根电缆敷设时间约为13秒左右，在软件运行完毕之后即形成了满足出版要求的Excel表格文件，格式工整，数据准确，极大提高了工作效率。
参考文献：
[1]数据结构：C语言描述，方贤进，国防科技大学出版社，2010.9，ISBN978-7-81099-803-1.
[2]一种基于Dijkstra 算法的启发式最优路径搜索算法， 王景存/张晓彤，北京科技大学学报，第29 卷第3 期.
[3]动态网络中的最短路径改进算法，韩平阳/罗五明，军事运筹与系统工程，第21卷第1期.
[4]基于Dijkstra 算法的最短路径的实现，冯桂莲，青海大学学报（自然科学版），第25 卷第1 期.
[5]复杂网络中最短路径算法的研究及应用，罗飞/魏开平，电子测量技术，第30 卷第4 期.
[6]电力工程电气设计手册，电气一次部分，中国电力出版社.
作者简介：
谭李师（1978.02-）男，汉族，籍贯：河北省保定市，2000年毕业于华北电力大学电力工程系，现就职于中国核电工程有限公司河北分公司，高级工程师，从事核从事核电站电气设计工作。
解险峰（1970.09-）男，汉族，籍贯：河北省保定市，1992年毕业于华北电力大学电力工程系，现就职于中国核电工程有限公司河北分公司，高级工程师，从事核从事核电站电气设计工作。