楊 瑋, 李 程, 傅衛(wèi)平, 李雪蓮

自動(dòng)化立體倉庫固定貨架揀選路徑問題研究

楊 瑋1, 李 程1, 傅衛(wèi)平2, 李雪蓮1

(1.陜西科技大學(xué)機(jī)電工程學(xué)院,西安710021;2.西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院,西安710048)

為提高自動(dòng)化立體倉庫揀選效率,以存取時(shí)間最短為目標(biāo),針對(duì)單巷道固定貨架揀選作業(yè)過程,構(gòu)建了解決揀選作業(yè)路徑優(yōu)化問題的數(shù)學(xué)模型,提出結(jié)合模擬退火算法的混合粒子群算法.該算法在求解過程中用粒子群算法初始化種群,提高了優(yōu)化效率,縮短了搜索時(shí)間;在迭代過程中采用模擬退火算法,利用其概率突跳能力,以避免基本粒子群算法迭代過程中陷入局部最優(yōu)和早熟收斂.通過實(shí)例驗(yàn)證,該算法比標(biāo)準(zhǔn)粒子群算法所用時(shí)間短、收斂速度快、迭代次數(shù)少.

混合粒子群算法;模擬退火算法;單巷道固定貨架;揀選路徑

固定貨架揀選作業(yè)是自動(dòng)化立體倉庫調(diào)度的核心內(nèi)容,也是影響自動(dòng)化立體倉庫效率的主要因素.合理安排揀選路徑,能夠減少堆垛機(jī)的工作量,縮短進(jìn)出庫的移動(dòng)距離和作業(yè)時(shí)間,從而降低物流業(yè)務(wù)的成本,提高經(jīng)濟(jì)收益.國內(nèi)外學(xué)者對(duì)自動(dòng)化立體倉庫系統(tǒng)的優(yōu)化調(diào)度問題進(jìn)行了大量的研究.王嫻等[1]應(yīng)用人工魚群算法對(duì)自動(dòng)化立體倉庫的揀選作業(yè)優(yōu)化問題進(jìn)行了求解,并與遺傳算法的優(yōu)化結(jié)果進(jìn)行了比較,證明此種算法得到了有效應(yīng)用.黃楊波等[2]對(duì)自動(dòng)化立體倉庫揀選作業(yè)優(yōu)化提出了一種免疫單親遺傳算法,仿真實(shí)驗(yàn)表明,這種改進(jìn)遺傳算法可行性好,且算法穩(wěn)定性得到提高.方彥軍等[3]采用最大最小蟻群算法克服了基本蟻群算法過早陷入局部最優(yōu)的缺陷,對(duì)于求解自動(dòng)化立體倉庫揀選作業(yè)優(yōu)化問題具有很好的效果.Sarker等[4]提出了一種基于控制和調(diào)度系統(tǒng)的混合智能方法,解決了自動(dòng)化立體倉庫固定貨架揀選作業(yè)問題,證明了該方法求解此類問題的有效性.本文提出基于模擬退火的混合粒子群算法來解決自動(dòng)化立體倉庫揀選作業(yè)問題,并與PSO算法進(jìn)行對(duì)比,通過實(shí)例驗(yàn)證了該混合粒子群算法的有效性和優(yōu)越性.

1 單巷道固定貨架揀選路徑問題

1.1 問題描述

在固定貨架系統(tǒng)中,若每條巷道內(nèi)都配備有一臺(tái)堆垛機(jī)負(fù)責(zé)同一巷道內(nèi)相應(yīng)兩排貨架的揀選作業(yè),則這類問題稱為單巷道固定貨架揀選作業(yè)問題[5].

揀選作業(yè)過程描述:控制系統(tǒng)獲得需求貨單后,堆垛機(jī)攜帶空貨箱從巷道口,或者說I/O臺(tái)開始運(yùn)行,對(duì)貨單第一條目所對(duì)應(yīng)的貨位進(jìn)行揀選操作;再向下一個(gè)被揀選貨位運(yùn)行,繼續(xù)揀選;將貨單中的所有條目揀選完畢后,堆垛機(jī)攜帶貨箱返回I/O臺(tái),則一次揀選作業(yè)完成.

圖1是單巷道固定貨架結(jié)構(gòu)示意圖,出/入庫臺(tái)都設(shè)置在貨架系統(tǒng)的同一端.圖中x表示貨架的列號(hào),y表示貨架層號(hào),黑點(diǎn)表示需要堆垛機(jī)進(jìn)行揀選作業(yè)的貨位點(diǎn),用坐標(biāo)(X,Y)表示.將揀選出/入庫臺(tái)作為揀選作業(yè)的附加貨位點(diǎn),坐標(biāo)表示為原點(diǎn)坐標(biāo).設(shè)每個(gè)貨格長度為a,寬度為b,高度為h,且a,b,h均為常數(shù).對(duì)于一個(gè)有n個(gè)貨單條目的待揀選貨單,問題的研究目標(biāo)就是要尋找一條最優(yōu)的貨位揀選路徑,使完成這個(gè)揀選訂單n個(gè)條目所用總時(shí)間最少.

圖1 單巷道固定貨架結(jié)構(gòu)示意圖Fig.1 Schematic diagram of single aisle rack structure

1.2 數(shù)學(xué)模型

根據(jù)貨物不同存取過程,為了簡(jiǎn)化研究,作出如下假設(shè)[6-7]:

a.堆垛機(jī)可在x軸(水平方向)和y軸(垂直方向)上同時(shí)運(yùn)動(dòng)且速度恒定,并設(shè)其運(yùn)行速度分別為Vx和Vy,堆垛機(jī)的起止過程不作考慮;

b.堆垛機(jī)從貨位中取貨和放貨時(shí)間設(shè)為常量Q和F,計(jì)算時(shí)可以忽略不計(jì);

c.待揀選貨單中的每個(gè)貨位只進(jìn)行一次揀選.

據(jù)上述假設(shè),堆垛機(jī)開始揀選作業(yè),揀選完貨位i再對(duì)貨位j進(jìn)行揀選,操作過程所需時(shí)間為

式中,n為待揀選貨單的貨單條目數(shù),即待揀選的貨位總數(shù);S表示待揀選的貨位集合.式(2)要求堆垛機(jī)對(duì)貨位進(jìn)行揀選所用的時(shí)間最短;式(3)和式(4)是確保要求每個(gè)貨位只被進(jìn)行一次揀選;式(5)表示堆垛機(jī)進(jìn)行揀選作業(yè)時(shí),不能在揀選貨位之間形成揀選回路,在揀選完所有的貨位后返回揀選臺(tái).

2 混合粒子群算法解決揀選作業(yè)問題

2.1 基本粒子群算法

粒子群優(yōu)化算法[8](particle swarm optimizer, PSO)是一種基于群智能方法的演化計(jì)算技術(shù),最早由Kennedy博士和Eberhart博士于1995年提出.其原理可簡(jiǎn)單地表述為:每只鳥(粒子)在自己最優(yōu)位置的基礎(chǔ)上通過追蹤有限個(gè)處于當(dāng)前最優(yōu)位置的鄰居,逐漸向食物目標(biāo)位置靠近.

數(shù)學(xué)模型表達(dá)如下:粒子的種群表示為X=(X1, X2,…,XN),粒子飛過的每個(gè)位置Xi=(xi1,xi2,…, xiD)T都對(duì)應(yīng)于一個(gè)問題的解;飛行速度Vi=(vi1, vi2,…,viD)T,粒子飛行的過程就是搜索的過程;粒子在迭代過程中的最佳位置Pi=(Pi1,Pi2,…,PiD)T,種群迭代的最佳位置為第g個(gè)粒子的最優(yōu)位置,表示為Pg.粒子的位置和速度更新公式為

式中,d是尋優(yōu)空間維度,d=1,2,…,D;i為粒子群體數(shù)目,i=1,2,…,N;m為迭代次數(shù);c1,c2為學(xué)習(xí)因子,也稱加速系數(shù),使粒子具有向群體中較優(yōu)粒子學(xué)習(xí)的能力,從而向個(gè)體極值和全局極值方向靠攏;r1和r2為(0,1)上均勻分布的隨機(jī)數(shù),以保證粒子種群的多樣性.對(duì)于位置和速度的更新變化,可以限定其變化范圍,當(dāng)更新值超過了其邊界范圍時(shí),取其邊界值.

2.2 模擬退火粒子群算法

模擬退火算法(simulated annealing,SA)是基于Monte Carlo迭代求解策略[9-10]的一種隨機(jī)尋優(yōu)算法,其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性.從某一較高初溫出發(fā),伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解.基于模擬退火算法的混合粒子群算法的尋優(yōu)策略是,求解過程中用粒子群算法初始化種群,利用模擬退火算法概率突跳的特性,求解全局最優(yōu)解.混合粒子群算法的計(jì)算步驟如下:

a.根據(jù)編碼思想對(duì)粒子種群進(jìn)行初始化.利用公式

計(jì)算初始溫度t0.式中,f表示目標(biāo)函數(shù)值;fPg為初始種群中的全局極值.

b.確定適應(yīng)度函數(shù).

c.計(jì)算粒子的適應(yīng)度值,由Pi相對(duì)于Pg的突跳概率公式

確定.式中,r為退溫速率;m為迭代次數(shù);tm為m代時(shí)的溫度.根據(jù)式(6)和式(7)更新粒子的速度與位置,計(jì)算新粒子的適應(yīng)度值,由步驟c確定最優(yōu)粒子位置Pgl,完成退溫循環(huán).

e.循環(huán)過程完成后,得出最優(yōu)結(jié)果.

結(jié)合模擬退火的粒子群算法流程如圖2所示.

圖2 混合粒子群算法的流程圖Fig.2 Flow chart of SAPSO

3 基于混合粒子群算法揀選路徑的實(shí)現(xiàn)

3.1 參數(shù)設(shè)定[11]

設(shè)一個(gè)自動(dòng)化立體倉庫固定貨架的組成為10排72列,每排10層共720個(gè)貨位;貨架長度a= 1 m,寬度b=1 m,高度h=1 m;堆垛機(jī)水平運(yùn)行速度Vx=3 m/s,垂直運(yùn)行速度Vy=1 m/s;算法中最大迭代次數(shù)取mmax=800.需揀選的80個(gè)貨位坐標(biāo)如表1所示.

表1 80個(gè)貨位點(diǎn)的實(shí)驗(yàn)數(shù)據(jù)Tab.1 Experimental data of the 80 cargo sites

3.2 實(shí)驗(yàn)結(jié)果及算法比較

采用整數(shù)編碼[12-13]求解種群粒子及其速度,將待揀選的貨位坐標(biāo)設(shè)置為一個(gè)2維矩陣,矩陣的列由待揀選貨位的貨位數(shù)決定,以此矩陣作為編碼思想中的源數(shù)據(jù),進(jìn)而粒子以向量的方式進(jìn)入算法優(yōu)化流程[14].針對(duì)不同的算法參數(shù)進(jìn)行實(shí)驗(yàn),平均運(yùn)行30次,實(shí)驗(yàn)結(jié)果如表2所示.對(duì)于80個(gè)貨位的揀選路徑優(yōu)化結(jié)果和算法收斂效果對(duì)比如圖3和圖4 (見下頁)所示.

表2 兩種算法性能比較表Tab.2 Performance comparison between the two algorithms

從圖4可以看出:模擬退火粒子群算法的收斂速度快,迭代次數(shù)少,充分驗(yàn)證了利用該算法求解自動(dòng)化立體倉庫揀選路徑優(yōu)化問題的可行性.從表2可以得出,隨著貨位數(shù)的增加,混合粒子群算法的收斂性明顯提高,優(yōu)化效果更為顯著,算法的應(yīng)用效果更好.

圖3 兩算法貨位揀選路徑優(yōu)化結(jié)果圖Fig.3 Chosen path optimization results by the two algorithms

圖4 兩算法收斂效果對(duì)比圖Fig.4 Convergence comparison between the two algorithms

4 結(jié) 論

針對(duì)單巷道路徑揀選作業(yè)問題,將實(shí)際問題抽象為可以進(jìn)行算法實(shí)現(xiàn)的數(shù)學(xué)模型[15-16];提出的混合粒子群算法兼有粒子群算法優(yōu)化效率高、模擬退火算法概率突跳的優(yōu)點(diǎn),在求解大規(guī)模貨物揀選作業(yè)優(yōu)化問題時(shí)收斂速度顯著提高,優(yōu)勢(shì)明顯,可行性強(qiáng).通過對(duì)80個(gè)貨位揀選路徑的分析,與標(biāo)準(zhǔn)粒子群算法對(duì)比,結(jié)果顯示混合粒子群算法收斂速度快、迭代次數(shù)少,進(jìn)一步驗(yàn)證了該算法的可行性和有效性.但是,算法的穩(wěn)定性有待提高.因此在后續(xù)的研究中,將通過對(duì)算法中參數(shù)設(shè)置的調(diào)整,來提高算法的穩(wěn)定性,并進(jìn)一步將該算法應(yīng)用到多巷道路徑揀選作業(yè)中及其它組合優(yōu)化問題中.

[1] 王嫻,杜亞江,欒睿.基于人工魚群算法的揀選作業(yè)優(yōu)化問題[J].蘭州交通大學(xué)學(xué)報(bào),2012,31(1):123-126.

[2] 黃楊波,劉萬軍,丁鵬,等.基于免疫單親遺傳算法的揀選作業(yè)優(yōu)化[J].計(jì)算機(jī)工程,2011,37(11):206 -208.

[3] 方彥軍,謝宜凈.基于MMAS算法的計(jì)量檢定中心倉儲(chǔ)堆垛機(jī)揀選路徑優(yōu)化[J].武漢大學(xué)學(xué)報(bào)(工學(xué)版), 2013,46(5):645-648.

[4] Sarker R,Omar M.Hybrid evolutionary algorithm for job scheduling under machine maintenance[J].Applied Soft Computing Journal,2013,13(3):1440-1447.

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

[6] 謝樹新.自動(dòng)化立體倉庫揀選作業(yè)路徑優(yōu)化方法研究[D].蘇州:蘇州大學(xué),2010.

[7] 龐龍,陸金桂.基于蟻群遺傳算法的自動(dòng)化立體倉庫揀選路徑優(yōu)化[J].計(jì)算機(jī)工程與科學(xué),2012,34(3): 148-151.

[8] 江濤.改進(jìn)的粒子群優(yōu)化算法[D].長春:吉林大學(xué),2013.

[9] Yang W Q,Deng L,Fei M R,et al.Multi-objective automated warehousing scheduling based on improved tabu search[J].Computer Integrated Manufacturing Systems,2013,19(8):2097-2104.

[10] 謝旻.一種混合粒子群優(yōu)化算法在TSP中的應(yīng)用[J].太原理工大學(xué)學(xué)報(bào),2013,44(4):506-509.

[11] Khalid H,Beatrix B.Integration of products expiry dates in optimal scheduling of storage/retrieval operations for a flow-rack AS/RS[J].International Journal of Industrial and Systems Engineering,2013, 15(2):216-233.

[12] 傅家旗,葉春明.求解旅行商問題的混合量子算法[J].上海理工大學(xué)學(xué)報(bào),2010,32(5):466-470.

[13] 陸園,洪躍.多目標(biāo)下的自動(dòng)化立體倉庫揀選作業(yè)路徑優(yōu)化[J].機(jī)械制造,2012,50(3):84-87.

[14] 陳義雄,梁昔明,黃亞飛.一種改進(jìn)的混沌量子粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2013,39(8):253-256.

[15] 周蓉,葉春明.基于粒子群的多目標(biāo)多執(zhí)行模式項(xiàng)目調(diào)度[J].上海理工大學(xué)學(xué)報(bào),2013,35(1):27-32.

[16] 賈建芳,楊瑞峰,王莉.混合遺傳粒子群優(yōu)化算法的研究[J].自動(dòng)化儀表,2013,34(9):1-3.

(編輯:丁紅藝)

Chosen Path Optiomization for Fixed Shelves in AS/RS

YANGWei1, LICheng1, FUWeiping2, LIXuelian1
(1.College of Mechanical&Electrical Engineering,Shaanxi University of Science&Technology,Xi’an 710021,China; 2.School of Mechanical and Precision Instrument Engineering,Xi’an University of Technology,Xi’an 710048,China)

To improve the order picking efficiency and shorten storage time in Automatic Storage &Retrieval System(AS/RS),a mathematical model was constructed to solve the problem of picking path optimization.According to the operation character of the order picking of fixed shelf storage area in a single roadway,an hybrid particle swarm algorithm combined with simulated annealing algorithm was presented.In the solution process,particle swarm optimization(PSO)was used to initialize the swarm,so as to improve the searching performance of the algorithm and optimize the results.The method can improve the optimization efficiency and shorten the searching time.In the iterative process,the simulated annealing algorithm was used to avoid premature convergence and to prevent from getting into local optimum as in the conventional PSO due to its probabilistic jumping ability.The examples show that compared with the standard PSO,the algorithm has the merits of shorter calculation time,faster convergence and fewer times of iterations.

hybrid particle swarm algorithm;simulated annealing algorithm;a single roadway fixed shelves;chosen path

TP 18

A

1007-6735(2015)01-0084-05

10.13255/j.cnki.jusst.2015.01.015

2014-04-10

國家自然科學(xué)基金資助項(xiàng)目(11072192);陜西科技大學(xué)科研啟動(dòng)基金資助項(xiàng)目(BJ12-21);國家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃資助項(xiàng)目(201210708037);陜西省農(nóng)業(yè)科技創(chuàng)新與攻關(guān)項(xiàng)目(2014K01-29-01);陜西省科技廳基金資助項(xiàng)目(14JK1093)

楊 瑋(1972-),女,副教授.研究方向:現(xiàn)代物流系統(tǒng)工程與技術(shù)、工業(yè)工程.E-mail:yangwei613@126.com