自動存取系統多載量軌道小車避碰調度方法

馬昌譜， 周炳海

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

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

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

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

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

1 問題描述

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

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

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

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

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

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

2 數學模型

建立數學模型如下：

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

3 改進型和聲搜索算法

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

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

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

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

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

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

步驟6判斷終止準則.若當前迭代次數N大于最大迭代次數NI，則合并所有和聲片段形成新的和聲記憶庫，否則重復步驟 4和5.

步驟7變鄰域搜索操作.隨機選取一個和聲向量進行變鄰域搜索操作，并更新HM.

步驟8判斷終止準則：若任兩個和聲對應目標值之差均小于ε，則算法終止，否則重復執(zhí)行步驟3～7.

3.1 和聲編碼方案

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

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

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

編碼方案對應的解如圖3所示，橫線部分表示RGV進行裝或卸操作.初始時刻，V1從0位置出發(fā)，完成搬運任務后返回至原位置；V2從 |W|+ 1出發(fā)，完成分配的任務后返回至出發(fā)點.V1對應的路徑為0→2→4→1→3→0，執(zhí)行的任務順序為②→①；RGV2對應的路徑為11→9→4→5→9→11，執(zhí)行的任務順序為④→③.

圖3 編碼方案對應的解Fig.3 Corresponding solution of coding mode

3.2 和聲記憶庫初始化

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

步驟1隨機生成任務矩陣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)、余杭夢想小鎮(zhèn)等對特色小鎮(zhèn)產業(yè)發(fā)展規(guī)劃進行科學論證，按照主導產業(yè)特色鮮明、相關產業(yè)按需配套的原則，合理確定特色小鎮(zhèn)產業(yè)功能布局。一些個別特色小鎮(zhèn)用地規(guī)模過大，產業(yè)定位不夠清晰等問題，將不符合土地利用總體規(guī)劃的建設用地劃出規(guī)劃區(qū)范圍，在此基礎上提出明確的用地需求菜單，落實到城市控規(guī)和土地利用總體規(guī)劃上，科學劃分相關功能區(qū)塊，確定用地類型為特色小鎮(zhèn)建設提供科學指引[6]。

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

步驟6將h1和h2轉化成在[Lmin,Lmax]上的編碼，一并存入HM，實現和聲記憶庫的初始化.

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

針對每個Sub_HM，新和聲Snew以HMCR概率繼承現有Sub_HM中和聲，并以PAR概率進行微調.同時，對Snew進行鄰域搜索，新和聲Snew以(1-HMCR)的概率應用GRASP算法進行創(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 任務對和組合任務的重置操作Fig.4 Re-located operations of couple and component

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

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

(5) 變異操作.設原變量Sold經移動操作后得到Smv，若f(Smv)

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

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

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

(21)

式中：q為[0,1]之間的隨機數.

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

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

(22)

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

3.5 MHS的核心流程

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

參數初始化：HMS,HMCR,PAR,NI,Sbest

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

按rn的數量，規(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 達到終止標準

returnSbest

4 仿真實驗及分析

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

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

4.1 算法有效性驗證

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

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

表1 小規(guī)模問題實驗結果Tab.1 Results of small scale instances

表2 MHS、HGA和PSO的實驗結果統計Tab.2 Experimental results of MHS, HGA and PSO

4.2 MHS收斂性驗證

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

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

4.3 系統搬運效率分析

為評估本文調度方法對系統效率的影響情況，引入AHT和ART兩個參數作為衡量基準.AHT表示任務的平均搬運時間，其值越小，表示系統的運行效率越高；ART表示為了避免 II 類沖突，RGV之間相互避讓，導致貨物在車上的滯留時間，其值越小，說明調度越有效.

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

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

5 結語

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