不同訂單分配和算法下的揀貨路徑優化組合

孟 鑫，楊 琴 ，4，郝婷婷，張 潔，曹策俊

1.四川師范大學 商學院，成都 610101

2.長安大學 經濟與管理學院，西安 710054

3.重慶工商大學 商務策劃學院，重慶 400067

4.四川工商學院 經濟管理學院，成都 611745

1 引言

隨著網絡購物的現象日益普遍，人們對物流配送行業倍加關注。配送中心的揀貨作業過程是典型的勞動密集型，據了解，單件產品的揀貨作業成本占配送成本的30%～40%之多，揀貨作業勞動量占倉庫總作業量60%，并且作業時間占到總時間的40%[1]。雖然倉庫揀貨作業趨向于無人化，但無人化技術的推廣需要投入大量資金，現階段無人倉還未完全普及，所以絕大部分的倉庫仍處于人工倉。倉庫揀貨作業一般分為兩個步驟：一是分配客戶訂單，產生揀貨單計劃；二是由揀貨員進行商品揀取任務。前一個步驟執行過程中，不合理的訂單分配方式會引發訂單周期較長、商品錯誤率高等問題；后一個步驟中，不合理的路徑規劃會產生較多不必要的重復行走路線，導致搬運成本增加。因此，合理規劃倉庫中的揀貨作業環節，提高揀貨作業效率具有研究價值。

目前已有國內外學者針對倉庫揀貨作業中存在的問題進行了大量的研究和分析。從訂單分配層次，Khojasteh 等[2]就如何在最短時間內完成客戶訂單檢索這一問題描述成一個非線性規劃模型，討論了一個多通道自動化倉庫中的訂單揀配問題。Bozer 等[3]運用兩種訂單揀選系統（Miniload 系統和Kiva 系統）處理同一組客戶訂單，得出預期的檢索時間。王旭坪等[4]構建以總服務時間最短和分區均衡度最優的雙目標訂單合并優化模型，研究如何合理進行訂單合并優化。盧燁彬等[5]創新性地將引力模型應用到波次劃分模型中，以波次內不同儲位商品之間的引力大小衡量訂單之間的相似度，從而進行訂單的波次劃分。揀貨作業路徑規劃是否合理直接影響揀貨作業的效率和人工成本，因此，研究者致力于優化揀貨作業路線。Lu 等[6]任務訂單的揀選是影響倉庫業績的關鍵因素，并提出了一種干預路由算法來解決動態路徑規劃問題。Hong等[7]介紹了一種采用S形路由方法并行-過道訂單揀選（SRSB）的路徑選擇訂單批量模型。郭興海等[8]提出了一種兩階段的全局路徑規劃方法，促進了無人倉庫高效運轉。孫軍艷等[9]提出并設計動態貨位調整與人工揀貨協同作業的動態揀貨策略，針對雙區型倉庫，以揀貨時間最短為目標函數構建數學模型，進一步提高揀貨效率。王轉等[10]構建基于節約里程的訂單分批模型，有效地減少了揀貨行走總距離和平均行走距離。

然而，少有學者同時從訂單分配方式和路徑規劃兩個層次對揀貨作業規劃進行研究。所幸，已有學者注意到上述差距。Giannikas 等[11]介紹了一種動態的揀貨策略，在揀貨周期中更新揀貨路線和訂單分配。王華東等[12]采用訂單動態時間窗分揀策略，倉庫揀貨路徑優化算法，重點對跨境電商保稅倉庫揀貨流程進行分析與優化。基于此，本文的主要工作有：（1）針對不同訂單分配方式下的揀貨路徑規劃問題，以京東典型的雙區型倉庫為例，建立與之相適應的路徑規劃模型，并設計了算法——S型啟發算法和遺傳算法。（2）通過算例仿真，將不同訂單分配方式下的結果進行對比，并比較分析兩種算法下的仿真結果。（3）選擇最優的訂單分配方式和算法，組合形成較優的倉庫揀貨作業規劃。

2 問題描述

如圖1所示，首先確定了兩種揀貨方式，即單一揀貨與批量揀貨。其次，運用三元組α/β/γ 方法分析揀貨路徑規劃問題特征與布局特點。然后根據雙區型倉庫的布局特點，建立以最小化揀貨路徑為目標的路徑規劃模型。最后，設計兩種算法（S型啟發式算法與遺傳算法）進行算例仿真，對比兩種算法下的路徑，得出最優解。

圖1 倉庫揀貨作業設計過程圖

2.1 兩種揀貨方式

單一揀取即在同一時間，一名揀貨員只揀取一個客戶訂單，一個客戶訂單相應形成一個揀貨單，揀貨員揀取完成后，可直接打包配送至客戶。本文假設每一個訂單中商品總量都小于或等于揀貨車的最大裝載商品數量，即一個訂單只能夠用一輛揀貨車揀取。

批量揀取是將一些客戶訂單中的待揀商品集中起來在一張揀貨單上呈現，并只由一名揀貨員揀取，這減少了很多不必要的重復行走路線。由于揀貨車的最大裝載商品數量有限，且假設每一客戶的訂單不允許分割，若總訂單中商品數量較大，則需要進行訂單分批，使得每批訂單中的商品總量都小于或等于揀貨車的最大裝載商品數量。本文采用訂單包絡算法[13]對總訂單進行分批處理。

2.2 揀貨路徑規劃問題與布局特征分析

（1）資源環境（α域）：揀貨員從倉庫的進/出口出發，按照揀貨單去各個不同的貨位揀取商品，直到揀貨單上的所有商品揀取完成，回到倉庫的進出口位置，意味著一次揀貨作業的完成。結合調度理論在服務業中的應用，在這種情形下，倉庫中的商品是資源，而對揀貨員的路徑規劃服務是任務。（2）任務特征和約束（β域）：揀貨員從倉庫進出口出發，揀取完商品后，返回倉庫進出口，具有再循環的特征。在問題中，存在一系列約束條件：揀貨車有容量限制，一張揀貨單的商品數量不能超過揀貨車容量；任意兩個待揀商品之間只有一條路線等。（3）調度目標（γ 域）：本模型的主要目標為最小化揀貨路徑。

3 揀貨作業路徑規劃模型

在對客戶訂單的處理過程后列出相應的揀貨單，揀貨員拿著揀貨單推著揀貨車從倉庫進/出口到各個待揀商品的儲位揀取相應的商品，直到將揀貨單上的所有貨品揀取完，返回倉庫進/出口。本文根據京東典型的雙區型倉庫布局的特點，建立以最小化揀貨路徑為目標的路徑規劃模型。

3.1 基本假設

假設1N為倉庫中的總儲位數，每個儲位只能存放一種商品，一種商品只能放在一個倉庫儲位上。

假設2每一張揀貨單最少有一種商品，最多包含Q種商品（Q為一輛揀貨車的最大裝載商品數量）。

假設3每位揀貨員在同一時間內只負責揀取一張揀貨單，每個揀貨單中的商品數量不得超過揀貨車的最大裝載商品數量Q。

假設4在同一條巷道中揀貨時從一邊的儲位轉身另一邊儲位的距離忽略不計。

假設5揀貨單上的待揀商品在倉庫中均不缺貨。

3.2 參數設置

建立數學模型的部分主要相關參數如表1所示。

表1 符號說明表

3.3 路徑分析

對客戶提供的商品訂單進行處理后，形成多張揀貨單，一張揀貨單只能由一名揀貨員進行揀取任務。一張揀貨單內有n種商品(n∈[1,Q]) ，每種商品需揀取qi個，且一張揀貨單的商品總數量不能超過揀貨車最大裝載商品數量Q。

在本文的倉庫設定中，倉庫被分為東、西兩個半區，有一條主通道、兩條邊通道，巷道垂直于三條通道，在巷道的兩側是裝載商品的貨架，未開封的商品放在高層貨架上，需揀取的商品全部放在底層貨架的儲位上。揀貨員憑借揀貨單在巷道內對商品進行揀取，沿著每條通道都可以進入任意巷道內。倉庫只有一個進/出口，揀貨員從該口出發，揀貨完成后需返回該口。進/出口正對西半區的邊通道，巷道從離進/出口由近到遠一次為巷道1至巷道10，商品的儲位寬度為D1、巷道的寬度為D2、儲位深度為D3、主通道的寬度為D4。設用[x,y,z]來表示每個商品的儲位位置，商品所在的巷道數用x來表示；y表示商品儲位序號，yi∈[1,b],1 → 0.5b表示商品在倉庫西半區范圍，0.5b→b表示商品在倉庫東半區范圍；z表示巷道兩側商品，z∈( 0,1) ，z為1 時，揀取巷道內距離進/出口較遠儲位的商品，z為0 時，揀取距離進/出口較近儲位的商品。因為揀貨員在同一條巷道中揀貨時從一邊的儲位轉身揀另一邊儲位的距離忽略不計，商品儲位坐標可以用[x,y]表示。該倉庫基本結構如圖2。

圖2 雙區型倉庫基本結構圖

倉庫內任意商品儲位用坐標表示為：

根據商品所在位置有所不同，分情況寫出了任意兩個商品之間的最短距離dij的表達公式（i、j表示揀貨單上任意兩個揀貨商品）。

（1）當揀貨單上任意兩個待揀商品儲位分布在同一半區時，即，則求解dij可分為以下三種情況：

①當揀貨區的任意兩個商品的儲位都在同一半區、同一巷道內時，即xi=xj，y1,y2∈[1 , 0.5b]ory1,y2∈[0.5b,b]，則dij可表示為：

②當揀貨區的任意兩個商品儲位位于倉庫西半區、不同巷道內時，即xi≠xj，y1,y2∈[1,0.5b]，則dij可表示為：

③當揀貨區的任意兩個商品儲位位于倉庫東半區、不同巷道內時，即xi≠xj，y1,y2∈[0.5b,b]，則dij可表示為：

由倉庫進/出口到達任意商品儲位點的距離d0i的求取公式可表示為：

則揀貨作業過程的總路徑D的函數可表示為：

決策變量：

d01與dn0分別表示在一次揀貨作業過程中，揀貨員從倉庫進/出口到揀取的第一個商品的距離；從揀取的最后一個商品到倉庫進/出口的距離。

3.4 模型建立

綜上所述，揀貨作業路徑規劃模型如下所示：

在模型中，公式（9）為目標函數，求解在一次揀貨作業過程中揀貨員行走的最短總路徑；公式（10）和公式（11）分別表示揀貨員揀貨過程中從商品i到商品j和從商品j到商品i的總次數都為1，也就是說：任意兩個待揀商品之間只有一條路線；公式（12）表示在一次揀貨作業時商品總量不能超過Q；公式（13）為分段函數，分別表示任意兩個商品的儲位“位于同一半區、同一巷道內時”“位于倉庫西半區、不同巷道內時”“位于倉庫東半區、不同巷道內時”“位于在不同半區時”這四種情況下倉庫中兩個待揀商品儲位之間的最短距離；公式（14）為分段函數，分別表示由倉庫進/出口到達位于西半區和東半區中任意商品儲位點的最短距離。

4 算法設計

在一個調度問題中當機器和任務人多時，求解一個最優解的計算時間是難以估算的，因此尋找一個能在比較短的時間內找到較好調度的啟發式算法是非常有必要的[14]。因此，本文采用了兩種啟發式算法求解路徑規劃模型，即S型啟發式算法和遺傳算法。其中S型啟發式算法是一種較簡單基礎的尋找較優可行路徑的方法，操作簡單，容易實現，在許多倉庫管理系統中得到了廣泛的應用，而遺傳算法的基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解的算法，是應用領域廣泛、計算能力較強的全局優化算法[15]，由此，將S型啟發式算法得出的結果與遺傳算法的結果相比較，從而可驗證遺傳算法的有效性。

4.1 S型啟發式算法

此算法在揀貨過程中行走路線的思路是：從距離進/出口最近的通道出發進入存在待揀商品的巷道，（1）當存在商品在該巷道中的儲位離所在通道的距離大于巷道的一半長度時，則揀貨員從所在通道由近及遠揀取該巷道內的待揀商品然后走過該巷道，從另一端巷道接著進入下一巷道繼續揀貨；（2）當不存在商品在該巷道中的儲位離所在通道的距離大于巷道長度的一半時，則先揀取離所在通道距離最遠的商品，再由遠及近揀取該巷道內的商品并返回到原來通道進入下一巷道繼續揀貨；（3）如果該巷道上沒有商品可揀取，則跳過此巷道進入下一巷道繼續揀貨。重復以上三個規則，直到完成對揀貨單上的商品的揀取。

本文以雙區型倉庫為例，提出了S 型啟發式算法的具體操作，如圖3 所示：從最接近進/出口的西邊通道出發，按離進/出口由近及遠的巷道順序依次揀取西半區的待揀商品，揀取完西半區的所有商品后，然后再從主通道開始按離進/出口由遠到近的巷道順序一次揀取東半區的待揀商品，揀取完東半區的所有商品后返回進/出口。因S 型啟發式算法的操作簡單容易實現，所以在算例仿真中采用手動計算規劃出的揀貨總路徑。

4.2 遺傳算法

（1）染色體編碼。將染色體定義為由揀貨單中的待揀商品種類基因組成，根據揀貨單整理出待揀商品種數，在進行數值仿真之前首先為其進行編號，設n為揀貨單上的待揀商品的種數，且每一種待揀商品編號唯一，待揀商品編號由兩位十進制數表示，對每一商品都有其對應的揀貨次序，如染色體“01，03，05，02，04”代表該揀貨單有5 種待揀商品，對于編號03 的商品，它對應的揀貨次序是2，也就是說揀貨員第2 個揀取的商品是03。

（2）種群初始化。根據揀貨單可知待揀商品上的種類、數量及位置編號，設計代碼程序求商品儲位點到進/出口的距離以及倉庫中任意兩個商品儲位點的最短距離。在生成揀貨作業路徑規劃方案時，隨機生成一組m個包含n個待揀商品儲位編碼號的初始方案，并且分別計算目標函數值。

圖3 S型啟發式算法揀貨流程圖

（3）適應度函數。本研究問題中目標為最小化揀貨作業總路徑，據此適應度函數為minD。

（4）遺傳算子。

①選擇。首先將初始種群進行適應度的評估，產生新種群后，以概率ps舍棄劣勢個體，將適應度高的種群保留進入下一輪的自我復制。

②交叉。交叉運算在遺傳算法中起著核心的作用，其有利于組合之間傳遞新的信息，通過信息的交換和組合，有利于快速得到最優解。本文根據交叉概率pc=0.85，從生成的種群中選擇交叉的個體。例如，選取兩個染色體A、B進行操作，使得生產的新染色體A′、B′。

式中，“|”為交叉點；“*”的填入方式為（以染色體A為例）：從染色體B的第1位開始向后依次比較，其若與染色體A的前2位數不同則填入染色體A的“*”中，若相同則跳過，將染色體A的“*”一一補齊，從而產生新的染色體。

③變異。根據變異率pm=0.02篩選出需要變異的個體。從每個被選擇的個體中隨機選擇兩個變異點，并交換兩個變異點的信息以獲得新的個體。

5 算例仿真

本文以雙區型倉庫環境為例，其中包含400個商品儲位，由1條主通道、2條邊通道和10條揀貨巷道組成。假設每次的揀貨量不超過30 件商品；儲位寬度D1=2 m、深度D3=2 m；揀貨巷道寬度D2=2 m；主通道寬度D4=4 m。假設在某一段時間內某倉庫共收到了6個客戶訂單，訂單中商品的位置及數量如表2所示。

5.1 單一揀取方式下的仿真結果

在一輛揀貨車只揀取一個客戶訂單的情況下，6 個客戶訂單生成了6 個揀貨單，運用遺傳算法和S 型啟發算法的仿真結果如表3所示。

5.2 批量揀取方式下的仿真結果

根據訂單包絡算法對6個客戶訂單進行分批，共分為三批，分別是[1，2]、[3]、[4，5，6]，即訂單1 和2 在一張揀貨單上，訂單4、5和6在一張揀貨單上，訂單3在一張揀貨單上，如表4所示。

3張揀貨單運用遺傳算法和S型啟發式算法的仿真結果如圖4和表5所示。

5.3 仿真結果

總訂單的具體改善數據如表6所示。

仿真結果表明，訂單分批后的總揀貨路徑比不分批的總路徑改善了很多，說明訂單分批策略能有效提升揀貨效率；根據路徑規劃仿真結果將兩種算法進行對比，不同的算法對揀貨單上的商品的揀取次序有些不同，且遺傳算法下的揀貨路徑規劃較優，從而驗證了遺傳算法的有效性。因此將訂單分批策略與遺傳算法下的揀貨路徑規劃相結合能得到較為合理的揀貨作業規劃。

表2 訂單中商品的位置及數量

表3 單一揀取路徑規劃匯總表

表4 分批后揀貨單中商品的位置及數量

圖4 三張揀貨單在兩種算法下的路線圖

表5 批量揀取路徑規劃匯總表

表6 總訂單匯總表

6 結語

設計較為合理的揀貨作業規劃，不但能夠解決目前物流配送效率低下的嚴峻問題，還能降低倉庫的成本。因此，為了提升揀貨作業效率，減少揀貨成本，本文以雙區型倉庫為對象，討論了不同訂單分配方式和揀貨路徑規劃，構建相應的模型，設計兩種啟發式算法進行求解，以實現較為合理的揀貨作業規劃。但是本文研究的不足之處是只考慮了訂單分配的兩種基本方法，沒有深入考慮結合揀貨策略后的多種分配方式；同時在對路徑規劃的過程中只研究了進行一次揀貨作業過程中的路徑規劃，沒有考慮多名揀貨員同時進行揀貨作業時的路徑規劃情況。因此，如何結合實際揀貨作業情況選擇更為合適的訂單分配方式，并在路徑規劃模型之中添加多人的揀貨路徑規劃將是下一步主要的研究方向。