梁場倉儲裝備智能集群控制系統中運梁車調度研究

肖浩，畢鶴鳴，李國鋒，冷志堅，易飛

（1.中交第二航務工程局有限公司，湖北 武漢 430040；2.中國交通建設集團有限公司，北京 100088；3.長大橋梁建設施工技術交通行業重點實驗室，湖北 武漢 430040；4.交通運輸行業交通基礎設施智能制造技術研發中心，湖北 武漢 430040）

0 引言

梁場倉儲裝備智能集群控制系統在橋梁建設領域扮演著至關重要的角色。運梁車作為其中的核心裝備之一，其調度對于提高施工效率和減少成本具有重要意義。傳統的運梁車調度通常依靠人工經驗和簡單的規則，效率較低且容易出現問題，而隨著工程規模的擴大和施工難度的增加，傳統的調度方法已經無法滿足實際需求。

本文將針對梁場倉儲裝備智能集群控制系統中的運梁車調度問題進行深入研究[1-3]。將基于現有的智能調度算法和技術，結合梁場倉儲裝備的特點和需求[4-6]，提出一種高效、智能的運梁車調度方法。通過優化調度方案，本文旨在實現運梁車的最大利用率，減少空閑時間和資源浪費，從而提高施工效率和降低成本。

1 工程概況

梁場倉儲裝備智能集群控制系統運梁車調度研究依托于某高速改擴建工程。該工程梁場場地布置圖如圖1 所示。

圖1 某擴建工程梁場場地布置圖Fig.1 Layout diagram of the beam yard for a certain expansion project

如圖1 所示，該預制梁場包含入庫口、出庫口、上存梁區、下存梁區、節段梁預制區及運梁車通道組成。

梁場施工裝備集群控制系統根據人工智能規劃算法實現設備的智能調度[7-8]、倉位的合理分配、危險區域的自動避讓及路徑優化等功能，自主完成移梁、存梁、取梁、倒運等工作，達到自主決策、自動執行、實時跟蹤為一體的信息流與實物流高度一致的梁場施工裝備集群控制系統[9]。

2 梁場倉儲布局圖與運梁車路徑策略選擇

梁場的倉儲系統主要包括存梁區、運梁車和控制系統。存梁區是用來儲存節段梁的，每條梁道上都有若干個空間，表示若干個儲存的梁位，一條存梁巷中只可儲存一種類型的節段梁；運梁車是用來實現節段梁體的水平運轉；控制與管理系統主要是對倉庫中的設備進行監視與調度。

圖2 是一種運梁車倉儲系統的布置圖。位于中央主要道路之上的被稱作上存梁區，而位于中央主要道路之下的被稱作下存梁區。在此存儲系統中，進出料提升裝備設置在進出入口。運梁車可在存梁巷道橫、縱2 個方向移動。在無貨物的情況下，運梁車能在存梁巷道內自由地移動，并能抵達倉庫系統內任何一個存梁位置。

圖2 運梁車倉儲系統的布置圖Fig.2 Layout diagram of the beam transportation vehicle warehousing system

在運梁車倉儲系統中，由于多輛運梁車輛同時工作，會在主要道路的交叉路口和通道中發生碰撞和卡死，從而造成存梁區的擁堵，影響出入庫作業的順利進行。因此，在求解該問題時，如何有效地避免運輸車輛間的碰撞和卡死，是求解該問題的一個重要方面。

首先，建立存梁區交通網絡模型，如圖3 所示。先將其表示為圖G={V（G），E（G）}，圖G里所有點的集合為V（G），所有邊的集合為E（G）。其中主要道路、車道等被等價于圖G中的邊，十字路口被等價于點。利用Hopcroft-Tarjan 算法，對無割邊的連通圖G進行了計算，得出了圖G的強連通方向圖，其步驟如下：

圖3 存梁區交通網絡路徑定向圖（圖G）Fig.3 Directed graph of traffic network paths in beam warehousing district(Fig.G)

第一步：在圖G中任取某頂點v，使得l（v）=1，L={v}，U=V-{v}且R=?；

第二步：從L中選取1 個頂點u，其中l（u）的值是最大的；同時，確保在U中存在1 個與u相鄰的頂點w。然后從U中選擇1 個與u相鄰的頂點w，并將邊uw轉變為有向邊u→w；接著，設置l（w）的值為l（u）+1，將w加入L，從U中移除w，并將u→w加入A中；

第三步：如果L≠V，則進入第二步，否則，進入第四步；

第四步：對于目前尚未定向的邊ab，根據下面的方式進行定向：如果l（a）＞l（b），那么指定方向后的邊為a→b，反之，邊為b→a。

其中，U是尚未給出標號的頂點集，L是已給出標號的頂點集，R是方向已確定的邊的集。

根據上述求解步驟，在圖G中出現多個強連通定向圖，需在此基礎上，結合梁場布局和出入庫原則，確定最終路徑定向路徑選擇方法。

3 運梁車調度算法研究及應用

在梁場的倉儲設備調度中，本文結合了模擬退火算法在局部搜索中的優勢，提出了一種新的混合遺傳算法（IH-GA）。這種算法既繼承了遺傳算法在全局搜索中的高效性，又融合了模擬退火算法在局部尋優中的強大能力。

IH-GA 的操作機制如下：首先，通過GA 對初代種群執行遺傳處理，以實現種群的進化。接著，利用模擬點火算法中的Metropolis 采樣方式，對由遺傳算法進化得來的結果進行評估和抽樣。這些抽樣的結果將再次作為遺傳算法的起始種群，為下一輪的進化做準備。

將該算法應用到運梁車調度上，首先需對運梁車調度問題進行建模，倉儲系統中運梁車的作業調度問題可以數學化描述為：由m臺運梁車來完成n個存梁出入庫任務的分派，全部任務集A={A1，A2，…，Am}，運梁車集S= {s1，s2，…，sm}，第i臺運梁車的任務集Ai= {a1i，a2i，…，aki}。基于約束條件，合理地規劃運梁車的任務分派和執行順序。以下是約束條件的構建：

式中：ki為第i臺運梁車分配的任務總數量，式（1）表示每輛運梁車至少指派一個任務。

式（4）表示所有的工作都由運梁車來完成。

式（5）表示一項任務僅可通過一個運梁車來完成。

在上述約束模型的基礎上，建立了以下目標函數：為了確定多臺運梁車完成出入庫任務的最短

時間，也就是實現所有運梁任務的時間最小化，考慮編號為i的運梁車完成ki個任務的操作時長Ti如下：

式中：sPosj為編號為j的任務起點；ePosj為編號為j的任務終點。

運梁車的工作時間取決于具體的工作任務，并與車輛的起點和梁的位置相關，基于以上的路徑定位策略，對運輸路線進行規劃，并對運輸時間進行計算。在進庫工作中，運梁小車從起點出發，行駛到進庫入口，再按照存梁區的路徑導向策略，規劃出一條路線，從進庫入口一直行駛到目標梁位。入庫任務作業示意圖如圖4 所示，其空載階段運行時間為：

圖4 入庫作業示意圖Fig.4 Warehouse entry operation diagram

式中：（xe，ye）為目標貨位坐標；（xs，ys）為運梁車停靠點坐標；w為單個貨位寬度；l為單個貨位長度；tu為運梁車轉向時間。

同理可得運梁車的出庫作業建模。

將IH-GA 算法帶入到該模型，并且使用GA算法和SA 算法作為對照組，其得到的在40、80、120 任務下的平均完成時間、平均偏差與優化效率如表1 所示。

表1 3 種算法實驗結果對比Table 1 Comparison of experimental results for 3 algorithms

與GA 算法和SA 算法相比，IH-GA 算法具有更高的計算效率、計算精度、穩定性和更快的計算速度。隨著任務規模的增加，出入庫任務分配及運梁車執行序列變得更加復雜，與GA、SA等算法相比，IH-GA 在計算精度、穩定性等方面的優勢得到了放大，其優化表現更為出色，進出庫任務的分配和運梁車的執行次序變得更加有序，任務的總完成時長縮短了，從而提高了工作效率，因此，IH-GA 算法更適合于解決大規模的調度優化問題。

圖5 展示了GA、SA 和IH-GA 三種算法在不同任務規模時的收斂情況。在開始階段，GA 算法展現出了優秀的全局搜索性能，具有很好的收斂性，但是由于其局部尋優能力較差，使得其解的精度較低；SA 算法具有很好的尋優性能，但存在著尋優時間長、收斂緩慢等缺點；IH-GA 算法融合GA、SA 的優勢，在GA 的基礎上，充分發揮GA 的全局尋優能力，使其在初始階段就能達到較快的收斂性，并且將SA 的局部尋優能力相結合，使其在初始階段就能達到較快的收斂性與較好的收斂性。與其它2 種方法相比，該方法不僅具有較高的計算精度，而且具有較快的收斂性，因此該方法更適用于該模型的優化問題。

圖5 3 種算法在不同任務規模下的算法收斂圖Fig.5 Algorithm convergence graphs for 3 algorithms at different task scales

當處理任務規模達到40 時，通過IH-GA 算法的優化，實驗得到了5 臺運梁車的任務執行順序，見表2。

表2 優化后運梁車分配的專業任務及執行順序Table 2 Optimized professional task and execution sequence assigned by beam transportation vehicle

這5 臺運梁車的操作時間分別為420.36 s、421.92 s、427.26 s、424.63 s 和428.59 s。任務的總完成時間為428.59 s。優化之后，第5 臺運梁車的工作路徑如圖6 所示。而第5 臺運梁車的作業路線是：（1，1）→（22，44）→（0，0）→（11，6）→（31，11）→（0，60）→（0，0）→（41，33）→（0，0）→（70，15）→（0，0）→（43，21）→（65，24）→（1，60）→（56，38）→（0，60）。

圖6 優化后第5 臺運梁車出入庫專業路徑圖Fig.6 Optimized path diagram for entry and exit of the 5th beam transportation vehicle in the warehouse

從上述分析中可以看出，通過優化混合遺傳算法的編碼方法和變異修復策略，成功地解決了在迭代中容易產生的非法解問題，擴大了解的多樣性，并增強了算法的快速收斂特性和全局搜尋效率。

4 結語

本論文主要對運梁車存儲系統的調度優化進行了研究。基于Hopcroft-Tarjan 算法，研究存梁區的路徑定向策略，構建基于最短運梁時間的調度優化模型，研究基于Hopcroft-Tarjan 的多目標優化問題。實驗結果表明，該方法能有效地解決車輛的碰撞和卡死問題，提高了系統的運行效率。為了比較計算法的性能，將IH-GA 算法與GA 算法、SA 算法的計算結果進行了對比。通過算例分析，證明了IH-GA 的尋優性能好，收斂速度快，可大幅提高系統工作效率。