基于樹的糧食物流工藝流程選擇算法的實現

◎ 魏鵬飛，張凱鋒

（鄭州中糧科研設計院有限公司，河南 鄭州 450001）

隨著糧食物流企業倉容的逐年擴大，糧食物流自動化控制系統的規模日益龐大。當項目分期建設時，由于分期項目工藝流程設計的整體性，需要對多期項目整體考慮，這就極大的增加了控制系統工藝流程選擇的復雜程度。

1 流程選擇現狀

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

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

2 理論基礎

本文通過對糧食物流工藝流程中的設備及上下游關系進行抽象，將樹中的結點與工藝流程中的設備進行一一對應，基于成熟的計算機樹理論和遍歷算法，實現了基于樹的糧食物流工藝流程選擇算法。

3 數據庫設計

為方便結點數據和流程信息的存儲，本文選擇MySQL作為數據庫進行存儲和記錄。

數據庫包括2張表[3]：①結點表，用于存儲以設備作為結點的樹結構，如表1所示。②流程表，用于存儲自動生產的流程信息表和相關控制信息，如表2所示。

表1 結點表

表2 流程表

4 算法設計與實現

4.1 算法分析

根據糧食物流進出倉工藝流程圖，梳理設備及上下游關系，可以得到類似下圖1所示的樹結構[4]，填入表1所示結點表，這里以包含兩個根結點樹結構為例。

圖1 工藝流程樹圖

顯然，從根結點到任意一個葉子結點所經歷的所有結點形成的有向路徑即構成了一條工藝流程。

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

以R2為根結點，得到如下流程：①R2→H。②R2→E→H。

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

4.2 算法流程圖

這里以圖1所示樹結構為例進行討論。R1、R2為根結點，B、C、E為子結點，D、F、G、H為葉子結點，算法實現如下。

（1）獲取樹結構的根結點列表。

（2）遍歷所有根結點。選取第一個根結點，這里取R1。從R1結點出發，通過遞歸依次找尋該結點的子結點，孫子結點等，直到找到葉子結點，進而獲取從R1開始的所有路徑。

（3）以R2為根結點，獲取從R2開始的所有路徑。

（4）R1、R2開始的所有路徑即為圖1所示樹結構的表示的所有流程。

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

圖2 算法流程圖

4.3 算法實現

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

4.3.1 結點實體類實現

5 小結與實踐

5.1 理論小結

通過將工藝流程中的設備及設備之間的關系抽象為如圖1類似的樹結構，實際當中更為復雜，可以使用樹理論的算法自動羅列出存在的工藝流程路徑。

對于生成的工藝流程路徑，結合生產中的實際應用，一部分工藝路徑在實際中并沒有實際的意義。因此，需要對自動羅列出的流程路徑按照關鍵設備組合自動進行剔除，以得到對于實際應用更為有意義流程線路。

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

與二叉樹工藝流程選擇算法不同的是，基于樹理論的選擇算法，使用的范圍更為廣泛，對于中小規模的糧食物流控制系統同樣適用。但是，由于根結點的不唯一性和樹結構子結點的數量不確定性，導致在流程選擇過程中，不僅需要選擇根結點和葉子結點，還需要增加部分子結點，才能確定唯一的流程路徑。此外，增加結點的不同權重，既有利于流程路線的選擇，同時也有利于企業生產過程中的節能和提質增效。

5.2 工程實踐

基于樹理論的糧食物流選擇算法已經在多個新建或續建的糧食物流自動化控制項目當中成功應用。通過流程首尾設備和關鍵設備的選擇，即可唯一確定相對應的流程。

特別的，對于之前已經使用該算法的項目，其續建項目的流程擴容將更加方便，只需通過適當地更改原來結點表，即可自動生成新的流程控制信息。基于多個糧食物流項目應用的成功經驗，目前流程選擇算法正在進一步使用、完善和推廣當中。