王海珍，彭梅香

（新余學(xué)院 工程系，新余 338025）

基于SA的PSO自動(dòng)化倉庫揀選作業(yè)路徑優(yōu)化方法

王海珍，彭梅香

（新余學(xué)院 工程系，新余 338025）

0 引言

現(xiàn)在，自動(dòng)化立體倉庫已經(jīng)成為現(xiàn)代物資存取技術(shù)與自動(dòng)化技術(shù)相結(jié)合的高新技術(shù)產(chǎn)物，是物流自動(dòng)化的顯著標(biāo)志之一，是現(xiàn)代化大生產(chǎn)的必然產(chǎn)物。為滿足現(xiàn)代生產(chǎn)與物流的需要，就必須采用以計(jì)算機(jī)控制技術(shù)為主要手段組成的自動(dòng)化立體倉庫。立體倉庫制造業(yè)在國外已經(jīng)發(fā)展成為一個(gè)新興的高科技產(chǎn)業(yè)，取得了可觀的經(jīng)濟(jì)效益。而我國對(duì)該課題的研究起步較晚，尤其缺少對(duì)物流信息論、輸送系統(tǒng)控制和優(yōu)化調(diào)度的系統(tǒng)性理論研究，使目前的自動(dòng)化立體倉庫不能實(shí)現(xiàn)物流信息化、最優(yōu)化作業(yè)，大大降低了操作效率，產(chǎn)生高投入、低運(yùn)行速度和低效率的狀態(tài)。

1 自動(dòng)化立體倉庫和揀選作業(yè)原理

自動(dòng)化立體倉庫又稱自動(dòng)化高架倉庫和自動(dòng)存儲(chǔ)系統(tǒng)（AS/RS系統(tǒng)），它是一種基于高層貨架、利用電子計(jì)算機(jī)進(jìn)行控制管理、采用自動(dòng)化存取輸送設(shè)備自動(dòng)進(jìn)行存取作業(yè)的倉儲(chǔ)系統(tǒng)。自動(dòng)化立體倉庫由多排的立體貨架構(gòu)成，還包括物資自動(dòng)存取設(shè)備、輸送系統(tǒng)、堆垛機(jī)系統(tǒng)、 自動(dòng)分揀系統(tǒng)、計(jì)算機(jī)管理與控制系統(tǒng)等幾部分，如圖1所示。

揀選操作流程通常是由堆垛機(jī)操作員先從倉庫管理控制系統(tǒng)取得一張打印的批量揀選作業(yè)任務(wù)表單，然后乘坐巷道堆垛機(jī)按照任務(wù)表單上列出的每項(xiàng)存取揀選任務(wù)，通過手動(dòng)或自動(dòng)的操作方式，依次控制堆垛機(jī)從一個(gè)己完成的任務(wù)點(diǎn)移動(dòng)到下一個(gè)將要進(jìn)行揀選的任務(wù)點(diǎn)。當(dāng)任務(wù)表單上的所有任務(wù)全部完成或者揀選貨箱己放滿時(shí)，將堆垛機(jī)開回到出/入庫站臺(tái)處，卸下物資。通過揀選作業(yè)流程的描述可以把堆垛機(jī)的揀選作業(yè)調(diào)度歸納成如下問題：設(shè)有n個(gè)揀選任務(wù)，即有n個(gè)貨位點(diǎn)等待堆垛機(jī)到達(dá)，堆垛機(jī)從出/入庫站臺(tái)處出發(fā)，分別到達(dá)n個(gè)貨位點(diǎn)，且每個(gè)貨位點(diǎn)只去一次，最后回到起點(diǎn)，求堆垛機(jī)運(yùn)行的最短路徑。

圖1 自動(dòng)化立體倉庫構(gòu)成圖

2 粒子算法

粒子群算法簡(jiǎn)介：粒子群算法（Particle Swarm Optimization，簡(jiǎn)稱PSO）最早是在1995年由美國的Eberhart和Kennedy共同提出的，其基本思想受他們?cè)缙趯?duì)許多鳥類的群體行為進(jìn)行建模與仿真研究結(jié)果的啟發(fā)，他們的模型及仿真算法主要利用了生物學(xué)家Hepper的模型。在粒子群算法中，每個(gè)個(gè)體稱為一個(gè)“粒子”，其實(shí)每個(gè)粒子代表著一個(gè)潛在的解。例如，在一個(gè)D維的目標(biāo)搜索空間中，每個(gè)粒子看成是空間內(nèi)的一個(gè)點(diǎn)。設(shè)群體由m個(gè)粒子構(gòu)成。m也被稱為群體規(guī)模，過大的m會(huì)影響算法的運(yùn)算速度和收斂性。

3 基于模擬退火的粒子群優(yōu)化算法

3.1 固定貨架堆垛機(jī)揀選作業(yè)路徑優(yōu)化問題

自動(dòng)化立體倉庫的工作效率也主要取決于固定貨架的揀選作業(yè)效率，所以固定貨架的揀選作業(yè)路徑的優(yōu)化對(duì)自動(dòng)化立體倉庫的自動(dòng)化程度的提高有相當(dāng)重要的作用。假設(shè)某自動(dòng)化立體倉庫的固定貨架子系統(tǒng)共包含13排立體貨架，每排貨架分為10層72列共720個(gè)貨位。

固定貨架及堆垛機(jī)運(yùn)行參數(shù)設(shè)定如下：

設(shè)定1：以揀選方式存取貨物時(shí)，操作者對(duì)某一貨物的揀選時(shí)間只與該貨物的種類和數(shù)量有關(guān)，不隨存取順序的變化而變化；在計(jì)算揀選作業(yè)時(shí)間代價(jià)時(shí)，忽略貨物存取時(shí)間。

設(shè)定2：堆垛機(jī)在不同貨物之間移動(dòng)時(shí)，在水平方向和垂直方向上都以恒高速運(yùn)行，其制動(dòng)和起動(dòng)過程忽略不計(jì)；堆垛機(jī)水平運(yùn)行速度為vx，垂直運(yùn)行速度為vy；堆垛機(jī)運(yùn)行時(shí)在水平方向和垂直方向可以同時(shí)運(yùn)動(dòng)。

設(shè)定3：圖形結(jié)點(diǎn)為在單巷道內(nèi)堆垛機(jī)需要存取的貨位點(diǎn)，以坐標(biāo)（x，y）標(biāo)志，x和y分別表示貨位點(diǎn)的列號(hào)和層號(hào)，將貨位點(diǎn)（0，0）視為巷道口，并將其作為整個(gè)揀選作業(yè)的附加貨位點(diǎn)。單個(gè)貨格寬度為b，高度為h。

設(shè)定4：在揀選任務(wù)全部完成后，揀選貨箱未滿或剛好滿。

3.2 粒子群算法求解揀選作業(yè)路徑優(yōu)化問題

令粒子群中的第i個(gè)粒子表示為zi=(zi1,zi2,...,zid)，由于每個(gè)位置向量zid在算法的初始階段是隨機(jī)產(chǎn)生的實(shí)數(shù)，并且每個(gè)位置向量通過位置-速度模型中的初等運(yùn)算進(jìn)行更新，粒子zi中每個(gè)向量zid在數(shù)值上存在相同的機(jī)率很小，因此，粒子zi中的所有位置向量必然存在一個(gè)次序S，這個(gè)次序S在迭代計(jì)算過程中隨著粒子位置向量的不斷更新也不斷地發(fā)生變化。

3.2.1 粒子位置和速度

我們將zi取[zmin,zmax]之間的隨機(jī)數(shù)為粒子初始位置。在迭代計(jì)算時(shí)對(duì)粒子位置向量值的大小不設(shè)定限制范圍，而只是將初始粒子群中的粒子位置限定在一定的范圍內(nèi)產(chǎn)生。將vi取[vmin,vmax]之間的隨機(jī)數(shù)為粒子zi初始速度的取值。

3.2.2 評(píng)價(jià)函數(shù)

3.2.3 個(gè)體和全局最優(yōu)粒子

根據(jù)粒子位置向量排序生成有效揀選作業(yè)路徑后計(jì)算其所花費(fèi)的時(shí)間代價(jià)來確定的個(gè)體和全局最優(yōu)粒子，即選擇花費(fèi)的時(shí)間代價(jià)最小的粒子作為個(gè)體和全局最優(yōu)粒子。3.2.4 粒子群模型及參數(shù)

采用慣性權(quán)重線性遞減粒子群模型，慣性權(quán)重w從0.9線性遞減到0.4，學(xué)習(xí)因子c1和c2取值為2，粒子鄰域大小取全部粒子種群。

3.3 基于模擬退火的粒子群優(yōu)化算法

模擬退火算法（Simulated Annealing，SA）是局部搜索算法的擴(kuò)展，它不同于局部搜索之處是它以一定的概率選擇鄰域中適應(yīng)度值高的狀態(tài)，理論上來說，它是一個(gè)全局優(yōu)化算法。

圖2 m=50，maxIteration=100時(shí)的計(jì)算結(jié)果

圖3 m=50，maxIteration=200時(shí)的計(jì)算結(jié)果

圖4 m=50，maxIteration=500時(shí)的計(jì)算結(jié)果

圖5 m=50，maxIteration=1000時(shí)的計(jì)算結(jié)果

模擬退火法出發(fā)點(diǎn)是利用物理退火過程與優(yōu)化問題間的相似性，將優(yōu)化目標(biāo)看作退火過程中金屬的能量狀態(tài)，模擬金屬退火過程，尋求目標(biāo)函數(shù)最優(yōu)解。模擬退火法從某一初始溫度出發(fā)，伴隨系統(tǒng)溫度的不斷降低，在全局解空間中隨機(jī)尋找最優(yōu)解，不但接受對(duì)目標(biāo)函數(shù)值有改善的好狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)值惡化的劣狀態(tài)，從而實(shí)現(xiàn)大范圍粗略搜索與局部精細(xì)搜索的結(jié)合?；玖Ｗ尤核惴ㄖ?，雖然粒子速度作了限制，不會(huì)變化太大，但位置更新未作限制，就有可能新的位置會(huì)變得很壞，引起收斂速度緩慢，所以要對(duì)更新的位置作限制。論文引入模擬退火思想，計(jì)算粒子位置更新前后目標(biāo)函數(shù)值的變化量ΔE，若ΔE≤0，接收新值；否則，若exp(-ΔE/T)>rand（0，1）（T為模擬退火初始控制參數(shù)，模擬退火系數(shù)α=0.99），也接受新值；否則就拒絕。

4 實(shí)驗(yàn)仿真與結(jié)果

自動(dòng)化立體倉庫其貨架及堆垛機(jī)的參數(shù)設(shè)定為：b=1m，h=1m，vx=3m/s，vy=1m/s。由于受揀選臺(tái)機(jī)械強(qiáng)度的限制，單次揀選作業(yè)揀選的貨位數(shù)一般小于100個(gè)。隨機(jī)產(chǎn)生30個(gè)貨位點(diǎn)的揀選單，各貨位點(diǎn)坐標(biāo)如下：{（0,0），（33,5），（31,7），（3,9），（8,2），（14,6），（44,5），（0,7），（23,1），（48,1），（58,6），（25,0），（32,5），（46,5），（30,8），（29,7），（4,5），（70,9），（57,3），（66,8），（53,3），（19,8），（18,7），（55,4），（65,5），（52,1），（10,9），（13,1），（64,9），（71,1）}，應(yīng)用MATLAB編輯計(jì)算。用模擬退火算法進(jìn)行改進(jìn)，起始溫度T=10000，退火速度a=0.99，最大迭代次數(shù)maxIteration分別為100、200、500和1000，程序各運(yùn)行20次，得到的計(jì)算結(jié)果，在這里不列出所有計(jì)算結(jié)果。不同最大迭代次數(shù)迭代終止時(shí)單次計(jì)算結(jié)果如圖2、3、4、5所示。

從計(jì)算結(jié)果可看出，基于模擬退火的粒子群算法在求解揀選作業(yè)路徑優(yōu)化問題時(shí)，在最大迭代次數(shù)分別為100和1000時(shí)求解效果略差與基本粒子群算法，而在最大迭代次數(shù)為200和500時(shí)略優(yōu)于基本粒子群算法，而且當(dāng)最大迭代次數(shù)maxIteration=1000時(shí)反而沒有最大迭代次數(shù)maxIteration=500時(shí)的求解效果好。分析其原因，是模擬退火中粒子位置更新的限制條件約束了粒子的尋優(yōu)過程，導(dǎo)致有時(shí)粒子沒有移動(dòng)，減少了粒子向最佳位置靠攏的機(jī)會(huì)。所以，應(yīng)用基于模擬退火的粒子群算法在最大迭代次數(shù)為200和500時(shí)可得到比基本粒子群算法較好的效果。

基于模擬退火的粒子群算法在最大迭代次數(shù)設(shè)置合適時(shí)可以得到比基本粒子群算法較好的效果，且算法復(fù)雜度和基本粒子群算法相差不大，只多了一個(gè)粒子位置更新的約束條件。所以，在實(shí)際應(yīng)用中可以考慮應(yīng)用基于模擬退火的粒子群算法來優(yōu)化揀選作業(yè)路徑。

[1]常發(fā)亮,劉增曉,辛征,劉冬冬.自動(dòng)化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐,2007,27(2):139-143.

[2]李梅娟,陳雪波,劉臣奇.基于改進(jìn)蟻群算法揀選作業(yè)優(yōu)化問題的求解[J].計(jì)算機(jī)工程,2009,35(3):219-221.

[3]劉志雄.物流自動(dòng)化倉庫揀選作業(yè)調(diào)度粒子群優(yōu)化研究[J].機(jī)械制造,2010,48(1):66-69.

An optimization methods of order picking path in automated warehouse based on SA

WANG Hai-zhen, PENG Mei-xiang

自動(dòng)化立體倉庫是現(xiàn)代化大生產(chǎn)的必然產(chǎn)物，立體倉庫制造業(yè)是我國新興的高科技產(chǎn)業(yè)。本文分析自動(dòng)化立體倉庫揀挑算法的路徑優(yōu)化問題，提出基于模擬退火的粒子算群算法，求解揀選作業(yè)路徑優(yōu)化問題，得到了較好的效果。

模擬退火；粒子群算法；自動(dòng)化倉庫

王海珍(1974 -)，女，江西樟樹人，講師，本科，研究方向?yàn)樽詣?dòng)化。

TP311

B

1009-0134(2011)5(上)-0090-03

10.3969/j.issn.1009-0134.2011.5(上).31

2010-12-21