基于迷宮尋路算法的大規(guī)模筒倉(cāng)工藝流程 計(jì)算的解決方案

◎ 林錦暉，陳智偉，何曉濤

（廣州港集團(tuán)股份有限公司南沙糧食通用碼頭分公司，廣東 廣州 511462）

1 方案提出背景

廣東省廣州市某散貨碼頭續(xù)建二期筒倉(cāng)工程，建設(shè)完成后將擁有淺圓筒倉(cāng)與立筒倉(cāng)合計(jì)170 余個(gè)，倉(cāng)容合計(jì)約900 000 t，筒倉(cāng)規(guī)模十分龐大。整片筒倉(cāng)區(qū)域的工藝設(shè)備主要以皮帶輸送機(jī)和斗提機(jī)為主，其中皮帶輸送機(jī)合計(jì)將近100 臺(tái)次，斗提機(jī)合計(jì)20 余臺(tái)次，各種閘門(mén)、犁頭卸料裝置等附屬設(shè)備數(shù)量眾多，整套工藝系統(tǒng)包含了進(jìn)倉(cāng)、出倉(cāng)、倒倉(cāng)、裝車(chē)和直走等多種工藝類型，設(shè)備的繁雜與工藝類型的多樣性必然產(chǎn)生大量的工藝流程。不僅如此，整套工藝系統(tǒng)的交叉工藝點(diǎn)達(dá)10 余個(gè)之多，而且一些設(shè)備擁有正反轉(zhuǎn)兩種工況，由此產(chǎn)生的工藝流程數(shù)量將以成倍遞增，達(dá)到一個(gè)十分龐大的數(shù)字。在此背景下，需要研究一種算法用于解決電氣自動(dòng)控制系統(tǒng)工藝流程的選擇與生成難題。工藝流程的準(zhǔn)確與全面關(guān)系到整個(gè)電氣自動(dòng)化控制系統(tǒng)的安全性與穩(wěn)定性，為此，本文闡述了一種針對(duì)工藝流程計(jì)算的全新高效的解決方案。解決方案的實(shí)現(xiàn)方式有多種，本文主要討論運(yùn)算思路。

2 算法簡(jiǎn)介

迷宮算法的思路：利用0 和1 的矩陣構(gòu)建一個(gè)簡(jiǎn)易“迷宮”，如圖1 所示。其中1 表示迷宮里的“墻”，0 表示迷宮里的“路”，破解這一“迷宮”本質(zhì)上就是要循著0 從入口尋找路徑達(dá)到出口。此類“迷宮”一般具有的特點(diǎn)：①“尋路”過(guò)程中，相鄰點(diǎn)之間具有絕對(duì)的前后對(duì)應(yīng)關(guān)系，簡(jiǎn)言之就是具有方向性。②每個(gè)點(diǎn)向前“走”的方向可能不止一個(gè)，換言之就是同時(shí)符合需求的路徑可能不止一條。因此，要破解此類“迷宮”的所有路徑，需要注意：①使用堆?；蛘咧羔榿?lái)進(jìn)行數(shù)據(jù)存儲(chǔ)，表征方向性[1]。②走過(guò)路徑的點(diǎn)的值置1，避免走重復(fù)路徑。③通過(guò)原路返回，搜尋其他可能的路徑，直至所有路徑上的點(diǎn)都置1，最終將返回入口點(diǎn)。

圖1 迷宮示意圖

破解“迷宮”所有路徑的思路邏輯如圖2 所示。

以圖1“迷宮”為例，按照?qǐng)D2 的思維邏輯導(dǎo)圖，整個(gè)尋找路徑的完整過(guò)程如圖3 所示。由此可以尋找到兩條路徑并生成路徑記錄。

圖2 迷宮“尋路”思維邏輯圖

圖3 過(guò)程路徑示意圖

3 工藝流程計(jì)算核心算法實(shí)現(xiàn)

利用迷宮算法來(lái)尋找工藝流程的路徑，首先需要利用工藝設(shè)備搭建起工藝流程的“迷宮”。結(jié)合上文提到的“迷宮”的特點(diǎn)，可以類比出：搭建工藝流程的“迷宮”需要確定所有設(shè)備之間的前后關(guān)系。本次案例運(yùn)用了EXCEL 進(jìn)行所有工藝設(shè)備前后關(guān)系的統(tǒng)計(jì)，如圖4 所示。所有工藝設(shè)備組合產(chǎn)生的前后關(guān)系合計(jì)1 596 對(duì)。

每組前后關(guān)系實(shí)際上代表著工藝流程的走向，在尋找首、尾設(shè)備之間的工藝流程路徑的過(guò)程中，為了避免重復(fù)尋找同一條路徑，應(yīng)該對(duì)應(yīng)每組前后關(guān)系設(shè)置一個(gè)標(biāo)志位（圖中所示的“選中狀態(tài)”一列）。此標(biāo)志位在初始化階段中置0，代表所有前后關(guān)系都是可用的，所有路徑都是通路。在尋找工藝流程路徑的過(guò)程中，走過(guò)的每一組前后關(guān)系都置1，作用是避免重復(fù)走入同一條路徑，致使程序進(jìn)入死循環(huán)。

圖4 工藝設(shè)備前后關(guān)系整理圖

每走一步，判斷后設(shè)備是否與尾設(shè)備相同，相同即表示成功找到一條工藝流程，原路返回繼續(xù)尋找其他通路是否存在所需的工藝流程路徑；不同即繼續(xù)向后尋找，直到返回至前后關(guān)系的前設(shè)備等于首設(shè)備，代表所有路徑已經(jīng)找出，工藝流程的生成過(guò)程完成，輸出結(jié)果。以上可以總結(jié)歸納出如圖5 所示的思維邏輯導(dǎo)圖。

應(yīng)用EXCEL 的開(kāi)發(fā)工具，采用VBA 語(yǔ)言，圖5所展示出來(lái)的核心邏輯的程序代碼如下：

Public Sub FlowAdd(ByVal a As String, ByVal n As Integer, ByRef FlowStack() As String)

Dim sht As Worksheet, m As Integer, j As Integer, s As Integer

Set sht = Worksheets(Range(“M4”).Value)

m = Application.WorksheetFunction.CountIfs(Range(“A2:A” & _

Range(“A1048576”).End(xlUp).Row), _

a, Range(“H2:H” & Range(“A1048576”).End(xlUp).Row), 0)

If m = 0 Then ‘判斷此路徑是否走過(guò)，判斷此路是否通

If n = 1 Then ‘回到原點(diǎn)說(shuō)明歷遍過(guò)程已完成‘MsgBox “流程設(shè)備已生成完畢！”

Else

a = FlowStack(n - 1)

n = n - 1

Call FlowAdd(a, n, FlowStack())

End If

Else

FlowStack(n) = Range(“A” & j) ‘設(shè)備編號(hào)依次放入數(shù)據(jù)存儲(chǔ)

Range(“H” & j).Value = 1 ‘走過(guò)的路徑賦值1

圖5 工藝流程“尋路”思維邏輯圖

n = n + 1 If Range(“B” & j) = Range(“M3”) Then

‘找到路徑

FlowStack(n) = Range(“B” & j)

s = sht.Range(“A1048576”).

End(xlUp).Row

目前，東營(yíng)市不少農(nóng)民合作社都是白手起家，社員數(shù)量少，生產(chǎn)規(guī)模小，經(jīng)濟(jì)實(shí)力較弱，在資金融通、技術(shù)引進(jìn)、設(shè)施改造、市場(chǎng)開(kāi)拓上面臨很大困難，導(dǎo)致帶動(dòng)輻射能力弱。

For t = 1 To n

sht.Cells(s + 1, t + 5) = FlowStack(t)

sht.Cells(s + 1, 1) = s

sht.Cells(s + 1, 2) = FlowStack(1)

sht.Cells(s + 1, 5) = FlowStack(n) ‘找到路徑并填充

Next

a = FlowStack(n - 1) ‘繼續(xù)尋找其他路徑

n = n - 1

Call FlowAdd(a, n, FlowStack())

Exit Sub

Else

a = Range(“B” & j)

Call FlowAdd(a, n, FlowStack()) ‘路徑未走完，繼續(xù)向前走

Exit Sub

End If

End If

Next

End If

End Sub

以上核心算法搭配遞歸運(yùn)算與循環(huán)運(yùn)算，即可同時(shí)生成多個(gè)首設(shè)備與多個(gè)尾設(shè)備之間的工藝流程，最大限度的提高運(yùn)算效率。核心循環(huán)運(yùn)算已包含在以上的核心算法里。遞歸運(yùn)算程序以及一些基本的錯(cuò)誤判斷，如下所示：

Public Sub FlowCreate()

Application.EnableEvents = False ‘關(guān)閉事件響應(yīng)

Dim i As Integer, a As String, j As Integer, FlowStack() As String, sht1 As Worksheet

a = UCase(Range(“M2”).Value)

ReDim FlowStack(1 To 100)

Set sht1 = Worksheets(Range(“M4”).Value)

For i = 2 To Range(“A1048576”).End(xlUp).Row

Range(“H” & i) = 0 ‘全部路徑賦值0，初始化

Next

If Application.Work sheet Function.CountIf(Range(“A2:A” & Range(“A1048576”).End(xlUp).Row), _

Range(“M2”)) = 0 Or Application.WorksheetFunction.CountIf(Range(“B2:B” & _

Range(“A1048576”).End(xlUp).Row), Range(“M3”)) = 0 Then ‘判斷首尾設(shè)備是否合法

MsgBox “設(shè)備編號(hào)填寫(xiě)錯(cuò)誤，請(qǐng)重新填寫(xiě)！”

Exit Sub

Else

Call FlowAdd(a, 1, FlowStack()) ‘判斷此設(shè)備組合合法后傳遞參數(shù)，進(jìn)入遞歸函數(shù)

End If

Application.EnableEvents = True ‘打開(kāi)事件響應(yīng)End Sub

最終的使用情況如圖6 所示，在首設(shè)備列表與尾設(shè)備列表里分別設(shè)置需要尋找工藝流程路徑的首尾設(shè)備，即可進(jìn)行工藝流程生成運(yùn)算。

圖6 設(shè)置首尾設(shè)備圖

以上首尾設(shè)備列表對(duì)應(yīng)生成的運(yùn)算結(jié)果如圖7 所示。通過(guò)人工校對(duì)驗(yàn)證，工藝流程生成的結(jié)果十分準(zhǔn)確。

圖7 運(yùn)算結(jié)果示例圖

4 應(yīng)用效果

在本文的案例中，二期筒倉(cāng)續(xù)建工程完成后，項(xiàng)目的電氣自動(dòng)控制系統(tǒng)涉及皮帶輸送機(jī)合計(jì)將近100臺(tái)次，斗提機(jī)合計(jì)20 余臺(tái)次，各種閘門(mén)、犁頭卸料裝置等附屬設(shè)備數(shù)量眾多。運(yùn)用該套解決方案來(lái)進(jìn)行工藝流程的運(yùn)算與統(tǒng)計(jì)，配合人工統(tǒng)計(jì)以輔助，成功統(tǒng)計(jì)出650 000 余條工藝流程。相對(duì)于續(xù)建前合計(jì) 60 000 余條工藝流程，續(xù)建后的工藝流程數(shù)量增長(zhǎng)了10 倍，該項(xiàng)成果為整套系統(tǒng)的電氣自動(dòng)化控制打下了穩(wěn)定的數(shù)據(jù)基礎(chǔ)。此外，利用該套解決方案針對(duì)續(xù)建前的工藝設(shè)備進(jìn)行一次工藝流程統(tǒng)計(jì)運(yùn)算，將得出的結(jié)果與原工藝流程數(shù)據(jù)庫(kù)進(jìn)行對(duì)比，工藝流程的數(shù)量與結(jié)果完全一致，進(jìn)一步驗(yàn)證了該套算法的準(zhǔn)確性。

5 局限性與程序優(yōu)化

該算法運(yùn)用了遞歸運(yùn)算與循環(huán)運(yùn)算來(lái)進(jìn)行多組設(shè)備路徑計(jì)算與完全路徑計(jì)算。在進(jìn)行大量的工藝流程計(jì)算時(shí)，可能出現(xiàn)內(nèi)存溢出的情況導(dǎo)致程序崩潰。為了避免這一情況的出現(xiàn)，需要人工分組規(guī)劃好設(shè)備組，分批次進(jìn)行運(yùn)算。例如，每次只計(jì)算單獨(dú)一排筒倉(cāng)的出倉(cāng)工藝流程，分?jǐn)?shù)次完成整片立筒倉(cāng)區(qū)域的出倉(cāng)工藝流程計(jì)算。

程序的進(jìn)一步優(yōu)化，應(yīng)該考慮根據(jù)不同路徑所產(chǎn)生的效率與能耗差別，針對(duì)每組前后設(shè)備關(guān)系設(shè)置權(quán)重系數(shù)，在工藝流程計(jì)算時(shí)，優(yōu)先尋找權(quán)重系數(shù)高的工藝流程路徑，并在生成的結(jié)果中進(jìn)行排序，有利于提高工藝效率與降低作業(yè)能耗。