電商倉儲聯合訂單批次分配排序和路徑問題

王 迪

（上海交通大學 安泰經濟與管理學院，上海 200030）

0 引言

中國每年要產生300億件以上的快遞包裹，這得益于電子商務的快速發展。倉儲物流日益成為電商發展中的瓶頸所在。訂單揀選流程是倉儲運營中最為關鍵的流程，占用了60%以上的運營成本。相較于傳統的倉儲中心，電商倉儲中心的訂單具有日均單量高、訂單體量小、及時響應性高等特點。如何確定最優的訂單批次，如何調度批次的分配和排序，如何在較短時間內完成訂單的揀選，聯合訂單批次分配排序和路徑問題引起了業界和學術界的關注。

客戶訂單通常會有一個確切的完成期限，一旦產生延誤，會降低客戶滿意度并帶來較高的成本。在多人揀選的場景下，是否發生延誤以及延誤程度，取決于批次的分配和先后排序、批次的訂單組成和批次處理時間（主要是路徑行走時間）等。一般的，由于不可能滿足所有訂單的完成期限，必須確定一個最優分配排序方案，以最小化訂單的總延遲時間。

本文對最小化訂單總延遲時間的聯合訂單批次分配排序和路徑問題進行描述并建立數學模型，之后給出求初始解的方法，并用可變鄰域下降算法改進訂單分批、用2-opt方法改進行走路徑，最終求得最小的訂單總延遲時間。

1 聯合訂單批次分配排序和路徑問題

1.1 問題描述

我們考慮的是一個人工揀選、低位貨架的單庫區，采用人到貨的揀選方式。庫區中貨架有規則地編號，商品可以方便地被揀選員揀取。庫區僅有一個起始點，分布在庫區左下角，可以進行準備、卸貨和打包等操作。揀選員采用手推車等揀選設備進行揀選，揀選設備有容量限制。

問題涉及的揀選流程描述如下：首先，一定數目的客戶訂單進入系統，訂單通常包含商品編碼、名稱、所需數量、存儲點和完成期限等信息。由于揀選設備容量、完成期限等因素限制，訂單按某些規則匯總成批次，又稱為揀選單。最后，將揀選單分配給揀選員，揀選員按照揀選單進行揀選，直到完成任務。

S型策略是實際應用中最常用的揀選路徑策略，圖1是S型策略的示意圖。揀選路徑問題是一個TSP，由于批次容量的限制，一個批次的路徑問題規模不大，我們將S型路徑作為初始解，采用2-opt方法，可以更快求得最優路徑。

揀選過程所花費的時間包括準備時間、行走時間和搜尋時間等。其中，準備時間包含領取揀選單和推車、卸貨打包等動作時間，一般是固定的。假設行走速度恒定，行走時間取決于路徑策略和貨位點的分布。假設搜索每個商品的速度恒定，搜尋時間包括對商品的搜索、揀取和核對等時間，主要取決于貨位點的多少。對于一個批次，揀選員從起始點領取揀選單的時刻記為批次起始時刻。類似的，揀選員完成揀選任務回到起始點的時刻記為批次完成時刻。一個批次中所有訂單的完成時刻都是批次完成時刻，這樣每個訂單的延遲時間等于訂單所在批次的批次完成時刻減去該訂單完成期限。

圖1 S型策略

訂單批次分配與排序問題的示意圖如圖2所示。在圖2中，8個訂單（含有1～5件商品）被分批次地分配給兩名揀選員，每個批次容量限制為7件。例如，在圖2（a）給出的初始解中，訂單O2和O3匯總成批次＃1，被分配給了揀選員甲，該批次共需揀選6件商品。圖2（b）是揀選員甲的批次＃1與批次＃2交換后生成的解。圖2（c）是揀選員甲的批次＃1和揀選員乙的批次＃4交換后生成的解。訂單圖示和每個解的訂單總延遲時間如圖2（d）和圖2（e）所示。

1.2 集合、參數與變量

結合如上問題描述，我們給出建立模型所需的集合、參數和決策變量。

集合：

P=｛1，2，…，pmax｝ 揀選員的集合；

B=｛1，2，…，m｝ 可行批次的集合；

J=｛1，2，…，n｝ 客戶訂單的集合；

V=｛v1，v2，…，vg｝ 商品存儲點的集合。

參數：

cj訂單j（j∈J）包含的商品數量；

C 批次容量限制；

dj訂單j（j∈J）的完成期限；

M 一個足夠大的數；

圖2 訂單批次的排序與分配變換

vtravel揀選員在揀選路徑中的行走速度（單位：距離每單位時間）；vitem揀選員搜尋、揀取、核對貨品的速度（單位：時間每單位貨品）；

tsetup揀選員準備一個批次的時間；

est商品存儲點s與t之間的距離的集合（?s≠t∈V）；

αsj訂單j（j∈J）中是否包含存儲在位置s（s∈V）的商品；若是則αsj=1，否則αsj=0。

決策變量：

Tjpk訂單j（j∈J）分配到揀選位置Lpk（p∈P，k∈K）的延遲時間；

ctp，k揀選位置Lpk（p∈P，k∈K）的完成時間；

xjpk訂單j（j∈J）是否分配到揀選位置Lpk（p∈P，k∈K）中，若是則xjpk=1，否則xjpk=0；

zbs在存儲點s（s∈V）的商品是否在可行批次b（b∈B）中被揀選，是則為1，否則為0；

ybst弧段（s，t）（s≠t∈V）是否在可行批次b（b∈B）的行走路徑中，是則為1，否則為0；

ubpk批次b（b∈B）是否分配到揀選位置Lpk（p∈P，k∈K）中，是則為1，否則為0；

Vbj訂單j（j∈J）是否分配到可行批次b（b∈B）中，是則為1，否則為0。

數學模型：

根據上面的參數和變量，建立如下混合整數規劃（MIP）模型：

模型闡述：

函數（1）是目標函數，即求訂單總延遲時間的最小值。約束（2）給出訂單分配到批次的決策變量的定義，保證只有當訂單與可行批次分配到同一揀選位置時，決策變量才為1。約束（3）保證每個訂單僅被分配到一個可行批次中。約束（4）保證批次中的商品數不超過其批次容量限制。約束（5）確保每個揀選位置最多分配一個可行批次。若一個可行批次被分配到某個揀選位置，該位置記為有效揀選位，約束（6）～（8）可看作該批次的揀選路徑問題（TSP）；否則，該位置為空揀選位。約束（6）給出批次的行走路徑長度公式。約束（7）保證批次中的商品存儲點僅被訪問一次。約束（8）確保批次揀選路徑中沒有子回路出現。約束（9）表示批次中的商品存儲點受限于訂單中的商品存儲點。約束（10）保證兩個相鄰的有效揀選位（批次）的處理時間不重疊，即一個揀選員在某個時刻僅能處理一個批次。約束（11）表示揀選員的批次起始時刻為0。約束（12）表示揀選位置中訂單的延遲時間。約束（13）保證批次完成時刻和揀選位置中訂單的延遲時間的非負性。

2 問題求解

對于上述建立的非線性混合整數模型，當問題規模較大時，求最優解十分困難，所以我們采用啟發式算法求解。本文首先設計了改進節約法得到一個較好的初始解，再利用可變鄰域下降算法得到最優解。涉及路徑問題，采用2-opt方法得到每個批次的最優揀選路徑。

2.1 問題初始解

鄰域算法的結果受初始解的影響較大，好的初始解能夠提高算法的收斂速度。Henn給出了一種最早起始日期（ESD）算法。這種算法基于訂單完成期限的優先級規則，卻沒有考慮到批次處理時間（主要是路徑行走時間）對總延遲時間的影響。因此，我們結合最早起始日期算法，提出了一種基于Clark-wright算法的改進節約法。該算法的基本思路是：首先基于ESD算法，將每個訂單作為一個批次分配給揀選員；然后，在批次容量限制下，先選擇當前完成期限最早的訂單，再選擇另一個訂單與其合并為一個批次，選擇依據是選擇能使訂單總延遲時間減少最多的那個。算法的具體步驟如下：

算法1：改進節約法

階段一

步驟1：若未分配訂單集合U中還有未分配的訂單，取其中完成期限最早的訂單j；否則，跳轉階段二；

步驟2：對每個揀選員p，將訂單j作為一個單獨的批次，分配到該揀選員p最后一個批次位置之后，記分配前揀選員p的最后一個批次的結束時間為sdp；

步驟3：取p*=arg min｛sdp｜p∈P｝；給揀選員p*新開一個批次并將訂單j分配到新批次中；在集合U中去除訂單j，返回步驟1。

階段二

步驟4：記初始解為當前解；重置所有訂單到集合U；

步驟5：若集合U非空，取集合U中完成期限最早的訂單n*；否則，跳轉步驟9；

步驟6：記訂單n*所在批次Bpk=｛n*｝，批次Bpk的容量W=wn*，在集合U中去除訂單n*；

步驟7：定義savn，pk為將訂單n分配到批次Bpk中后得到的新解比當前解減少的總延遲時間。若savn，pk存在且 max｛savn，pk｜n∈U：W+wn≤C｝＞0（C為批次容量限制，wn是訂單n的商品數），進入下一步；否則，返回步驟5；

步驟8：取使總延遲時間減少最多的訂單n’，將訂單n’加入批次Bpk中，更新批次容量，調整當前解并重新計算總延遲時間；在集合U中去除訂單n’；返回步驟7；

步驟9：輸出當前解，算法結束。

2.2 鄰域結構

在運用可變鄰域下降算法前，首先分析初始解的鄰域結構。鄰域的定義：設一個組合優化問題的可行解集合為S，對一個解s∈S，我們定義N（s）為解s的鄰域，其中N（s）?S。對于?s’∈N（s），s’可以通過s的一次局部移動或交換獲得。本文初始解的結構可以參考圖2（a）。初始解的鄰域分為兩種類型，一種參考圖2（b）和圖2（c），我們稱為批次鄰域，另一種稱為訂單鄰域。

批次鄰域并不改變批次的內部訂單組成，只通過批次的移動或交換生成。批次的移動或交換，可以發生在一個揀選員內部，也可以發生在兩個揀選員之間。考慮到我們已基于最早起始日期構造了初始解，顯然同一揀選員內部批次之間的移動或交換已不能改善初始解。這樣，初始解的批次鄰域有如下兩種：

Nbatch1：在兩個不同的揀選員之間，移動其中一個揀選員的某個批次到另一個的批次序列中；

Nbatch2：在兩個不同的揀選員之間交換兩個批次。

類似的，訂單鄰域通過訂單的移動或交換生成。然而，由于訂單的移動或交換會改變批次結構，需要考慮兩方面的特殊情況。一方面，由于批次存在容量限制，訂單不一定能移動或交換進去，為保證鄰域是可行解，對于這種訂單，需要開辟一個新批次來放置，新批次將插入目標揀選序列最后一個揀選位置之后。另一方面，當某個批次的訂單被移走后，揀選位置會變成空揀選位，需要刪除這些空揀選位，避免計算資源的浪費。初始解的訂單鄰域有如下四種：

Norder1：在同一個揀貨員內部，移動其中某批次的某個訂單到另一個批次中；

Norder2：在兩個不同的揀選員之間，移動一個揀選員某個批次的某個訂單到另一揀選員的某個批次中；

Norder3：在同一個揀貨員內部，交換不同的兩個批次中的兩個訂單；

Norder4：在兩個不同的揀選員之間交換兩個訂單。

2.3 可變鄰域下降算法

以確定性的方式探索鄰域結構的局部搜索算法被稱為可變鄰域下降算法（Variable Neighborhood Descent，VND）。因為不同的鄰域結構通常具有不同的局部最小值，所以通過鄰域的確定性變化，VND能較快擺脫局部最優陷阱。

算法需要一個確定的鄰域結構序列。我們基于改進節約法，結合之前的數值實驗，確定選取N1=Nbatch2，N2=Norder1，N3=Norder2，N4=Norder3，N5=Norder4。VND算法的具體步驟如下

算法2：可變鄰域下降算法

步驟1：生成初始解s；

步驟2：sinc=s；m=1；計算總延遲時間tard（s）；

步驟3：當m不大于M 時，取s*=arg min｛tard（s）｜s∈Nm（sinc）｝；否則跳轉步驟6；

步驟4：當tard（s*）＜tard（sinc）時，進入步驟5；否則，m=m+1，跳回步驟3；

步驟5：sinc=s*；m=1；跳回步驟3；

步驟6：輸出當前解sinc，算法結束。

2.4 2-opt方法

2-opt方法是一種簡便實用的局部搜索算法，被廣泛應用于解決TSP。其基本思想是隨機取路徑中的兩個節點（非起止點），將兩個節點之間的路徑翻轉獲得新路徑（2-opt操作）。舉個例子，若原路徑是［A，B，C，D，E，F，A］，2-opt操作選取節點B和E，則新路徑變為［A，E，D，C，B，F，A］。在所有2-opt操作得到的新路徑都不能改善當前路徑時，當前路徑即為一條2-opt路徑。在小規模TSP中，2-opt路徑幾乎可以作為最優解。

算法3：2-opt方法

步驟1：將S型策略的路徑作為初始解s；sinc=s；

步驟2：置count為0，當count不滿足終止條件，進入下一步；否則，跳至步驟6；

步驟3：通過2-opt操作產生新路徑snew=2opt（sinc）；

步驟4：若distance（snew）＜distance（sinc），進入下一步；否則，count++；跳轉回步驟2；

步驟5：count=0；sinc=snew；跳轉回步驟2；

步驟6：輸出當前解sinc，算法結束。

3 數值實驗

算法的實現基于一組數值實驗。我們假設了一個單庫區，具有800個貨位，通道的具體分布如圖1所示。庫區起始點在庫區左下角。庫區有10個通道，通道從左向右依次從1到10號編號。每個通道兩邊各有40個貨位。倉儲中心實際常采用ABC三分類的存儲策略，A類商品能夠滿足50%的訂單需求，B類商品能夠滿足30%，剩余20%歸為C類。我們設定1、2號通道存放A類商品，3、4、5號通道存放B類商品，剩余通道存放C類商品。

揀選員人數設定為2人和4人。批次容量限制設為10和20。訂單的數目設置成50和100。由于電商的訂單體量較小，假定訂單包含的商品數均勻分布在集合｛1，2，3，4，5｝中。每個訂單的完成期限從一個時間窗口［minj∈Jptj，（2·（1-MTCR）∑j∈Jptj+minj∈Jptj）／pmax］中隨機生成。其中，訂單處理時間ptj是指訂單j單獨作為一個批次揀選處理的時間，MTCR（0＜MTCR＜1）稱為修正交通阻塞率，描述了訂單完成期限的緊急度。當比率較大時，訂單的完成期限比較緊急，且上述的時間窗口較窄。我們設定MTCR的比率為0.6和0.8，分別對應完成期限要求寬松和緊急的情況。

設兩個貨位之間的距離為一個長度單位，記為LU。起始點距離最近的貨位點距離為5LU。通道寬1LU，通道出入口轉彎需1LU。行走速度vtravel設為20LU／min，搜索核對商品速度vitem設為0.25min／item，準備時間tsetup設為3min。設立三種情形，后兩種都是對第一種的改進。情形Ⅰ采用ESD算法求初始解，S型路徑策略進行揀選作業；情形Ⅱ保持路徑策略不變，用節約法改進初始解；情形Ⅲ仍用ESD算法求初始解，換用2-opt路徑策略揀選。

基于上述設定，我們隨機生成了一批訂單，對聯合訂單批次分配排序和路徑問題，分別對上述三種情形進行求解，用python3.6編程，在Core（TM）i7-6700 CPU＠3.4GHz，16G內存的PC上實現了仿真實驗。結果如表1所示，其中對初始解的提升比率imp=（tard（sESD）-tard（sVND）／tard（sESD）。

分析實驗結果。首先，VND算法對初始解的提升比率平均約為40%，當訂單完成期限較緊（MTCR=0.8）時，VND對初始解的提升比率（情形Ⅰ、情形Ⅲ）達到50%以上。其次，情形Ⅲ的2-opt路徑策略比情形Ⅰ求得的總延遲時間更優，平均減少約100min；提升比率也最高，平均比情形Ⅰ高出近7%。最后，當MTCR=0.8時，情形Ⅱ的改進節約法給出的初始解優于ESD算法；對初始解提升比率，當訂單量較大（N=100）時提升顯著，比情形Ⅰ高出9%。

表1 三種情形的總延遲時間（單位：min）和對初始解的提升比率

4 結語

本文對電商倉儲中前沿的聯合訂單批次分配排序和路徑問題進行描述，給出了相應的示例圖，并建立了混合整數規劃的數學模型。我們采用啟發式算法求解，基于改進節約法給出一個較好的初始解，通過可變鄰域下降算法對模型進行求解，其中對批次揀選路徑利用2-opt方法快速優化。仿真實驗結果表明，在聯合揀選路徑問題之后，2-opt路徑策略能顯著節省訂單總延遲時間；當訂單完成期限較緊急、訂單量較大時，改進節約法給出的初始解優于ESD算法。