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

王彥博

?

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

王彥博

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

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

0 引言

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

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

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

1 數(shù)學模型建立與分析

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

以南寧市軌道交通一號線信號系統(tǒng)電纜為例，可以分為信號電纜（DWZR-PTYA23）、計軸電纜（DWZR-PJYL23）、信標電纜（ET-2PI795）以及電力電纜（WDZC-YJY23），部分類型電纜還要區(qū)分不同芯數(shù)。結合廠家生產(chǎn)能力，設有根長度不均的光電纜，記為1、2、3...n；假如1光電纜大于預定的閾值而產(chǎn)生的差值記為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）中的受限條件即為任意根光電纜進行組合配盤，不能超過廠家生產(chǎn)能力閾值，若一根光電纜超過預定的閾值，剩余的差值繼續(xù)與其他光電纜進行組合配盤；式（2）、式（3）是根據(jù)差值計算出的接頭量；總函數(shù)即為求所有光電纜組合接頭量最小。在現(xiàn)場施工中，配盤時如果考慮了地鐵施工左右線的影響因素，將明顯提升光電纜敷設的效率，所以該受限條件不加入模型中，在Matlab中由程序進行篩選與處理。

2 回溯算法的設計

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

圖1 回溯算法流程圖

3 Matlab模塊化配盤

3.1 數(shù)據(jù)處理

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

圖2 南湖站信號電纜數(shù)據(jù)處理示意圖

3.2 回溯算法配盤

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

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

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

3.3 比較分析

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

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

表1 對比分析結果表

4 結語

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

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

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

（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] 車明，秦存秀，劉凱. 基于改進回溯算法的計算機排課系統(tǒng)[J]. 沈陽工業(yè)大學學報，2006，28（6）：667-670.

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

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

[9] 王巖冰，鄭明春，劉弘. 回溯算法的形式模型[J]. 計算機研究與發(fā)展，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。