基于Matlab融合回溯算法在光電纜配盤中的應用

王彥博

?

基于Matlab融合回溯算法在光電纜配盤中的應用

王彥博

結合南寧市軌道交通一號線信號系統光電纜配盤情況，介紹了通過Matlab模塊化編程進行配盤算法優化。結果表明采取回溯算法進行深度優化搜索，可減少接頭，節約成本，提高運營穩定性，降低維護難度，且通過Matlab進行模塊化編程解決該一維裝箱問題，操作性和移植性強、時間短、易優化。

光電纜配盤；Matlab；回溯算法

0 引言

在城市軌道交通工程中，光電纜敷設作為其主要工程內容之一，良好的配盤既可以提升光電纜敷設效率，又可以削減光電纜接頭數量，節約成本，提高運營穩定性，降低維護難度，在項目管控中具有重要意義。

基于城市軌道交通建設中各站、各處采用光電纜的長度和型號不同，廠家生產的光電纜每盤長度有上限閾值，光電纜配盤作為一種一維裝箱問題在工程實施中具有重要的研究價值。國內外對于一維裝箱問題以及算法做了大量的研究，文獻[1]探討并研究了貪心算法的思想及實現過程，通過實例分析了貪心算法的具體應用，指出了貪心算法的特點及存在問題；文獻[2]就如何給出材料利用率最高的切割方案提出了優化算法；文獻[3]提出了一種近似算法來解決一維裝箱問題；文獻[4]通過研究搜索樹的平均節點數，分析了回溯算法求解隨機模型的平均復雜性；文獻[5]基于回溯算法建立了飛機離場排序問題的數學模型，證明了回溯算法解決該類問題的高效性；文獻[6]在回溯算法中引入了擬人策略和遺傳算法，建立了排課系統的數學模型。

傳統光電纜配盤方法即為簡單的貪心算法，該算法沒有從整體最優加以考慮，僅從局部最優加以求解[1]，即只考慮滿足即將配盤的這一根電纜的條件，不考慮整體情況以及對后續剩余電纜的影響，從而增加了整個光電纜工程的接頭量，產生了額外成本，以及帶來其他維護問題。本文利用回溯算法，對南寧市軌道交通一號線信號系統光電纜數據進行了配盤，減少了光電纜接頭量，且采用Matlab進行模塊化編程，移植性和操作性強，方便快捷，為城市軌道交通光電纜配盤提供了一種新方法。

1 數學模型建立與分析

在運籌學領域有一類所謂最優化問題，即一維裝箱問題，其一般形式是：在滿足約束條件的前提下，給出自變量值，使目標函數值最優（通常是使得目標函數值最小或最大），學者們已經證明該經典組合優化問題是一個NP難度問題[7]，意味著不存在時間復雜度為多項式的完整算法，完整算法對于優化問題就意味著是可保證找到最優解的算法，而對于判定問題就是可保證正確判定的算法。

以南寧市軌道交通一號線信號系統電纜為例，可以分為信號電纜（DWZR-PTYA23）、計軸電纜（DWZR-PJYL23）、信標電纜（ET-2PI795）以及電力電纜（WDZC-YJY23），部分類型電纜還要區分不同芯數。結合廠家生產能力，設有根長度不均的光電纜，記為1、2、3...n；假如1光電纜大于預定的閾值而產生的差值記為1，依次類推分別記為2、3...n；每根光電纜的接頭量記為1、2、3...n；為所有光電纜接頭量總和，列出如下模型（以電纜閾值為例）。

min

s.t. 2000＜i+j＜2300 （1）

i= 1 (0＜j＜2300) （2）

i= 2 (j＞2300) （3）

＞0；＞0

式（1）中的受限條件即為任意根光電纜進行組合配盤，不能超過廠家生產能力閾值，若一根光電纜超過預定的閾值，剩余的差值繼續與其他光電纜進行組合配盤；式（2）、式（3）是根據差值計算出的接頭量；總函數即為求所有光電纜組合接頭量最小。在現場施工中，配盤時如果考慮了地鐵施工左右線的影響因素，將明顯提升光電纜敷設的效率，所以該受限條件不加入模型中，在Matlab中由程序進行篩選與處理。

2 回溯算法的設計

本文選取回溯算法進行配盤?；厮菟惴▽嶋H上是一個類似枚舉的搜索嘗試過程[9]，在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件或原先選擇并非最優解時，就回溯返回嘗試其他路徑（滿足回溯條件的某個狀態的點稱為回溯點）[10]，按照選優條件依次搜索，以達到目標。結合南寧市軌道交通一號線實際情況，靠近站臺中心的設備光電纜用量較小（幾百米不等），而遠離站臺中心以及位于區間的設備光電纜用量較大，所以在搜尋節點和約束條件設立的過程中應避免類似于貪心策略的選擇而導致的浪費?；厮菟惴鞒倘鐖D1所示。

圖1 回溯算法流程圖

3 Matlab模塊化配盤

3.1 數據處理

Matlab是一套功能強大的工程計算軟件，被廣泛應用于自動控制、機械設計、流體力學和數理統計等工程領域，可高效求解復雜的工程問題，并可對系統進行動態仿真，在此選取Matlab解決該一維裝箱問題。在初始數據中有7個關鍵字段，分別為規格型號、芯數、定測長度、起點、終點、作用、設備里標。在前文中提到，配盤時考慮左右線的影響將明顯提升光電纜敷設效率，首先將設備里標劃分出左線、右線，再按照型號、芯數、長度依次排列存入矩陣。由于部分光電纜長度已經超過了廠家預定的閾值，對該部分光電纜進行拆分處理并加以標記，超過閾值的部分作為新的光電纜存入矩陣（除長度以外的其他字段信息與原光電纜一致），以東段南湖聯鎖區信號電纜為例生成143×8的矩陣，見圖2。

圖2 南湖站信號電纜數據處理示意圖

3.2 回溯算法配盤

在包含所有問題解的解空間樹中，按照深度優先搜索策略，從根節點出發深度搜索解空間樹，當探索到某一節點時，要先判斷該節點是否包含問題的解，如果包含，則從該節點繼續探索下去，如果不包含，則逐層向其祖先節點回溯，分為3步：（1）確定解空間；（2）確定節點的擴展搜索規則；（3）以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索，提高程序運行速度。

上述數據處理分別生成3個聯鎖區對應的5個矩陣（信號電纜、計軸電纜、信標電纜、電力電纜、光纜），按照芯數、長度由高到低排序后，由于長度遠低于閾值的光電纜配盤靈活性較高，相反長度位于閾值附近的光電纜靈活性較低，所以在配盤時，優先組合處理靈活性低的光電纜。在某節點有多種可行解時記錄下該節點，并順著第一種路徑繼續配盤，組合所有候選對象后，剩下的未被選擇的對象強行配盤，計算接頭數量，之后再回溯到該節點，計算該點其余旁支結果，對比選取最小接頭數的解，保證所有的可行旁支都被搜索后才結束，依此類推得到最終配盤結果，以東段南湖聯鎖區信號電纜為例生成40×10的矩陣，見圖3。

圖3 南湖站信號電纜配盤結果示意圖

3.3 比較分析

在新的教學標準背景下，新修訂的高中英語課程標準增加了對英語詞匯和詞匯難度的需求。面對現狀下的英語教學標準，對比舊的英語教學方式，應在教學方式上作出改變才能滿足政策標準，讓英語詞匯記憶教學的有效性有所提高。如何使學生高效、優質地記憶英語詞匯已成為英語教學的首要任務。

南寧市軌道交通一號線石埠、西鄉塘、廣西大學、新民路、南湖、百花嶺、火車東站7個聯鎖區光電纜原配盤接續共325處，經回溯算法進行深度搜索優化后，共產生接續256處。對比分析結果如表1。在關鍵節點上回溯算法和貪心策略所做出的組合配盤不同，由于回溯算法考慮到每個對象的后效性，回溯過程相當于一個自動糾錯的過程，而貪心算法的貪心策略只考慮了當下局部的最優解，從而導致最后接頭數量有較大差異。

表1 對比分析結果表

4 結語

結合南寧市軌道交通一號線信號系統正線施工情況，通過數學模型的建立、回溯算法的選取、Matlab模塊化處理對7個聯鎖區的光電纜進行了配盤，得出如下結論：

（1）通過對配盤算法的改進，特別是利用回溯算法，避免了以往貪心算法導致的只能解出局部最優解的情況，合理組合優化了南寧市軌道交通一號線正線光電纜，共減少接頭69處，節約成本 82 264.82元，為項目成本管控提供了技術支持。

（2）配盤方法的改進，減少了光電纜的接頭量，提高了施工效率，增強了運行的穩定性，降低了維護的難度和工作量，為施工、運營、維護各方面帶來了一定的經濟效益和工作效益。

（3）利用Matlab對城市軌道交通光電纜配盤一維裝箱問題進行模塊化編程處理，與人工手動配盤相比，避免了人工失誤，操作性強，時間短，可復制，準確性高，適用于各地城市軌道交通工程。

[1] 肖衡. 淺析貪心算法[J]. 辦公自動化：綜合版，2009（18）：25-26.

[2] 曹晶，鄭巍，許旻鴻. 有約束的一維裝箱問題的新型算法設計[J]. 計算機應用與軟件，2008，25（5）：234-236.

[3] Coffman E J, Garey M, Johnson D. Approximation algorithms for bin-packing[J]. Algorithm Design for Computer System Design, 1984.

[4] 許可，李未. 隨機約束滿足問題的回溯算法分析[J]. 軟件學報，2000，11（11）：1467-1471.

[5] 李楠，劉來永，徐肖豪. 融合回溯算法在離場航班排序問題中的應用[J]. 計算機仿真，2012，（6）：88-92.

[6] 車明，秦存秀，劉凱. 基于改進回溯算法的計算機排課系統[J]. 沈陽工業大學學報，2006，28（6）：667-670.

[7] 孫春玲，陳智斌，李建平. 裝箱問題的一種新的近似算法[J]. 云南大學學報：自然科學版，2004，26（5）：392-396.

[8] 應莉. 0-1背包問題及其算法分析[J]. 計算機與現代化，2009，（6）：24-26.

[9] 王巖冰，鄭明春，劉弘. 回溯算法的形式模型[J]. 計算機研究與發展，2001，38（9）：1066-1079.

[10] 趙群英. 回溯算法及其改進型的分析與比較[J]. 電腦知識與技術，2011，7（8）：5436-5438.

With connection of situations for allocation of optical cable drums for signal system of line 1 of Nanning Urban Mass Transit, the paper introduces the allocation and optimization of cable drums by means of Matlab modularized programming. The results show that profound optimization and searching conducted by application of back-fitting algorithm may cut the number of joints, improve the operation stability and lower the difficulty of maintenance; and one dimensional packing problem may be solved by Matlab modularized programming, which is easy for operation, transplanting and optimization.

Allocation of drums of optical cables; Matlab; back-fitting algorithm

U231.7

B

1007-936X(2017)03-0028-03

2016-08-27

王彥博.中鐵電氣化局集團有限公司電氣化公司，助理工程師，電話：18817598843。