陳彥博，陳 峰，文若霖

(上海交通大學 中美物流研究院，上海 200030)

隨著電商平臺的快速發(fā)展與普及，電商交易量及物流量快速增長。2020年，中國快遞業(yè)務量和收入分別完成630億件和7 450億元，同比增長24%和23%。物流對于電子商務的作用越來越大，以平臺銷售為主的電子商務逐漸轉變成以倉儲運作與服務為主的現(xiàn)代化電商模式。因此，倉儲物流成為了電商服務質量的一個重要問題和瓶頸之一。實際的電商倉儲揀選作業(yè)流程如圖1所示。電商倉儲庫區(qū)中，通常采用人工揀選的方式，貨架為統(tǒng)一的低位貨架，庫區(qū)中會按照貨位進行編號，以便揀選人員進行揀貨。

圖1 電商倉儲揀選作業(yè)流程Figure 1 E-commerce warehouse picking process

在揀選作業(yè)中，常遇到以下問題：1) 大量相似度高的商品未能有效合并，造成多次重復揀選；2) 實際揀選作業(yè)中大規(guī)模訂單未能合理安排，揀選人員眾多但實際效率不高。為了解決訂單揀選的問題，本文研究電商倉儲的訂單分批和路徑優(yōu)化問題，本質上是訂單分批問題和路徑優(yōu)化問題的組合優(yōu)化問題。針對這兩個問題，近年來許多學者都對這方面進行過許多研究。

訂單分批問題，可以看作特殊的裝箱問題。裝箱問題的目標是希望能用盡量少的容器裝入更多的物品，同裝箱問題稍有所不同，訂單分批的目標是批次的總揀選路徑距離最短，且包含所有的訂單。Hwang等[1]用聚類的方法，將訂單的相似度定義為向量的相似度，通過計算向量相似度，將訂單進行合并。陳方宇[2]定義了基于偏離度的相似性，并在多區(qū)塊的庫區(qū)中，通過偏離度相似性對訂單分批進行求解。

訂單路徑優(yōu)化問題中，對每一位揀選員來說，可以看作是特殊的旅行商問題，其目標是使每個批次內單一揀選員完成批次所有訂單商品的揀選任務所需要行走的距離最小。解決揀選中的路徑優(yōu)化問題，通常有兩種方向，一種是基于啟發(fā)式的行走策略，另一種是基于網(wǎng)絡的策略。?ncan等[3]對路徑優(yōu)化問題進行建模，建立混合整數(shù)規(guī)劃模型，并分別利用S型策略、返回策略及中點策略對問題進行求解。李詩珍等[4]在S型策略的基礎上，提出一種動態(tài)規(guī)劃的算法對問題進行求解，保證在既定規(guī)則下的最優(yōu)揀貨路徑。

隨著訂單分批和路徑優(yōu)化問題研究的不斷深入，相關學者開始對訂單分批和路徑優(yōu)化的組合優(yōu)化問題進行研究。Won等[5]較早開始對訂單分批和路徑優(yōu)化問題進行研究，將批次的整體處理時間作為優(yōu)化目標，并構建一個整數(shù)規(guī)劃模型進行求解。Kulak等[6]提出基于聚類的禁忌搜索算法用于求解訂單分批和路徑優(yōu)化問題。Valle等[7]針對聯(lián)合訂單分批和路徑優(yōu)化問題提出一個混合整數(shù)規(guī)劃模型，并通過分支定界割平面的方法進行求解。Valle等[8]在此基礎上，又提出一個近似模型，將路徑優(yōu)化中的TSP (travelling salesman problem，旅行商問題) 問題轉化為一個近似模型進行求解。Hong等[9]考慮揀選過程中可能產(chǎn)生的堵塞問題，并提出啟發(fā)式算法進行求解。Van Gils等[10]提出一個考慮揀選時間的混合整數(shù)規(guī)劃模型，并通過局部搜索對模型進行求解。Briant等[11]考慮一個HappyChic的特定倉儲揀選模式下的訂單分批問題，并通過列生成算法對問題進行了分解并求解。也有很多學者從工作負荷[12]、交付時間[13]、工作時間[14]等方面對問題進行研究。

精確算法之外，元啟發(fā)式算法也廣泛應用于訂單分批和路徑規(guī)劃問題中。Chen等[15]提出蟻群算法用于多區(qū)塊、多通道的訂單揀選問題中。之后，在蟻群算法的基礎上實現(xiàn)了許多元啟發(fā)式的組合算法。Li等[16]結合蟻群算法和鄰域搜索。De Santis等[17]結合Floyd算法和蟻群算法。Chen等[18]結合蟻群算法和遺傳算法。啟發(fā)式算法可以較快地獲得一個近似解，并且經(jīng)過不斷的研究和擴展，也已比較成熟。

現(xiàn)有研究中已經(jīng)包含對于訂單分批和路徑優(yōu)化問題的混合整數(shù)規(guī)劃建模和求解。但主要基于啟發(fā)式算法，并且沒有對大規(guī)模問題進行較為深入的研究。本文在上述研究的基礎上，考慮在電商倉儲環(huán)境下的庫區(qū)中，如何合理地對訂單進行分批，并使得每一個批次中的路徑最優(yōu)。在此基礎上建立混合整數(shù)規(guī)劃模型，針對提出的模型設計分支定價算法，構造模型的主問題和子問題；通過列生成算法獲得限制主問題的近似最優(yōu)解；再利用分支定界法對初始解進行改進，獲得最優(yōu)整數(shù)解；最后使用算法進行數(shù)值實驗，通過多組數(shù)值實驗和案例驗證模型的有效性和算法的高效性。

1 問題描述和數(shù)學模型

1.1 問題描述

本文研究面向電商倉儲的訂單分批和路徑優(yōu)化問題，其對象是具有多區(qū)塊、多通道、多交叉點物理布局的倉庫，如圖2所示。揀貨路徑從起點出發(fā)，沿虛線經(jīng)過貨架間的通道和通道間的交叉點，揀選所有貨物后，再回到起點。問題具體描述如下。

圖2 揀貨路徑圖Figure 2 Picking routing

假設庫區(qū)為一個有向圖G=(V,A)，其中，V為庫區(qū)網(wǎng)絡中所有頂點集合，包括起點和多個貨位點，共有vmax個 頂點；A為網(wǎng)絡中各個貨位點所連接的弧的集合，其中弧 (i,j)∈A，弧之間的距離為di j。O代表所有需要揀選的訂單集合，數(shù)量為n；訂單分批的批次集合為B，包含的批次數(shù)量為m。從訂單分批到完成揀選，需要解決分批和路徑優(yōu)化兩個問題，其中的路徑優(yōu)化實際上是一個TSP問題。對于每一個批次b中 的所有訂單O′，以xij作 為弧 (i,j)的決策變量，要使得批次內的所有貨物揀選的路徑xijdij最優(yōu)。優(yōu)化每一個批次的路徑后，同時需要優(yōu)化每個批次中的訂單集合O′，在滿足每個批次不超過訂單容量上限C的情況下，使得總距離最短。因此，本文研究的是同時考慮訂單分批和路徑優(yōu)化的組合優(yōu)化問題。在這個問題中，不考慮揀選員的工作負荷，假設每個揀選員擁有相同的行走速度和揀選熟練度，優(yōu)化只考慮行走的距離最優(yōu)。

1.2 集合及變量

為解決如上問題描述，綜合考慮訂單分批問題和路徑優(yōu)化問題，建立一個混合整數(shù)規(guī)劃模型，目標是使得所有訂單進行分批后總揀選距離最優(yōu)。同時考慮有向圖中可能存在貨位點和只用于行走的交叉點。首先，給出以下建立模型所需的集合、參數(shù)變量和決策變量。

集合：

O={1,2,···,n}，為包含所有訂單的集合；

B={1,2,···,m}，為包含所有批次的集合；

V={0,1,2,···,vmax}，為包含所有頂點的集合；

參數(shù)變量：

C為每個批次的訂單數(shù)量上限；

di j為頂點i到j的距離；

Aij為弧 (i,j)是否在網(wǎng)絡圖中，是則為1，否則為0；

li為頂點i是否為一個貨位點，是則為1，否則為0；

Uoi為 訂單o中 是否包含貨位點在i的貨物，是則為1，否則為0。

決策變量：

為 批次b中 的路徑是否經(jīng)過弧 (i,j)，是則為1，否則為0；

為批次b中 是否包含訂單o，是則為1，否則為0；Qb為批次b是否至少包含一個訂單(被選擇)，是則為1，否則為0；

為批次b中 頂點i的出度。

國外的餐飲企業(yè)充分的調動了社會資源，實行輕資產(chǎn)運營，在供應鏈和中央廚房的選擇上，并不自己建設，而是采用參股或者合作的方式，組織非常靈活，沒有任何重資產(chǎn)，例如麥當勞、肯德基。

1.3 模型建立

建立如下混合整數(shù)規(guī)劃(MIP)模型。

其中，目標函數(shù)(1)表示最小化所有批次的總揀選行走距離，約束主要可以分為2個部分。

約束(2)～(6)表示對于批次中的路徑優(yōu)化。約束(2)保證批次中每一個弧 (i,j)的流量平衡，如果從弧中的一個點進入，則必然會從該點去往另一個點。約束(3)、(4)保證在一個批次中，如果至少包含一個訂單，那么它的路徑必須包含起點 0。約束(5)、(6)用于消除路徑優(yōu)化中的子回路，其中約束(5)表示在批次中某一個頂點的出度；約束(6)則是利用出度的性質，消除可能產(chǎn)生的子回路。

約束(7)～ (14)表示對于所有訂單分批。約束(7)保證訂單的數(shù)量不超過批次的訂單容量約束。約束(8)保證每一個訂單只包含在唯一的批次內。約束(9)表示批次節(jié)點與訂單的關系，如果有一個訂單被安排到一個批次中，那么這個訂單中包含商品的庫位頂點至少將被訪問一次。約束(10)表示批次、訂單、弧之間的關系，當訂單在一個批次中，該批次才能夠包含可被訪問的弧。約束(11)表示只有當批次中含有訂單才選擇批次。約束(12)～ (14)定義了變量的類型。

2 分支定價算法設計

為解決大規(guī)模問題、加快求解速度，本文針對提出的訂單分批與路徑優(yōu)化問題設計分支定價算法，利用列生成算法對大規(guī)模問題進行分解。將混合整數(shù)規(guī)劃模型松弛為線性規(guī)劃模型，并將問題分解為主問題和子問題(價格問題)。主問題對選定的分批形式進行選擇，子問題對每種批次內的貨物揀選路徑進行求解。每求一次子問題，便將對應的檢驗數(shù)為負的“列”(批次)加入到主問題中，相當于修正的單純形法。將新列作為進基變量加入主問題，再對主問題求解，迭代直至所有檢驗數(shù)非負，找到主問題的最優(yōu)解。若主問題的最優(yōu)解為整數(shù)，即得到訂單分批和路徑優(yōu)化問題的最優(yōu)解；否則，利用分支定界算法，獲得原問題的最優(yōu)整數(shù)解。

2.1 主問題模型 (master problem，MP)

首先要將模型轉換為集合覆蓋模型，才能滿足列生成算法的要求。假設S表示滿足批次容量的O中所有訂單的所有可能批次訂單組合子集：S={s1,s2,···,。其中，s∈S表示列生成中所需要的“列”。訂單與列之間的關系，通過決策變量來表示：，其中n表示表示訂單的數(shù)量。每個表 示這個“列”s的批次訂單組合中是否包含訂單o中的所有貨物。由于集合覆蓋模型中不再有頂點的含義，因此用ds表 示揀選所有s中訂單的貨物的最優(yōu)路徑距離。因此，實際上S表示了所有滿足批次訂單容量限制的可行路徑的集合，而其中的每一個s，不止可以當作一個批次訂單組合，也可以表示一條可行的路徑，而ds就 表示最優(yōu)路徑s的距離。因此，主問題模型就轉換為一個選擇路徑的集合覆蓋模型。

令變量 αs∈{0,1}表 示是否選擇了路徑s。可以得到一個整數(shù)規(guī)劃模型作為主問題如下。

其中，目標函數(shù)(15)表示所有選擇的路徑(批次訂單組合)的總距離最?。患s束(16)確保每個訂單都被揀選。為了使用列生成算法，需要將這個問題進行線性松弛，得到一個新的線性主問題(linear master problem,LMP)。此外，由于集合S的數(shù)量隨訂單的數(shù)量以指數(shù)增加，因此需要對主問題進行松弛。令S′表 示S的一個子集，定義該問題的一個限制主問題(restricted linear master problem,RLMP)如下。

2.2 子問題模型 (sub-problem,SP)

由rs的定義，對應的子問題如下。

其中，po表 示是否選擇了訂單o。約束(22)表示每個批次中的最大容量不超過C。約束(23)保證網(wǎng)絡中的流量平衡。約束(24)保證每條路徑從起點出發(fā)。約束(25)表示xij與po之 間的關系：如果選擇了訂單o，則必須經(jīng)過訂單o中的某一個貨位點。約束(26)、(27)用于消除可能產(chǎn)生的子回路。約束(28)表示子問題中距離d的計算方式，通過求解子問題的線性松弛問題，能夠得到xij的 整數(shù)解，進而獲得po的解。

2.3 生成初始可行解

在列生成算法中，主問題首先需要通過初始可行解，得到一個對偶值，代入子問題中進行求解獲得檢驗數(shù)。因此，在算法開始時需要生成一個初始解。初始解包含多個“列”，即多種批次的可能訂單情況。由于可行解必然包含所有的訂單，因此為了快速生成一個初始可行解，則可以按訂單次序，生成批次數(shù)量最小的訂單批次組合。例如：當前有100個訂單，假設每個揀選員分配到的批次訂單上限為8個訂單，則按訂單次序，將100個訂單填滿12個批次，最后4個訂單放到第13個批次中。這樣即可生成一個最簡單的初始可行解(列)。而對于每一個初始可行解，還要求解其最優(yōu)路徑，因此對于初始可行解的每一個批次，都利用TSP模型對其求解一個最優(yōu)的距離ds，求解模型如下。

其中，變量及參數(shù)與子問題相同，約束中去除子問題中主問題解的對偶值的影響。

2.4 算法具體步驟

根據(jù)上文的主問題、子問題模型，實現(xiàn)對于原問題的分解，原問題被分解為一個選擇訂單批次組合的主問題和單個批次訂單組合的TSP子問題。在此基礎上，可以實現(xiàn)列生成算法，在生成初始解后，利用列生成算法不斷迭代，直至找到限制主問題的最優(yōu)解。由于原問題希望得到最優(yōu)的整數(shù)解，因此，需要在列生成算法的基礎上，通過分支定界法生成新的分支節(jié)點進行進一步搜索，將分支節(jié)點加入限制主問題中繼續(xù)求解。若解為整數(shù)，則更新上界，直至找不到一個更好的整數(shù)解，則此時的上界即為原問題的最優(yōu)整數(shù)解，這也是分支定價算法的過程，如圖3所示。因此，分支定價算法的流程可以描述如下。

圖3 分支定價算法流程圖Figure 3 Branch and price algorithm flow

步驟1產(chǎn)生初始解后，加入到主問題的集合S，組成根節(jié)點，并作為初始的上界，下界初始為0；

步驟2初始搜索，根據(jù)主問題，選擇一個節(jié)點作為初始解生成初始可行的限制主問題R LMP(S′)；

步驟3求解當前限制主問題，獲得初始解 αs和對偶變量 σo；

步驟4求解對應的子問題，對于所有的s∈S′，如果檢驗數(shù)均為非負，那么轉向步驟6，否則轉向步驟5；

步驟5將檢驗數(shù)為負且最小的列s對應的列添加到限制主問題中，轉向步驟2；

步驟6如果此時限制主問題的解 αs為整數(shù)，轉步驟7，否則轉步驟8；

步驟7將解的目標值與當前的上界進行比較，如果小于上界，則更新上界值；

步驟8刪除當前節(jié)點，根據(jù)分支定價的策略進行分支，更新批次路徑集合S，生成分支節(jié)點，加入搜索樹中；

步驟9若搜索樹非空，則轉向步驟3，否則轉向步驟10；

步驟10當前的上界即為最優(yōu)解。

3 數(shù)值實驗

3.1 模型與算法的驗證分析

為了驗證模型的準確性，本文利用IBM ILOG CPLEX 12.10對原模型進行求解，然后與分支定價算法的求解結果進行比較。實驗設計了3組倉儲示例，貨位點數(shù)量分別為6、12、32。每組實例中，分別設置3組訂單數(shù)量，批次數(shù)量不同的算例進行測試，實驗參數(shù)如表1所示。表2是小規(guī)模的實驗結果，其中d表示總最優(yōu)路徑(m)，t表示求解時間(s)。從結果可以看出，直接利用CPLEX求解和使用分支定價法求解可以得到相同的整數(shù)解，隨著規(guī)模的逐漸增加，分支定價法求解的速度將會明顯優(yōu)于CPLEX，并能夠得到一個同樣精確的結果。

表1 小規(guī)模實驗參數(shù)Table 1 Parameters of small scale experiment

表2 小規(guī)模實驗求解結果Table 2Results of small scale experiments

3.2 大規(guī)模的實驗分析

由于在大規(guī)模問題中，直接利用CPLEX求解器求解需要非常長的時間，因此，對于大規(guī)模問題，通過分支定價算法對其求解，能提高求解速度，并且也能夠獲得精確解。為了驗證分支定價算法對于大規(guī)模問題的可行性，本文設計了12組算例進行實驗。倉儲貨位分布如圖2所示，有72個貨位點和12個交叉點，貨架節(jié)點間的距離設置為1，實驗參數(shù)如表3所示。結果如表4所示。通過結果可以看出，分支定價算法針對規(guī)模較大的訂單分批和路徑優(yōu)化問題，也可以在一個可接受時間內獲得精確解，因此也驗證了分支定價算法對于大規(guī)模訂單分批和路徑優(yōu)化問題的可行性。

表3 大規(guī)模實驗參數(shù)Table 3 Parameters of large scale experiments

結合表4的數(shù)值實驗結果，同時分析訂單數(shù)量和單個訂單內貨物數(shù)量大小對于求解速度的影響，如圖4、圖5所示。求解時間會隨著訂單規(guī)模的增大發(fā)生比較明顯的上升，但總體而言，在處理大規(guī)模問題時，分支定價算法依然可以在有限時間內得到一個精確解，滿足實際的求解需要。

圖4 不同訂單規(guī)模求解時間Figure 4 Solution time of different order size

圖5 不同訂單規(guī)模求解時間增長趨勢Figure 5 Time growth trend of different order sizes

表4 大規(guī)模實驗結果Table 4Results of large scale experiments

4 案例分析

本文以實際的電商第三方倉儲企業(yè)的庫區(qū)作為實例進行分析。圖6是某個單一庫區(qū)的布局圖。庫區(qū)中共有26個貨位點、12個交叉點，所有的貨架采用標準的低位貨架，忽略揀選過程中不同貨架的揀選難度和不同揀選員的熟練度。在實際的倉儲環(huán)境中，與數(shù)值實驗中模擬數(shù)據(jù)不同的主要有兩點。獲取的訂單數(shù)量不是一個固定的值，在不同的時間訂單的數(shù)量差異很大，而由于揀選對時間的要求較高，因此需要固定一段時間就進行一次訂單分批。在實際的貨位中，每種商品可能對應的貨位不止一個，即在同一個庫區(qū)中，某種商品可能存在2個以上的貨位點。

圖6 某第三方電商倉儲區(qū)域Figure 6 Storage area of a third-party e-commerce warehouse

針對以上的不同，在實際的分批計算前，需要作一定的處理。訂單的數(shù)量由每20 min到達的訂單數(shù)作為一次需要處理的訂單數(shù)據(jù)。而對于訂單與貨位點關系的問題，在數(shù)據(jù)處理中，需要對變量Uoi進行調整，由原來的訂單與貨物的關系，轉變?yōu)橛唵闻c貨位點的關系，是則為1，否則為0。

在此基礎上，考慮實際的倉儲庫區(qū)環(huán)境進行建模求解，累計對2 h的實時訂單進行分批，每個分批的容量上限為20。不同時間的訂單數(shù)量用O表示，每段時間的平均訂單商品數(shù)用pmean表示，每段時間的訂單最大商品數(shù)用pmax表示。得到表5中的結果。總體來看，平時段(20 min)的平均訂單數(shù)為93.75，每個訂單的平均商品數(shù)為4.66，通過分支定價算法求解，平均的求解時間為138.11 s，可以滿足實際的倉儲作業(yè)需要，證明了本文的模型和算法可以在實際中應用。

表5 實際案例的求解結果Table 5Results of practical cases

5 結論

本文對電商倉儲的訂單分批和路徑優(yōu)化問題進行描述，結合現(xiàn)有研究，提出電商倉儲環(huán)境下的訂單分批和路徑優(yōu)化問題的混合整數(shù)規(guī)劃模型。由于電商環(huán)境下的訂單規(guī)模巨大，為求解大規(guī)模問題，本文設計分支定價算法進行求解，將初始模型松弛為線性規(guī)劃模型，并利用列生成算法對問題進行分解，分別求解主問題和子問題，循環(huán)迭代找到松弛問題的最優(yōu)解，再利用分支定界算法，找到原問題的最優(yōu)整數(shù)解，完成分支定價算法的求解。為了驗證模型及算法，設計多組數(shù)值實驗，在小規(guī)模實驗中驗證了模型的可行性，并設計大規(guī)模數(shù)值實驗，驗證了分支定價算法可以較好地求解大規(guī)模的訂單分批和路徑優(yōu)化算法，并能夠得到精確的整數(shù)解。最后，利用某第三方電商倉儲企業(yè)的實際數(shù)據(jù)進行案例分析，并使用實際數(shù)據(jù)進行實驗，驗證本文的模型及算法可以應用于實際的倉儲揀選作業(yè)中。

6 致謝

感謝上海發(fā)網(wǎng)供應鏈管理有限公司提供的業(yè)務與數(shù)據(jù)支持。