基于遺傳算法的倉儲管理優(yōu)化研究

鄭 斌，林 欽

福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108

隨著城市軌道交通行業(yè)的迅速發(fā)展，軌道交通企業(yè)的倉儲需求逐漸增大。軌道交通企業(yè)的倉儲貨物中，機電設(shè)備占了較大比例，機電設(shè)備種類繁多、需求的時間和數(shù)量不一，每當有出庫作業(yè)要求時，備貨速度就成了影響出庫效率的關(guān)鍵環(huán)節(jié)。因此，如何通過優(yōu)化管理方法、提升備貨效率，來降低倉儲管理的成本，成為軌道交通企業(yè)越來越關(guān)心的問題[1]。

1 倉儲管理研究現(xiàn)狀

現(xiàn)階段，軌道交通行業(yè)的倉儲管理中仍然存在不少問題，如儲貨倉庫貨位安排不合理，倉庫基礎(chǔ)設(shè)施較為落后，信息化程度不高等，這些都會導(dǎo)致倉儲管理成本過高。軌道交通企業(yè)的倉庫大多仍采取人工備貨方式。據(jù)研究，在物流訂單的備貨總耗時中，行走時間占總耗時的50%左右，如圖1 所示。針對不同出庫單，采用合適方法優(yōu)化備貨路徑，對提高備貨效率，減少倉儲管理成本具有重要意義。

現(xiàn)階段，針對倉庫備貨路徑優(yōu)化的研究大部分集中在減少揀選時間方面。朱文真等采用遺傳算法和其他禁忌搜索算法結(jié)合，得出立體倉庫的優(yōu)化揀選路徑[2]；李梅娟等研究靜態(tài)情況下立體倉庫貨位的調(diào)度優(yōu)化，設(shè)計出合理的揀選路徑[3]；王占磊分別使用S 型策略和遺傳算法來優(yōu)化揀選路徑[4]。

各個行業(yè)的倉儲存在業(yè)務(wù)、貨物規(guī)格形狀、存儲要求等諸多不同，在實際生產(chǎn)過程中需具體分析實際情況，根據(jù)軌道交通企業(yè)的倉儲特點和要求，實現(xiàn)倉儲管理備貨揀選路徑的優(yōu)化，滿足軌道交通企業(yè)對倉儲的要求。

2 基于遺傳算法的倉儲貨物揀選路徑優(yōu)化

2.1 遺傳算法簡介

遺傳算法是最早提出的模擬生物遺傳系統(tǒng)的算法模型，模擬基因的進化，通過選擇操作與重組操作進行驅(qū)動。算法過程從初始種群開始，先得到一個初始解，然后經(jīng)過反復(fù)調(diào)整優(yōu)化，不斷產(chǎn)生新的可行解，其演化過程模擬自然界生物優(yōu)勝劣汰的法則，直至最終出現(xiàn)最優(yōu)解。遺傳算法的基本過程示意圖如圖2。

2.2 揀貨路徑優(yōu)化模型構(gòu)建

研究對象是某軌道交通企業(yè)的一個倉庫，通過用遺傳算法針對該倉庫建立數(shù)學(xué)模型，來解決倉庫備貨揀選的路徑問題，計算出最優(yōu)揀貨路徑，來達到提升備貨效率的目的。

2.2.1 模型假設(shè)條件

目前遺傳算法在路徑優(yōu)化方面應(yīng)用的頻率較高。對于某軌道交通企業(yè)倉庫的機電設(shè)備揀貨路徑優(yōu)化問題，選取了幾種不同的方法來求解，并對各種方法得到的解進行對比分析，以此來確定最優(yōu)算法和最優(yōu)路徑，達到最大限度降低備貨揀選時間，提高出庫作業(yè)效率的目的?；谘芯康膫}庫和貨物的情況，在構(gòu)建模型時，做如下幾點假設(shè)：

（1）每次揀貨時，如一批揀貨訂單中包含多種貨物，則至少需一個高位叉車來完成揀選作業(yè)。

（2）根據(jù)高位叉車的承載重量來揀選貨物，所揀選的貨物總重量需小于等于高位叉車的承載重量，根據(jù)不同揀選能力分配不同種類零部件。

（3）倉庫內(nèi)的貨架布局為：所有單個貨架水平、雙排并列排放。

（4）所有叉車在行駛和取貨過程中都是勻速的，要取的貨物所存放的位置設(shè)為已知變量。

（5）每個設(shè)備的大小尺寸不同，研究時不考慮尺寸因素，認為設(shè)備大小一致。

2.2.2 模型建立

在優(yōu)化揀選路徑、提高備貨效率方面，主要考慮實現(xiàn)兩個目標，一是揀選時間最短，二是揀選路程最近?？稍O(shè)定模型如式（1）、（2）所示。

2.2.3 遺傳算法步驟設(shè)計

針對訂單備貨揀貨路徑優(yōu)化這一問題，采取遺傳算法來進行最優(yōu)解的計算，以期能較快得到貨物揀選的最優(yōu)路徑，同時節(jié)省揀貨時間。主要步驟如下：

染色體編碼：按完成一次揀選L 種貨品的順序組成一條染色體，采用整數(shù)編碼，每條染色體由L段基因構(gòu)成，每個基因?qū)?yīng)一個貨位，貨位用行、列、層表示。如“{3，6，7，2}”表示揀選路徑為“I/O→貨位3→貨位6→貨位7→貨位2→I/O”。

適應(yīng)度函數(shù)：目標函數(shù)是求最小值，優(yōu)化效果越好的個體適應(yīng)度值越大，因此設(shè)計適應(yīng)度函數(shù)為

交叉算子：染色體中基因表示要選取的貨品，不能缺漏或重復(fù)，因此對兩個染色體分別選取一個交叉點進行基因的配對交換，即采用單點交叉，步驟如圖3 所示：

交叉概率取值為PC=0.85，對每條染色體，根據(jù)隨機數(shù)P∈[0,1]，如果P＜PC則對該染色體進行交叉操作。

所有個體篩選操作：所有個體按照相對種群的適應(yīng)度值由大到小排列，選擇優(yōu)秀染色體遺傳下一代。

計算終止條件：按照一般的參數(shù)取值推薦，種群規(guī)模取值為50，變異概率取值為0.05，迭代次數(shù)到了500 時終止算法。

2.3 仿真分析

研究的軌道交通企業(yè)的倉庫是35m*28m 的立體倉庫，擺放有貨架12 行*12 列*6 層，每個貨位尺寸為2.5m*1.3m*1.6m，叉車通道寬1.2m，叉車在通道的平均水平行駛速度Vx=0.9m/s，垂直移動速度Vy=0.3m/s。

通過模型分析，根據(jù)所研究的倉庫的布局情況[5]，設(shè)定初始參數(shù)。從庫存的機電設(shè)備中選取了20種不同類別的貨物，各類貨物位置及仿真參數(shù)如表1 所示。各貨品在倉庫中的簡易布局如圖3 所示。

表1 仿真數(shù)據(jù)

選用混合型策略、S-shape 策略、最大間隙法和遺傳算法分別對表1 中的具體參數(shù)進行仿真計算，通過MATLAB 編程實現(xiàn)各個方法，求出四種方法的時間和最有路徑，結(jié)果如下：

2.3.1 S-shape 策略

S-shape 路徑優(yōu)化策略先要通過每個揀貨通道，再根據(jù)訂單來選取不同的貨物[6]。通過該策略優(yōu)化后所需要的訂單備貨揀選距離為249m，訂單備貨揀選時間為617 秒，得到的訂單備貨揀選路徑如下，如圖5 所示。

2.3.2 混合型策略

混合型策略包含兩種策略，分別是退回策略與S-shape 策略，將這兩種策略相結(jié)合得到的優(yōu)化策略即為混合型策略[7]，利用該策略進行優(yōu)化后的訂單備貨揀選距離為256m，訂單備貨揀選時間632s，得到訂單備貨揀選路徑如下，如圖6 所示。

2.3.3 最大間隙法

最大間隙法首先要選出訂單貨物所在區(qū)域的通道，然后叉車只走這些通道取貨，直接省略無關(guān)通道[8]。應(yīng)用此法計算叉車揀貨行走距離為253m，訂單備貨揀選耗時627 秒，得到的訂單備貨揀選路徑如下，如圖7 所示。

2.3.4 遺傳算法按照3.2.3 節(jié)的設(shè)計步驟，應(yīng)用遺傳算法進行優(yōu)化后，計算得叉車揀貨行走距離為215m，訂單備貨揀選耗時575s，訂單備貨揀選優(yōu)化的路徑如下，如圖8 所示。

對比四種方法得到的路徑長度和揀選時間如表2 所示。

表2 四種策略結(jié)果對比

通過表2 數(shù)據(jù)對比，遺傳算法相較于其他三種方法，揀選路徑最短，揀選耗時最少，采用遺傳算法優(yōu)化軌道交通企業(yè)的倉庫備貨路徑問題，可以有效的提高訂單的備貨工作效率。

3 結(jié)語

通過分析軌道交通企業(yè)倉儲管理的現(xiàn)狀與存在的問題，針對提升倉儲作業(yè)效率問題，采用遺傳算法對倉儲貨物揀選路徑模型進行了優(yōu)化，通過與仿真結(jié)果的對比，證明采用遺傳算法得出的貨物揀選路徑最優(yōu)解對倉儲作業(yè)效率提升最大。結(jié)論可為后續(xù)倉儲管理優(yōu)化提供理論依據(jù)與實際參考。