馬昌譜， 周炳海

(1. 同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院， 上海 201804； 2. 桂林航天工業(yè)學(xué)院 管理學(xué)院， 廣西 桂林 541004)

軌道小車(RGV)被廣泛應(yīng)用于自動(dòng)化存取系統(tǒng)(AS/RS)[1].作為AS/RS的主要存取部件，一次能夠搬運(yùn)多個(gè)物品的RGV，即多載量RGV能提高系統(tǒng)的作業(yè)能力，其作業(yè)效率直接影響系統(tǒng)的吞吐率，因此，RGV的合理調(diào)度對系統(tǒng)性能有著非常重要的影響.在多車AS/RS中，RGV的調(diào)度不僅要考慮多貨物同時(shí)載運(yùn)的裝卸順序約束，還須考慮多車之間的碰撞問題，這是RGV調(diào)度的難點(diǎn).

目前，關(guān)于RGV的研究主要聚焦于其設(shè)計(jì)、控制、派遣規(guī)則及路徑選擇等方面.Zheng等[2]設(shè)計(jì)了環(huán)形共軌RGV，并將其應(yīng)用于分載系統(tǒng).Lee等[3]構(gòu)建了AS/RS仿真模型，確定了RGV的最優(yōu)數(shù)量和導(dǎo)出系統(tǒng)吞吐率最大化策略.Lee和Chen等[4-5]研究了RGV的調(diào)度和系統(tǒng)控制問題，設(shè)定RGV的分派規(guī)則，并用仿真實(shí)驗(yàn)對其規(guī)則做了評價(jià).Dotoli 等[6]應(yīng)用著色Petri網(wǎng)，分析貨物搬運(yùn)系統(tǒng)并建立模型，提出控制策略，解除環(huán)軌RGV的死鎖問題.Liu等[7]使用仿真實(shí)驗(yàn)，提出雙RGV系統(tǒng)的兩種作業(yè)策略，并分析了兩者的優(yōu)劣.RGV的調(diào)度方面，Kung等[8]將訂單分為不同的集群，按照規(guī)則將訂單集群序列分配給同軌運(yùn)行的RGV.Gao等[9]構(gòu)建了在線調(diào)度算法，用于調(diào)度同軌RGV，以實(shí)例證明其可行性.

縱觀上述文獻(xiàn)，系統(tǒng)中的RGV無論是一輛還是多輛，每次只能搬運(yùn)單個(gè)物品，屬于單載量RGV.針對多載量RGV的調(diào)度問題，目前僅有Hu等[10]對其作了研究，并考慮了貨物裝卸順序約束，應(yīng)用滾動(dòng)時(shí)域法對RGV作了最優(yōu)路徑規(guī)劃.

但是，目前尚未發(fā)現(xiàn)其他關(guān)于同時(shí)考慮貨物裝卸順序約束和同軌雙車避碰調(diào)度問題的研究.為此，本文將創(chuàng)新引入 I 類和 II 類沖突的概念，研究多載量RGV貨物裝卸順序與同軌雙車路徑規(guī)劃相結(jié)合的問題，以貨物搬運(yùn)總時(shí)間最小為優(yōu)化目標(biāo)，建立解除雙沖突的決策模型.針對小規(guī)模問題，應(yīng)用CPLEX求其最優(yōu)解，并構(gòu)造改進(jìn)型和聲搜索算法獲取中大規(guī)模的全局滿意解.

1 問題描述

如圖1所示，AS/RS由兩輛RGV(V1,V2)共享同一直線軌道，RGV和貨架都安裝了滾輪滑道，方便貨物的自動(dòng)存取.系統(tǒng)由RGV按生產(chǎn)計(jì)劃載運(yùn)貨物至對應(yīng)貨架，以滿足生產(chǎn)需求.調(diào)度開始前，V1和V2分別位于系統(tǒng)的最左端和最右端，調(diào)度開始時(shí)，兩輛RGV分別從各自的端點(diǎn)啟程，完成所分配的任務(wù)后，返回至各自的出發(fā)點(diǎn).在此，重點(diǎn)需要解決兩個(gè)問題：① RGV裝卸貨物的先后順序問題，即解決多件貨物在RGV內(nèi)部的死鎖問題，此死鎖是指已經(jīng)裝載在RGV上的貨物，相互阻擋了對方的卸載通道，以致貨物被迫處于停滯等待狀態(tài)；② RGV之間的碰撞問題，即確定避碰情況下的最佳取送路徑.

圖1 以RGV為存取部件的AS/RSFig.1 Configuration of AS/RS with RGV as storage and retrieval component

為有效描述該存取系統(tǒng)，進(jìn)行如下基本假設(shè)：① RGV可同時(shí)搬運(yùn)多個(gè)貨物，且車上貨物只能順序裝卸；② RGV裝載和卸載單位貨物的時(shí)間相等且為常數(shù)；③ RGV不能相互跨越，也不能發(fā)生碰撞；④ RGV速度恒定，且兩輛RGV型號(hào)相同；⑤ 同一軌道位置對應(yīng)的兩對稱貨架同時(shí)只能被一輛RGV訪問；⑥ 每個(gè)貨物的源點(diǎn)和終點(diǎn)已知；⑦ RGV一旦裝載了某件貨物，到達(dá)終點(diǎn)之前，一件貨物只能由此輛RGV完成整個(gè)搬運(yùn)過程.

定理1?t∈T，當(dāng)Vk同時(shí)取送貨物組合j∈E3和l∈E4或j∈E4和l∈E3時(shí)，發(fā)生 I 類沖突.

證明對j∈E3，Vk將rj裝載后在車內(nèi)的移動(dòng)方向是1→2，若再裝載rl，l∈E4，其移動(dòng)方向?yàn)?→1，若將rj,rl形成組合搬運(yùn)，根據(jù)定義1，rj和rl彼此阻礙了對方的目的去向，形成死鎖， I 類沖突發(fā)生.

原理與i∈E1,j∈E1/{i}類似，證明略.

2 數(shù)學(xué)模型

建立數(shù)學(xué)模型如下：

minM=

(1)

s.t.

(2)

?j∈E1/{l},l∈E1,k∈K

?j∈E2/{l},l∈E2,k∈K

(3)

?j∈E3/{l},l∈E3,k∈K

?j∈E4/{l},l∈E4,k∈K

(4)

?(i,j)∈A′

?j∈E3/{l},l∈E3,k∈K

?j∈E4/{l},l∈E4,k∈K

(5)

?(i,j+n)∈A′

?j∈E4,l∈E1,k∈K

?j∈E3,l∈E2,k∈K

(6)

?(i,j)∈A′

?j∈E4,l∈E3,k∈K

?j∈E3,l∈E4,k∈K

(7)

(8)

(9)

(10)

z0k0=1，k=1

(11)

z|W|+1k0=1，k=2

(12)

(13)

?i,j∈A,pi

(14)

(15)

(16)

(17)

(18)

(19)

zλkt∈{0,1}

(20)

λ∈{0}∪W∪{2n+1}，k∈K

式(1)為Vk在消除兩類沖突中最后完成所有任務(wù)的最少時(shí)間；式(2)～(5)為消除 I 類沖突約束，其中，式(2)為后進(jìn)先出(LIFO)策略，式(3)為先進(jìn)先出(FIFO)策略，式(4)為交叉任務(wù)先入(CFI)策略，式(5)為交叉任務(wù)后出(CLO)策略式；式(6)為 I 類沖突消除；式(7)和(8)表示每個(gè)任務(wù)只能被服務(wù)一次；式(9)～(13)為消除 II 類沖突約束，式(9)～(10)為同一時(shí)刻一個(gè)位置只能被一輛RGV訪問，式(11)～(12)為初始時(shí)刻兩輛RGV的位置，式(13)表示避免兩輛RGV碰撞；式(14)表示每個(gè)取貨任務(wù)必須在對應(yīng)送貨任務(wù)之前完成；式(15)表明同一貨架有多項(xiàng)任務(wù)需要裝載，則按照FIFO原則裝載，“i⊕1”表示緊接著任務(wù)ri的后一個(gè)任務(wù)；式(16)為Vk的容量約束式；式(17)表示局部取送任務(wù)和全局取送任務(wù)關(guān)系；式(18)～(20)為決策變量的取值范圍.

3 改進(jìn)型和聲搜索算法

和聲搜索算法(HS)最早由Geem等[11]受音樂即興創(chuàng)作過程的啟發(fā)而提出，具有原理簡單、控制參數(shù)少、收斂速度快等優(yōu)點(diǎn).然而，該算法仍存在一些缺陷，如搜索后期收斂緩慢、局部搜索能力欠缺、易陷入局部最優(yōu)，故本文提出改進(jìn)型和聲搜索算法(MHS)求解中大規(guī)模問題，以獲取較高質(zhì)量的解.基本步驟如下.

步驟1問題參數(shù)初始化.包括和聲記憶庫大小HMS、最大迭代次數(shù)NI、和聲記憶庫取值概率HMCR、音調(diào)微調(diào)概率PAR、微調(diào)幅度BW以及精度ε.

步驟2和聲記憶庫初始化.結(jié)合式(2)～(6)，隨機(jī)生成HMS個(gè)和聲向量，存入HM.

步驟3劃分和聲片段.將每個(gè)和聲向量按照 I 類約束關(guān)系，分解為若干和聲片段.

步驟4新和聲即興創(chuàng)作.對于每個(gè)和聲片段，基于HMCR、PAR進(jìn)行即興創(chuàng)作，形成新的和聲.

步驟5更新和聲記憶庫.將新形成的和聲和當(dāng)前最差和聲進(jìn)行對比，若優(yōu)于當(dāng)前最差和聲，則替代當(dāng)前和聲.

步驟6判斷終止準(zhǔn)則.若當(dāng)前迭代次數(shù)N大于最大迭代次數(shù)NI，則合并所有和聲片段形成新的和聲記憶庫，否則重復(fù)步驟 4和5.

步驟7變鄰域搜索操作.隨機(jī)選取一個(gè)和聲向量進(jìn)行變鄰域搜索操作，并更新HM.

步驟8判斷終止準(zhǔn)則：若任兩個(gè)和聲對應(yīng)目標(biāo)值之差均小于ε，則算法終止，否則重復(fù)執(zhí)行步驟3～7.

3.1 和聲編碼方案

用Si(i=1,2,…,HMS)表示和聲向量元素，采用3層變長編碼方式：第1層表示圖G頂點(diǎn)層，代表RGV訪問的線路節(jié)點(diǎn)；第2層為位置層，代表頂點(diǎn)對應(yīng)的源點(diǎn)位置p或終點(diǎn)位置d；第3層為執(zhí)行任務(wù)的RGV編號(hào)層.以圖1為例，若將r1,r2指派給V1，將r3,r4指派給V2，則其中一個(gè)可行解可表示為圖2.其中頂點(diǎn)層的數(shù)字9為2×4+1，位置層中間的“11”表示初始時(shí)刻，V2的位置為 |W|+1.

圖2 和聲編碼圖解Fig.2 Encoding mode for harmony

給定任務(wù)n，根據(jù)有向圖G的定義以及兩輛RGV的起訖點(diǎn)位置，可得和聲的最大長度Lmax=2n+4.當(dāng)n=1時(shí)，可知Lmin=5，即一輛RGV的初始點(diǎn)和執(zhí)行一個(gè)完整任務(wù)的源點(diǎn)和終點(diǎn).因此和聲Si的長度范圍為[Lmin,Lmax].

編碼方案對應(yīng)的解如圖3所示，橫線部分表示RGV進(jìn)行裝或卸操作.初始時(shí)刻，V1從0位置出發(fā)，完成搬運(yùn)任務(wù)后返回至原位置；V2從 |W|+ 1出發(fā)，完成分配的任務(wù)后返回至出發(fā)點(diǎn).V1對應(yīng)的路徑為0→2→4→1→3→0，執(zhí)行的任務(wù)順序?yàn)棰凇?；RGV2對應(yīng)的路徑為11→9→4→5→9→11，執(zhí)行的任務(wù)順序?yàn)棰堋?

圖3 編碼方案對應(yīng)的解Fig.3 Corresponding solution of coding mode

3.2 和聲記憶庫初始化

為生產(chǎn)初始可行解，本文采用貪婪隨機(jī)自適應(yīng)搜索算法(GRASP)初始化和聲記憶庫.具體步驟如下.

步驟1隨機(jī)生成任務(wù)矩陣Rn=[r1r2…rn]T,rn=(αn,Pn,βn,Dn),αn=rand(1,2),Pn=rand(1,|W|),βn=rand(1,2),Dn=rand(1,|W|).

如文中提到的山南基金小鎮(zhèn)、余杭?jí)粝胄℃?zhèn)等對特色小鎮(zhèn)產(chǎn)業(yè)發(fā)展規(guī)劃進(jìn)行科學(xué)論證，按照主導(dǎo)產(chǎn)業(yè)特色鮮明、相關(guān)產(chǎn)業(yè)按需配套的原則，合理確定特色小鎮(zhèn)產(chǎn)業(yè)功能布局。一些個(gè)別特色小鎮(zhèn)用地規(guī)模過大，產(chǎn)業(yè)定位不夠清晰等問題，將不符合土地利用總體規(guī)劃的建設(shè)用地劃出規(guī)劃區(qū)范圍，在此基礎(chǔ)上提出明確的用地需求菜單，落實(shí)到城市控規(guī)和土地利用總體規(guī)劃上，科學(xué)劃分相關(guān)功能區(qū)塊，確定用地類型為特色小鎮(zhèn)建設(shè)提供科學(xué)指引[6]。

(4) 根據(jù)定理1及式(2)～(6)判定終點(diǎn)，若終點(diǎn)為di-1，則將di-1設(shè)置為新源點(diǎn)，di為新終點(diǎn)，返回(1).若終點(diǎn)為di，則設(shè)di為新源點(diǎn)，di-1為新終點(diǎn)，轉(zhuǎn)至(1).

步驟6將h1和h2轉(zhuǎn)化成在[Lmin,Lmax]上的編碼，一并存入HM，實(shí)現(xiàn)和聲記憶庫的初始化.

3.3 即興創(chuàng)作產(chǎn)生新和聲

針對每個(gè)Sub_HM，新和聲Snew以HMCR概率繼承現(xiàn)有Sub_HM中和聲，并以PAR概率進(jìn)行微調(diào).同時(shí)，對Snew進(jìn)行鄰域搜索，新和聲Snew以(1-HMCR)的概率應(yīng)用GRASP算法進(jìn)行創(chuàng)作.具體流程如下.

r1,r2,r3=rand( )

forj=2 to 2n+2 do

ifr1

Snew←Sαwhereα∈(1,2,…,HMS)

ifr2

Snew←Snew±r3BW

end if

else

Snew←Sub_HM+GRASP

iff(Snew)

Sworst←Snew∥*更新HM

end if

end for

3.4 變鄰域搜索操作

圖4 任務(wù)對和組合任務(wù)的重置操作Fig.4 Re-located operations of couple and component

(3) 任務(wù)對交換.隨機(jī)選取兩個(gè)任務(wù)對，交換對應(yīng)的位置，如圖5(b)所示，交換了初始解(圖5(a))中r1和r3的位置.

(4) 組合任務(wù)交換.隨機(jī)選取兩個(gè)組合任務(wù)，并交換對應(yīng)的位置，如圖5(c)所示，交換了初始解(如圖5(a))中Cx和Cy的位置.

(5) 變異操作.設(shè)原變量Sold經(jīng)移動(dòng)操作后得到Smv，若f(Smv)

圖5 任務(wù)對和組合任務(wù)的交換操作Fig.5 Swap operations of couple and component

圖6 和聲向量變異操作Fig.6 Mutation operation of harmony vecor

重置任務(wù)對(ope1)、重置組合任務(wù)(ope2)、交換任務(wù)對(ope3)和交換組合任務(wù)(ope4)4個(gè)操作的執(zhí)行控制為

(21)

式中：q為[0,1]之間的隨機(jī)數(shù).

經(jīng)以上操作得到的新向量有可能不可行，為保證解的多樣性，允許一定數(shù)量不可行解的存在.為此，本文引入罰函數(shù)法，通過懲罰函數(shù)，所有的不可行解向量都傾向于朝著可行解的方向搜索，從而完成不可行解向可行解的轉(zhuǎn)化.

令 I 類約束式(2)～(6)分別用g1,g2,…,g5表示，II 類約束式(13)用u表示.則罰函數(shù)可構(gòu)建為

(22)

式中：γ>0為違反 I 類約束和 II 類約束的懲罰系數(shù).

3.5 MHS的核心流程

基于以上分析，給出MHS的核心流程.

參數(shù)初始化：HMS,HMCR,PAR,NI,Sbest

按照GRASP算法，初始化和聲記憶庫

按rn的數(shù)量，規(guī)劃Sub_HM

fori=1 to HMS do

iff(Si)

Sbest←Si

end if

end for

新和聲創(chuàng)作Snew(見3.3)

更新和聲記憶庫(見3.4)

ifSnew不可行) then

end if

iff(Snew)

Sbest←Snew

end if

until 達(dá)到終止標(biāo)準(zhǔn)

returnSbest

4 仿真實(shí)驗(yàn)及分析

為評價(jià)本文提出的MHS算法的有效性，結(jié)合文獻(xiàn)[10]生成如下參數(shù)：Vk(k={1,2})速度v=1 m/s；最大容量Ck=2；裝卸時(shí)間tu=1 s；貨架間距為0.1 m，貨架寬為1 m.分別取不同的n和 |W| 的組合，做仿真實(shí)驗(yàn)，并進(jìn)行統(tǒng)計(jì)分析.

算法采用MATLAB(R2014a)編程實(shí)現(xiàn)，仿真環(huán)境是主頻為2.60 GHz，內(nèi)存為16 GB的便攜式計(jì)算機(jī).

4.1 算法有效性驗(yàn)證

為驗(yàn)證MHS的有效性，將問題規(guī)模 |W| 設(shè)定為5和10；n設(shè)為8、10、12、14、16，且均勻分布于W，進(jìn)行小規(guī)模問題求解.將運(yùn)行結(jié)果與CPLEX12.6進(jìn)行比較，針對每個(gè) |W| 和n的組合，CPLEX的最大求解時(shí)限設(shè)為2 h，MHS算法運(yùn)行10次取其平均值，統(tǒng)計(jì)結(jié)果如表1所示.其中，最優(yōu)解是CPLEX求解所得，可以看出，MHS運(yùn)行得出的結(jié)果與最優(yōu)解的最大偏差為4.68%，小于5%，驗(yàn)證了算法的有效性.另外，“*”表示CPLEX無法在規(guī)定的時(shí)限內(nèi)獲得最優(yōu)解，只能獲得最優(yōu)解的下界，因此，有必要構(gòu)建智能優(yōu)化算法求解中、大規(guī)模的滿意解.

令問題規(guī)模 |W|∈{15,20}，n∈{20,50,80,110}進(jìn)行中、大規(guī)模問題的仿真，以驗(yàn)證MHS的有效性.由于本文研究的問題沒有標(biāo)準(zhǔn)的算例庫，考慮到本調(diào)度問題與同時(shí)取送(SPD)問題有一定的相似性，而文獻(xiàn)[13]的混合遺傳算法(HGA)和文獻(xiàn)[14]的粒子群算法(PSO)在求解取送問題(PDP)上具有較好性能，故將其用于本文的中、大規(guī)模問題求解.為了讓文獻(xiàn)的算法更好地求解該問題，初始種群同樣由GRASP算法產(chǎn)生，編碼方案做了細(xì)微的修改，并加入了3.4節(jié)的變鄰域搜索操作，以彰顯與目標(biāo)算法(MHS)的可比性.表2所示為將MHS獲得的結(jié)果和HGA、PSO 得到的結(jié)果進(jìn)行了對比統(tǒng)計(jì).從表中可以看出：隨著問題的擴(kuò)大，MHS的尋優(yōu)能力明顯比HGA和PSO突出；當(dāng)n=110時(shí)，最大相對偏差達(dá)到11.02%和9.92%，一定程度上驗(yàn)證了MHS求解中、大規(guī)模問題的有效性.

表1 小規(guī)模問題實(shí)驗(yàn)結(jié)果Tab.1 Results of small scale instances

表2 MHS、HGA和PSO的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)Tab.2 Experimental results of MHS, HGA and PSO

4.2 MHS收斂性驗(yàn)證

為進(jìn)一步驗(yàn)證MHS的收斂性能，令問題規(guī)模 |W|=15，n=50以及 |W|=20，n=110，繪制兩種組合的收斂曲線，將其與HS常見的兩種改進(jìn)型算法，即改進(jìn)型和聲搜索算法(IHS)和全局最優(yōu)和聲搜索算法(GHS)進(jìn)行對比，結(jié)果如圖7所示.

由圖7可見，3條曲線的收斂趨勢大抵一致，主要原因在于都是在基本HS的基礎(chǔ)上對其后期收斂速度慢進(jìn)行改進(jìn).中小規(guī)模下，3種算法都能在較短時(shí)間內(nèi)搜索到最優(yōu)解，隨著規(guī)模的增大，本文融入的變鄰域搜索機(jī)制使得MHS能夠在搜索深度上更勝一籌，如圖7(b)所示.實(shí)驗(yàn)結(jié)果表明，MHS具備良好的收斂性能.

4.3 系統(tǒng)搬運(yùn)效率分析

為評估本文調(diào)度方法對系統(tǒng)效率的影響情況，引入AHT和ART兩個(gè)參數(shù)作為衡量基準(zhǔn).AHT表示任務(wù)的平均搬運(yùn)時(shí)間，其值越小，表示系統(tǒng)的運(yùn)行效率越高；ART表示為了避免 II 類沖突，RGV之間相互避讓，導(dǎo)致貨物在車上的滯留時(shí)間，其值越小，說明調(diào)度越有效.

令 |W| 分別為6,8,10,12,14,16,18,20，任務(wù)n=50，仿真實(shí)驗(yàn)結(jié)果如圖8所示，其中，t′為任務(wù)所需平均時(shí)間.

由圖8可見：當(dāng) |W| 從6增加到16時(shí)，AHT呈逐漸下降的趨勢，主要原因可能是空間狹窄，任務(wù)都集中在較少的貨架上，兩輛RGV相互干擾，大部分的時(shí)間花費(fèi)在等待上；而 |W|>16時(shí)，AHT開始逐漸增加，空間問題逐步得到緩解，兩輛RGV基本可以按照各自的預(yù)定線路進(jìn)行搬運(yùn)；ART則是逐漸下降，當(dāng) |W| 從6增加到16時(shí)下降緩慢；當(dāng) |W|>16時(shí)，其值下降趨勢明顯；同AHT變化的原因一致，RGV之間的干擾降低，貨物的滯留時(shí)間也隨之減少，貨物在小車上的滯留時(shí)間幾乎等于貨物的搬運(yùn)時(shí)間.從上述結(jié)果來看，兩輛RGV同時(shí)作業(yè)，貨架數(shù)量 |W|>16比較合適.當(dāng)貨架數(shù)量比較少(少于16)時(shí)，不太適合采用多RGV同時(shí)作業(yè).

5 結(jié)語

本文研究了自動(dòng)存取系統(tǒng)多載量RGV避碰調(diào)度問題，在對問題描述的基礎(chǔ)上建立了混合整數(shù)規(guī)劃模型.在算法部分，提出改進(jìn)型和聲搜索算法，在局部搜索部分融入了變鄰域搜索機(jī)制，以提高基本和聲搜索算法后期的收斂速度和解的質(zhì)量.同時(shí)，引入AHT和ART兩個(gè)參數(shù)作為系統(tǒng)搬運(yùn)效率的評價(jià)指標(biāo)，當(dāng)貨架數(shù)量大于16時(shí)平均搬運(yùn)時(shí)間呈緩慢遞增趨勢，貨物在RGV內(nèi)的平均滯留時(shí)間呈持續(xù)下降趨勢，說明了調(diào)度的有效性.