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

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

0 引言

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

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

1 工程概況

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

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

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

梁場施工裝備集群控制系統(tǒng)根據(jù)人工智能規(guī)劃算法實現(xiàn)設(shè)備的智能調(diào)度[7-8]、倉位的合理分配、危險區(qū)域的自動避讓及路徑優(yōu)化等功能，自主完成移梁、存梁、取梁、倒運等工作，達到自主決策、自動執(zhí)行、實時跟蹤為一體的信息流與實物流高度一致的梁場施工裝備集群控制系統(tǒng)[9]。

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

梁場的倉儲系統(tǒng)主要包括存梁區(qū)、運梁車和控制系統(tǒng)。存梁區(qū)是用來儲存節(jié)段梁的，每條梁道上都有若干個空間，表示若干個儲存的梁位，一條存梁巷中只可儲存一種類型的節(jié)段梁；運梁車是用來實現(xiàn)節(jié)段梁體的水平運轉(zhuǎn)；控制與管理系統(tǒng)主要是對倉庫中的設(shè)備進行監(jiān)視與調(diào)度。

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

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

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

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

圖3 存梁區(qū)交通網(wǎng)絡(luò)路徑定向圖（圖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(wèi)（u）的值是最大的；同時，確保在U中存在1 個與u相鄰的頂點w。然后從U中選擇1 個與u相鄰的頂點w，并將邊uw轉(zhuǎn)變?yōu)橛邢蜻卽→w；接著，設(shè)置l（w）的值為l（u）+1，將w加入L，從U中移除w，并將u→w加入A中；

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

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

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

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

3 運梁車調(diào)度算法研究及應(yīng)用

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

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

將該算法應(yīng)用到運梁車調(diào)度上，首先需對運梁車調(diào)度問題進行建模，倉儲系統(tǒng)中運梁車的作業(yè)調(diào)度問題可以數(shù)學(xué)化描述為：由m臺運梁車來完成n個存梁出入庫任務(wù)的分派，全部任務(wù)集A={A1，A2，…，Am}，運梁車集S= {s1，s2，…，sm}，第i臺運梁車的任務(wù)集Ai= {a1i，a2i，…，aki}?；诩s束條件，合理地規(guī)劃運梁車的任務(wù)分派和執(zhí)行順序。以下是約束條件的構(gòu)建：

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

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

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

在上述約束模型的基礎(chǔ)上，建立了以下目標(biāo)函數(shù)：為了確定多臺運梁車完成出入庫任務(wù)的最短

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

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

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

圖4 入庫作業(yè)示意圖Fig.4 Warehouse entry operation diagram

式中：（xe，ye）為目標(biāo)貨位坐標(biāo)；（xs，ys）為運梁車?？奎c坐標(biāo)；w為單個貨位寬度；l為單個貨位長度；tu為運梁車轉(zhuǎn)向時間。

同理可得運梁車的出庫作業(yè)建模。

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

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

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

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

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

當(dāng)處理任務(wù)規(guī)模達到40 時，通過IH-GA 算法的優(yōu)化，實驗得到了5 臺運梁車的任務(wù)執(zhí)行順序，見表2。

表2 優(yōu)化后運梁車分配的專業(yè)任務(wù)及執(zhí)行順序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。任務(wù)的總完成時間為428.59 s。優(yōu)化之后，第5 臺運梁車的工作路徑如圖6 所示。而第5 臺運梁車的作業(yè)路線是：（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 優(yōu)化后第5 臺運梁車出入庫專業(yè)路徑圖Fig.6 Optimized path diagram for entry and exit of the 5th beam transportation vehicle in the warehouse

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

4 結(jié)語

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