貨位指派和揀貨路徑協(xié)同優(yōu)化及算法研究

方忠民

（中車株洲電力機(jī)車有限公司，湖南 株洲 412000）

1 引言

隨著電子商務(wù)的迅猛發(fā)展，客戶對訂單時效性的要求愈加強(qiáng)烈，為提高揀貨效率，增強(qiáng)客戶滿意度，針對人工揀貨系統(tǒng)的優(yōu)化迫在眉睫。揀貨是將商品從其存儲位置揀出以滿足客戶訂單要求的過程[1]，作為典型的勞動密集型作業(yè)，約占整個訂單作業(yè)勞動力的60%、作業(yè)時間的30%-40%[2-5]。在人工揀貨系統(tǒng)中，存儲商品種類、貨位指派策略以及揀貨路徑策略是影響其揀貨效率的重要因素[6-10]，而貨位指派作為其中最重要的影響因素之一，其優(yōu)化目標(biāo)通常是揀貨成本（行走路徑）最優(yōu)或揀貨時間最短[11]。因此，基于人工揀貨系統(tǒng)的貨位指派和揀貨路徑的研究具有重要的實踐意義。

現(xiàn)有文獻(xiàn)分別從COI[12-13]、需求相關(guān)性[14-15]、出貨量[16]、周轉(zhuǎn)率[17]以及需求和結(jié)構(gòu)相關(guān)性[18-20]等方面對貨位指派問題進(jìn)行了深入研究，但考慮貨位指派與其他相關(guān)問題協(xié)同優(yōu)化的研究則較少。鑒于此，本文協(xié)同考慮貨位指派和揀貨路徑問題并進(jìn)行研究，目的主要是在揀貨員揀貨的同時進(jìn)行貨位指派，以此合并作業(yè)流程、優(yōu)化倉庫存儲結(jié)構(gòu)并進(jìn)一步提升揀貨效率。

2 模型構(gòu)建

貨位指派和揀貨路徑存在密切聯(lián)系，以最小化作業(yè)周期內(nèi)揀貨總行程時間最短為目標(biāo)。為不失一般性，做出如下假設(shè)：（1）倉庫的出入口（Input/Output，I/O）只有一個，揀貨員從該處開始揀選并至該處結(jié)束作業(yè)；（2）不考慮貨位的異質(zhì)性，即倉庫中的貨位具有相同的尺寸；（3）只考慮低層貨架，即每個貨架只有一層貨位，并以該貨位的中心位置作為該貨位的坐標(biāo)；（4）倉庫中同一種商品只可存放于一個貨位，每個貨位只能存放一種商品，也即同一個貨位的商品具有同質(zhì)性，且不考慮倉庫缺貨情形；（5）巷道為窄巷道，揀貨員在巷道內(nèi)可以方便地揀選該巷道兩邊貨架上的商品，且不考慮商品上下架的時間。在以上假設(shè)的基礎(chǔ)上，定義模型參數(shù)如下：

K—商品編號，數(shù)量為qk，索引號為k，k'；

N—貨位編號，數(shù)量qN，索引號為m，m'，n。其中m=0表示為I O；

v—揀貨員平均行走速度；

Cnt—周期t內(nèi)貨位n可存放商品的數(shù)量，其中當(dāng)n∈時，Cnt取值為1，否則為0；

Jnt—周期t內(nèi)貨位n可揀取商品的數(shù)量，其中當(dāng)n?時，Jnt取值為1，否則為0；

M—周期t內(nèi)最大貨位調(diào)整量；

Pt—周期t內(nèi)滿足訂單需求條件的待揀取商品集合；

Qmnt—周期t內(nèi)揀貨員訪問完貨位m后在訪問貨位n之前的揀貨車容量；

St—周期t內(nèi)滿足貨位調(diào)整（重新指派貨位）條件的商品集合，滿足Pt?St=?；

dmn—揀貨員從貨位m到貨位n的行走距離，m,n∈N；

(Am,Bm)—貨位m的坐標(biāo)，(0,0)代表 I O，m∈N；

Wmnt—若揀貨員在訪問貨位m后隨即立刻訪問貨位n，則Wmnt的值為1，否則為0，其中m,n∈N；

Vmt—若貨位m在周期t內(nèi)被訪問，Vmt值為1，否則為0，其中m∈N，t∈T；

Dt—周期t內(nèi)揀貨員完成全部任務(wù)的總行走距離；

DT—周期t內(nèi)揀貨員完成全部任務(wù)的總行走時間。

（2）0-1決策變量

xkmt—若揀貨員從貨位m處揀取商品k，xkmt的值為1，否則為0，其中k∈Pt，m∈，t∈T ；

yk'm't—若揀貨員從貨位m'處的揀取商品k'（或?qū)'商品下架）使其以滿足貨位調(diào)整的條件，yk'm't的值為1，否則為0，其中k'∈St，m'∈，t∈T ；

Zk'nt—若揀貨員從貨位m'處揀取的商品k'被重新分配存放在貨位n處（靠近I O的貨位），Zk'nt的值為1，否則為0，其中k'∈St，n∈，t∈T 。

將貨位指派和揀貨路徑進(jìn)行協(xié)同優(yōu)化的主要目的是為了減少揀貨員在尋找待揀選商品時的行走距離，從而提高揀貨環(huán)節(jié)的作業(yè)效率，揀貨員完成全部任務(wù)的總行走距離見式（1）。

以全部工作時間內(nèi)揀貨員的總行走時間最小為優(yōu)化目標(biāo)[27]，建立數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

約束條件：

其中：t為時間周期；dmn為揀貨員從貨位m到貨位n的行走距離；wmnt為揀貨員訪問貨位m后立刻訪問貨位n，取值1或0。式（3）表示周期t內(nèi)揀貨員從貨位m上揀取商品k以滿足訂單揀貨要求；式（4）表示周期t內(nèi)揀貨員從貨位m'揀取需要重新調(diào)整貨位的商品 k'；式（5）和式（6）表示周期t內(nèi)商品k'被重新指定一個空貨位進(jìn)行存放；式（7）表示若周期t內(nèi)待調(diào)整貨位的商品k'被揀貨員揀取，則一定可以被重新存儲在新的貨位上；相反，若周期t內(nèi)不存在空貨位供商品k'存儲，則商品k'將不會被揀貨員揀??；式（8）表示周期t內(nèi)商品k為待揀取滿足客戶訂單要求的商品或者滿足貨位重新指派的商品，不存在商品k既是訂單商品又是待重新貨位調(diào)整的商品；式（9）表示周期t內(nèi)需要重新進(jìn)行貨位調(diào)整的貨位數(shù)的最大限額，且M小于待揀商品數(shù)；式（10）表示周期t內(nèi)揀貨員只訪問已經(jīng)被分配的待揀取商品的貨位和重新存放商品的貨位（I O除外）；式（11）和式（12）表示周期t內(nèi)揀貨員遍歷所有任務(wù)中已經(jīng)被分配的待揀取商品的貨位和待指派商品的貨位（I O除外）；式（13）表示周期t內(nèi)揀貨員訪問某一貨位（I O除外）后，必須離開該貨位前往下一貨位；式（14）表示揀貨員訪問貨位n后揀貨車的容量變化；式（15）和式（16）分別確保揀貨員完成任務(wù)前后，揀貨車容量能夠滿足訂單揀貨時的取貨商品存放需求和貨位調(diào)整過程中的商品存放需求；式（17）表示揀貨車的最大載貨容量。

3 算法設(shè)計

3.1 解的編碼

利用蟻群算法求解由0-1決策變量xkmt、yk'm't和zk'nt所確定的一條揀貨員行走路徑。由于協(xié)同優(yōu)化涉及貨位指派和商品揀選兩個作業(yè)環(huán)節(jié)的協(xié)同，要將貨位指派和揀貨問題轉(zhuǎn)化成能被蟻群行走的點(diǎn)，關(guān)鍵在于要提前處理待重新貨位指派的商品，以確定蟻群在去往下一個訪問點(diǎn)的路徑上是否執(zhí)行揀貨任務(wù)（或者貨位指派任務(wù)）。因此，將問題分為貨位指派階段和揀貨路徑規(guī)劃階段。

在構(gòu)建貨位指派方案方面，用整數(shù)0-1表示倉庫中的貨位屬性，0表示空貨位，1表示非空貨位，構(gòu)建貨位指派方案的可行解集。采用隨機(jī)生成的方法從可行解中產(chǎn)生初始貨位指派方案，并用0-1-2碼表示當(dāng)前貨位屬性，以0表示待重新貨位指派的空貨位屬性，以1表示待揀取滿足訂單需求的商品當(dāng)前所在的貨位屬性，以2表示待揀取滿足重新貨位指派的商品當(dāng)前所在的貨位屬性，如下所示：

貨位編號： 3 91 6 5 810 2 4 7

貨位屬性1： 1 11 1 0 1 1 0 1 1

貨位屬性2： 2 11 2 0 1 1 2 1 1

在初始貨位指派方案的基礎(chǔ)上，采用整數(shù)編碼方式表示每只螞蟻所行進(jìn)的路線。但是由于整條路徑的終始點(diǎn)為I O處（以0為編碼），則最終路徑階段的個體編碼為[0 3 9 1 6 5 8 10 2 4 7 0]。

3.2 路徑的構(gòu)建

3.2.1 生成距離矩陣。假設(shè)任意兩個貨位的坐標(biāo)分別為 Pm(xm,ym)和 Pn(xn,yn)，設(shè)dmn為 Pm和 Pn的最短折線距離，則dmn=Xmn+Ymn。其中，Xmn為兩貨位間最短橫向折線距離，即Xmn=|Xm-Xn|。假設(shè)ΔYi表示為兩貨位縱向距離Ymn，ΔY1為揀貨員向正北行走的距離，ΔY2為向正南行走的距離，Rm和Rn為倉庫貨架的排號，Cm和Cn為倉庫貨架的列號，l為倉庫揀貨巷道的深度，則Ymn為：

3.2.2 構(gòu)造可行解。在初始貨位指派方案的基礎(chǔ)上，采用改進(jìn)的最近鄰點(diǎn)法[27]，每只螞蟻模仿一個揀貨員，構(gòu)造所有揀貨路線，其搜索范圍由揀貨車容量決定，當(dāng)揀貨容量可以滿足貨位調(diào)整時商品臨時占用，則從空貨位、待揀貨貨位和待調(diào)整貨貨位的并集中搜索，否則只能從待揀貨貨位集合中搜索。路線構(gòu)造完畢后，需進(jìn)行可行性檢驗，其可行性需滿足的條件為：（1）任意螞蟻訪問了待重新指派貨位的商品所在的當(dāng)前貨位點(diǎn)，則必定訪問該商品被重新指派的新貨位點(diǎn)，反之亦然；（2）任意螞蟻必須先訪問待重新指派貨位的商品所在的當(dāng)前貨位點(diǎn)，后訪問該商品被重新指派的新貨位點(diǎn)，反之不可行。

3.3 轉(zhuǎn)移策略

用一個禁忌表記錄該路線中每個時刻螞蟻所處的位置，并且以該路徑的總長度dij作為衡量該路線的評價標(biāo)準(zhǔn)，螞蟻從出發(fā)點(diǎn)開始出發(fā)，根據(jù)路徑上的信息素濃度函數(shù)概率，采取輪盤賭法選擇其下一個待訪問的貨位點(diǎn)，直到所有貨位點(diǎn)都被訪問完。

其中，ηis(t)為啟發(fā)式函數(shù)，ηis(t)=1/dij表示螞蟻從貨位i到貨位j的期望程度；allowk表示螞蟻下一步即將訪問的貨位集合；τis(t)表示路徑上的信息量。

3.4 信息素更新

在螞蟻行走釋放信息素的同時，隨著時間的推移，其所留信息濃度會不斷揮發(fā)減少。在經(jīng)過時間t后，當(dāng)螞蟻完成一次循環(huán)，各路徑上的信息素濃度需要實時更新，其計算方法見式（20）。

4 實驗與分析

4.1 實驗方案設(shè)計

蟻群算法參數(shù)設(shè)置為：信息素重要程度參數(shù)α=1，啟發(fā)式信息重要程度β=5，信息素保留率ρ=0.7，螞蟻個數(shù)等于揀貨員訪問的貨位數(shù)，啟發(fā)式因子為揀貨員訪問各貨位間最短行走距離的倒數(shù)，仿真實驗中采用ant-cycle模型，以隨機(jī)可行解作為初始解，最大迭代次數(shù)為200次。以單區(qū)型倉庫作為仿真實驗的倉庫模型，以隨機(jī)存儲策略作為倉庫商品的初始貨位分配方案，揀貨員揀貨作業(yè)時間以周期t為截止點(diǎn)。假設(shè)倉庫共有1 200個儲位（Pmax=1 200），由20條揀貨巷道和2條前后揀貨通道組成，每條揀貨巷道兩邊各有10列貨架，每條揀貨巷道共60個儲位，倉庫布局參數(shù)見表1。

表1 倉庫布局參數(shù)

4.2 實驗結(jié)果分析

4.2.1 不同訂單規(guī)模下的仿真分析。假設(shè)周期t內(nèi)的平均貨位調(diào)整量n=3，平均訂單規(guī)模g分別為大（g=60）、中（g=30）、?。╣=5,10），根據(jù)運(yùn)行結(jié)果得到訂單規(guī)模大小對優(yōu)化效果的影響程度，如圖1所示。

由圖1可知，分別優(yōu)化和協(xié)同優(yōu)化在訂單規(guī)模大小不同的情況下存在以下結(jié)論：

圖1 訂單規(guī)模大小對優(yōu)化效果的影響程度

（1）不同訂單規(guī)模下采用協(xié)同優(yōu)化方法可以改善揀貨員在倉庫揀貨作業(yè)過程中的行程時間。

（2）訂單規(guī)模的大小對揀貨行程時間有影響，且訂單規(guī)模較小時，揀貨行程時間改善效果越好。

4.2.2 不同貨位調(diào)整量下的仿真分析。假設(shè)周期t內(nèi)的平均訂單規(guī)模g=10（小規(guī)模），平均貨位調(diào)整量n分別為大（n=10）、中（n=5）、?。╪=1,3），根據(jù)運(yùn)行結(jié)果得到貨位調(diào)整量大小的影響程度，如圖2所示。

由圖2可知，分別優(yōu)化和協(xié)同優(yōu)化在貨位調(diào)整量大小不同的情況下存在以下結(jié)論：

（1）在不同貨位調(diào)整量條件下，采用協(xié)同優(yōu)化方法仍然可以在一定程度上改善揀貨過程中的行程時間。

（2）當(dāng)訂單規(guī)模為定值，且為小規(guī)模訂單時，貨位調(diào)整量的大小對揀貨行程時間有影響；且貨位調(diào)整量較小時，協(xié)同優(yōu)化方法優(yōu)于分別優(yōu)化方法。但當(dāng)貨位調(diào)整量較大時，協(xié)同優(yōu)化方法不一定優(yōu)于分別優(yōu)化方法。

圖2 貨位調(diào)整量大小的影響程度

5 結(jié)語

本文以人工揀貨系統(tǒng)為研究對象，研究了配送中心的貨位指派與揀貨路徑協(xié)同優(yōu)化問題。以揀貨作業(yè)總行程時間最短為目標(biāo)，協(xié)同考慮人工揀貨系統(tǒng)中的貨位指派問題和揀貨路徑問題，并建立了兩者協(xié)同優(yōu)化模型。仿真結(jié)果顯示，在以人工揀貨系統(tǒng)為研究對象，采用考慮貨位指派和揀貨路徑協(xié)同優(yōu)化的方法能夠有效地減少整個周期內(nèi)揀貨員總揀貨行程時間，并以此提升揀貨效率；進(jìn)一步分析了基于不同平均訂單規(guī)模下的優(yōu)化效果以及不同貨位調(diào)整量的系統(tǒng)優(yōu)化效果，在平均訂單規(guī)模較小及貨位調(diào)整量較小時，獲得的優(yōu)化效果最好，改善效果最明顯。