貨位指派和揀貨路徑協同優化及算法研究

方忠民

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

1 引言

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

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

2 模型構建

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

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

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

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

Cnt—周期t內貨位n可存放商品的數量，其中當n∈時，Cnt取值為1，否則為0；

Jnt—周期t內貨位n可揀取商品的數量，其中當n?時，Jnt取值為1，否則為0；

M—周期t內最大貨位調整量；

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

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

St—周期t內滿足貨位調整（重新指派貨位）條件的商品集合，滿足Pt?St=?；

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

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

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

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

Dt—周期t內揀貨員完成全部任務的總行走距離；

DT—周期t內揀貨員完成全部任務的總行走時間。

（2）0-1決策變量

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

yk'm't—若揀貨員從貨位m'處的揀取商品k'（或將k'商品下架）使其以滿足貨位調整的條件，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 。

將貨位指派和揀貨路徑進行協同優化的主要目的是為了減少揀貨員在尋找待揀選商品時的行走距離，從而提高揀貨環節的作業效率，揀貨員完成全部任務的總行走距離見式（1）。

以全部工作時間內揀貨員的總行走時間最小為優化目標[27]，建立數學模型如下：

目標函數：

約束條件：

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

3 算法設計

3.1 解的編碼

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

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

貨位編號： 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

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

3.2 路徑的構建

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

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

3.3 轉移策略

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

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

3.4 信息素更新

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

4 實驗與分析

4.1 實驗方案設計

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

表1 倉庫布局參數

4.2 實驗結果分析

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

由圖1可知，分別優化和協同優化在訂單規模大小不同的情況下存在以下結論：

圖1 訂單規模大小對優化效果的影響程度

（1）不同訂單規模下采用協同優化方法可以改善揀貨員在倉庫揀貨作業過程中的行程時間。

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

4.2.2 不同貨位調整量下的仿真分析。假設周期t內的平均訂單規模g=10（小規模），平均貨位調整量n分別為大（n=10）、中（n=5）、小（n=1,3），根據運行結果得到貨位調整量大小的影響程度，如圖2所示。

由圖2可知，分別優化和協同優化在貨位調整量大小不同的情況下存在以下結論：

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

（2）當訂單規模為定值，且為小規模訂單時，貨位調整量的大小對揀貨行程時間有影響；且貨位調整量較小時，協同優化方法優于分別優化方法。但當貨位調整量較大時，協同優化方法不一定優于分別優化方法。

圖2 貨位調整量大小的影響程度

5 結語

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