肖浩，畢鶴鳴，李國(guó)鋒，冷志堅(jiān)，易飛

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

0 引言

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

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

1 工程概況

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

圖1 某擴(kuò)建工程梁場(chǎng)場(chǎng)地布置圖Fig.1 Layout diagram of the beam yard for a certain expansion project

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

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

2 梁場(chǎng)倉(cāng)儲(chǔ)布局圖與運(yùn)梁車路徑策略選擇

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

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

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

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

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

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

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

第二步：從L中選取1 個(gè)頂點(diǎn)u，其中l(wèi)（u）的值是最大的；同時(shí)，確保在U中存在1 個(gè)與u相鄰的頂點(diǎn)w。然后從U中選擇1 個(gè)與u相鄰的頂點(diǎn)w，并將邊uw轉(zhuǎn)變?yōu)橛邢蜻卽→w；接著，設(shè)置l（w）的值為l（u）+1，將w加入L，從U中移除w，并將u→w加入A中；

第三步：如果L≠V，則進(jìn)入第二步，否則，進(jìn)入第四步；

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

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

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

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

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

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

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

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

式（4）表示所有的工作都由運(yùn)梁車來(lái)完成。

式（5）表示一項(xiàng)任務(wù)僅可通過(guò)一個(gè)運(yùn)梁車來(lái)完成。

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

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

式中：sPosj為編號(hào)為j的任務(wù)起點(diǎn)；ePosj為編號(hào)為j的任務(wù)終點(diǎn)。

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

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

式中：（xe，ye）為目標(biāo)貨位坐標(biāo)；（xs，ys）為運(yùn)梁車停靠點(diǎn)坐標(biāo)；w為單個(gè)貨位寬度；l為單個(gè)貨位長(zhǎng)度；tu為運(yùn)梁車轉(zhuǎn)向時(shí)間。

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

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

表1 3 種算法實(shí)驗(yàn)結(jié)果對(duì)比Table 1 Comparison of experimental results for 3 algorithms

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

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

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

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

表2 優(yōu)化后運(yùn)梁車分配的專業(yè)任務(wù)及執(zhí)行順序Table 2 Optimized professional task and execution sequence assigned by beam transportation vehicle

這5 臺(tái)運(yùn)梁車的操作時(shí)間分別為420.36 s、421.92 s、427.26 s、424.63 s 和428.59 s。任務(wù)的總完成時(shí)間為428.59 s。優(yōu)化之后，第5 臺(tái)運(yùn)梁車的工作路徑如圖6 所示。而第5 臺(tái)運(yùn)梁車的作業(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 臺(tái)運(yùn)梁車出入庫(kù)專業(yè)路徑圖Fig.6 Optimized path diagram for entry and exit of the 5th beam transportation vehicle in the warehouse

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

4 結(jié)語(yǔ)

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