何立華， 任海朝

（中國石油大學(xué)（華東）經(jīng)濟管理學(xué)院，山東青島 266580）

倉儲作為物流活動中的一個重要環(huán)節(jié)，在制造業(yè)、物流業(yè)中起著承上啟下的作用. 據(jù)統(tǒng)計［1］，揀選作業(yè)時間占整個倉儲作業(yè)時間的30%～40%，揀選成本占倉庫運營成本的65%以上. 不同的貨位分配會對倉庫的揀選效率產(chǎn)生不同影響［2］.

貨位分配問題是經(jīng)典的倉儲管理問題［3］. Wang等［4］最早提出了基于物料的訂單體積指數(shù)（cube-per-order index），即COI原則，一種物料的COI值等于一段時間內(nèi)它的總存儲空間與該段時間內(nèi)的周轉(zhuǎn)率之比. 其值越小越要將該物料存儲在靠近倉庫出入口的貨位上，該指標(biāo)同時考慮了物料所需的總存儲空間和周轉(zhuǎn)率，大大提高了物料的存儲效率. 后來Heskett［5-6］又將COI原則進(jìn)一步應(yīng)用到倉庫布局中. Yang和Nguyen［7］基于COI原則，利用主成分分析對物料進(jìn)行分類分級，并根據(jù)COI系數(shù)進(jìn)行存儲位置分配. 王洋和謝勇［8］提出了基于COI的改進(jìn)分類存儲策略，對貨物先按COI值分類，再按照定位存儲進(jìn)行貨位分配. 李明琨和張楊平［9］將COI儲位分配方法與巷道作業(yè)平衡改進(jìn)策略相結(jié)合，提出絕對分巷道存儲模型和相對平均與最大值控制模型兩種儲位分配改進(jìn)方法.

上述貨位分配主要考慮物料的單一屬性，如訂單體積指數(shù)，沒有從物料的多個屬性進(jìn)行綜合考慮. 僅依靠COI 原則進(jìn)行貨位分配，會出現(xiàn)需求相關(guān)性大的物料被分配到的貨位相距較遠(yuǎn)的情況，從而增加揀選距離. 所以部分文獻(xiàn)以物料之間的需求相關(guān)性為指標(biāo)進(jìn)行優(yōu)化研究. 肖建和鄭力［10］擴展了僅考慮兩個物料成對需求的情況，構(gòu)建相關(guān)數(shù)學(xué)模型，通過遺傳算法進(jìn)行求解. Jane和Laih［11］根據(jù)物料的需求相關(guān)性對其分類，并采用隨機存儲策略分配貨位. 李建斌等［12］建立基于產(chǎn)品出庫頻次和相關(guān)性的優(yōu)化指標(biāo)，構(gòu)建整數(shù)線性規(guī)劃模型，運用模擬退火算法求解. 鄧愛民等［13］基于時間，以貨物出入庫效率高、相似貨物擺放在一起和貨物移動距離最短三個指標(biāo)構(gòu)建模型，并用遺傳算法求解. 周亞云等［14］綜合考慮了物料的需求關(guān)聯(lián)和周轉(zhuǎn)率，基于貨位指派規(guī)則建模并用譜聚類算法求解.

為提高揀選效率，一些學(xué)者拋棄傳統(tǒng)倉儲布局，轉(zhuǎn)為研究揀選效率更高的非傳統(tǒng)倉儲布局，并進(jìn)行貨位分配優(yōu)化. Gue和Meller［15］提出了Flying-V和Fishbone非傳統(tǒng)布局方式. 劉建勝等［16］在Flying-V布局基礎(chǔ)上，考慮貨物出入庫效率最高和貨物存放重心最低，建立多目標(biāo)優(yōu)化模型，并將遺傳算法和粒子群算法結(jié)合進(jìn)行求解. 雖然以上兩種倉儲布局相較于傳統(tǒng)布局降低了倉庫揀選總距離，但也降低了倉庫的空間利用率［17］.

傳統(tǒng)倉儲布局和非傳統(tǒng)倉儲布局大都是窄巷道式，這以最低的成本提高了空間利用率，但可能會使得被高頻揀貨的巷道產(chǎn)生擁堵［18］. 另外，倉庫同時進(jìn)行的多張訂單揀選任務(wù)也可能會導(dǎo)致距離出入口較近的巷道發(fā)生作業(yè)擁堵. 同時，單純依靠COI原則，由于體積差異，可能導(dǎo)致某些需求相關(guān)性大的物料，體積小的被分配到距離出入口較近的貨位，體積大的被分配到距離出入口較遠(yuǎn)的貨位，不利于同時揀貨，影響揀貨效率. 本文采用多巷道存儲策略解決COI原則導(dǎo)致的靠近出入口的巷道擁堵問題，同時考慮需求相關(guān)性，解決COI原則導(dǎo)致的相關(guān)性大的物料因體積差異被分配到的貨位相距較遠(yuǎn)的問題.

本文以倉庫中的物料和貨位為研究對象，以物料的訂單體積指數(shù)和需求相關(guān)性為優(yōu)化指標(biāo)，采用多巷道存儲策略，以訂單體積指數(shù)加權(quán)的最小距離和需求相關(guān)物料所處貨位之間的最小距離之和為目標(biāo)，建立數(shù)學(xué)模型，并通過改進(jìn)的遺傳算法進(jìn)行求解.

1 貨位分配模型構(gòu)建

對倉庫布局做如下假設(shè)：

每條巷道左右兩側(cè)各有一排貨架，貨架為背靠背式；允許一貨多位；貨位至出入口的距離計算采用城市距離，且規(guī)定同一巷道同一列的貨位到出入口的距離相同，即不考慮層數(shù)對貨位到出入口距離的影響.

模型參數(shù)設(shè)定如下：

根據(jù)COI原則和需求相關(guān)性，采用多巷道存儲策略，構(gòu)建如下目標(biāo)函數(shù).

1）最小化COI加權(quán)下物料所處貨位到倉庫出入口的距離：

2）最小化具有需求相關(guān)性的物料所處貨位之間的距離：

將目標(biāo)函數(shù)（1）和（2）加權(quán)轉(zhuǎn)化成單目標(biāo)函數(shù)：

約束條件：

式（4）表示分配到該貨位的所有物料的總體積不大于該貨位的可利用空間；式（5）表示存儲在各個貨位上的物料數(shù)量之和與該物料總量相等；式（6）表示允許同一種物料被存儲在不同的貨位上；式（7）表示將需要超過一個貨位的物料進(jìn)行多巷道存儲；式（8）為0～1變量，xwhgk=1 表示物料w存儲在第h巷道第g列第k層的貨位上，否則xwhgk=0；式（9）為目標(biāo)權(quán)重.

其中，相關(guān)參數(shù)計算如下：

式（10）表示第h巷道第g列貨位距離出入口最近的城市距離；式（11）表示兩種物料所處的貨位之間的距離；式（12）表示物料w的訂單體積指數(shù)；式（13）表示物料之間的需求相關(guān)度［18］.

2 貨位分配模型求解

本文考慮的兩種距離因素下的貨位分配優(yōu)化問題，本質(zhì)是旅行商問題的延伸，是NP難問題，相較于經(jīng)典的旅行商問題，本文所研究的優(yōu)化問題具有以下復(fù)雜性：

1）參數(shù)眾多. 需要將眾多物料及倉庫參數(shù)經(jīng)過計算轉(zhuǎn)化成距離.

2）目標(biāo)特殊. 具有兩個關(guān)于距離的優(yōu)化指標(biāo).

貨位優(yōu)化問題是一個NP難問題，所以只能使用啟發(fā)式算法進(jìn)行求解［19］. 因為該問題涉及參數(shù)眾多、目標(biāo)特殊以及該模型會產(chǎn)生非常多的可行解，同時也會產(chǎn)生很多局部最優(yōu)解，尋找這些可行解并從中尋求最優(yōu)解的工作量較大，要求求解算法具有良好的局部搜索能力和全局搜索能力，采用改進(jìn)的遺傳算法就能很好地解決這一問題.

2.1 編碼

根據(jù)貨位分配的目標(biāo)函數(shù)及物料和貨位編號的特點，采用整數(shù)編碼的方式. 每條染色體由貨位所處的巷道數(shù)、列數(shù)及層數(shù)組成. 一條染色體表示一種貨位分配的可行解，即一種可行的貨位分配方案. 倉庫布局平面圖如圖1所示，假設(shè)有9條巷道，每條巷道兩側(cè)共20列貨架，每列貨架有3層. 基因編碼示意圖如圖2所示.

圖1 倉庫布局平面圖Fig.1 Schematic diagram of warehouse layout

圖2 基因編碼示意圖Fig.2 Schematic diagram of gene coding

在上述示意圖中，如（1，1，1）表示位于第一巷道第一列第一層的貨位. 根據(jù)物料數(shù)量所需的∑Sw個貨位，將物料放于前∑Sw個貨位，即可獲得其中一種貨位分配方案. 將貨位順序隨機打亂，即可獲得其他貨位分配方案.

2.2 初始化種群

由于本文涉及的貨物種類和貨位數(shù)量較多，問題的可行解也會非常多，為了保證遺傳算法的全局搜索能力，保證其具有遍歷整個解空間的能力，采用隨機產(chǎn)生的初始種群，在初始種群的基礎(chǔ)上進(jìn)行后續(xù)遺傳操作. 本文選取種群規(guī)模大小為200.

2.3 適應(yīng)度評價

適應(yīng)度函數(shù)在進(jìn)化過程中起到優(yōu)勝劣汰的作用. 適應(yīng)度函數(shù)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解. 遺傳算法中的適應(yīng)度值要求越大越好，其值越大越利于被選中. 本文目標(biāo)函數(shù)為最小化，所以采用目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù). 適應(yīng)度函數(shù)如下：

2.4 遺傳操作

遺傳算法（Genetic Algorithm，GA）是一種模擬生物進(jìn)化的隨機搜索算法，采用選擇、交叉和變異的操作來進(jìn)行種群的進(jìn)化［20］.

選擇操作，輪盤賭和錦標(biāo)賽選擇是常用的選擇算子，但若僅采用輪盤賭選擇，有時會出現(xiàn)即使適應(yīng)度值較大的個體也不被選中的情況，而僅采用錦標(biāo)賽選擇，不論是二元錦標(biāo)賽還是四元錦標(biāo)賽，每次選擇出的個體數(shù)量又有限. 為了保證算法的全局搜索能力且盡可能快的使算法收斂，對選擇操作進(jìn)行改進(jìn)，提出輪盤賭選擇和錦標(biāo)賽選擇相結(jié)合的選擇算子，即同時采用輪盤賭和錦標(biāo)賽選擇，對分別通過兩種算子選擇出的最優(yōu)個體進(jìn)行比較，然后再次選擇出二者中適應(yīng)度值較大的個體，進(jìn)而提高算法的全局搜索能力并加快算法的收斂. 圖3為改進(jìn)的選擇算子示意圖.

圖3 輪盤賭+錦標(biāo)賽選擇算子示意圖Fig.3 Schematic diagram of roulette+tournament selection operator

交叉操作，傳統(tǒng)的兩點交叉已不再適用于本文研究問題，若直接簡單交換兩個父代中交叉點之間的基因片段，則會在同一個父代中出現(xiàn)基因重復(fù)的情況，進(jìn)而導(dǎo)致子代出現(xiàn)不可行解，因此本文提出改進(jìn)型兩點交叉，交叉操作示意圖如圖4所示. 父代1和父代2為兩個可行解，隨機生成兩個交叉點，兩個父代交換兩個交叉點之間的基因片段，如果交換的基因片段中帶有和原來父代個體上相同的基因片段，則將原有父代基因中重復(fù)的基因用交換前的基因進(jìn)行替換.

圖4 交叉操作示意圖Fig.4 Schematic diagram of cross operation

變異操作是實現(xiàn)種群多樣性的重要手段，是跳出局部最優(yōu)進(jìn)行全局尋優(yōu)的重要保證. 在染色體中隨機生成一個變異起始點和一個變異終止點，將兩點之間的基因片段進(jìn)行完全倒置. 變異操作示意圖如圖5.

圖5 變異操作示意圖Fig.5 Schematic diagram of mutation operation

2.5 終止操作

進(jìn)化終止條件為達(dá)到固定的進(jìn)化代數(shù)，當(dāng)?shù)螖?shù)達(dá)到規(guī)定次數(shù)之后，停止迭代并輸出最優(yōu)解. 本文選取MAXGEN=250.

3 算例分析

本節(jié)選取一家汽車電子產(chǎn)品制造企業(yè)的倉庫進(jìn)行算例分析.

3.1 倉庫布局及物料信息

該制造企業(yè)倉庫共有9條巷道，巷道寬2 m，每條巷道兩側(cè)共有20列貨架，每列貨架高3層，倉庫布局平面圖如圖1所示，貨位長1.2 m，寬0.8 m，高0.5 m，空間利用率為90%. 選取某段時間內(nèi)該倉庫中需要進(jìn)行貨位分配的10種物料進(jìn)行貨位分配.

為了探究本文構(gòu)建模型及設(shè)計算法的有效性，特針對以下兩種情況進(jìn)行求解：

1）不同倉庫規(guī)模對貨位分配結(jié)果的影響，即改變倉庫的巷道數(shù)，選取小、中、大三種倉庫規(guī)模，相應(yīng)地，n=2、n=4 和n=9 .

2）不同權(quán)重取值對最終貨位分配結(jié)果的影響，即α從0每隔0.1取值到1，相應(yīng)地，β從1每隔0.1取值到0.本文運用MATLAB2018對模型進(jìn)行仿真.

3.2 結(jié)果分析

本文針對小、中、大三種倉庫規(guī)模的不同權(quán)重取值（其中β=1-α）進(jìn)行比較分析，結(jié)果如表1～3所示.

表1 小規(guī)模算例的求解結(jié)果（n=2）Tab.1 The solution result of a small scale calculation example

表2 中規(guī)模算例的求解結(jié)果（n=4）Tab.2 The solution result of a medium scale calculation example

表3 大規(guī)模算例的求解結(jié)果（n=9）Tab.3 The solution result of a large scale calculation example

優(yōu)化前采用隨機存儲的分配方式，優(yōu)化過程采用本文提出的考慮訂單體積指數(shù)和需求相關(guān)性，同時采用多巷道存儲策略進(jìn)行貨位分配，由小、中、大三種規(guī)模的30個算例優(yōu)化前后結(jié)果及改進(jìn)百分比可知，運用本文提出的分配策略及改進(jìn)后的遺傳算法對貨位分配進(jìn)行優(yōu)化求解，針對小、中、大三種倉庫規(guī)模的算例，改進(jìn)效果均較為明顯.

下面給出了一個中規(guī)模算例的具體數(shù)據(jù)及結(jié)果. 物料信息如表4所示，物料在該段時間內(nèi)的100個歷史訂單中被訂購情況如表5所示，表6為物料之間的需求相關(guān)系數(shù).

表4 物料信息Tab.4 Material information

表5 物料在某段時間內(nèi)100個訂單（O1～O100）中被訂購情況Tab.5 Material being ordered in 100 orders within a certain period of time

表6 物料需求相關(guān)系數(shù)(rwiwj)Tab.6 Correlation coefficient of material demand

根據(jù)圖6中兩個單目標(biāo)及總目標(biāo)函數(shù)的進(jìn)化趨勢可以看出，進(jìn)化前30代目標(biāo)值處于下降趨勢且進(jìn)化速度較快，而120代后目標(biāo)值趨于穩(wěn)定數(shù)值，說明了改進(jìn)的算法具有良好的局部和全局搜索能力. 圖6 a、b、c變化趨勢說明，隨著進(jìn)化代數(shù)的增加，相關(guān)貨物正在聚集存儲，且整體向靠近倉庫出入口的方向存儲. 根據(jù)表2及圖6 d可知，當(dāng)α=0 時，表示只考慮需求相關(guān)性指標(biāo)；當(dāng)α=1時，表示只考慮訂單體積指數(shù)指標(biāo)；當(dāng)α的取值在0～1之間時，表示同時考慮需求相關(guān)性和訂單體積指數(shù). 由目標(biāo)權(quán)重的變化可知，其取值不同，對總目標(biāo)函數(shù)影響較大，即對揀選總距離影響較大，但不同權(quán)重取值對改進(jìn)百分比影響不大. 表7為優(yōu)化前后的貨位分布情況.

圖6 迭代圖Fig.6 Iterative figure

表7 優(yōu)化前后的貨位分布情況Tab.7 Goods location distribution before and after optimization

4 結(jié)論

本文對現(xiàn)有貨位分配策略進(jìn)行優(yōu)化改進(jìn)，同時考慮COI原則和需求相關(guān)性原則，并采用多巷道存儲策略進(jìn)行貨位分配. 本文構(gòu)建模型及改進(jìn)算法主要貢獻(xiàn)包括：①解決了僅考慮COI原則產(chǎn)生的具有需求相關(guān)性的物料被存儲在相距較遠(yuǎn)的貨位和靠近倉庫出入口的巷道擁堵問題；②驗證了構(gòu)建模型及改進(jìn)的求解算法對小、中、大三種規(guī)模算例的適用性和可行性；③分析了不同權(quán)重取值對最終揀選總距離的影響，為決策者根據(jù)實際情況進(jìn)行權(quán)重選擇提供了依據(jù).

由于優(yōu)化目標(biāo)僅是從提高揀選效率角度出發(fā)，所以構(gòu)建的優(yōu)化模型僅僅是有關(guān)距離的函數(shù)，未考慮貨位分配過程中的其他影響因素，如時間、成本等，未來的研究可以從多個維度綜合考慮來提升倉庫揀選效率.