吳 炳，瞿 暢

（南通大學機械工程學院，江蘇 南通 226019）

1 引言

近年來，隨著鋁加工工業(yè)的飛速發(fā)展，鋁加工材料特別是長直桿件鋁擠壓型材對現(xiàn)代物流管理提出了新要求。適用于存儲長直桿件的懸臂梁式立體倉庫的出現(xiàn)，徹底改變了鋁型材企業(yè)倉儲的落后面貌。

立體倉庫的工作效率主要受貨位分配的影響[1]，為了提高效率，文獻[2]提出以減少堆垛機運行時間以及單位載荷為目標的分配規(guī)則。文獻[3]為解決立體倉庫的貨位分配與交叉存取問題，提出停留持續(xù)時間的共享存儲原則，以此來減少堆垛機等待時間，提高倉庫運行效率。依照分配原則而進行的優(yōu)化算法不僅可以充分利用存儲空間提高存儲效率，而且能使貨架受到良好的受力承載，保證其安全性能[4-5]。文獻[6]提出的并列選擇單親遺傳算法，對優(yōu)化后貨位對應的揀選效率及貨架穩(wěn)定性有明顯的提高?？紤]倉庫與貨物的特殊性來制定分配規(guī)則及優(yōu)化算法，是貨位分配首要解決的問題。針對鋁型材尺寸長、重量大的特點，提出了適用于懸臂梁式貨架倉庫的貨位分配策略，從提高入庫效率，降低貨架重心、保持貨架平衡以提高倉庫安全性能為出發(fā)點，構建懸臂梁式立體倉庫入庫貨位優(yōu)化的數(shù)學模型。結合GA 算法與SA 算法的優(yōu)點，設計了SAGA 算法來求解模型，尋找合理的分配貨位。

2 倉庫布局

自動化立體倉庫的布局是影響倉儲調度效率的重要因素[7]，倉庫合理的布局不僅滿足倉儲需要，方便操作人員使用，而且也直接影響著貨物的貨位分配。根據(jù)某鋁型材企業(yè)庫房的實際情況。構建的懸臂梁式立體倉庫平面示意圖，如圖1 所示。堆垛機從I/O 端口處出發(fā)，沿X 方向是倉庫的排方向，沿Y 方向是倉庫的列方向，沿Z 方向是倉庫的層方向。堆垛機運行軌跡在圖中已標出，在I/O 端口處取得貨物，分別沿X 方向、Y 方向和Z 方向運行到貨物對應的位置，完成作業(yè)后回到I/O 進行下一次任務循環(huán)。

圖1 鋁型材立體倉庫示意圖Fig.1 The Diagram of Aluminum Three-Dimensional Warehouse

3 多目標優(yōu)化模型建立

根據(jù)鋁型材立體倉庫的特點，以提高貨架安全性能為主要目標，依據(jù)入庫效率和貨架穩(wěn)定性原則確立優(yōu)化目標，建立合理的多目標貨位優(yōu)化數(shù)學模型。

3.1 模型假設

為了便于模型的建立，現(xiàn)對倉庫邊界提出以下假設：（1）假設倉庫出入庫端口為唯一端口，且堆垛機每次只取一次貨物；（2）假設貨架貨格空間為長方體，貨物與貨格尺寸相匹配；（3）堆垛機勻速運行，且存取動作耗時不計；（4）存放有貨物的貨格不再存放其他貨物。

3.2 模型建立

假設鋁型材立體倉庫沿X 方向共有a 排，沿Y 方向共有b列，沿Z 方向共有c 層，其中離地面最近的一層為第一層，離出入端口最近的為第一排、第一列，（i，j，k）為貨物在倉庫中的位置，即貨物在倉庫i 排j 列k 層。為方便問題的描述，對數(shù)學模型中的符

號作如下定義：

3.2.1 效率分析

懸臂梁式立體倉庫的入庫效率關系到倉庫的倉儲性能，在不改變現(xiàn)有堆垛機性能的基礎上，提高倉庫出入庫效率的關鍵是減少堆垛機的行程。若貨物存放于貨位（i，j，k），則堆垛機在X 方向運行路程為在Y 方向運行路程為jb，在Z 方向運行路程為（k-1）h，由此可得到堆垛機擺放該貨物的運行時間。累計所有貨物的運行時間f1，建立效率數(shù)學模型如下：

3.2.2 穩(wěn)定分析

懸臂梁式立體貨架存儲的多為尺寸長、重量大的貨物，在此種類型倉庫中進行貨位分配需要考慮其穩(wěn)定性。懸臂式倉庫貨架的穩(wěn)定與否取決于貨架重心高低。將較重的貨物放入低層、較輕貨物放入高層，使得貨架的整體重心最低。參照效率分析，累計貨物重心f2，建立貨架穩(wěn)定數(shù)學模型如下：

3.2.3 平衡分析

考慮到貨物重載荷及懸臂梁式貨架的結構特點，需著重考慮貨架的平衡，以確保倉庫有足夠的安全系數(shù)。因此，在貨位分配中，應最大限度地將質量相近的貨物放入懸臂式貨架的兩側，使得整個倉庫工作貨架的兩側懸臂有最小的質量差。累計貨架兩側的質量差f3，建立貨架平衡模型如下：

3.3 權重系數(shù)的分配

上述針對貨位分配優(yōu)化的數(shù)學模型屬于多目標優(yōu)化問題，求解較為復雜。為方便求解，采用加權法對三個優(yōu)化目標函數(shù)分別賦以權重 α、β 和 γ，并使得 α+β+γ=1。

權重系數(shù)的選取受主觀因素影響，為使倉庫獲得最大安全系數(shù)[8]，目標函數(shù)權重系數(shù)應滿足α＜β＜γ，為使定性因素定量化，采用層次分析法（AHP）來確立權重系數(shù)，AHP 的使用流程與步驟，如圖2 所示。應用AHP 方法時，規(guī)定uij表示ui對uj的相對重要性數(shù)值（ui和uj表示各權重），其中i，j∈｛1，2，…，N｝，uij的取值通常用（1～9）標度方法[9]，如表1 所示。

圖2 AHP 的步驟流程圖Fig.2 Step Flow Diagram of AHP

表1 判斷矩陣標度及其定義Tab.1 Judgement Matrix Scale and Its Definition

根據(jù)上述定義及標度，構造權重系數(shù)α、β 以及γ 的取值判斷矩陣P，如下所示：

應用方根法計算權重系數(shù)：

（1）計算判斷矩陣P 的每一行元素的乘積M1，得到：M=［1/35 5/6 42］T

檢驗權重系數(shù)合理性：

（2）引入一致性指標CI=（λmax-N）/N-1。

（3）判斷矩陣隨機一致性比率CR=CI/RI，其中，RI—判斷矩陣隨機一致性指標，3 階矩陣取值為0.58[10]。

這里CR=CI/RI=-1.25 根據(jù)參考文獻[10]，當CR＜0.1 時，判斷矩陣滿足一致性要求，權重系數(shù)合理，因此，權重系數(shù)α、β 與γ 依次確立為0.07，0.2，0.73。同時，對目標函數(shù)進行歸一化處理，以消除目標函數(shù)的量綱，可得優(yōu)化函數(shù)：

4 SAGA 貨位分配算法

SAGA 是結合傳統(tǒng)遺傳算法（GA）與模擬退火算法（SA）的一種混合算法，其能夠很好的跳出局部最優(yōu)解，在解空間中搜索到較好的解集。SAGA 算法實現(xiàn)流程，如圖3 所示。

圖3 SAGA 算法流程示意圖Fig.3 The Algorithm Flow Chart of SAGA

SAGA 算法具體實現(xiàn)步驟如下：

（1）對需要入庫的貨位隨機分配貨位地址，形成初始種群P。對地址采用整數(shù)排列方式進行編碼，一條染色體代表一個貨物的分配地址，染色體中的三個整數(shù)分別代表三個基因，表示該貨物在倉庫位置中的排、列、層。

（2）適應度函數(shù)用來評價每個個體的優(yōu)劣型，由于優(yōu)化目標是越低越好，因此可以直接將優(yōu)化函數(shù)作為評價函數(shù)，將貨物的質量及對應貨位坐標代入到式（6）中，計算數(shù)值即為適應度值。

（3）選擇運算采用輪盤賭算子，計算每個貨物的個體適應度值，比較個體在總體中適應度值的占比，占比越大其在下一代被選中的概率越大。

（4）交叉和變異是模擬退火遺傳算法中產生新個體的核心步驟，交叉從群體中按較大值的概率選擇兩個貨物個體，交換兩個個體染色體中某個或某些基因，即交換貨物的某些坐標數(shù)值以得到新的貨位坐標值。變異是將某個體染色體編碼串中不同基因位進行交換，即交換某個貨物的三維坐標數(shù)值以變異得到新的貨位。交叉變異后，保留較好的個體，得到新種群P1。

（5）為保證搜索能跳出局部空間，對得到的新種群進行“退火”處理。設置初始溫度T0，溫降與迭代次數(shù)相關為Ti=T0/1+i。在種群P1解空間周圍隨機生成新的種群P2，計算P2的增量d=F（P）2-F（P）1，若d＜0，則接受種群P2為當前解；否則按Metropolis原則接受種群，即計算P2的接受概率exp（d/T）i，隨機生成（0，1）區(qū)間上的均勻分布隨機數(shù)rand，若exp（d/T）i＆gt;rand，則接受種群P2為當前解，否則保留P1為當前解。

（6）判斷是否滿足終止條件，滿足則接受當前解為最優(yōu)解并解碼，得到入庫貨物的分配貨位；否則循環(huán)以上操作。

5 仿真實例分析

某鋁型材企業(yè)的懸臂梁式立體倉庫貨架共12 排6 列10層，巷道寬L 為1.2m，倉庫基本參數(shù)信息，如表2 所示。

表2 倉庫基本參數(shù)Tab.2 The Basic Parameters of Warehouse

現(xiàn)有14 種質量不同的鋁型材需要進行入庫處理，貨物的信息，如表3 所示。算法參數(shù)的選取會影響優(yōu)化結果的優(yōu)劣，因此在進行仿真時需要對參數(shù)進行測驗，考慮到仿真結果的客觀性，經過多次對比，選取算法種群規(guī)模NPop=40，迭代次數(shù)G=150，遺傳交叉概率Pc=0.8，變異概率Pm=0.1，初始溫度T0=500。運行SAGA算法進行貨位分配，優(yōu)化前后的目標函數(shù)值，如表4 所示。結果表明，相比于初始位置，經過SAGA 算法優(yōu)化后，堆垛機運行效率提高11.98%，貨架重心降低59.93%，倉庫貨架的平衡性能提高了72.57%。三維立體仿真效果，如圖4 所示。

表3 入庫貨物質量表Tab.3 The Weight List of Goods

表4 優(yōu)化運行結果Tab.4 The Results of Optimization

圖4 貨位優(yōu)化前后對比圖Fig.4 The Location Comparison Diagram Before and After Optimization

針對這里的多目標函數(shù)優(yōu)化問題，SAGA 算法與傳統(tǒng)的GA和SA 算法求解過程對比，如圖5 所示。可以看出，SAGA 迭代至75 代已經趨向于收斂，而GA 需要迭代110 次才能達到相似收斂值，雖然SA 僅僅迭代50 次已能收斂，但其收斂值也大大高于其他兩種算法。

圖5 SAGA 與GA、SA 收斂對比曲線圖Fig.5 Convergence Curves of SAGA、GA、SA

6 結論

旨在解決存儲大尺寸、重載貨物的懸臂梁式貨架倉庫的入庫貨位分配問題。以貨物入庫效率，貨架穩(wěn)定性和倉庫安全性為優(yōu)化目標建立數(shù)學模型，將定性分析轉化為定量分析，并設計了SAGA算法來求解此問題。設計的SAGA 算法相較于傳統(tǒng)GA 算法擁有更快的收斂速度，比傳統(tǒng)SA 算法擁有更好的收斂性能。仿真實例表明，在尺寸長、重量大的鋁型材存儲行業(yè)，應用SAGA 算法來進行貨位分配，不僅能夠提高工作效率，更能保障倉庫的安全性能。