基于遺傳粒子群算法的堆垛機作業(yè)路徑優(yōu)化

劉 凱， 牛江川， 申永軍， 李素娟

(石家莊鐵道大學 機械工程學院，河北 石家莊 050043)

?

基于遺傳粒子群算法的堆垛機作業(yè)路徑優(yōu)化

劉 凱， 牛江川， 申永軍， 李素娟

(石家莊鐵道大學 機械工程學院，河北 石家莊 050043)

堆垛機的作業(yè)路徑?jīng)Q定了自動化倉庫的作業(yè)效率。建立了堆垛機作業(yè)的數(shù)學模型，并采用遺傳粒子群算法對自動化倉庫堆垛機作業(yè)路徑進行優(yōu)化。該算法引入了遺傳算法中交叉和變異操作，通過粒子與個體極值和群體極值的交叉和粒子自身變異的方式來搜索最優(yōu)解。仿真實驗結果表明，該算法的求解效果在收斂速度和優(yōu)化效果方面都有明顯的提高，可以有效地減少堆垛機系統(tǒng)揀選作業(yè)運行時間，提高了自動化倉庫的作業(yè)效率。這對實際應用有一定的參考價值。

遺傳粒子群算法；自動化倉庫；揀選作業(yè)；堆垛機

0 引言

自動化立體倉庫又稱為自動化倉儲AS/RS(Automatic Storage and Retrieval System)系統(tǒng)，它可以按照指令自動完成貨物的存取，并能對庫存貨物進行自動管理，實現(xiàn)自動化作業(yè)，具有作業(yè)效率高，占地面積小，存儲容量大，計算機自動控制等優(yōu)勢。立體倉庫中堆垛機的作業(yè)周期由3部分組成，分別是出入庫臺的管理時間，出入庫臺的處理時間和堆垛機的行走作業(yè)時間，其中堆垛機的行走作業(yè)時間約占整個作業(yè)周期的50%[1]。在實際工作中, 特別是在任務集中的階段，堆垛機往往成為物料搬運系統(tǒng)中的瓶頸環(huán)節(jié)，由于沒有優(yōu)化調(diào)度經(jīng)常會產(chǎn)生“死鎖”的現(xiàn)象，因此合理的解決自動化倉庫堆垛機的揀選作業(yè)路徑，對提高倉庫作業(yè)效率具有重要意義。

堆垛機作業(yè)路徑優(yōu)化問題求解方法的研究吸引了很多學者進行研究。文獻[1-2]提出了遺傳算法尋求堆垛機揀選作業(yè)路徑優(yōu)化方案。文獻[3]提出了改進自適應遺傳算法，克服了傳統(tǒng)遺傳算法的早熟收斂問題。文獻[4-5]提出了混合遺傳算法，使解的優(yōu)化程度以及收斂速度都較傳統(tǒng)遺傳算法有了一定程度的提高。文獻[6]提出了粒子群算法，驗證了該算法解決堆垛機路徑優(yōu)化問題也是有效可行的。文獻[7-8]對混合粒子群算法進行了研究，在粒子群優(yōu)化算法中加入倒置、對換等局部搜索算法，利用遺傳算法全局搜索能力強的特點對用粒子群優(yōu)化算法進行了優(yōu)化。文獻[9]提出了蟻群算法解決自動化倉庫中存取路徑優(yōu)化問題。其中，解決堆垛機揀選作業(yè)路徑優(yōu)化問題效果較好的方法有遺傳算法和蟻群算法。本文采用的遺傳粒子群算法，通過引入了遺傳算法中變異和交叉的操作，克服了傳統(tǒng)粒子群算法隨著迭代次數(shù)增加可能會陷入局部最優(yōu)解的死循環(huán)中的缺點。因此，采用遺傳粒子群算法解決堆垛機路徑優(yōu)化問題的研究具有重要意義。

1 堆垛機揀選作業(yè)數(shù)學模型

堆垛機在每次進入巷道揀選貨物總量不超周轉貨箱裝箱能力的前提下，如何安排貨物的揀選順序，使堆垛機經(jīng)過需要的貨位點后再回到入口處，運行時間及垂直和水平方向走過的總路程最短，同時減少堆垛機作業(yè)次數(shù)，提高貨物裝箱率[9-11]。

針對的自動化立體倉庫形式是固定單元貨格式立體貨架倉庫系統(tǒng)，它由貨架區(qū)和輸送系統(tǒng)兩部分組成。在貨架區(qū)，每相鄰的兩排貨架產(chǎn)生一個巷道，每一個巷道由一臺堆垛機負責貨物的存取，為了方便堆垛機存取貨物，每一個巷道口均有出入庫臺。輸送系統(tǒng)由輸送車和導軌組成，可以方便輸送車存取貨物[12-13]。

為了建立堆垛機揀選路徑優(yōu)化問題的數(shù)學模型，首先給出如下假設：

(1) 固定單元貨格式立體貨架的貨位點x，y表示，其中x為貨位列，y為貨位的層，以巷道口為原點O。貨格寬度為W，高度為H。

圖1 遍歷貨位示意圖

(2) 在進行出入庫作業(yè)時，堆垛機的出入庫操作速度均恒定，所以可以忽略貨物的存取時間。

(3) 在進行存取作業(yè)時，堆垛機在水平和垂直方向以恒定的速度進行出入庫作業(yè)，且能沿水平和垂直方向同時運行，設水平方向的速度為Vx，垂直方向的速度為Vy。

假設堆垛機從貨位i(Xi,Yj)到貨位j(Xj,Yj)，如圖1所示。

堆垛機從貨位i到貨位j行走直線距離

堆垛機從貨位i到貨位j運行時間

式中，W為貨格寬度；H為貨格高度。

終止條件即每次執(zhí)行揀選作業(yè)必須滿足的條件

式中，ci為第i個貨位待揀選貨物的體積；C為周轉箱的體積；n為該次作業(yè)任務待揀選貨位數(shù)。

2 遺傳粒子群算法實現(xiàn)

標準粒子群算法源于鳥群捕食行為研究，是一種進化算法，它通過迭代完成尋優(yōu)，實現(xiàn)容易、精度高且收斂速度快，但是隨著迭代次數(shù)的增加，在種群收斂集中的同時，各粒子也越來越相似，可能會在局部最優(yōu)解周邊無法跳出。遺傳粒子群算法引入了遺傳算法中交叉和變異的操作，通過粒子同個體極值和群體極值的交叉和粒子自身變異的方式來搜索最優(yōu)解。

2.1 粒子個體編碼與初始種群

每個粒子表示遍歷的每個貨位點，例如，當需要遍歷10個貨位點時，個體編碼為[7 9 6 10 1 2 4 5 3 8],表示堆垛機從貨位7開始，經(jīng)過貨位9，6，10，…，最終回到入庫位。設種群規(guī)模為N，則隨機產(chǎn)生N個這樣的個體，即形成初始種群。

2.2 適應度值

粒子適應度值表示遍歷路徑的長度，計算公式為

式中，n為貨位數(shù)目；pathi,j為貨位i，j間路徑長度。

以個體“7，9，6，10，1，2，4，5，3，8”為例，它表示的揀選路線為從貨位7開始經(jīng)過貨位9，6，10，…，最終回到庫位，在此作業(yè)過程中，當堆垛機的容量達到上限時，定義一個懲罰系數(shù)M，對違反揀選作業(yè)約束的情況進行懲罰，懲罰系數(shù)設為堆垛機周轉箱的體積C。

2.3 交叉

在優(yōu)化過程中，選取適應度最差的幾個粒子同全局最優(yōu)的粒子進行交叉操作。首先，先選擇兩個交叉位置，然后把個體和個體極值或個體和群體極值進行交叉。例如，選取的交叉位置為2和4，交叉方法示意如下：

個體[7 9 6 10 1 2 4 5 3 8],個體極值或群體極值[9 6 7 2 1 10 3 8 4 5]交叉操作后，得到新個體為[7 6 6 2 1 2 4 5 3 8],產(chǎn)生新個體后，難免會出現(xiàn)一些重復的位置，需要用個體中沒有的貨位點來替換。方法如下：

新個體[7 6 6 2 1 2 4 5 3 8]，調(diào)整后的個體[7 11 6 12 1 2 4 5 3 8]，然后計算適應度值，只有當新粒子的適應度值優(yōu)于舊粒子時，才更新粒子。

2.4 變異

變異操作是粒子自身變異得到新粒子，每次優(yōu)化過程中，隨機選擇適應度最差的幾個粒子進行變異，變異操作采用個體內(nèi)部兩位互換的方式，例如，選擇變異的位置為5，7，變異方法示意如下：

個體[7 9 6 10 1 2 4 5 3 8]變異后為[7 9 6 10 4 2 1 5 3 8],變異操作后計算適應度值，只有當新粒子的適應度值優(yōu)于舊粒子時，才更新粒子。

為保持交叉變異操作后的粒子優(yōu)化搜索的延續(xù)性，避免算法陷入局部最優(yōu)解無法跳出，每隔幾代才會進行上述變異和交叉操作，代數(shù)的選擇根據(jù)初始種群的數(shù)量確定，這樣可使失去有效搜索功能的停滯粒子跳出停滯狀態(tài)而重新獲得搜索功能,能夠更好地保持粒子種群的多樣性。

3 算例仿真實驗

30個貨位點的位置坐標如表1所示。

表1 貨位與坐標

堆垛機作業(yè)優(yōu)化算法流程如圖2所示。

圖2 算法流程

其中，更新粒子模塊根據(jù)粒子適應度值更新個體最優(yōu)和群體最優(yōu)；個體最優(yōu)交叉把個體和個體最優(yōu)粒子進行交叉得到新粒子；群體最優(yōu)交叉把個體和群體最優(yōu)粒子進行交叉得到新粒子；粒子變異是粒子自身變異得到新粒子。

在本案例中，利用matlab2012對路徑優(yōu)化進行仿真驗證，參數(shù)設置如下：

貨位點設置了30個，所以選擇個體數(shù)目為120個，最大進化次數(shù)為400，當算法迭代次數(shù)達到400時，算法終止。貨物分布圖如圖3所示。從圖3中可以看出，這些貨物很分散，如果有一個很好的優(yōu)化的路徑則可以大大節(jié)約時間和成本。

路徑優(yōu)化收斂圖如圖4所示，從圖中可以看出，當?shù)螖?shù)達到223時，路徑值不再發(fā)生變化，當?shù)螖?shù)達到終止條件時，算法結束。

采集堆垛機路徑優(yōu)化過程中距離隨迭代次數(shù)變化的數(shù)據(jù)如表2所示。

圖3 貨位分布圖

圖4 路徑優(yōu)化收斂圖

表2 優(yōu)化仿真數(shù)據(jù) m

圖5 最短路徑軌跡圖

從表2中可以看出，迭代到151次時，出現(xiàn)最短路徑，最短路徑為405.132 6 m，隨著迭代次數(shù)的增加，最短路徑不再發(fā)生變化。最短路徑軌跡如圖5所示。

為了驗證遺傳粒子群算法有效性,本文采用的實驗數(shù)據(jù)來自文獻[1]，文獻[1]中采用了解決該問題較好的遺傳算法求解，本次實驗結果與文獻[1]中遺傳算法結果相比較，對比結果如表3。

從表3中可以看出，本文算法明顯優(yōu)于同等條件下的遺傳算法，而且同等條件下遺傳算法的運行時間遠遠大于本文算法的運行時間，再次說明本文算法的有效性。

表3 優(yōu)化結果對比

4 結論

首先分析了立體倉庫堆垛機的作業(yè)特點，然后采樣結合了遺傳算法和粒子群算法兩者優(yōu)點的遺傳粒子群算法對堆垛機路徑優(yōu)化問題進行求解，最后通過 matlab軟件進行了仿真驗證。從仿真結果可以看出，求解的效果無論在收斂速度還是優(yōu)化效果方面都有明顯地提高，有效地減少了堆垛機系統(tǒng)揀選作業(yè)運行時間，提高了自動化倉庫的作業(yè)效率。

[1]萬欣欣,陳君若,王中明,等.基于遺傳算法的堆垛機路徑優(yōu)化[J].新技術新工藝,2010(7):30-32.

[2] 劉劍,王鑫,張冬梅,等.基于遺傳算法的立體倉庫堆垛機路徑優(yōu)化[J].沈陽建筑大學學報：自然科學版,2010,26(5):1006-1016.

[3] 周耿烈,馮無恙,胡赤兵.基于改進自適應遺傳算法求解機床制造企業(yè)立體倉庫堆垛機路徑優(yōu)化問題[J].制造技術與機床,2012(4):66-70.

[4] 張海軍,張博,岳溥庥,等.基于混合遺傳算法的多巷道間移動揀選優(yōu)化[J].計算機工程與應用,2014,50(16): 243-249.

[5] 田國會,張攀,尹建芹.基于混合遺傳算法的固定貨架揀選優(yōu)化問題研究[J].機械工程學報,2004,40(2):141-144.

[6] 黃學飛,劉云霞,曹玉華.基于粒子群算法的立體倉庫系統(tǒng)堆垛機作業(yè)路線優(yōu)化[J]起重運輸機械,2007( 10):26-29.

[7] 俞靚亮,王萬良,介婧.基于混合粒子群優(yōu)化算法的旅行商問題求解[J].計算機工程,2010,36(11):183-187.

[8] 高尚,韓斌,吳小俊,等.求解旅行商問題的混合粒子群優(yōu)化算法[J].控制與決策,2004,19(11):1286-1289.

[9] 華紅艷,張丹.基于蟻群算法的自動化倉庫路徑優(yōu)化[J].計算技術與自動化,2010,29(1):51-54.

[10] 楊文強.基于智能方法的自動化立體倉庫系統(tǒng)優(yōu)化研究與應用[D].上海:上海大學,2013.

[11] 曾強,張澤斌,楊龍飛.有容量限制的自動化立體倉庫堆垛機路徑規(guī)劃優(yōu)化方法[J].機械設計與制造,2015(1):172-176.

[12] 彭燁,涂海寧,顧嘉.基于改進捕食搜索算法的堆垛機揀選路徑優(yōu)化[J].制造業(yè)自動化,2013,35(10):42-46.

[13] 楊進,馬濱亮,馬良.基于改進SFLA對立體倉庫系統(tǒng)堆垛機作業(yè)路徑的優(yōu)化[J].數(shù)學的實踐與認識,2014,44(12):224-232.

Stacker Job Path Optimization Based on Genetic Particle Swarm

Liu Kai, Niu Jiangchuan, Shen Yongjun, Li Sujuan

(School of Mechanical Engineering,Shijiazhuang Tiedao University, Shijiazhuang 050043, China)

The route optimization of the stacker determines the operating efficiency of automatic storage and retrieval system. The mathematical model of stacker job is established, and the route optimization problem of the stacker is investigated by means of Genetic PSO. The algorithm uses genetic algorithm crossover and mutation, by particles and groups with individual extremes crossover and mutation particle itself way to search for the optimal solution. The simulation results show that, the speed and optimization convergence effect of the solving has been significantly improved, the picking operations time has been effectively reduced, and the operating efficiency of automatic storage and retrieval system has been improved, which is of reference value for practical application.

Genetic PSO; automated warehouse; picking operations; stacker

2015-05-19 責任編輯:車軒玉

10.13319/j.cnki.sjztddxxbzrb.2016.02.13

國家自然科學基金(51275321)；河北省自然科學基金((F2013210109)；河北省高等學校創(chuàng)新團隊領軍人才培育計劃(LJRC018)；河北省教育廳自然科學青年基金 (QN2014151)

劉凱(1988-)，男，碩士研究生，主要從事企業(yè)信息化與協(xié)同管理技術的研究。E-mail:lk1256229856@126.com

TH165+.1

A

2095-0373(2016)02-0067-05

劉凱，牛江川，申永軍，等.基于遺傳粒子群算法的堆垛機作業(yè)路徑優(yōu)化[J].石家莊鐵道大學學報:自然科學版,2016,29(2):67-71.