電商倉(cāng)儲(chǔ)聯(lián)合訂單批次分配排序和路徑問題

王 迪

（上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院，上海 200030）

0 引言

中國(guó)每年要產(chǎn)生300億件以上的快遞包裹，這得益于電子商務(wù)的快速發(fā)展。倉(cāng)儲(chǔ)物流日益成為電商發(fā)展中的瓶頸所在。訂單揀選流程是倉(cāng)儲(chǔ)運(yùn)營(yíng)中最為關(guān)鍵的流程，占用了60%以上的運(yùn)營(yíng)成本。相較于傳統(tǒng)的倉(cāng)儲(chǔ)中心，電商倉(cāng)儲(chǔ)中心的訂單具有日均單量高、訂單體量小、及時(shí)響應(yīng)性高等特點(diǎn)。如何確定最優(yōu)的訂單批次，如何調(diào)度批次的分配和排序，如何在較短時(shí)間內(nèi)完成訂單的揀選，聯(lián)合訂單批次分配排序和路徑問題引起了業(yè)界和學(xué)術(shù)界的關(guān)注。

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

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

1 聯(lián)合訂單批次分配排序和路徑問題

1.1 問題描述

我們考慮的是一個(gè)人工揀選、低位貨架的單庫(kù)區(qū)，采用人到貨的揀選方式。庫(kù)區(qū)中貨架有規(guī)則地編號(hào)，商品可以方便地被揀選員揀取。庫(kù)區(qū)僅有一個(gè)起始點(diǎn)，分布在庫(kù)區(qū)左下角，可以進(jìn)行準(zhǔn)備、卸貨和打包等操作。揀選員采用手推車等揀選設(shè)備進(jìn)行揀選，揀選設(shè)備有容量限制。

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

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

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

圖1 S型策略

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

1.2 集合、參數(shù)與變量

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

集合：

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

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

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

V=｛v1，v2，…，vg｝ 商品存儲(chǔ)點(diǎn)的集合。

參數(shù)：

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

C 批次容量限制；

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

M 一個(gè)足夠大的數(shù)；

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

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

tsetup揀選員準(zhǔn)備一個(gè)批次的時(shí)間；

est商品存儲(chǔ)點(diǎn)s與t之間的距離的集合（?s≠t∈V）；

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

決策變量：

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

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

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

zbs在存儲(chǔ)點(diǎn)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。

數(shù)學(xué)模型：

根據(jù)上面的參數(shù)和變量，建立如下混合整數(shù)規(guī)劃（MIP）模型：

模型闡述：

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

2 問題求解

對(duì)于上述建立的非線性混合整數(shù)模型，當(dāng)問題規(guī)模較大時(shí)，求最優(yōu)解十分困難，所以我們采用啟發(fā)式算法求解。本文首先設(shè)計(jì)了改進(jìn)節(jié)約法得到一個(gè)較好的初始解，再利用可變鄰域下降算法得到最優(yōu)解。涉及路徑問題，采用2-opt方法得到每個(gè)批次的最優(yōu)揀選路徑。

2.1 問題初始解

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

算法1：改進(jìn)節(jié)約法

階段一

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

步驟2：對(duì)每個(gè)揀選員p，將訂單j作為一個(gè)單獨(dú)的批次，分配到該揀選員p最后一個(gè)批次位置之后，記分配前揀選員p的最后一個(gè)批次的結(jié)束時(shí)間為sdp；

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

階段二

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

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

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

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

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

步驟9：輸出當(dāng)前解，算法結(jié)束。

2.2 鄰域結(jié)構(gòu)

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

批次鄰域并不改變批次的內(nèi)部訂單組成，只通過批次的移動(dòng)或交換生成。批次的移動(dòng)或交換，可以發(fā)生在一個(gè)揀選員內(nèi)部，也可以發(fā)生在兩個(gè)揀選員之間?？紤]到我們已基于最早起始日期構(gòu)造了初始解，顯然同一揀選員內(nèi)部批次之間的移動(dòng)或交換已不能改善初始解。這樣，初始解的批次鄰域有如下兩種：

Nbatch1：在兩個(gè)不同的揀選員之間，移動(dòng)其中一個(gè)揀選員的某個(gè)批次到另一個(gè)的批次序列中；

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

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

Norder1：在同一個(gè)揀貨員內(nèi)部，移動(dòng)其中某批次的某個(gè)訂單到另一個(gè)批次中；

Norder2：在兩個(gè)不同的揀選員之間，移動(dòng)一個(gè)揀選員某個(gè)批次的某個(gè)訂單到另一揀選員的某個(gè)批次中；

Norder3：在同一個(gè)揀貨員內(nèi)部，交換不同的兩個(gè)批次中的兩個(gè)訂單；

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

2.3 可變鄰域下降算法

以確定性的方式探索鄰域結(jié)構(gòu)的局部搜索算法被稱為可變鄰域下降算法（Variable Neighborhood Descent，VND）。因?yàn)椴煌泥徲蚪Y(jié)構(gòu)通常具有不同的局部最小值，所以通過鄰域的確定性變化，VND能較快擺脫局部最優(yōu)陷阱。

算法需要一個(gè)確定的鄰域結(jié)構(gòu)序列。我們基于改進(jìn)節(jié)約法，結(jié)合之前的數(shù)值實(shí)驗(yàn)，確定選取N1=Nbatch2，N2=Norder1，N3=Norder2，N4=Norder3，N5=Norder4。VND算法的具體步驟如下

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

步驟1：生成初始解s；

步驟2：sinc=s；m=1；計(jì)算總延遲時(shí)間tard（s）；

步驟3：當(dāng)m不大于M 時(shí)，取s*=arg min｛tard（s）｜s∈Nm（sinc）｝；否則跳轉(zhuǎn)步驟6；

步驟4：當(dāng)tard（s*）＜tard（sinc）時(shí)，進(jìn)入步驟5；否則，m=m+1，跳回步驟3；

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

步驟6：輸出當(dāng)前解sinc，算法結(jié)束。

2.4 2-opt方法

2-opt方法是一種簡(jiǎn)便實(shí)用的局部搜索算法，被廣泛應(yīng)用于解決TSP。其基本思想是隨機(jī)取路徑中的兩個(gè)節(jié)點(diǎn)（非起止點(diǎn)），將兩個(gè)節(jié)點(diǎn)之間的路徑翻轉(zhuǎn)獲得新路徑（2-opt操作）。舉個(gè)例子，若原路徑是［A，B，C，D，E，F(xiàn)，A］，2-opt操作選取節(jié)點(diǎn)B和E，則新路徑變?yōu)椋跘，E，D，C，B，F(xiàn)，A］。在所有2-opt操作得到的新路徑都不能改善當(dāng)前路徑時(shí)，當(dāng)前路徑即為一條2-opt路徑。在小規(guī)模TSP中，2-opt路徑幾乎可以作為最優(yōu)解。

算法3：2-opt方法

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

步驟2：置count為0，當(dāng)count不滿足終止條件，進(jìn)入下一步；否則，跳至步驟6；

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

步驟4：若distance（snew）＜distance（sinc），進(jìn)入下一步；否則，count++；跳轉(zhuǎn)回步驟2；

步驟5：count=0；sinc=snew；跳轉(zhuǎn)回步驟2；

步驟6：輸出當(dāng)前解sinc，算法結(jié)束。

3 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

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

4 結(jié)語(yǔ)

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