單區(qū)型物流配送中心訂單分批與路徑優(yōu)化研究

張 娟，李 莉ZHANG Juan, LI Li

（新疆農(nóng)業(yè)大學(xué)交通與物流工程學(xué)院，新疆 烏魯木齊 830000）

0 引 言

隨著社會(huì)經(jīng)濟(jì)的快速發(fā)展，人們網(wǎng)購(gòu)的數(shù)量直線增長(zhǎng)，同時(shí)人們消費(fèi)需求也向小批量、多品種轉(zhuǎn)變，伴隨著人們觀念的轉(zhuǎn)變，對(duì)物流業(yè)發(fā)展的要求也愈發(fā)的嚴(yán)格。尤其是對(duì)貨物的分揀工作，這是最耗時(shí)同時(shí)也是物流成本占據(jù)較大的環(huán)節(jié)，因此如何選擇快速、高效、準(zhǔn)確的揀貨方式已經(jīng)成為物流配送中心急需解決的重大問(wèn)題并且也是當(dāng)前研究的重點(diǎn)之一。

在對(duì)訂單分批的研究中，陳曉艷等把倉(cāng)庫(kù)揀選問(wèn)題轉(zhuǎn)換成TSP 問(wèn)題，將蟻群算法、遺傳算法、禁忌搜索算法、模擬退火算法進(jìn)行對(duì)比研究，然后經(jīng)過(guò)仿真對(duì)比，當(dāng)訂單量多時(shí)，蟻群算法的優(yōu)化結(jié)果更好。徐宣國(guó)等采用系統(tǒng)聚類的方法研究了大批量情況下的訂單分批過(guò)程，通過(guò)建立系數(shù)矩陣，對(duì)客戶的訂單進(jìn)行聚類。胡小建等將Canopy 編程環(huán)境與聚類算法相結(jié)合，提出了基于兩者結(jié)合的Canopy-k-means 算法，發(fā)現(xiàn)改進(jìn)后的算法大大減少了揀選的批次，在很大程度上加快了揀選貨物的效率。Zhang 等建立了有類別約束和無(wú)類別約束的JOBPRP 優(yōu)化模型，并對(duì)種子算法進(jìn)行了改進(jìn)、采用新的種子添加規(guī)則和改進(jìn)的近優(yōu)路由方法對(duì)模型進(jìn)行求解。李詩(shī)珍等建立了訂單分批模型，基于相似系數(shù)對(duì)訂單進(jìn)行分批，通過(guò)啟發(fā)式算法求解訂單分批結(jié)果，根據(jù)模型得到了最短的揀選貨物的路徑。秦馨等研究的是“貨到人”模式下的訂單分批問(wèn)題，比較了基于歐式距離的聚類算法、基于余弦相似性的聚類算法，先到先分批算法以及不分批算法四種算法下的揀選搬運(yùn)次數(shù)，最后得到基于余弦相似性的聚類算法更加能夠提高揀選效率。

本文主要研究的是單區(qū)型物流配送中心“人到貨”工作場(chǎng)景中的靜態(tài)訂單，通過(guò)對(duì)訂單之間的品項(xiàng)相似系數(shù)以及貨位相似系數(shù)的計(jì)算，來(lái)作為對(duì)訂單分批的依據(jù)，并且通過(guò)禁忌搜索算法來(lái)對(duì)研究的訂單進(jìn)行揀選路徑的計(jì)算，進(jìn)而比較兩種算法在訂單揀選過(guò)程中的優(yōu)勢(shì)和劣勢(shì)，希望能為訂單揀選工作提供新的方法。

1 模型構(gòu)建

1.1 問(wèn)題描述

本文主要研究的是某醫(yī)藥物流公司在一定的時(shí)間節(jié)點(diǎn)內(nèi)到達(dá)的貨物揀選訂單，由于醫(yī)藥物品種類繁多且在疫情期間需求量大、時(shí)間緊急，因此對(duì)物品的揀選工作要更加以節(jié)省時(shí)間為主。若對(duì)到達(dá)的訂單進(jìn)行逐個(gè)揀選，則需要增加更多的勞動(dòng)力，并且會(huì)浪費(fèi)更多的時(shí)間，可能在貨物揀選過(guò)程中造成擁堵的情況，在很大程度上增加了時(shí)間成本以及人力成本。因此在對(duì)訂單進(jìn)行揀選時(shí)需要對(duì)訂單進(jìn)行分批，并且盡可能多的減少揀選的路徑，在一定程度上提高效率。

1.2 相似系數(shù)

在判斷兩個(gè)訂單的相似程度時(shí)，可以通過(guò)對(duì)訂單中品項(xiàng)的相似系數(shù)以及巷道相似系數(shù)進(jìn)行計(jì)算，通常采用的是Jaccard 相似系數(shù)計(jì)算原理，即把每個(gè)訂單都看作是一個(gè)集合，定義為用集合的交集比上集合的并集，公式如下：

則訂單品項(xiàng)相似系數(shù)=相同的貨物品項(xiàng)數(shù)/總貨物品項(xiàng)數(shù)，巷道相似系數(shù)=共同巷道數(shù)/總巷道數(shù)。

1.3 訂單分批問(wèn)題的聚類模型

根據(jù)上面的分析，將訂單分批和揀選路徑結(jié)合起來(lái)，建立兩階段的訂單分批模型，第一階段為以訂單相似系數(shù)最大為依據(jù)，先對(duì)訂單進(jìn)行分批，第二階段為分批訂單之間的揀選路徑最短，對(duì)貨物進(jìn)行揀選。

為了構(gòu)建模型的方便，所用到的符號(hào)及定義如表1 所示。

表1 參數(shù)定義

目標(biāo)函數(shù)式（1） 表示形成分批的訂單中，同一批次中的訂單的品項(xiàng)相似系數(shù)和巷道相似系數(shù)之和為最大，并且分批訂單的揀選路徑為最短。約束條件式（2） 表示一個(gè)訂單只能對(duì)應(yīng)一個(gè)批次，不能重復(fù)分批。約束條件式（3） 表示只有當(dāng)揀選路徑存在即第j 批訂單時(shí)，訂單i 才分配到第j 批。本模型暫不考慮揀貨車的容積和重量問(wèn)題，因此不設(shè)對(duì)于此的約束條件。

2 聚類算法

2.1 聚類分析概念

聚類分析是對(duì)事物按照一定的規(guī)則進(jìn)行分類的算法，它又稱群算法。它是對(duì)事先已經(jīng)獲得的數(shù)據(jù)，按照一定的規(guī)則，將數(shù)據(jù)分類到不同的類或者簇這樣的一個(gè)過(guò)程，類和簇就相當(dāng)于是一個(gè)相似數(shù)據(jù)的集合。采用聚類的思想對(duì)訂單進(jìn)行分批是為了最小化揀取所有訂單的行走距離，從而加快貨物的揀選速度，減少人力勞動(dòng)成本。

2.2 聚類結(jié)果分析

本文隨機(jī)選取了某醫(yī)藥物流公司某天的12 張訂單，對(duì)這12 張訂單的品項(xiàng)相似系數(shù)和巷道相似系數(shù)進(jìn)行計(jì)算，得到品項(xiàng)相似系數(shù)和巷道相似系數(shù)之和，結(jié)果如表2 所示。通過(guò)對(duì)品項(xiàng)相似系數(shù)和巷道相似系數(shù)之和進(jìn)行計(jì)算，采用聚類算法，對(duì)訂單進(jìn)行分批，結(jié)果如圖1 所示。

圖1 訂單分批結(jié)果

表2 相似系數(shù)結(jié)果表

本文選用8 巷道的單區(qū)型倉(cāng)庫(kù)作為研究對(duì)象，倉(cāng)庫(kù)為長(zhǎng)方形，倉(cāng)庫(kù)的出入口位于倉(cāng)庫(kù)的左上角和左下角，倉(cāng)庫(kù)布局圖如下，假設(shè)貨架寬1 個(gè)單位，每個(gè)貨格長(zhǎng)1 個(gè)單位，巷道寬2 個(gè)單位，圖2 中黑格表示貨物存放的位置，揀選路徑都采用“S型”和“中點(diǎn)返回”揀選策略，對(duì)訂單進(jìn)行分批后，以第一批訂單為例，其揀選路徑如圖2 所示，總揀選路徑為L(zhǎng)=82 米，三批訂單總的揀選路徑L=230 米。

圖2 訂單揀選路徑

3 禁忌搜索算法

3.1 禁忌搜索算法步驟

禁忌（Tabu Search） 算法是一種隨機(jī)搜索算法，它可以避免產(chǎn)生局部最優(yōu)的情況，在運(yùn)用禁忌搜索算法求解路徑優(yōu)化問(wèn)題時(shí)，通常將問(wèn)題轉(zhuǎn)化為求解TSP 問(wèn)題，具體計(jì)算步驟如下：

Step1：將訂單中的各個(gè)品項(xiàng)所在的巷道數(shù)和層數(shù)在直角坐標(biāo)系中用XY 軸表示出來(lái)，這樣就將訂單揀選問(wèn)題轉(zhuǎn)換成TSP 旅行商問(wèn)題，在本文中，所有訂單總共有90 個(gè)品項(xiàng)，因此對(duì)應(yīng)90 個(gè)二維坐標(biāo)，這樣就把問(wèn)題轉(zhuǎn)換成遍歷90 個(gè)地方所需的最短路徑問(wèn)題；

Step2：產(chǎn)生任意兩個(gè)城市的間隔矩陣，并初始化禁忌表并確定禁忌表長(zhǎng)度。產(chǎn)生一個(gè)90*90 的零矩陣，作為初始禁忌表，確定禁忌表的長(zhǎng)度，公式為（N* （N- 1 ）/2 ）^0.5；

Step3：設(shè)置候選集的個(gè)數(shù)為200，存放于一個(gè)新的集合中，初始化揀選貨位，隨機(jī)生成初始解，設(shè)置迭代次數(shù)G 為1 000次；

Step4：進(jìn)行禁忌搜索循環(huán)計(jì)算，判斷是否滿足收斂準(zhǔn)則，即如果參數(shù)p＞G，則停止運(yùn)算，輸出結(jié)果，反之轉(zhuǎn)Step5；

Step5：在初始解的鄰域內(nèi)進(jìn)行搜索產(chǎn)生新的候選解，求交換的貨位矩陣，生成鄰域解，選擇最好鄰域解并判斷是否滿足藐視準(zhǔn)則，若滿足，則轉(zhuǎn)Step6，若不滿足，則判斷候選解的屬性，轉(zhuǎn)Step7；

Step6：將該鄰域解作為當(dāng)前解，并將此解移動(dòng)列入禁忌表中，禁忌表向前移動(dòng)，將最初進(jìn)入禁忌表的鄰域解移出禁忌表，不斷地更新禁忌表，轉(zhuǎn)Step4 繼續(xù)進(jìn)行計(jì)算；

Step7：將非禁忌對(duì)象對(duì)應(yīng)的最優(yōu)解作為當(dāng)前解，并列入禁忌表中，禁忌表向前移動(dòng)，將最初進(jìn)入禁忌表的候選解移出禁忌表，轉(zhuǎn)Step4 繼續(xù)進(jìn)行計(jì)算；

Step8：求解結(jié)束，輸出當(dāng)前的最短路徑以及適應(yīng)函數(shù)曲線。

3.2 結(jié)果分析

參數(shù)設(shè)置完畢后，經(jīng)MATLAB R2015b 仿真研究，獲得最短路徑和適應(yīng)度進(jìn)化曲線。其中路徑距離中的點(diǎn)代表貨點(diǎn)的位置，適應(yīng)度進(jìn)化曲線的橫坐標(biāo)代表算法的迭代次數(shù)，在計(jì)算過(guò)程中，設(shè)置迭代次數(shù)為1 000 次，縱坐標(biāo)代表目標(biāo)函數(shù)值，可以看出目標(biāo)函數(shù)值由最初的350 米經(jīng)過(guò)不斷的迭代最后變?yōu)?2 米。根據(jù)MATLAB 仿真得到數(shù)據(jù)結(jié)果如圖3、圖4 所示。

將兩種算法進(jìn)行對(duì)比，如表3 所示。

從表3 可以看出，訂單相似系數(shù)的聚類算法下，總的揀選路徑為230 米，禁忌搜索算法下的揀選路徑為82 米，可以看出禁忌搜索算法是將所有的訂單當(dāng)作一批進(jìn)行揀選，而在訂單不分批情況下，揀選路徑長(zhǎng)度為763 米，可以看出大大提高了揀選的路徑，前后優(yōu)化了64%左右，但在進(jìn)行計(jì)算時(shí)，禁忌搜索算法的工作量大，迭代次數(shù)較多，在實(shí)際工作之中，訂單相似系數(shù)的聚類算法速度更快，計(jì)算方法也更加簡(jiǎn)便。

4 結(jié)束語(yǔ)

本文在當(dāng)前社會(huì)面臨的大背景下，通過(guò)對(duì)醫(yī)藥物流的研究，基于“人到貨”模式下，以單區(qū)型物流配送中心為研究對(duì)象，根據(jù)倉(cāng)儲(chǔ)系統(tǒng)揀貨操作實(shí)際情況，以優(yōu)化揀貨路徑為目的建立了基于訂單相似系數(shù)的兩階段聚類算法模型，通過(guò)對(duì)訂單進(jìn)行分批，計(jì)算訂單揀選路徑，又通過(guò)禁忌搜索算法來(lái)計(jì)算訂單揀選路徑，經(jīng)MATLAB 仿真研究，得到禁忌搜索算法的優(yōu)化最短距離和適應(yīng)度曲線。通過(guò)對(duì)比得到禁忌搜索算法的優(yōu)化路徑遠(yuǎn)遠(yuǎn)大于訂單相似系數(shù)的聚類算法的優(yōu)化路徑。

圖3 禁忌搜索算法最短路徑圖

圖4 適應(yīng)度進(jìn)化曲線