基于免疫算法的物流揀貨路徑優化問題的研究

賈 鵬 管 錚 徐善頂* 吳天豪

（1、南京工程學院電力工程學院，江蘇 南京210000 2、南京工程學院數理部，江蘇 南京210000 3、南京工程學院機械工程學院，江蘇 南京210000）

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

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

定位→組單→揀貨→復核→打包

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

組單：將多個客戶的訂單合并，構成任務單。

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

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

1 揀貨路徑距離模型的基礎

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

圖1

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

圖2

2 問題分析

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

3 免疫模型的建立

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

下面基于本倉內揀貨路徑優化問題，建立免疫算法的模型：

（1）通過對采集的冀北地區中生代巖漿巖標本進行分類、測量密度等操作，基于統計數據得出：冀北地區偏基性的巖漿巖密度較高，而偏酸性巖漿巖的密度較低。兩種巖漿巖密度在空間分布上呈現一定的規律。

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

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

（3）適應度（親和力）的計算：

抗體V 和抗原W 之間的適應度公式為：

axv=optw

抗體m 和抗體n 之間的適應度公式為：

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

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

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

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

圖3

4 模型的求解

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

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

由上數據比較，可知：當起點固定為復核臺FH10，終點為復核臺FH01 時，路程s 最短，為399200mm，即399.2m。

具體的揀貨路線如下：

圖4

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

（1）路程時間t：

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

因此，

（2）取貨時間t2：

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

商品件數為2 的有4 個貨格；

商品件數為3 的有6 個貨格。

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

（3）復核和打包時間t3：

由于任務單t0001 打包了合計10 個訂單，

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

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

5 結論

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