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

鄭 斌，林 欽

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

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

1 倉(cāng)儲(chǔ)管理研究現(xiàn)狀

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

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

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

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

2.1 遺傳算法簡(jiǎn)介

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

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

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

2.2.1 模型假設(shè)條件

目前遺傳算法在路徑優(yōu)化方面應(yīng)用的頻率較高。對(duì)于某軌道交通企業(yè)倉(cāng)庫(kù)的機(jī)電設(shè)備揀貨路徑優(yōu)化問(wèn)題，選取了幾種不同的方法來(lái)求解，并對(duì)各種方法得到的解進(jìn)行對(duì)比分析，以此來(lái)確定最優(yōu)算法和最優(yōu)路徑，達(dá)到最大限度降低備貨揀選時(shí)間，提高出庫(kù)作業(yè)效率的目的。基于研究的倉(cāng)庫(kù)和貨物的情況，在構(gòu)建模型時(shí)，做如下幾點(diǎn)假設(shè)：

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

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

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

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

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

2.2.2 模型建立

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

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

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

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

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

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

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

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

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

2.3 仿真分析

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

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

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

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

2.3.1 S-shape 策略

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

2.3.2 混合型策略

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

2.3.3 最大間隙法

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

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

對(duì)比四種方法得到的路徑長(zhǎng)度和揀選時(shí)間如表2 所示。

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

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

3 結(jié)語(yǔ)

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