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

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

?

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

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

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

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

遺傳粒子群算法；自動(dòng)化倉(cāng)庫(kù)；揀選作業(yè)；堆垛機(jī)

0 引言

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

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

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

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

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

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

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

圖1 遍歷貨位示意圖

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

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

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

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

堆垛機(jī)從貨位i到貨位j運(yùn)行時(shí)間

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

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

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

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

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

2.1 粒子個(gè)體編碼與初始種群

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

2.2 適應(yīng)度值

粒子適應(yīng)度值表示遍歷路徑的長(zhǎng)度，計(jì)算公式為

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

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

2.3 交叉

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

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

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

2.4 變異

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

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

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

3 算例仿真實(shí)驗(yàn)

30個(gè)貨位點(diǎn)的位置坐標(biāo)如表1所示。

表1 貨位與坐標(biāo)

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

圖2 算法流程

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

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

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

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

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

圖3 貨位分布圖

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

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

圖5 最短路徑軌跡圖

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

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

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

表3 優(yōu)化結(jié)果對(duì)比

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

[13] 楊進(jìn),馬濱亮,馬良.基于改進(jìn)SFLA對(duì)立體倉(cāng)庫(kù)系統(tǒng)堆垛機(jī)作業(yè)路徑的優(yōu)化[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(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 責(zé)任編輯:車軒玉

10.13319/j.cnki.sjztddxxbzrb.2016.02.13

國(guó)家自然科學(xué)基金(51275321)；河北省自然科學(xué)基金((F2013210109)；河北省高等學(xué)校創(chuàng)新團(tuán)隊(duì)領(lǐng)軍人才培育計(jì)劃(LJRC018)；河北省教育廳自然科學(xué)青年基金 (QN2014151)

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

TH165+.1

A

2095-0373(2016)02-0067-05

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