王小偉，張秋菊

（江南大學(xué)　機械工程學(xué)院，江蘇 無錫　214122）

單巷道雙堆垛機作業(yè)路徑優(yōu)化問題研究

王小偉，張秋菊

（江南大學(xué)機械工程學(xué)院，江蘇 無錫214122）

針對不斷提高的自動化倉庫能效和輸送作業(yè)效率要求，本文對長縱深巷道配兩臺堆垛機的作業(yè)形式進行了探討?；趦蓚€中心點車輛路由問題模式，建立了單巷道雙堆垛機作業(yè)路徑優(yōu)化問題的數(shù)學(xué)模型。采用動態(tài)區(qū)域劃分法將兩個中心點車輛路由問題簡化為一個中心點車輛路由問題，并設(shè)計了最大最小蟻群算法對兩臺堆垛機的作業(yè)路徑進行優(yōu)化。實例對比分析表明所建立的數(shù)學(xué)模型和給出的求解算法能夠有效地求解雙堆垛機作業(yè)路徑優(yōu)化問題，提高了自動化立體倉庫的作業(yè)效率。

雙堆垛機；路徑優(yōu)化；NP難題；蟻群算法；自動化立體倉庫

自動化立體倉庫是現(xiàn)代物流的發(fā)展趨勢。典型的自動化立體倉庫的巷道中通常配有一臺堆垛機，當(dāng)倉庫巷道的縱深較長、且貨物出入庫比較頻繁時，單臺堆垛機往往難以滿足物流輸送需求。傳統(tǒng)的做法是將巷道分段，每段巷道分別配一臺堆垛機。由于每段巷道的貨物輸送頻度不同，難免會存在堆垛機忙閑不均，貨物輸送效率的提高受到限制。針對上述問題，可以考慮采用一個巷道中配有兩臺堆垛機的形式，并通過合理調(diào)度最大限度地發(fā)揮堆垛機的輸送能力，提高工作效率。

在同一巷道內(nèi)配置兩臺堆垛機存在的最大問題是如何進行兩臺堆垛機的優(yōu)化調(diào)度，避免干涉或碰撞。所謂的優(yōu)化調(diào)度就是要根據(jù)一段時間內(nèi)的一批入庫和出庫任務(wù)，合理地給兩個堆垛機分配任務(wù)并安排任務(wù)執(zhí)行順序，要求這批任務(wù)的執(zhí)行時間最短且兩個堆垛機不發(fā)生干涉［1］。這屬于典型的多車場車輛路由問題 （Multi-Depot Vehicle Routing Problem，MVRP）。對于這類問題的求解，目前大多采用啟發(fā)式算法。例如在解決多AGV無碰撞規(guī)劃問題上，賀麗娜和趙東雄均將Dijkstra算法和時間窗相結(jié)合，先順序規(guī)劃各個AGV的路徑，通過檢測后續(xù)規(guī)劃路徑是否與已存在的規(guī)劃路徑發(fā)生空間和時間沖突，并調(diào)用優(yōu)化算法和規(guī)避策略進行最優(yōu)路徑的選擇，從而實現(xiàn) AGV的無碰撞路徑規(guī)劃［2-3］；馬兆敏采用遺傳算法和時間窗相結(jié)合實現(xiàn)了雙鉆頭的孔群加工路徑優(yōu)化［4］；對于多配送中心的車輛調(diào)度問題，馬宇紅、殷脂分別采用幾何重心分區(qū)方法和采用聚類分析最短距離分配法將多配送中心車輛調(diào)度問題轉(zhuǎn)化為單配送中心車輛調(diào)度問題，大大降低了運算量［5-6］。文中利用區(qū)域劃分和最大最小螞蟻算法解決了雙堆垛機的作業(yè)路徑優(yōu)化問題，使一個長巷道內(nèi)兩個堆垛機形式的應(yīng)用具備可行性。

1　問題描述

1.1堆垛機的作業(yè)路徑優(yōu)化問題描述

如圖1所示，圖中為某物流配送中心自動化立體倉庫巷道配備2個堆垛機的前視圖。每過一段時間控制系統(tǒng)都會把這段時間內(nèi)的所有入庫任務(wù)和出庫任務(wù)分配給巷道。堆垛機在兩排貨架的巷道之間行走。貨架用于存放貨物，貨架兩邊都有出入庫臺。入庫時堆垛機行走到入庫臺將貨物搬運到貨架上，出庫時堆垛機將貨架上的貨物搬運到出庫臺上。堆垛機一次最多只能攜帶一個貨物，兩個堆垛機在同一軌道上行走但不能發(fā)生碰撞，要求2個堆垛機執(zhí)行出入庫任務(wù)的時間最短。

圖1　巷道布局示意圖Fig．1　The layout of the aisle

文中的堆垛機路徑優(yōu)化問題就是一種MVRP，問題中有2個車輛，2個中心，每個車輛的容量都為1，每個目標(biāo)貨位就是客戶，他們的需求都為1。特別的是，車輛提供的資源是運輸服務(wù)，有的客戶想離開目標(biāo)貨位而有的客戶想進入目標(biāo)貨位；車輛具有把客戶從中心送到目標(biāo)貨位后又帶其他客戶離開目標(biāo)貨位的能力。

1.2雙堆垛機出入庫作業(yè)路徑優(yōu)化的數(shù)學(xué)模型

符號說明：

1）把一組出入庫任務(wù)中目標(biāo)出入庫貨位以及兩組出入庫平臺O1、O2稱為頂點v。所有頂點集合記為V=｛1，2，3…，n｝，vi（i=1，2，3，．．，n）∈V，vi水平方向編號為Xvi，垂直方向的編號為Yvi。

2）兩個堆垛機m1、m2初始時刻分別位于頂點O1、O2，坐標(biāo)為（Oxk，Oyk），k=1，2。堆垛機m1、m2的路徑分別為R1、R2，包含的頂點個數(shù)分別是 n1、n2，n1+n2=n，R1∪R2=V。

3）E（i，j）表示頂點i與頂點j組成的邊，如果路徑Rk中存在任意相鄰的頂點組成的邊與E（i，j）∈Rk相同，則稱，否則E（i，j）?Rk；

假設(shè)：

1）堆垛機在水平方向和垂直方向的運動相互獨立，運動速度恒定，分別是vx和vy。

2）單元貨位間隔為常數(shù)，貨位寬度為w，高度為h。

3）堆垛機從路徑中一個頂點移動到下一個頂點的時間成本已知，不因頂點在路徑的順序不同而改變。

4）堆垛機啟動、停止、貨叉伸縮時間成本忽略不計。

堆垛機mk從目標(biāo)頂點i運行到頂點j的時間成本根據(jù)i、j頂點類型不同而采用下面不同的計算規(guī)則［7］：

否則，

路徑優(yōu)化的目標(biāo)是巷道式堆垛機的完成一組出入庫任務(wù)的時間成本最小，它數(shù)學(xué)模型為：

其中，目標(biāo)式（1）確定目標(biāo)函數(shù)是總路徑的揀選時間最短。約束式（2）和（3）表示對每個頂點只被訪堆垛機問一次；式（4）～（6）表明了決策變量xki，j的0-1屬性以及xki，j的取值公式。（7）表示任意一個頂點到自身的時間按成本為無窮大，即頂點被堆垛機訪問過后就不能再被訪問了。

2　問題求解與算法設(shè)計

2.1動態(tài)區(qū)域劃分

文中的兩臺堆垛機的作業(yè)路徑優(yōu)化問題屬于多車場車輛路由問題（MVRP），解決車輛之間的沖突和碰撞是多車場車輛路由問題的關(guān)鍵。目前一般采用區(qū)域劃分法、預(yù)測防碰撞等方法來解決車輛之間的沖突和碰撞。區(qū)域劃分法顧名思義是通過幾何中心分區(qū)、聚類分析等方法把工作環(huán)境劃分為幾個相互沒有重疊部分的區(qū)域，而且每個區(qū)域只能容納一輛車，從而實現(xiàn)防碰和沖突等問題；預(yù)測式避障則是首先為單個車輛分配好最優(yōu)化的路徑，然后根據(jù)每臺車輛路徑離線計算在運行過程中是否發(fā)生沖突，如果檢測沒有沖突則繼續(xù)檢測下一輛車，如果檢測有沖突發(fā)生則立刻調(diào)整后車的路徑來避免碰撞。雖然預(yù)測式碰撞通過合適的沖突檢測和沖突消除方法，可以對系統(tǒng)做很好的優(yōu)化，但是計算步驟較多，比較費時。區(qū)域劃分法簡單直接，計算速度快，更適合文中只有2輛車的MVRP。文中采用動態(tài)區(qū)域劃分法，將出入庫任務(wù)劃分給不同的堆垛機，避免堆垛機之間的干涉與碰撞。劃分步驟如下：

1）如圖2，每隔一段時間（160 s），搜集這一段時間內(nèi)所有出入庫任務(wù)的目標(biāo)貨位。這里的時間間隔不是個定值，但是應(yīng)當(dāng)和優(yōu)化后的執(zhí)行時間盡可能接近，這樣系統(tǒng)在執(zhí)行的完成后就可以剛好收到優(yōu)化后的命令。令兩邊出貨臺和入貨臺的中心點為配貨中心，分別記為depot1、depot2。取index=1，記最小距離差為minD=+∞。

2）計算目標(biāo)貨位x坐標(biāo)小于等于n的所有任務(wù)到depot1的距離總和，為sumOfDistance1；目標(biāo)貨位x坐標(biāo)大于n的所有任務(wù)到depot2的距離總和，為sumOfDistance2；

3）如果 minD＞|sumOfDistance1-sumOfDistance2|，則minD=|sumOfDistance1-sumOfDistance2|。

4）index=index+1；

5）如果index小于貨架列數(shù)就轉(zhuǎn)到步驟②，否則將目標(biāo)貨位x坐標(biāo)小于等于index的所有任務(wù)劃分給堆垛機1，目標(biāo)貨位x坐標(biāo)大于n的所有任務(wù)劃分給堆垛機2。

圖2　一批出入庫任務(wù)的區(qū)域劃分Fig．2　The zone division of a group of entry/exit storage task

通過任務(wù)區(qū)域劃分，可將圖2中的MVRP問題分解為2 個VRP問題，兩個堆垛機互不干擾，不會發(fā)生碰撞。目前學(xué)者對于VRP問題的求解，大多采用Dijkstra算法［2］、遺傳算法［8］、蟻群算法 s等啟發(fā)式算法。蟻群優(yōu)化算法 （Ant Colony Optimization，ACO）是由意大利學(xué)者Dorigo Marco等人提出一種模擬螞蟻群體覓食行為方式的仿生優(yōu)化算法。ACO的基本思想是：螞蟻在某路口面臨選擇的時候，會隨機選擇一條路徑，在通過這條路徑時，它會釋放一種化學(xué)物質(zhì)，我們稱之為信息素，釋放信息素的濃度與路徑長度相關(guān)。后來的螞蟻再次來到相同的路口的時候，會根據(jù)前面螞蟻留下的信息素來判斷應(yīng)該走哪條路徑較短。螞蟻數(shù)量足夠多的情況下，它們就會形成一個有效的反饋機制，使整個蟻群最終找到那條通往食物最短的路徑。實驗證明蟻群算法在TSP問題上的設(shè)計及應(yīng)用具有很強的發(fā)現(xiàn)較好解的能力。由于單純的蟻群算法初期信息素匱乏，一般需要較長的搜索時間；后期易陷入局部最優(yōu)，許多學(xué)者一直在對ACO做出改進，提出了很多ACO變種。其中較為優(yōu)秀的當(dāng)屬MMAS最大最小螞蟻系統(tǒng)算法，它對蟻群算法做了一下改進：

1）迭代結(jié)束后，只有最優(yōu)解所屬路徑上的信息被更新，從而更好地利用了歷史信息。

2）為了避免算法過早收斂于局部最優(yōu)解，將各條路徑的信息素限制于［τmin，τmax］，超出這個范圍的值被強制設(shè)置為τmin或τmax，可以有效地避免某條路徑上的信息素遠(yuǎn)大或小于其余路徑，所有的螞蟻都集中到同一條路徑上，算法因此過早收斂的問題［10］。

蟻群算法在解決路徑優(yōu)化問題上有收斂性快，魯棒性強的特點，文中采用蟻群算法中較為優(yōu)秀的最大最小蟻群算法結(jié)合上述的區(qū)域劃分法來實現(xiàn)對雙堆垛機出入庫作業(yè)路徑的優(yōu)化。

2.2算法設(shè)計

1）節(jié)點分類

采用上述的區(qū)域劃分法將兩個堆垛機要遍歷的節(jié)點集合V分為2個集合V1和V2。V1只能由堆垛機m1遍歷；而V2只能由堆垛機m2遍歷；

2）初始化參數(shù)

堆垛機m1的路徑R1為｛O1｝，m1的路徑R2為｛O2｝；每個邊之間的信息素為1．0；負(fù)責(zé)優(yōu)化m1、m2路徑的蟻群均有m只螞蟻；蟻群最大迭代步數(shù)為Iteration。能見度因子為α、啟發(fā)式因子β；信息素?fù)]發(fā)率為ρ。

3）路徑構(gòu)造

每次迭代中m1的m只螞蟻各自先隨機選擇一個入庫頂點i，再根據(jù)貪心規(guī)則選擇一個出庫頂點j，并把剛才選擇的vi，vj添加到路徑集合R1中，頂點集合V1中刪去vi，vj。重復(fù)上述過程，直到螞蟻遍歷所有頂點。其中當(dāng)螞蟻完成復(fù)合循環(huán)時，即集合V中剩下的頂點沒有相應(yīng)的出入庫頂點與之配對，螞蟻隨機選擇其中的一個頂點添加到路徑集合R1中，并從頂點集合V1中刪去，直至集合V1為空，m1的m只螞蟻構(gòu)造路徑完成。m2的m只螞蟻構(gòu)造路徑的方法和m1的相同，此處不再敘述。

貪心規(guī)則：如果螞蟻處于當(dāng)前頂點i，選擇出下一頂點j的概率為

式中τi，j表示頂點i，j之間的信息素濃度；ηi，j表示頂點i，j之間的啟發(fā)值，是成本ti，j倒數(shù)；參數(shù)α、β為常數(shù)，分別體現(xiàn)了信息素濃度和啟發(fā)值的相對重要性［11］。

螞蟻一般按貪心規(guī)則選擇下一個頂點，即概率最大的頂點。但是如果總是是貪心規(guī)則，每次迭代時螞蟻們的路徑都是一樣的。所以螞蟻應(yīng)隨機采用貪心規(guī)則和輪盤賭規(guī)則選擇下一頂點，即從［0，1］中選擇一個隨機數(shù)rand，如果rand＞0．8螞蟻使用貪心規(guī)則選擇概率最大的頂點；否則使用輪盤賭規(guī)則：從［0，1］中選擇一個隨機數(shù)r，從剩余頂點集合中計算累加選擇概率sum——螞蟻選擇的第一個頂點概率為p1，則sum=p1，如果sum≥r，螞蟻選擇第一個頂點，否則sum加上選擇第二個頂點的概率p2，如果sum≥r，螞蟻選擇第二個頂點，否則sum加上選擇下一個頂點的概率pk，直到sum≥r，螞蟻選擇第k個頂點。這個選擇規(guī)則被稱為輪盤賭規(guī)則。

4）更新信息素

更新信息素包括邊E（i，j）信息素?fù)]發(fā)和螞蟻在邊E（i，j）釋放信息素。

信息素?fù)]發(fā)：τi，j=（1-ρ）τi，j

3　案例分析

以某一包裝容器的自動立體倉庫為例，此倉庫的單排貨架有3層，32列，層高1 200 mm，列寬650 mm。堆垛機巷道方向行走速度設(shè)為0．8 m/s，豎直方向升降速度為0．2 m/s。貨架編碼及出入庫平臺分布如圖3所示。

圖3　貨架編碼及布局Fig．3　The coding and layout of the rack

其中2個出入庫平臺均距離貨架1個列寬，高0．5個層高?，F(xiàn)有一組出/入庫作業(yè)任務(wù)：

出庫任務(wù)目標(biāo)貨位：1、6、9、11、16、29、35、36、52、60、64、70、88

入庫任務(wù)目標(biāo)貨位：2、7、14、21、28、34、42、48、67、72、 76、89、94

要求對倉庫該組出入庫任務(wù)進行優(yōu)化。

首先進行區(qū)域劃分。經(jīng)過計算后區(qū)域集合V1中的元素為：1、2、6、7、9、11、34、34、36、42、67、70、72、76；V2中的元素為：14、16、21、28、29、48、52、60、64、88、89、94。

表1　同一批出入庫任務(wù)不同處理方法的路徑及執(zhí)行時間比較Tab.1　The comparison of path and its time cost handled with different methods

其次進行路徑優(yōu)化。MMAS算法參數(shù)：α=1，β=2，ρ=0．2，螞蟻25只，迭代500次，得到優(yōu)化后的路徑見表1方式三所示，其中D0、D1分別代表出入庫平臺1、出入庫平臺2。

為便于對比，表1還給出了另外兩種方式的路徑及總作業(yè)時間：方式一不做優(yōu)化，兩個堆垛機根據(jù)任務(wù)到達(dá)次序依次執(zhí)行；方式二，不采用雙堆垛機的形式，而是將巷道均分為兩個巷道各配一臺堆垛機。兩種方式的處理結(jié)果見表。從表1可見：經(jīng)過本文中算法優(yōu)化后堆垛機作業(yè)執(zhí)行時間明顯減少。

4　結(jié)　論

本文對單巷道雙堆垛機形式的作業(yè)調(diào)度與路徑規(guī)劃優(yōu)化算法進行了研究，通過動態(tài)區(qū)域劃分與最大最小螞蟻算法，有效地對一個巷道中有兩個堆垛機的作業(yè)路徑進行了優(yōu)化。實例對比分析表明，倉庫物流效率有明顯的提高。當(dāng)倉庫巷道的縱深較長、且貨物出入庫比較頻繁時采用一個巷道中配兩臺堆垛機的形式，不失為一種可行的、效率較高的作業(yè)方式。

［1］朱文真，唐敦兵．基于遺傳禁忌搜索算法的自動化立體倉庫出入庫路徑優(yōu)化研究［J］．機械科學(xué)與技術(shù)，2011，30（7）: 1202-1206．

［2］賀麗娜，樓佩煌．基于時間窗的自動導(dǎo)引車無碰撞路徑規(guī)劃［J］．計算機集成制造系統(tǒng)，2010，16（12）:2630-2634．

［3］趙東雄．多自動導(dǎo)引小車系統(tǒng) （AGVS）路徑規(guī)劃研究［D］．武漢：湖北工業(yè)大學(xué)，2014．

［4］馬兆敏，戴青玲．基于雙鉆頭的孔群加工路徑優(yōu)化算法［J］．機床與液壓，2010，38（6）:13-15．

［5］馬宇紅．多車場多車型車輛調(diào)度問題及其遺傳算法［J］．?dāng)?shù)學(xué)的實踐與認(rèn)識，2014，44（3）:107-114．

［6］殷脂．多配送中心物流配送車輛調(diào)度問題的分層算法模型［J］．系統(tǒng)管理學(xué)報，2014，23（4）:602-606．

［7］丁彩紅．鋰電池化成物流系統(tǒng)的立體倉庫調(diào)度算法研究和建模［D］．上海:東華大學(xué)，2014．

［8］龔延成．基于遺傳算法的物流配送車輛調(diào)度問題研究［J］．?dāng)?shù)學(xué)的實踐與認(rèn)識，2004，34（6）:93-97．

［9］張裕華．基于蟻群算法的應(yīng)急物流配送車輛調(diào)度研究［J］．物流科技，2009，5（5）:47-50．

［10］陳昊．蟻群優(yōu)化算法的原理及其應(yīng)用［J］．湖北大學(xué)學(xué)報，2006，28（4）:350-353．

［11］Macro Dorigo，Thomas Stützle．Ant Colony Optimization［M］．London:A Bradford Book，2004．

［12］Thomas Stützle，Holger H．HoosMAX-MIN Ant System［J］．IEEE Computational Intelligence Magazine，2006，11（4）:28-39．

Job path optimization of single aisle with double stackers for automatic warehouse

WANG Xiao-wei，ZHANG Qiu-ju
（School of Mechanical Engineering，Jiangnan University，Wuxi 214122，China）

As the requirements for the energy efficiency of automated warehouse and delivery operation growing quickly，the form of two cranes worked in a long aisle are discussed in this paper．The problem is treated as double-depot vehicle problem and its mathematics model is built．Then the problem can be simplified as single-depot vehicle problem dynamic region partition．So the Max-Min Ant System（MMAS）algorithm is extended to the problem associated the path of Double Cranes in one aisle of an Automatic Storage and Retrieval System．Finally，the algorithm is performed with practical case，which produces high-quality for the problem．

double stackers；path optimization；NP-hard problem；ant colony optimization；automatic warehouse

TN01

A

1674－6236（2016）02-0068-04

2015-03-16稿件編號：201503210

王小偉（1989—），男，江蘇灌南人，碩士研究生。研究方向：物流自動化。