基于改進(jìn)貪婪關(guān)聯(lián)算法的在線零售商優(yōu)化拆單問題

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

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

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

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

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

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

1 建立模型

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

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

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

2) 本文僅考慮品類拆單的情況；

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

4) 配送中心具有容量限制，一個配送中心無法存儲所有單品；

5) 一種單品至少存儲于一個配送中心中；

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 現(xiàn)有算法

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

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

貪婪訂單算法和貪婪熱銷算法的貪婪策略選擇，啟發(fā)本文對單品分配方法的進(jìn)一步探討。不同的單品分配方法對求解算法的質(zhì)量產(chǎn)生不同的影響。從圖3、圖4中可以看出，雖然貪婪訂單算法和貪婪熱銷算法在二次分配時均使用共現(xiàn)矩陣來描述已分配單品和未分配單品間的關(guān)聯(lián)性，但其第1次分配時均未考慮訂單中單品間的關(guān)系，并僅用2個單品在訂單中共同出現(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)用于分析購物籃中不同商品間存在的關(guān)聯(lián)關(guān)系，關(guān)聯(lián)規(guī)則挖掘在本文中表述如下。所有項目集合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為單品的集合，稱為項集。支持度Support為D中包含項集A和B的事務(wù)數(shù)與總事務(wù)數(shù)的比值；置信度Confident為D中同時包含項集A和B的事務(wù)數(shù)與只包含項集A的事務(wù)數(shù)的比值?？煞謩e表示為

圖4 貪婪熱銷算法Figure 4 The greedy sales algorithm

支持度的大小影響最終生成的關(guān)聯(lián)規(guī)則的數(shù)量和質(zhì)量。若min_sup水平太低，則產(chǎn)生巨量候選項集，不但降低算法的挖掘效率，并產(chǎn)生很多無意義的關(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ù)測能力；合理的min_conf可在期望預(yù)測范圍內(nèi)生成關(guān)聯(lián)規(guī)則[14]?；谏鲜龇治?，本文通過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_項候選項集R1←掃描D。

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

Step4 2_項候選項集R2←L1join L1。

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

......

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

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

Step8 強(qiáng)關(guān)聯(lián)規(guī)則←{[Support_count(Lk)]/ Support_count(s)}≥min_conf，其中，s為Lk的所有非空子集，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大小對強(qiáng)關(guān)聯(lián)規(guī)則降序排序。

Step6 對每個配送中心d，如果?Cd＜Q：

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

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

Step7 如果Cd＞Q：

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

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

Step7.3 對每個未分配的單品:

Step7.3.1.1 計算未分配單品與已分配單品間的平均共現(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í)驗

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

算法測試采用一家在線零售商訂單交易數(shù)據(jù)。其中，OrderNO為訂單編碼，SKUNO為單品編碼，Quantity為每張訂單中單品的銷售數(shù)量，Total為每個單品的銷售額。由于原始數(shù)據(jù)中存在缺失值和異常值的數(shù)據(jù)記錄僅約占所有數(shù)據(jù)記錄的0.08%，因此在實(shí)驗過程中直接將其刪除。為便于算法的實(shí)現(xiàn)，對數(shù)據(jù)進(jìn)行預(yù)處理，預(yù)處理結(jié)果顯示，共有2 750張訂單，2 546個單品，一張訂單包含的單品種類數(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ù)測能力[14]。因此為確定適當(dāng)?shù)膍in_sup和min_conf，實(shí)驗在min_sup分別為0.1%、0.25%、0.5%、0.75%、1%，min_conf分別為70%、80%、90%的水平下，觀察候選項集、頻繁項集和強(qiáng)關(guān)聯(lián)規(guī)則的數(shù)量變化及算法運(yùn)行效率。選擇候選項集、頻繁項集和強(qiáng)關(guān)聯(lián)規(guī)則的適中數(shù)量及運(yùn)行效率的min_sup和min_conf為貪婪關(guān)聯(lián)算法的實(shí)驗參數(shù)。因為每張訂單包含的單品數(shù)量在(2,94)之間，范圍過廣，所以Apriori算法的測試結(jié)果以生成3項頻繁項集為例進(jìn)行分析。實(shí)驗結(jié)果如圖5～7所示。

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

圖6 不同min_sup水平下頻繁項集數(shù)量對比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ù)量對比Figure 7 Comparison of the number of strong association rules under different min_conf and min_sup levels

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

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

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

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

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

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

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

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

4 結(jié)語

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

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