水電站電纜敷設算法優化的研究和探討

黃志澎

（中國電建集團成都勘測設計研究院有限公司數字工程分公司，四川 成都 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 算法優化，實現了對動態橋架網的最短路徑的快速求解，并應用在猴子巖電站的電纜設計工作中，取得了顯著的成效。