王彥博

?

基于Matlab融合回溯算法在光電纜配盤中的應(yīng)用

王彥博

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

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

0 引言

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

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

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

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

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

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

2 回溯算法的設(shè)計(jì)

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

圖1 回溯算法流程圖

3 Matlab模塊化配盤

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

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

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

3.2 回溯算法配盤

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

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

圖3 南湖站信號(hào)電纜配盤結(jié)果示意圖

3.3 比較分析

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

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

表1 對(duì)比分析結(jié)果表

4 結(jié)語(yǔ)

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

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

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

（3）利用Matlab對(duì)城市軌道交通光電纜配盤一維裝箱問(wèn)題進(jìn)行模塊化編程處理，與人工手動(dòng)配盤相比，避免了人工失誤，操作性強(qiáng)，時(shí)間短，可復(fù)制，準(zhǔn)確性高，適用于各地城市軌道交通工程。

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

[2] 曹晶，鄭巍，許旻鴻. 有約束的一維裝箱問(wèn)題的新型算法設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用與軟件，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ī)約束滿足問(wèn)題的回溯算法分析[J]. 軟件學(xué)報(bào)，2000，11（11）：1467-1471.

[5] 李楠，劉來(lái)永，徐肖豪. 融合回溯算法在離場(chǎng)航班排序問(wèn)題中的應(yīng)用[J]. 計(jì)算機(jī)仿真，2012，（6）：88-92.

[6] 車明，秦存秀，劉凱. 基于改進(jìn)回溯算法的計(jì)算機(jī)排課系統(tǒng)[J]. 沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2006，28（6）：667-670.

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

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

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

[10] 趙群英. 回溯算法及其改進(jìn)型的分析與比較[J]. 電腦知識(shí)與技術(shù)，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

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