單巷道雙堆垛機作業路徑優化問題研究

王小偉，張秋菊

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

單巷道雙堆垛機作業路徑優化問題研究

王小偉，張秋菊

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

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

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

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

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

1　問題描述

1.1堆垛機的作業路徑優化問題描述

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

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

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

1.2雙堆垛機出入庫作業路徑優化的數學模型

符號說明：

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

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

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

假設：

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

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

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

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

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

否則，

路徑優化的目標是巷道式堆垛機的完成一組出入庫任務的時間成本最小，它數學模型為：

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

2　問題求解與算法設計

2.1動態區域劃分

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

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

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

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

4）index=index+1；

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

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

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

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

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

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

2.2算法設計

1）節點分類

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

2）初始化參數

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

3）路徑構造

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

貪心規則：如果螞蟻處于當前頂點i，選擇出下一頂點j的概率為

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

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

4）更新信息素

更新信息素包括邊E（i，j）信息素揮發和螞蟻在邊E（i，j）釋放信息素。

信息素揮發：τi，j=（1-ρ）τi，j

3　案例分析

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

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

其中2個出入庫平臺均距離貨架1個列寬，高0．5個層高。現有一組出/入庫作業任務：

出庫任務目標貨位：1、6、9、11、16、29、35、36、52、60、64、70、88

入庫任務目標貨位：2、7、14、21、28、34、42、48、67、72、 76、89、94

要求對倉庫該組出入庫任務進行優化。

首先進行區域劃分。經過計算后區域集合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　同一批出入庫任務不同處理方法的路徑及執行時間比較Tab.1　The comparison of path and its time cost handled with different methods

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

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

4　結　論

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

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

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

［3］趙東雄．多自動導引小車系統 （AGVS）路徑規劃研究［D］．武漢：湖北工業大學，2014．

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

［5］馬宇紅．多車場多車型車輛調度問題及其遺傳算法［J］．數學的實踐與認識，2014，44（3）:107-114．

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

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

［8］龔延成．基于遺傳算法的物流配送車輛調度問題研究［J］．數學的實踐與認識，2004，34（6）:93-97．

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

［10］陳昊．蟻群優化算法的原理及其應用［J］．湖北大學學報，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—），男，江蘇灌南人，碩士研究生。研究方向：物流自動化。