鐘麗文，姜同強(qiáng),2

(北京工商大學(xué) 1.計(jì)算機(jī)與信息工程學(xué)院；2.農(nóng)產(chǎn)品質(zhì)量安全追溯技術(shù)及應(yīng)用國(guó)家工程實(shí)驗(yàn)室，北京 100048)

針對(duì)在一個(gè)區(qū)域擁有多個(gè)配送中心的在線(xiàn)零售商，拆單是指一張訂單需拆分成多張訂單，由同一區(qū)域的不同配送中心進(jìn)行配送。企業(yè)實(shí)踐表明，通過(guò)調(diào)整各配送中心存儲(chǔ)的單品(最小存貨單位)，每降低1%的拆單率，原本每年需履約的包裹數(shù)量將減少約100萬(wàn)件。因此，若在線(xiàn)零售商具有巨大訂單數(shù)量，可直接減少企業(yè)運(yùn)輸成本，提高顧客服務(wù)滿(mǎn)意度。拆單率算法本質(zhì)就是對(duì)單品進(jìn)行分配，所以通過(guò)對(duì)單品分配方法進(jìn)行研究以降低拆單率是物流優(yōu)化的一個(gè)重要問(wèn)題。

目前，學(xué)者主要集中于通過(guò)研究訂單拆分，進(jìn)行配送路徑的規(guī)劃與優(yōu)化，庫(kù)存商品揀選效率的提高以及物流成本的降低等領(lǐng)域。Dullaert等[1]通過(guò)訂單拆分來(lái)滿(mǎn)足不同運(yùn)輸方式的選擇，提出一種元啟發(fā)進(jìn)化算法。秦雨虹等[2]將拆單規(guī)則與配送相結(jié)合建立聯(lián)合優(yōu)化模型。張?jiān)磩P[3]考慮訂單在多個(gè)倉(cāng)庫(kù)的拆分及匹配問(wèn)題，設(shè)計(jì)啟發(fā)式算法對(duì)訂單分配模型進(jìn)行優(yōu)化，從而降低物流配送成本。韋超豪[4]通過(guò)對(duì)訂單拆分策略研究設(shè)計(jì)了訂單分批算法。王善超[5]依據(jù)訂單是否可拆分建立相應(yīng)的訂單揀選模型，進(jìn)而提高倉(cāng)庫(kù)商品揀選效率。韓曙光等[6]、章園園[7]以2種拆單方式為原則建立配送路徑規(guī)劃模型，并采用改進(jìn)的蟻群算法求解最優(yōu)配送路徑。符卓等[8]、夏揚(yáng)坤等[9]針對(duì)需求依據(jù)訂單拆分的車(chē)輛路徑問(wèn)題，設(shè)計(jì)禁忌搜索算法對(duì)建立的車(chē)輛路徑規(guī)劃模型進(jìn)行求解。

較少學(xué)者關(guān)注通過(guò)單品分配方法研究訂單拆分以降低拆單率的問(wèn)題。Xu等[10]提出一種基于訂單實(shí)時(shí)發(fā)生的動(dòng)態(tài)優(yōu)化方法，通過(guò)重新分配訂單降低拆單率。Catalán等[11]考慮在線(xiàn)零售商一地多倉(cāng)場(chǎng)景下的單品分配問(wèn)題，建立最小化訂單配送次數(shù)模型，設(shè)計(jì)啟發(fā)式貪婪算法對(duì)模型進(jìn)行求解，實(shí)驗(yàn)表明，啟發(fā)式貪婪算法可降低約10%的拆單率。李樂(lè)樂(lè)[12]提出環(huán)形算法對(duì)單品進(jìn)行分配，拆單率可降低約8%。李建斌等[13]在多倉(cāng)單品存儲(chǔ)策略一定的基礎(chǔ)上，對(duì)單倉(cāng)單品數(shù)量不足所引發(fā)的拆單進(jìn)行了研究。

上述研究雖然均降低了拆單率，但環(huán)形算法未考慮訂單中單品間的關(guān)聯(lián)性；啟發(fā)式貪婪算法僅使用兩個(gè)單品在所有訂單中共同出現(xiàn)的次數(shù)衡量單品間的相關(guān)性，衡量標(biāo)準(zhǔn)較為單一，因此上述算法存在改進(jìn)空間。本文在已有研究的基礎(chǔ)上，結(jié)合Apriori算法，尋求訂單中具有強(qiáng)關(guān)聯(lián)關(guān)系的單品，提出一種新的單品分配方法，并對(duì)原有算法進(jìn)行改進(jìn)，實(shí)現(xiàn)了拆單率顯著降低的目標(biāo)。

1 建立模型

1.1 問(wèn)題描述及基本假設(shè)

導(dǎo)致拆單的主要原因包括品類(lèi)拆單、數(shù)量拆單和標(biāo)記拆單。其中，品類(lèi)拆單指在一張包含多種單品的訂單中，至少有2種單品不在同一配送中心存儲(chǔ)；數(shù)量拆單指訂單包含缺貨的單品；標(biāo)記拆單指訂單中包含屬性不同的單品，如訂單同時(shí)包含常溫商品和冷藏商品。本文在僅考慮品類(lèi)拆單的情況下，以拆單率為衡量指標(biāo)，對(duì)現(xiàn)有算法進(jìn)行改進(jìn)。模型基本假設(shè)如下。

1) 在線(xiàn)零售商的銷(xiāo)售環(huán)境穩(wěn)定；

2) 本文僅考慮品類(lèi)拆單的情況；

3) 同一區(qū)域具有多個(gè)配送中心(即一地多倉(cāng))；

4) 配送中心具有容量限制，一個(gè)配送中心無(wú)法存儲(chǔ)所有單品；

5) 一種單品至少存儲(chǔ)于一個(gè)配送中心中；

6) 所有的配送中心能滿(mǎn)足全部訂單。

1.2 建立最大化整單配送模型

本文符號(hào)設(shè)計(jì)及決策變量定義如下。

S為單品的總品類(lèi)數(shù)量，s表示第s種單品；D為配送中心的數(shù)量，d表示第d個(gè)配送中心；O為訂單總數(shù)量，o表示第o個(gè)訂單；Cd為第d個(gè)配送中心可容納單品的最大品類(lèi)數(shù)；Io為第o個(gè)訂單中包含的單品的集合。

整數(shù)規(guī)劃模型如下。

式(1)為目標(biāo)函數(shù)，求解所有配送中心能完成整單配送的最大訂單數(shù)量；式(2)約束每種單品必須分配給一個(gè)配送中心；式(3)約束每個(gè)配送中心存儲(chǔ)的單品不能超過(guò)該配送中心的單品種類(lèi)容量上限；式(4)約束一個(gè)配送中心不能存放所有單品，但全部配送中心可以；式(5)表示訂單o由第d個(gè)配送中心完成配送；式(6)表示第d個(gè)配送中心對(duì)訂單o進(jìn)行配送的前提條件是該配送中心存放了訂單o所需的單品。

Catalán等[11]學(xué)者經(jīng)過(guò)分析，證明在僅考慮品類(lèi)拆單情況下的訂單拆分問(wèn)題為NP-hard問(wèn)題，因此難以用精確的算法對(duì)該模型進(jìn)行求解。

2 貪婪關(guān)聯(lián)算法設(shè)計(jì)

本文旨在研究在線(xiàn)零售商一地多倉(cāng)場(chǎng)景下的拆單率算法來(lái)求解單品分配模型，并通過(guò)改進(jìn)拆單率算法調(diào)整單品的分配策略，達(dá)到明顯降低拆單率的目的。僅考慮品類(lèi)拆單的情況下，在線(xiàn)零售商一地多倉(cāng)運(yùn)作存儲(chǔ)如圖1、圖2所示。

圖1 原始單品存儲(chǔ)策略Figure 1 Original stock item storage strategy

圖2 調(diào)整后的單品存儲(chǔ)策略Figure 2 Adjusted single product storage strategy

由于配送中心容量有限，各配送中心存儲(chǔ)的單品和各訂單所需單品如圖1所示。現(xiàn)訂單處理系統(tǒng)需將訂單O1、O2分配給相應(yīng)的配送中心，因單個(gè)配送中心不包含O1、O2所需全部單品，故需將O1、O2拆分成多張訂單進(jìn)行4次配送。在其他條件不變的情況下，對(duì)各配送中心存儲(chǔ)的單品進(jìn)行調(diào)整，調(diào)整后的單品存儲(chǔ)策略如圖2所示，此時(shí)經(jīng)3次配送即可完成2張訂單。

綜上，僅考慮品類(lèi)拆單的情況，在多倉(cāng)運(yùn)作模式下，配送中心先根據(jù)某種分配方法選擇存儲(chǔ)的單品。當(dāng)訂單下達(dá)時(shí)，訂單管理系統(tǒng)根據(jù)各訂單對(duì)單品的需求，直接或拆分成多張訂單分配給配送中心，單個(gè)配送中心完成的訂單整單配送數(shù)量越多，拆單率越低。因此設(shè)計(jì)較為科學(xué)的拆單率算法是降低拆單率的核心。

2.1 現(xiàn)有算法

本文選用貪婪訂單算法和貪婪熱銷(xiāo)算法[11]為對(duì)比算法。貪婪算法的核心是求解各子問(wèn)題的貪婪策略的選擇，在貪婪訂單算法中，優(yōu)先選擇包含單品數(shù)量多的訂單進(jìn)行分配，再根據(jù)一輪分配結(jié)果選擇與已分配單品在訂單中共同出現(xiàn)次數(shù)最多的未分配單品進(jìn)行分配。在貪婪熱銷(xiāo)算法中，優(yōu)先選擇熱銷(xiāo)單品，使各配送中心均包含熱銷(xiāo)單品。提高各配送中心對(duì)僅包含熱銷(xiāo)單品的整單履行率，對(duì)于未分配的非熱銷(xiāo)單品，貪婪熱銷(xiāo)算法同樣采用共現(xiàn)矩陣對(duì)其進(jìn)行分配，并保證剩余未分配單品只分配給1個(gè)配送中心。其中，銷(xiāo)量排名前B類(lèi)的單品為熱銷(xiāo)單品，共現(xiàn)矩陣用于描述2個(gè)單品在訂單中出現(xiàn)的次數(shù)，定義熱銷(xiāo)品類(lèi)數(shù)量B和共現(xiàn)矩陣為

現(xiàn)有算法流程如圖3和圖4所示。

貪婪訂單算法和貪婪熱銷(xiāo)算法的貪婪策略選擇，啟發(fā)本文對(duì)單品分配方法的進(jìn)一步探討。不同的單品分配方法對(duì)求解算法的質(zhì)量產(chǎn)生不同的影響。從圖3、圖4中可以看出，雖然貪婪訂單算法和貪婪熱銷(xiāo)算法在二次分配時(shí)均使用共現(xiàn)矩陣來(lái)描述已分配單品和未分配單品間的關(guān)聯(lián)性，但其第1次分配時(shí)均未考慮訂單中單品間的關(guān)系，并僅用2個(gè)單品在訂單中共同出現(xiàn)的次數(shù)衡量單品間的相關(guān)性，衡量標(biāo)準(zhǔn)較為單一。

2.2 貪婪關(guān)聯(lián)算法

圖3 貪婪訂單算法Figure 3 The greedy order algorithm

經(jīng)典的關(guān)聯(lián)算法——Apriori算法，最早應(yīng)用于分析購(gòu)物籃中不同商品間存在的關(guān)聯(lián)關(guān)系，關(guān)聯(lián)規(guī)則挖掘在本文中表述如下。所有項(xiàng)目集合I={單品1,單品2, ···, 單品s}，事務(wù)數(shù)據(jù)集D={O1, O2, ···, OO}，且事務(wù) O ?I ，關(guān)聯(lián)規(guī)則A→B，其中， A ?I ，B ?I且A∩B=?，A、B為單品的集合，稱(chēng)為項(xiàng)集。支持度Support為D中包含項(xiàng)集A和B的事務(wù)數(shù)與總事務(wù)數(shù)的比值；置信度Confident為D中同時(shí)包含項(xiàng)集A和B的事務(wù)數(shù)與只包含項(xiàng)集A的事務(wù)數(shù)的比值?？煞謩e表示為

圖4 貪婪熱銷(xiāo)算法Figure 4 The greedy sales algorithm

支持度的大小影響最終生成的關(guān)聯(lián)規(guī)則的數(shù)量和質(zhì)量。若min_sup水平太低，則產(chǎn)生巨量候選項(xiàng)集，不但降低算法的挖掘效率，并產(chǎn)生很多無(wú)意義的關(guān)聯(lián)規(guī)則。若min_sup水平太高，則容易遺漏潛在的不易發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則。置信度的大小影響最終生成的關(guān)聯(lián)規(guī)則的相關(guān)強(qiáng)度。最小置信度min_conf控制關(guān)聯(lián)規(guī)則的可預(yù)測(cè)能力；合理的min_conf可在期望預(yù)測(cè)范圍內(nèi)生成關(guān)聯(lián)規(guī)則[14]?；谏鲜龇治?，本文通過(guò)Apriori算法求解訂單中單品間的強(qiáng)關(guān)聯(lián)關(guān)系，為改進(jìn)現(xiàn)有拆單率算法提供新的思路，改進(jìn)的貪婪關(guān)聯(lián)算法的具體步驟如下。

Stage1：

Step1 設(shè)置min_sup，min_conf。

Step2 1_項(xiàng)候選項(xiàng)集R1←掃描D。

Step3 1_項(xiàng)頻繁項(xiàng)集L1←Support(R1)≥min_sup。

Step4 2_項(xiàng)候選項(xiàng)集R2←L1join L1。

Step5 2_項(xiàng)頻繁項(xiàng)集L2←Support(R2)≥min_sup。

......

Step6 k_項(xiàng) 頻 繁 項(xiàng) 集Lk←Support(Rk?1)≥min_sup。

Step7 (k+1)_項(xiàng)候選項(xiàng)集Rk+1=?←Lkjoin Lk, 進(jìn)入Step8。

Step8 強(qiáng)關(guān)聯(lián)規(guī)則←{[Support_count(Lk)]/ Support_count(s)}≥min_conf，其中，s為L(zhǎng)k的所有非空子集，Support_count(X)=||{ J ∈D | X ?J||。

Step9 強(qiáng)關(guān)聯(lián)單品表←遍歷所有強(qiáng)關(guān)聯(lián)規(guī)則。

Stage2：

Step1 設(shè)置配送中心的數(shù)量d，配送中心d的容量限制Cd。

Step2 index list ←賦予配送中心唯一索引index。

Step3 單品表←遍歷所有訂單O中包含的單品。

Step4 Q ←強(qiáng)關(guān)聯(lián)單品表中單品的數(shù)量。

Step5 強(qiáng)關(guān)聯(lián)單品表←按Confident大小對(duì)強(qiáng)關(guān)聯(lián)規(guī)則降序排序。

Step6 對(duì)每個(gè)配送中心d，如果?Cd＜Q：

Step6.1 分配強(qiáng)關(guān)聯(lián)單品表中包含的前Cd個(gè)單品給Cd＜Q的配送中心d;

Step6.2 將配送中心d從index list中刪去。

Step7 如果Cd＞Q：

Step7.1 分配Q個(gè)單品給所有配送中心;

Step7.2 計(jì)算共現(xiàn)矩陣W=RTR;

Step7.3 對(duì)每個(gè)未分配的單品:

Step7.3.1.1 計(jì)算未分配單品與已分配單品間的平均共現(xiàn)次數(shù);

Step7.3.2 找到平均值最高的配送中心d，將單品分配給該配送中心d;

Step7.4.1 找到最小index的配送中心d;

Step7.4.2 根據(jù)共現(xiàn)矩陣W，找到與已分配單品共現(xiàn)次數(shù)最多的未分配單品;

Step7.4.3 將單品分配給配送中心d。

3 算法實(shí)驗(yàn)

3.1 原始數(shù)據(jù)預(yù)處理

算法測(cè)試采用一家在線(xiàn)零售商訂單交易數(shù)據(jù)。其中，OrderNO為訂單編碼，SKUNO為單品編碼，Quantity為每張訂單中單品的銷(xiāo)售數(shù)量，Total為每個(gè)單品的銷(xiāo)售額。由于原始數(shù)據(jù)中存在缺失值和異常值的數(shù)據(jù)記錄僅約占所有數(shù)據(jù)記錄的0.08%，因此在實(shí)驗(yàn)過(guò)程中直接將其刪除。為便于算法的實(shí)現(xiàn)，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，預(yù)處理結(jié)果顯示，共有2 750張訂單，2 546個(gè)單品，一張訂單包含的單品種類(lèi)數(shù)量在2～94種之間。

3.2 參數(shù)設(shè)置

適當(dāng)?shù)膍in_sup和min_conf可挖掘出潛在的有趣關(guān)聯(lián)規(guī)則并使關(guān)聯(lián)規(guī)則具有更好的預(yù)測(cè)能力[14]。因此為確定適當(dāng)?shù)膍in_sup和min_conf，實(shí)驗(yàn)在min_sup分別為0.1%、0.25%、0.5%、0.75%、1%，min_conf分別為70%、80%、90%的水平下，觀(guān)察候選項(xiàng)集、頻繁項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則的數(shù)量變化及算法運(yùn)行效率。選擇候選項(xiàng)集、頻繁項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則的適中數(shù)量及運(yùn)行效率的min_sup和min_conf為貪婪關(guān)聯(lián)算法的實(shí)驗(yàn)參數(shù)。因?yàn)槊繌堄唵伟膯纹窋?shù)量在(2,94)之間，范圍過(guò)廣，所以Apriori算法的測(cè)試結(jié)果以生成3項(xiàng)頻繁項(xiàng)集為例進(jìn)行分析。實(shí)驗(yàn)結(jié)果如圖5～7所示。

圖5 不同min_sup水平下候選項(xiàng)集數(shù)量對(duì)比Figure 5 Comparison of the number of candidate sets underdifferent min_sup levels

圖6 不同min_sup水平下頻繁項(xiàng)集數(shù)量對(duì)比Figure 6 Comparison of the number of frequent item sets under different min_sup levels

圖7 不同min_conf和min_sup水平下強(qiáng)關(guān)聯(lián)規(guī)則數(shù)量對(duì)比Figure 7 Comparison of the number of strong association rules under different min_conf and min_sup levels

從圖5～7中可以看出，在不同min_sup水平下，隨min_sup的增長(zhǎng)，2_項(xiàng)、3_項(xiàng)的候選項(xiàng)集和頻繁項(xiàng)集數(shù)量不斷減少。在同一min_conf水平下，強(qiáng)關(guān)聯(lián)規(guī)則數(shù)量具有相同變化規(guī)律。具體當(dāng)min_sup為0.1%和0.25%時(shí)，算法產(chǎn)生巨量2_項(xiàng)、3_項(xiàng)的候選項(xiàng)集、頻繁項(xiàng)集及強(qiáng)關(guān)聯(lián)規(guī)則；當(dāng)min_sup為0.75%和1.0%時(shí)，各項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則數(shù)量驟減；當(dāng)min_sup為0.5%時(shí)，候選項(xiàng)集、頻繁項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則的數(shù)量均處于測(cè)試結(jié)果的中間水平。在同一min_sup水平下，隨min_conf水平的上升，強(qiáng)關(guān)聯(lián)規(guī)則數(shù)量下降，但min_conf過(guò)高則容易遺漏潛在的關(guān)聯(lián)規(guī)則。算法在不同min_sup和min_conf下的運(yùn)行時(shí)間如圖8所示。

圖8 不同min_sup和min_conf水平下算法運(yùn)行效率對(duì)比Figure 8 Comparison of algorithm operation efficiency under different min_sup and min_conf levels

圖8 表明，在同一min_conf水平不同min_sup水平下，min_sup水平越高，算法運(yùn)行所需時(shí)間越少，而在同一min_sup水平不同min_conf水平下，算法運(yùn)行耗費(fèi)的時(shí)間沒(méi)有較大的變化。

綜合Apriori算法各參數(shù)的測(cè)試結(jié)果，在貪婪關(guān)聯(lián)算法的第1階段，選取min_sup=0.5%，min_conf=70%進(jìn)行實(shí)驗(yàn)。本文假設(shè)在一個(gè)區(qū)域內(nèi)有3個(gè)配送中心，每個(gè)配送中心的容量相同，并且單個(gè)配送中心的單品種類(lèi)容量上限Cd=0.7 S，算法采用Python3.0編碼實(shí)現(xiàn)。

3.3 實(shí)驗(yàn)結(jié)果分析

定義拆單率為需要拆分的訂單在總訂單中所占比例，則貪婪關(guān)聯(lián)算法、貪婪熱銷(xiāo)算法和貪婪訂單算法的表現(xiàn)結(jié)果如表1所示。

表1 各算法拆單率比較Table 1 Comparison of the split order rate of each algorithm

表1記錄不同算法下，分配給各配送中心的單品數(shù)量、各配送次數(shù)下的訂單數(shù)量及拆單率情況。實(shí)驗(yàn)結(jié)果顯示，相比貪婪熱銷(xiāo)算法和貪婪訂單算法，貪婪關(guān)聯(lián)算法拆單率分別下降8.11%和10.9%。雖然各算法拆單率數(shù)值都比較大，但對(duì)訂單數(shù)據(jù)進(jìn)行觀(guān)察發(fā)現(xiàn)，原始訂單數(shù)據(jù)中包含10種單品以上的訂單數(shù)量約占總訂單數(shù)量的70%，而在文獻(xiàn)[11]中，平均每個(gè)訂單包含的單品種類(lèi)數(shù)量為5.17[11]，文獻(xiàn)[12]采用的訂單生成算法設(shè)定每張訂單包含的單品種類(lèi)數(shù)量在2～10種之間[12]。因此算法可能因數(shù)據(jù)集的不同而呈現(xiàn)不同的拆單率表現(xiàn)，單張訂單包含單品數(shù)量越多，發(fā)生拆單的概率越大。但實(shí)驗(yàn)結(jié)果表明，和其他算法相比，貪婪關(guān)聯(lián)算法是有效的。

4 結(jié)語(yǔ)

本文從倉(cāng)儲(chǔ)管理的角度，建立最大化訂單整單配送模型。對(duì)于在線(xiàn)零售商一地多倉(cāng)運(yùn)作的情況，對(duì)貪婪訂單算法和貪婪熱銷(xiāo)算法的單品分配方法進(jìn)行研究。針對(duì)上述算法存在的不足，結(jié)合Apriori算法，提出一種改進(jìn)的拆單率算法。通過(guò)對(duì)各配送中心存儲(chǔ)的單品進(jìn)行調(diào)整，從而使拆單率顯著降低，進(jìn)而減少在線(xiàn)零售商的運(yùn)輸成本及其總體運(yùn)營(yíng)成本。最終實(shí)驗(yàn)結(jié)果表明，貪婪關(guān)聯(lián)算法的表現(xiàn)優(yōu)于貪婪熱銷(xiāo)算法和貪婪訂單算法。

在線(xiàn)零售商實(shí)際運(yùn)營(yíng)過(guò)程中，配送中心的單品存儲(chǔ)策略需參考多個(gè)因素，因此本文可在以下方面進(jìn)行拓展研究。例如，除了考慮品類(lèi)拆單外，未來(lái)可以結(jié)合數(shù)量拆單和標(biāo)記拆單進(jìn)行分析；為提高算法效率，未來(lái)可以采用深度學(xué)習(xí)算法對(duì)數(shù)據(jù)進(jìn)行挖掘。