基于樹的糧食物流工藝流程選擇算法的實(shí)現(xiàn)

◎ 魏鵬飛，張凱鋒

（鄭州中糧科研設(shè)計(jì)院有限公司，河南 鄭州 450001）

隨著糧食物流企業(yè)倉容的逐年擴(kuò)大，糧食物流自動化控制系統(tǒng)的規(guī)模日益龐大。當(dāng)項(xiàng)目分期建設(shè)時(shí)，由于分期項(xiàng)目工藝流程設(shè)計(jì)的整體性，需要對多期項(xiàng)目整體考慮，這就極大的增加了控制系統(tǒng)工藝流程選擇的復(fù)雜程度。

1 流程選擇現(xiàn)狀

對于小型的糧食物流控制系統(tǒng)（工藝流程條數(shù)300條以下），采用流程矩陣算法[1]進(jìn)行流程的選擇，完全可以實(shí)現(xiàn)，目前已經(jīng)有多個(gè)項(xiàng)目成功的案例。但是當(dāng)控制系統(tǒng)受控設(shè)備數(shù)量的進(jìn)一步增多時(shí)，流程矩陣規(guī)模呈指數(shù)級增長，人工處理和統(tǒng)計(jì)的難度大大增加，既降低了系統(tǒng)開發(fā)的效率，同時(shí)也增大了后期系統(tǒng)擴(kuò)容和維護(hù)的成本。

對于中型的糧食物流控制系統(tǒng)（工藝流程條數(shù)300～1 000條），采用基于二叉樹的流程選擇算法[2]，通過對工藝流程中設(shè)備關(guān)系的預(yù)處理，實(shí)現(xiàn)對工藝流程的選擇，目前已在工程項(xiàng)目中成功應(yīng)用。當(dāng)然，對于小型系統(tǒng)也適用。但是對于更大規(guī)模的控制系統(tǒng)，設(shè)備關(guān)系的預(yù)處理過程就變得比較煩瑣，不利于縮短系統(tǒng)開發(fā)周期。因此，需要尋找應(yīng)用更加廣泛的流程選擇算法，用來方便地解決大規(guī)模控制系統(tǒng)的工藝流程選擇問題。

2 理論基礎(chǔ)

本文通過對糧食物流工藝流程中的設(shè)備及上下游關(guān)系進(jìn)行抽象，將樹中的結(jié)點(diǎn)與工藝流程中的設(shè)備進(jìn)行一一對應(yīng)，基于成熟的計(jì)算機(jī)樹理論和遍歷算法，實(shí)現(xiàn)了基于樹的糧食物流工藝流程選擇算法。

3 數(shù)據(jù)庫設(shè)計(jì)

為方便結(jié)點(diǎn)數(shù)據(jù)和流程信息的存儲，本文選擇MySQL作為數(shù)據(jù)庫進(jìn)行存儲和記錄。

數(shù)據(jù)庫包括2張表[3]：①結(jié)點(diǎn)表，用于存儲以設(shè)備作為結(jié)點(diǎn)的樹結(jié)構(gòu)，如表1所示。②流程表，用于存儲自動生產(chǎn)的流程信息表和相關(guān)控制信息，如表2所示。

表1 結(jié)點(diǎn)表

表2 流程表

4 算法設(shè)計(jì)與實(shí)現(xiàn)

4.1 算法分析

根據(jù)糧食物流進(jìn)出倉工藝流程圖，梳理設(shè)備及上下游關(guān)系，可以得到類似下圖1所示的樹結(jié)構(gòu)[4]，填入表1所示結(jié)點(diǎn)表，這里以包含兩個(gè)根結(jié)點(diǎn)樹結(jié)構(gòu)為例。

圖1 工藝流程樹圖

顯然，從根結(jié)點(diǎn)到任意一個(gè)葉子結(jié)點(diǎn)所經(jīng)歷的所有結(jié)點(diǎn)形成的有向路徑即構(gòu)成了一條工藝流程。

以R1為根結(jié)點(diǎn)，得到如下流程：①R1→B→H。②R1→B→E→H。③R1→C→F。④R1→C→G。⑤R1→D。

以R2為根結(jié)點(diǎn)，得到如下流程：①R2→H。②R2→E→H。

綜上，可以歸納獲得圖1的所有工藝流程的算法步驟：①獲取所有根結(jié)點(diǎn)。②以一個(gè)根結(jié)點(diǎn)為切入點(diǎn)，通過遞歸算法得到從該結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的所有路徑。③遍歷所有根結(jié)點(diǎn)，得到所有路徑，即為圖1包含的所有工藝流程路線，流程及相關(guān)控制信息保存到表2所示流程表。

4.2 算法流程圖

這里以圖1所示樹結(jié)構(gòu)為例進(jìn)行討論。R1、R2為根結(jié)點(diǎn)，B、C、E為子結(jié)點(diǎn)，D、F、G、H為葉子結(jié)點(diǎn)，算法實(shí)現(xiàn)如下。

（1）獲取樹結(jié)構(gòu)的根結(jié)點(diǎn)列表。

（2）遍歷所有根結(jié)點(diǎn)。選取第一個(gè)根結(jié)點(diǎn)，這里取R1。從R1結(jié)點(diǎn)出發(fā)，通過遞歸依次找尋該結(jié)點(diǎn)的子結(jié)點(diǎn)，孫子結(jié)點(diǎn)等，直到找到葉子結(jié)點(diǎn)，進(jìn)而獲取從R1開始的所有路徑。

（3）以R2為根結(jié)點(diǎn)，獲取從R2開始的所有路徑。

（4）R1、R2開始的所有路徑即為圖1所示樹結(jié)構(gòu)的表示的所有流程。

限于篇幅，算法的主要流程如圖2所示。

圖2 算法流程圖

4.3 算法實(shí)現(xiàn)

本文使用java語言，通過循環(huán)和遞歸算法得到了樹結(jié)構(gòu)從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的所有有向路徑，即列舉了所有工藝流程。核心的算法程序如下[5]。

4.3.1 結(jié)點(diǎn)實(shí)體類實(shí)現(xiàn)

5 小結(jié)與實(shí)踐

5.1 理論小結(jié)

通過將工藝流程中的設(shè)備及設(shè)備之間的關(guān)系抽象為如圖1類似的樹結(jié)構(gòu)，實(shí)際當(dāng)中更為復(fù)雜，可以使用樹理論的算法自動羅列出存在的工藝流程路徑。

對于生成的工藝流程路徑，結(jié)合生產(chǎn)中的實(shí)際應(yīng)用，一部分工藝路徑在實(shí)際中并沒有實(shí)際的意義。因此，需要對自動羅列出的流程路徑按照關(guān)鍵設(shè)備組合自動進(jìn)行剔除，以得到對于實(shí)際應(yīng)用更為有意義流程線路。

對于大規(guī)模的工藝流程選擇，該算法既避免了基于流程矩陣算法的矩陣規(guī)模的指數(shù)級增長，同時(shí)也不像二叉樹算法那樣，需要對工藝流程的設(shè)備關(guān)系進(jìn)行煩繁瑣的預(yù)處理。

與二叉樹工藝流程選擇算法不同的是，基于樹理論的選擇算法，使用的范圍更為廣泛，對于中小規(guī)模的糧食物流控制系統(tǒng)同樣適用。但是，由于根結(jié)點(diǎn)的不唯一性和樹結(jié)構(gòu)子結(jié)點(diǎn)的數(shù)量不確定性，導(dǎo)致在流程選擇過程中，不僅需要選擇根結(jié)點(diǎn)和葉子結(jié)點(diǎn)，還需要增加部分子結(jié)點(diǎn)，才能確定唯一的流程路徑。此外，增加結(jié)點(diǎn)的不同權(quán)重，既有利于流程路線的選擇，同時(shí)也有利于企業(yè)生產(chǎn)過程中的節(jié)能和提質(zhì)增效。

5.2 工程實(shí)踐

基于樹理論的糧食物流選擇算法已經(jīng)在多個(gè)新建或續(xù)建的糧食物流自動化控制項(xiàng)目當(dāng)中成功應(yīng)用。通過流程首尾設(shè)備和關(guān)鍵設(shè)備的選擇，即可唯一確定相對應(yīng)的流程。

特別的，對于之前已經(jīng)使用該算法的項(xiàng)目，其續(xù)建項(xiàng)目的流程擴(kuò)容將更加方便，只需通過適當(dāng)?shù)馗脑瓉斫Y(jié)點(diǎn)表，即可自動生成新的流程控制信息?；诙鄠€(gè)糧食物流項(xiàng)目應(yīng)用的成功經(jīng)驗(yàn)，目前流程選擇算法正在進(jìn)一步使用、完善和推廣當(dāng)中。