基于SA的PSO自動化倉庫揀選作業路徑優化方法

王海珍，彭梅香

（新余學院 工程系，新余 338025）

基于SA的PSO自動化倉庫揀選作業路徑優化方法

王海珍，彭梅香

（新余學院 工程系，新余 338025）

0 引言

現在，自動化立體倉庫已經成為現代物資存取技術與自動化技術相結合的高新技術產物，是物流自動化的顯著標志之一，是現代化大生產的必然產物。為滿足現代生產與物流的需要，就必須采用以計算機控制技術為主要手段組成的自動化立體倉庫。立體倉庫制造業在國外已經發展成為一個新興的高科技產業，取得了可觀的經濟效益。而我國對該課題的研究起步較晚，尤其缺少對物流信息論、輸送系統控制和優化調度的系統性理論研究，使目前的自動化立體倉庫不能實現物流信息化、最優化作業，大大降低了操作效率，產生高投入、低運行速度和低效率的狀態。

1 自動化立體倉庫和揀選作業原理

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

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

圖1 自動化立體倉庫構成圖

2 粒子算法

粒子群算法簡介：粒子群算法（Particle Swarm Optimization，簡稱PSO）最早是在1995年由美國的Eberhart和Kennedy共同提出的，其基本思想受他們早期對許多鳥類的群體行為進行建模與仿真研究結果的啟發，他們的模型及仿真算法主要利用了生物學家Hepper的模型。在粒子群算法中，每個個體稱為一個“粒子”，其實每個粒子代表著一個潛在的解。例如，在一個D維的目標搜索空間中，每個粒子看成是空間內的一個點。設群體由m個粒子構成。m也被稱為群體規模，過大的m會影響算法的運算速度和收斂性。

3 基于模擬退火的粒子群優化算法

3.1 固定貨架堆垛機揀選作業路徑優化問題

自動化立體倉庫的工作效率也主要取決于固定貨架的揀選作業效率，所以固定貨架的揀選作業路徑的優化對自動化立體倉庫的自動化程度的提高有相當重要的作用。假設某自動化立體倉庫的固定貨架子系統共包含13排立體貨架，每排貨架分為10層72列共720個貨位。

固定貨架及堆垛機運行參數設定如下：

設定1：以揀選方式存取貨物時，操作者對某一貨物的揀選時間只與該貨物的種類和數量有關，不隨存取順序的變化而變化；在計算揀選作業時間代價時，忽略貨物存取時間。

設定2：堆垛機在不同貨物之間移動時，在水平方向和垂直方向上都以恒高速運行，其制動和起動過程忽略不計；堆垛機水平運行速度為vx，垂直運行速度為vy；堆垛機運行時在水平方向和垂直方向可以同時運動。

設定3：圖形結點為在單巷道內堆垛機需要存取的貨位點，以坐標（x，y）標志，x和y分別表示貨位點的列號和層號，將貨位點（0，0）視為巷道口，并將其作為整個揀選作業的附加貨位點。單個貨格寬度為b，高度為h。

設定4：在揀選任務全部完成后，揀選貨箱未滿或剛好滿。

3.2 粒子群算法求解揀選作業路徑優化問題

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

3.2.1 粒子位置和速度

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

3.2.2 評價函數

3.2.3 個體和全局最優粒子

根據粒子位置向量排序生成有效揀選作業路徑后計算其所花費的時間代價來確定的個體和全局最優粒子，即選擇花費的時間代價最小的粒子作為個體和全局最優粒子。3.2.4 粒子群模型及參數

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

3.3 基于模擬退火的粒子群優化算法

模擬退火算法（Simulated Annealing，SA）是局部搜索算法的擴展，它不同于局部搜索之處是它以一定的概率選擇鄰域中適應度值高的狀態，理論上來說，它是一個全局優化算法。

圖2 m=50，maxIteration=100時的計算結果

圖3 m=50，maxIteration=200時的計算結果

圖4 m=50，maxIteration=500時的計算結果

圖5 m=50，maxIteration=1000時的計算結果

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

4 實驗仿真與結果

自動化立體倉庫其貨架及堆垛機的參數設定為：b=1m，h=1m，vx=3m/s，vy=1m/s。由于受揀選臺機械強度的限制，單次揀選作業揀選的貨位數一般小于100個。隨機產生30個貨位點的揀選單，各貨位點坐標如下：{（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）}，應用MATLAB編輯計算。用模擬退火算法進行改進，起始溫度T=10000，退火速度a=0.99，最大迭代次數maxIteration分別為100、200、500和1000，程序各運行20次，得到的計算結果，在這里不列出所有計算結果。不同最大迭代次數迭代終止時單次計算結果如圖2、3、4、5所示。

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

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

[1]常發亮,劉增曉,辛征,劉冬冬.自動化立體倉庫揀選作業路徑優化問題研究[J].系統工程理論與實踐,2007,27(2):139-143.

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

[3]劉志雄.物流自動化倉庫揀選作業調度粒子群優化研究[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

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

模擬退火；粒子群算法；自動化倉庫

王海珍(1974 -)，女，江西樟樹人，講師，本科，研究方向為自動化。

TP311

B

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

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

2010-12-21