一種貨架共用模式自動化立體倉庫貨位優化

張衍會 邱建東 湯旻安

1(蘭州交通大學機電技術研究所 甘肅 蘭州 730070)2(蘭州交通大學新能源與動力工程學院 甘肅 蘭州 730070)

?

一種貨架共用模式自動化立體倉庫貨位優化

張衍會1邱建東1湯旻安2

1(蘭州交通大學機電技術研究所 甘肅 蘭州 730070)2(蘭州交通大學新能源與動力工程學院 甘肅 蘭州 730070)

為了保證貨物進出，航空貨運站中會采用貨位共用模式的自動化立體倉庫存儲散裝貨物。貨位優化對提升該模式立庫的工作效率，進而保證機場貨運站整體效率有著重要意義。在詳細分析該立庫的工作特點基礎之上，建立數學模型，采用遺傳算法對貨位優化問題進行了研究。仿真和實際現場應用結果表明該算法有效地提高了貨物進出庫的工作效率和存儲安全性。

自動化立體倉庫 貨位優化 遺傳算法

0 引 言

航空貨運隨著經濟全球化得到了快速發展，大型機場貨運站的主要職能就是對貨物進行出入庫、倒庫，其貨物處理的效率直接影響到貨物航空運輸的效率[1]。貨運站內的散裝貨物一般要通過自動化立體倉庫進行暫存處理。自動化立體倉庫最終要實現在耗能最小和成本最低的條件下對貨物的存取，在規定的時間內將具有準確品種和數量的物資提供給客戶[2]。其出入庫操作有以下特點：(1)隨機性：客戶托運貨物到達時間、航班承載貨物的情況、貨物等待提取時間等都具有隨機性。(2)時效性：貨物出入庫均根據航班編排計劃。(3)周轉快：一般貨架存儲日周轉量都在70%左右，貨架區的空貨位一般在30%左右。(4)多樣性：貨物種類繁多，只要滿足自動化立體庫尺寸限重要求，都可能存放。

通用自動化立體倉庫的布局模式如圖1所示，一個巷道內配備一臺堆垛機，兩排貨架。一旦某臺堆垛機故障，其他堆垛機無法救援。圖1中，SC(Stacker-Crane)為堆垛機。

圖1 常用自動化立體庫布局

航空貨運站內散貨出入庫除了滿足效率以外，還需要保證無故障操作的時間。因此，有些航空貨運站選擇了圖2模式的自動化立體倉庫，即堆垛機共用貨架模式。

圖2 貨架共用模式自動化立體庫布局

這種模式減少了貨架數量，但是增加了系統的可靠性和靈活性。堆垛機1不能正常工作時，2#貨架的貨物可由堆垛機2存取。堆垛機2發生故障，可由堆垛機1和堆垛機3分別存取2#和3#貨架貨物。而1#和4#貨架可配備提升高度15米的叉車進行出入庫操作。這種模式的自動化庫，任何一臺堆垛機發生故障時，貨物均能夠正常存取，確保了散貨處理不因為堆垛機故障而中斷，從而保證貨運站正常工作。

自動化立體倉庫出入庫貨物的存取與揀選成本平均能占到運營成本的40%以上，通過優化的庫區和貨位分配策略能大大提高存取頻率，對提高機場貨運站散貨自動化庫的工作效率，具有非常重要的工程意義。

1 自動化立體倉庫的貨位優化研究

自動化立體倉庫存儲貨位優化方面的研究成果比較豐富。楊文強、王盛明使用基于Pareto最優解的遺傳算法解決貨位分配策略優化問題[3-4]，薛亞莉提出了基于遺傳模擬退火的 Memetic算法對立庫調度進行局部優化[5]，邱建東采用非線性學習因子調整優化粒子群算法來改進ETV作業調度[6]，劉權衛利用基于分區改進型作業原則的多種群遺傳算法對優化問題進行求解[7]，陳元文提出了在堆垛機閑時對貨位進行以分類存儲 L 形分區為導向的再分配優化設計[8]。綜合分析這些研究使用的方法，能夠在高維空間搜索近似最優解,但上述研究成果主要是針對通用布局的自動化立體倉庫，對貨架共用模式的自動化立體倉庫，還缺乏針對性的研究工作。

在既有豐富成果的基礎上，結合機場貨運站貨架共用模式自動化立庫結構特點，通過分析其日常作業特點及要求，設計采用遺傳算法對該模式自動化立庫存儲貨位優化進行研究。

2 貨位優化模型與相關基本運算

2.1 優化計算的基本設定

討論貨架結構形式如圖2所示，其特點是堆垛機1和堆垛機2通過2#貨架進行了任務關聯，堆垛機2和堆垛機3通過3#貨架進行了任務關聯，三臺堆垛機之間的貨位分配和取貨任務具有相當的耦合度。

設定1 巷道出入口的坐標設為(0,0)，每一排貨架的編號方法相同，為了區分方便，分別以(z-x-y)表示，其中z表示貨架排數，按照圖2結構，z={1,2,3,4}。x為貨位的列數，y為貨位的層數。堆垛機行走最大速度Vi，提升最大速度Vj,行走加速度ai，提升加速度aj。水平和豎直運動完成一個完整加減速所需最短時間Ti、Tj。運行y層x列需要的時間按照式(1)、式(2)計算。

(1)

(2)

設定2 堆垛機1在1#、2#貨架上進行存取作業，堆垛機2在2#、3#貨架上進行存取作業，堆垛機3在3#、4#貨架上進行存取作業。三臺堆垛機完全等同對待。貨格尺寸一致，所有貨物通過托盤進行存取，每個托盤均相同，且托盤上承載的貨物認為是一件貨物，可用貨位號代表貨物。貨叉從貨位取放貨物的時間一樣。

設定3 為了保持四排貨架存貨均衡，同時也保證三臺堆垛機工作量均衡，分配入庫任務給三臺堆垛機時，如果按照一排貨架存儲量是100%統計，則2#貨架中35%的貨物進出由堆垛機1負責完成，3#貨架中的35%貨物進出由堆垛機3負責完成。2#貨架和3#貨架各自剩余的65%貨物吞吐由堆垛機2負責完成。

設定4 三臺堆垛機執行混合作業模式。在出庫任務隊列和入庫任務隊列均不為空時，執行雙周期模式DC(Double Circle)作業，即堆垛機首先從出入口取貨，然后運行到存貨貨位C1，完成存貨動作后，運行到取貨貨位C2，執行取貨動作，然后運行到出入口將貨物輸出，如圖3所示。

DC模式下的執行時間為：

(3)

(4)

如果有一者為空，則執行堆垛機單周期模式SC(Single Circle)作業，如圖4所示。堆垛機首先從出入口取貨，然后運行到存貨貨位C1，取上貨物以后，運行到出口出貨。并用同樣模式執行C2的取貨任務。

圖4 SC作業模式

堆垛機SC模式的執行時間為：

(5)

(6)

2.2 貨架平均重心高度計算

散貨自動化立體庫在設計時，每一個貨格的額定載重量設計相同。貨架立柱規格、貨架材料、部件及結構的設計都考慮了高貨位滿載對貨架重心及穩定度的影響，考慮了相關的安全系數，故貨架存貨以后的平均重心是不影響貨架安全的。但重心低對貨架各結構件的受力還是有利的，故貨架的平均重心高度可以作為一個次要的考核指標。設已經入庫存放的貨物總數為m，則貨架總體重心高度為：其中Gi是每一個貨物的重量，hi是每一個貨物的高度[9]。

(7)

2.3 建立優化仿真模型

(8)

3 使用遺傳算法進行貨位優化計算

根據對既有研究成果的分析，設計選用遺傳算法求解機場貨運站貨架共用模式的自動化立體倉庫貨位優化問題。

3.1 編碼設計及初始編碼生成

編碼要能夠體現任務分配與執行順序，要有利于三臺堆垛機工作的分配，因此采用實數編碼的方式，使用貨位編號來代表任務，約定空貨位代表一個入庫操作，滿貨位代表一個出庫操作[10]。設計染色體編碼結構如圖5所示。

C1R1C2R2………CxRx

圖5 染色體編碼結構

圖5染色體編碼結構中，Cx、Rx分別代表第x個周期的出庫任務和入庫任務貨位號。根據貨架規模，Cx、Rx均按照3位實數編碼，不足3位的前方補0。染色體由x個片段組成，每個片段為6位，前3位是出庫任務貨位號，后3位是入庫任務貨位號。當Ci=000，表示第i個周期中，沒有出庫任務，當Rj=000，表示第j個周期中，沒有入庫任務。因此，x=max(出入任務數、入庫任務數)，而編碼長度為2x。出入庫任務依泊松分布到達，編碼采用動態長度，為計算效率考慮并結合工程實際，編碼最大長度限定為120位。

任務集中包含有入庫任務和出庫任務，使用復合作業的方式能夠提高效率。隨著出庫任務的執行，能夠給入庫任務提供選擇并符合貨物存儲原則的空貨位是動態變化的。在染色體編碼中實現這種動態變化，就能夠實現任務集中貨位動態優化。初始種群產生流程如圖6所示。

3.2 算法設定

(1) 選擇

采用輪盤賭選擇法選擇，保證適應值高的個體有更高的遺傳機會。

(2) 交叉

為防止算法過早收斂，首先選擇兩個相關性較低的父代個體，相關性可以通過歐幾里得距離計算，交叉則選擇傳統的雙點交叉模式。需要注意的是，隨機產生的切點的位置一定是一個周期貨位編號的首尾位置，不能將貨位編號切斷。結合到本節，交叉切點的位置一定要選擇6的倍數。例如，隨機產生的交叉切點為12和24，則交叉運算如圖7所示。如果交叉運算后，染色體產生了重復貨位編號，意味著要給同一個貨位重復入貨或者從同一個貨位重復出貨，這是非法編碼染色體。產生這種情況時，按照修正最近鄰點策略從相應集合中選擇新的貨位號替換。修正閾值根據貨位編號準則，設定為40。

圖7 雙切點交叉示意

(3) 變異

隨機選擇染色體中的基因段，根據其是入庫貨位還是出庫貨位，從出庫貨位集合或入庫貨位集合中隨機選擇新的貨位編號進行替換。如果產生重復編號，則依舊按照最近鄰點策略從相應集合中選取。如果多次變異生成的種群最優適應度值趨于一致，則進一步加大變異概率，以加速進化防止提前局部收斂。

(4) 解碼與任務分配

運算收斂或者到達迭代次數后，生成最優解的形式都和圖7標識相同，根據指令周期的出庫入庫組合，就能夠將復合指令分配到堆垛機。如果出庫入庫任務數不相同，則需要根據任務編號向堆垛機分配。貨位號1～196分配給堆垛機1，600～796分配給堆垛機3，而200～396則可以分配給堆垛機1或者堆垛機2，400～596可以分配給堆垛機2或者堆垛機3。此時程序設計隨機產生一個1～100的整數，如果該整數大于35，則200～396編號和400～596編號均分配給堆垛機2，如果該隨機整數小于35，則200～396編號分配給堆垛機1，400～596編號均分配給堆垛機3。

3.3 算法流程

step1 根據貨架當前存貨和取貨任務，構造染色體；

step2 初始化各種參數；

step3k=1，產生初始種群Pop(k);

step4 計算個體適應值;

step5 主體進行選擇操作；

step6 主體進行交叉、變異操作，生成Pop(k+1);

step7k++；

step8 如果到終止條件，則輸出解，否則轉step4。

3.4 實例仿真驗證

(1) 工程基本參數

堆垛機水平運行最大速度120 m/min，水平最大加速度0.5 m/s2，載貨臺最大升降速度30 m/min，升降運行最大加速度0.5 m/s2。額定載重量1 000 kg，貨格尺寸1 000×1 200 mm。層間高度1 275 mm，列間距離2 350 mm。貨架為7層28列，總計4排，共計784個貨位。

(2) 設定出入庫任務及空余貨位

任務集隨機給出10個入庫任務，8個出庫任務，出庫任務貨位編號分別為(092、133、296、464、561、750、646、749)。設定貨架空貨位為200個，每個貨架50個，隨機產生。

(3) GA參數設定

染色體編碼長度為60位，種群規模為40，最大迭代次數500次，變異概率0.05，交叉概率0.8，目標權重系數β=0.15。

迭代仿真的結果如圖8所示。從圖8可以看出，最初的幾代遺傳中，種群最優適應值較高，然后能夠迅速收斂，基本在200代左右能夠收斂到最優解。計算時間大約1.5秒，能夠滿足實時性要求。

圖8 種群適應值變化曲線

為驗證算法的優越性，根據假設條件隨機產生出庫入庫任務組合20次，同時使用GA仿真20次。計算每次任務計劃的出入庫總時間，比對結果如表1所示。

表1 試驗對比記錄

通過計算最優出入庫總時間，能夠看出使用本算法能夠比隨機計劃提高13%左右的工作效率。計算時間能控制在3秒以內，能夠滿足現場實時性的要求。

4 結 語

一個大型機場貨運站，一年的貨物吞吐量可以達到50萬噸至上百萬噸。其中散貨的處理量能夠達到10萬噸級的水平。如果提升10%的處理效率，相當于在任何硬件條件、人力配置、工作時間不變的情況下，年多處理萬噸的貨物。這對于機場貨運站而言具有非常現實的工程意義。該算法融合在機場貨運站設備管理系統EMS(Equipment Management System)當中，是其中的核心算法模塊，使用C#語言編程，已經在現場得到了應用，并具有一定的推廣價值。

[1] 季瓊. 基于分配法的機場物流貨運站雙升降式轉運車任務調度研究[J]. 物流技術, 2015, 34(10):128-131.

[2] 王廳長, 邱建東, 商慶健,等. 病毒協同進化遺傳算法在自動化立體倉庫貨位優化中應用的研究[J]. 計算機科學, 2014, 41(s2):35-38.

[3] 楊文強, 鄧麗, 費敏銳,等. 基于改進禁忌搜索的多目標自動化倉庫調度[J]. 計算機集成制造系統, 2013, 19(8):2097-2104.

[4] 王盛明, 盧秉亮. 自動化立體倉庫貨位分配優化研究[J]. 微處理機, 2013, 34(6):46-48.

[5] 薛亞莉, 侯媛彬. 基于優化Memetic算法的立體倉庫貨位優化策略[J]. 計算機測量與控制, 2013, 21(12):3387-3389.

[6] 邱建東, 蔣兆遠, 湯旻安. NLA-PSO算法在機場貨運站ETV調度優化中的研究與應用[J]. 蘭州交通大學學報, 2015, 34(1):65-70.

[7] 劉權衛.自動化立體倉庫貨位分配與任務調度集成研究[D].山東大學,2013.

[8] 陳元文, 吳曉波, 孫耀磊,等. 基于FlexSim的軍隊自動化立體倉庫貨位優化研究[J]. 包裝工程, 2013(19):74-77.

[9] 楊朋, 繆立新, 戚銘堯. 多載具自動化存取系統貨位分配和揀選路徑集成優化[J]. 清華大學學報(自然科學版), 2011(2):261-266.

[10] 李小笠, 劉桂芝, 楊文亮. 基于嵌套分區算法的立體倉庫貨位分配優化[J]. 計算機工程與應用, 2014, 50(2):242-246.

SLOTTING OPTIMIZATION FOR THE AUTOMATED STEREOSCOPIC WAREHOUSE BY SHELF SHARED MODE

Zhang Yanhui1Qiu Jiandong1Tang Min’an2

1(MechatronicT&RInstitute,LanzhouJiaotongUniversity,Lanzhou730070,Gansu,China)2(SchoolofNewEnergyandPowerEngineering,LanzhouJiaotongUniversity,Lanzhou730070,Gansu,China)

In order to ensure input and output of goods, an automated stereoscopic warehouse with a shelf share structure will be used in air cargo station for bulk storage of goods. Slotting optimization is of great significance to improve the efficiency of the warehouse and to ensure the overall efficiency of the airport cargo terminal. Based on the detailed analysis of the working characteristics of the warehouse, a mathematic model is established, and the genetic algorithm is used to optimize the slotting optimization. The results of simulation and practical application show that the algorithm can effectively improve the work efficiency and storage security.

Automated stereoscopic warehouse Slotting optimization Genetic algorithm

2016-06-19。甘肅省自然科學基金項目(1208RJZA292)；蘭州市科技計劃資助基金項目(2013-4-18)。張衍會，碩士，主研領域：智能控制，嵌入式系統。邱建東，副教授。湯旻安，副教授。

TP39

A

10.3969/j.issn.1000-386x.2017.07.048