基于訂單體積指數(shù)和需求相關(guān)性的多巷道貨位分配優(yōu)化

何立華， 任海朝

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

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

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

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

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

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

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

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

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

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

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

根據(jù)COI原則和需求相關(guān)性，采用多巷道存儲(chǔ)策略，構(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）表示存儲(chǔ)在各個(gè)貨位上的物料數(shù)量之和與該物料總量相等；式（6）表示允許同一種物料被存儲(chǔ)在不同的貨位上；式（7）表示將需要超過一個(gè)貨位的物料進(jìn)行多巷道存儲(chǔ)；式（8）為0～1變量，xwhgk=1 表示物料w存儲(chǔ)在第h巷道第g列第k層的貨位上，否則xwhgk=0；式（9）為目標(biāo)權(quán)重.

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

式（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)過計(jì)算轉(zhuǎn)化成距離.

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

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

2.1 編碼

根據(jù)貨位分配的目標(biāo)函數(shù)及物料和貨位編號(hào)的特點(diǎn)，采用整數(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個(gè)貨位，將物料放于前∑Sw個(gè)貨位，即可獲得其中一種貨位分配方案. 將貨位順序隨機(jī)打亂，即可獲得其他貨位分配方案.

2.2 初始化種群

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

2.3 適應(yīng)度評(píng)價(jià)

適應(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ī)搜索算法，采用選擇、交叉和變異的操作來進(jìn)行種群的進(jìn)化［20］.

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

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

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

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

變異操作是實(shí)現(xiàn)種群多樣性的重要手段，是跳出局部最優(yōu)進(jìn)行全局尋優(yōu)的重要保證. 在染色體中隨機(jī)生成一個(gè)變異起始點(diǎn)和一個(gè)變異終止點(diǎn)，將兩點(diǎn)之間的基因片段進(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%. 選取某段時(shí)間內(nèi)該倉庫中需要進(jìn)行貨位分配的10種物料進(jìn)行貨位分配.

為了探究本文構(gòu)建模型及設(shè)計(jì)算法的有效性，特針對以下兩種情況進(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.本文運(yùn)用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)化前采用隨機(jī)存儲(chǔ)的分配方式，優(yōu)化過程采用本文提出的考慮訂單體積指數(shù)和需求相關(guān)性，同時(shí)采用多巷道存儲(chǔ)策略進(jìn)行貨位分配，由小、中、大三種規(guī)模的30個(gè)算例優(yōu)化前后結(jié)果及改進(jìn)百分比可知，運(yùn)用本文提出的分配策略及改進(jìn)后的遺傳算法對貨位分配進(jìn)行優(yōu)化求解，針對小、中、大三種倉庫規(guī)模的算例，改進(jìn)效果均較為明顯.

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

表4 物料信息Tab.4 Material information

表5 物料在某段時(shí)間內(nèi)100個(gè)訂單（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中兩個(gè)單目標(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)貨物正在聚集存儲(chǔ)，且整體向靠近倉庫出入口的方向存儲(chǔ). 根據(jù)表2及圖6 d可知，當(dāng)α=0 時(shí)，表示只考慮需求相關(guān)性指標(biāo)；當(dāng)α=1時(shí)，表示只考慮訂單體積指數(shù)指標(biāo)；當(dāng)α的取值在0～1之間時(shí)，表示同時(shí)考慮需求相關(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)，同時(shí)考慮COI原則和需求相關(guān)性原則，并采用多巷道存儲(chǔ)策略進(jìn)行貨位分配. 本文構(gòu)建模型及改進(jìn)算法主要貢獻(xiàn)包括：①解決了僅考慮COI原則產(chǎn)生的具有需求相關(guān)性的物料被存儲(chǔ)在相距較遠(yuǎn)的貨位和靠近倉庫出入口的巷道擁堵問題；②驗(yàn)證了構(gòu)建模型及改進(jìn)的求解算法對小、中、大三種規(guī)模算例的適用性和可行性；③分析了不同權(quán)重取值對最終揀選總距離的影響，為決策者根據(jù)實(shí)際情況進(jìn)行權(quán)重選擇提供了依據(jù).

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