基于免疫算法的物流揀貨路徑優(yōu)化問題的研究

賈 鵬 管 錚 徐善頂* 吳天豪

（1、南京工程學(xué)院電力工程學(xué)院，江蘇 南京210000 2、南京工程學(xué)院數(shù)理部，江蘇 南京210000 3、南京工程學(xué)院機械工程學(xué)院，江蘇 南京210000）

當(dāng)今社會的互聯(lián)網(wǎng)技術(shù)在不斷地高速革新，也因此造成了整個電商市場的蓬勃發(fā)展。而眾多電商公司的客戶會下達很多的訂單，由此造成了訂單下達倉庫后，商品開始下架出售。而在倉庫中有多個貨架，每個貨架有多個貨格。每個貨格中最多擺放一種商品，而商品可以擺放在多個貨格中。

電商公司客戶訂單下達倉庫后，商品開始下架出庫，出庫主要包含5 個流程：

定位→組單→揀貨→復(fù)核→打包

定位：訂單下達倉庫后，確定商品下架的貨格和每個貨格下架的商品數(shù)量。

組單：將多個客戶的訂單合并，構(gòu)成任務(wù)單。

揀貨：揀貨員在某個復(fù)核臺領(lǐng)揀貨車及任務(wù)單，然后按推薦順序依次訪問任務(wù)單中商品所在的貨格，并將商品放在揀貨車上，再送往某個復(fù)核臺。到達復(fù)核臺后，揀貨員繼續(xù)領(lǐng)取揀貨車和任務(wù)單，開始下一個任務(wù)單的揀貨流程。

復(fù)核和打包：揀貨車放到復(fù)核臺對任務(wù)中商品復(fù)核，審核是否多揀或者漏揀商品，然后將商品按照訂單打包。

1 揀貨路徑距離模型的基礎(chǔ)

在物流中心的某個倉庫中，有著13 個復(fù)核臺，4 排貨架，其中每排25 組貨架，每組2 個貨架，共50 個貨架，每個貨架包含15 個貨格。水平方向每組貨架之間的距離為1500 毫米，豎直方向相鄰兩排貨架縱向距離為2000 毫米，貨格長寬都是800 毫米，復(fù)核臺長寬都是1000 毫米。由于貨架和復(fù)核臺均為障礙物，揀貨員們在此處時均不能通行，其余位置均可通行。為了方便距離的計算，此處不考慮揀貨車的尺寸，貨架和復(fù)核臺高度。具體的3000 個貨格與13 個復(fù)核臺的示意圖如圖1 所示。

圖1

本模型有關(guān)貨架，貨格，復(fù)核臺，任務(wù)單的數(shù)據(jù)來源于第10屆Mathorcup 挑戰(zhàn)杯C 題，我們在計算揀貨員在倉庫中揀貨時的行走距離時，將其分成復(fù)核臺與復(fù)核臺、復(fù)核臺與貨格、貨格與貨格三種類型。而復(fù)核臺之間的距離可以簡化為其坐標(biāo)差的絕對值直接得出，復(fù)核臺與貨格之間的距離分成7 小類將其求出，貨格與貨格之間的距離分成5 小類來解出，最后將這三種類型的距離進行匯總，得出一個3013×3013 的距離矩陣。求解的部分結(jié)果如圖2 所示。

圖2

2 問題分析

我們已經(jīng)了解到所有的復(fù)核臺正常工作，任務(wù)單T0001 等待揀貨，如何給一個揀貨員P 規(guī)劃出理想的揀貨路線，從而獲得最短的出庫時間，這是我們現(xiàn)在需要解決的問題。該問題的約束條件是固定起點為復(fù)核臺FH10，終點為運行正常的復(fù)核臺FH01-FH13，任務(wù)單的數(shù)量僅有1 個（T0001）。我們可以看出這是一個典型旅行商（TSP）的問題，在眾多的非線性約束條件下，可以通過免疫算法來求解出最優(yōu)的揀貨路線和出貨最短時間。

3 免疫模型的建立

免疫算法是一種對多峰值函數(shù)進行多峰值檢索，經(jīng)過多次迭代，尋找全局最優(yōu)的算法。為了抵御外來病毒的入侵，免疫系統(tǒng)對于其引入的抗原則產(chǎn)生相應(yīng)的抗體。為了衡量抗原和抗體之間的匹配程度，我們引入親和力的概念來判別出最好的匹配效果。因此，免疫算法適合該類路徑優(yōu)化問題。

下面基于本倉內(nèi)揀貨路徑優(yōu)化問題，建立免疫算法的模型：

（1）通過對采集的冀北地區(qū)中生代巖漿巖標(biāo)本進行分類、測量密度等操作，基于統(tǒng)計數(shù)據(jù)得出：冀北地區(qū)偏基性的巖漿巖密度較高，而偏酸性巖漿巖的密度較低。兩種巖漿巖密度在空間分布上呈現(xiàn)一定的規(guī)律。

（1）抗原的識別階段：輸入目標(biāo)函數(shù)和各種約束作為免疫算法的抗原；

（2）初始抗體的產(chǎn)生階段：在解空間中用隨機方法產(chǎn)生抗體；

（3）適應(yīng)度（親和力）的計算：

抗體V 和抗原W 之間的適應(yīng)度公式為：

axv=optw

抗體m 和抗體n 之間的適應(yīng)度公式為：

（4）記憶單元的更新：將適應(yīng)度高的個體加入到記憶庫中，這保證了對優(yōu)良解的保留，使能夠延續(xù)到后代中；

（5）基于解的選擇：選入適應(yīng)度較高的個體，記其產(chǎn)生后代。所以適應(yīng)度較低的個體將受到抑制；

（6）產(chǎn)生新抗體：通過交叉，變異，逆轉(zhuǎn)等算子作用，選入的父代將產(chǎn)生新一代抗體；

（7）終止條件：條件滿足，則終止；不滿足，跳轉(zhuǎn)到第（3）步。

圖3

4 模型的求解

我們分別以13 個復(fù)核臺作為終點，得到的最短遍歷距離依次為：

399200，415600，438200，433700，429200，424700，420200，4 18900，454400，453500，449000，448000，452500。

由上數(shù)據(jù)比較，可知：當(dāng)起點固定為復(fù)核臺FH10，終點為復(fù)核臺FH01 時，路程s 最短，為399200mm，即399.2m。

具體的揀貨路線如下：

圖4

下面我們求解出庫花費的時間：

（1）路程時間t：

由上可得，最短路程smin=399200mm；

因此，

（2）取貨時間t2：

由表中的數(shù)據(jù)可知，商品件數(shù)為1 的有13 個貨格；

商品件數(shù)為2 的有4 個貨格；

商品件數(shù)為3 的有6 個貨格。

因此，t2=1×5×13+2×5×4+3×4×6=177s。

（3）復(fù)核和打包時間t3：

由于任務(wù)單t0001 打包了合計10 個訂單，

因此，t3=10×30s=300s

綜上所述， 出庫花費的時間為：Tmin=t1+t2+t3=266.13+177+300=743.13s。

5 結(jié)論

通過建立免疫算法的模型，在解決物流規(guī)劃問題的時候是非常合理的。比起常見的優(yōu)化算法，例如蟻群算法、模擬退火算法、最小粒子群算法，該算法的收斂速度更快，在產(chǎn)生滿足要求的最優(yōu)解時所用時間較短。在真正的實際生活當(dāng)中，根據(jù)預(yù)算成本的不同設(shè)置物流中心倉庫貨物的防置，從而快速計算出最短的揀貨路徑和出庫時間，此算法在倉庫貨物配送規(guī)劃當(dāng)中也因此具有一定的參考意義。