基于客戶動態(tài)需求屬性的物流配送線路聚類優(yōu)化

韓世蓮

（南京財經(jīng)大學(xué) 營銷與物流管理學(xué)院，南京 210042）

隨著網(wǎng)絡(luò)經(jīng)濟特別是各種新型電子商務(wù)模式如B2C、C2C、O2O 的蓬勃發(fā)展，物流配送環(huán)節(jié)的地位和作用愈加重要（2013“雙十一”節(jié)阿里銷售額350多億元，僅天貓1天就產(chǎn)生逾1.5億件包裹，平均每分鐘10萬件。實際遞送6 000萬件），并在很多情況下成為電子商務(wù)發(fā)展的制約因素和瓶頸環(huán)節(jié)［1-2］。物流配送路徑選擇問題是通過制定合理的配送路徑，快速而經(jīng)濟地將貨物送達(dá)用戶手中。配送路徑的選擇是否合理，對加快配送速度、提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟效益都有較大影響［1-2］。

物流配送路徑選擇問題是一個NP-難題，其求解計算量隨著問題規(guī)模的增大呈指數(shù)增長［1-2］。該問題屬組合優(yōu)化問題，很難獲得對一般問題的解決方案，尤其是帶時間窗的多目標(biāo)配送路徑選擇問題［3］。近年來，學(xué)者們用精確算法和啟發(fā)式算法求解組合優(yōu)化難題，取得了一定的進(jìn)展［4-24］。

精確算法基于嚴(yán)格的數(shù)學(xué)手段，在可以求解的情況下，其解通常要優(yōu)于啟發(fā)式算法。但由于引入嚴(yán)格的數(shù)學(xué)方法，因而無法避開指數(shù)爆炸問題，從而使該類算法只能有效求解中小規(guī)模的單目標(biāo)配送線路問題［4-5］。在求解大規(guī)模配送線路問題或多目標(biāo)配送線路問題時，啟發(fā)式算法總可以在有限時間內(nèi)，找到滿意的次優(yōu)解/可行解。目前的啟發(fā)式算法主要有以下幾種：

（1）路徑構(gòu)造啟發(fā)式算法［4-5］。路線改進(jìn)啟發(fā)式算法［5-6］復(fù)合啟發(fā)式算法包含路線構(gòu)造和路線改進(jìn)2個階段［8-10］。

（2）元啟發(fā)式算法。包括禁忌搜索法［11-15］、模擬退火法［16-19］、遺傳算法［20-23］以及蟻群算法［23］等。

（3）基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法［25-28］。把問題直接描述為一個數(shù)學(xué)規(guī)劃問題，根據(jù)其模型的特殊結(jié)構(gòu)，應(yīng)用一定的技術(shù)（如分解）進(jìn)行劃分，進(jìn)而求解已被廣泛研究的子問題。

以上方法基本都以運輸費用最小為目標(biāo)，事實上，對于配送而言，運輸費用、快速和準(zhǔn)時性都很重要，目前，將這幾個目標(biāo)綜合研究的文獻(xiàn)較少，而且，很多的配送線路選擇模型均未考慮產(chǎn)品的生命周期、產(chǎn)品價值及產(chǎn)品特性等客戶的需求屬性，而這些因素都會直接影響客戶的滿意度，即服務(wù)質(zhì)量。在電子商務(wù)背景下，這些因素的地位更大，影響也更加突出［29-30］。合理的配送線路應(yīng)當(dāng)在全面考慮客戶需求屬性的基礎(chǔ)上達(dá)到預(yù)定的目標(biāo)（時間最短、費用最小等）。因此，在綜合考慮多種因素的前提下，為配送線路選擇問題（包括單向、雙向及單雙向混合）提出一個通用的反應(yīng)需求屬性的客戶聚類方法具有十分重要的理論和實際意義，尤其在客戶有多樣性需求的復(fù)雜物流配送網(wǎng)絡(luò)中實施帶時間窗的配送策略時，在配送線路確定前按照客戶的需求屬性對客戶進(jìn)行分類，不僅可以降低和減少問題求解的復(fù)雜性，而且可以提高供需雙方的經(jīng)濟效益。

目前只有少量文獻(xiàn)［29-30］在解決物流配送線路選擇問題時涉及了客戶分組方法，但文獻(xiàn)［29］中僅考慮了靜態(tài)的地理性能和需求量，而沒有全面考慮客戶的需求屬性。文獻(xiàn)［30］中提出的行前客戶分類方法雖然對客戶的需求屬性進(jìn)行了全面考慮，但對所有決策變量采用了同樣的處理方法。由于定量決策變量的數(shù)值是確定的，轉(zhuǎn)化為模糊數(shù)表示顯然是多余和不必要的，而且該文所提方法無法保證每組客戶僅需1輛車進(jìn)行配送。

本文提出一種考慮客戶全面需求屬性的行前客戶聚類方法。就是根據(jù)客戶的需求屬性，利用模糊聚類技術(shù)事先對客戶分組，由于每組客戶數(shù)目并不大，只需要1輛汽車進(jìn)行配送，這樣問題規(guī)模就相對很小，運用精確算法可以快速得到客戶組的最優(yōu)配送線路。

1 反應(yīng)客戶需求屬性的模糊系統(tǒng)聚類方法

本文提出的混合模糊系統(tǒng)聚類方法可以看成一種無人監(jiān)督的混合模糊聚類技術(shù)，該技術(shù)在模糊數(shù)據(jù)分析中運用了模糊和系統(tǒng)聚類2個概念。對照應(yīng)用廣泛的模糊c-均值算法［31］，混合模糊系統(tǒng)聚類方法具有明顯的優(yōu)越性，這是因為模糊c-均值算法雖然在處理海量數(shù)據(jù)方面很有效，但計算復(fù)雜，且必須事先輸入聚類塊數(shù)。而模糊系統(tǒng)聚類法不但計算簡單，而且不必事先輸入聚類塊數(shù)。由于多點物流配送線路選擇前需要根據(jù)大量的客戶屬性將客戶分配為未知的類型，正好符合系統(tǒng)聚類法不必事先輸入聚類塊數(shù)的特點，故在物流配送領(lǐng)域中，將模糊系統(tǒng)聚類技術(shù)運用于客戶分類更為合適。

1.1 決策變量的確定

本文所提方法的第1步是確定決策變量以研究配送服務(wù)中的客戶滿意度。安全性、可靠性、經(jīng)濟性、便利性和對服務(wù)質(zhì)量的滿意度是客戶主要關(guān)心的指標(biāo)。為便于計算，本文選取能夠全面反映5個指標(biāo)的8個最重要的決策變量：

1.2 算法

模糊聚類算法的結(jié)構(gòu)如圖1所示，由數(shù)據(jù)處理、模糊相似矩陣的產(chǎn)生和客戶分組三部分組成。

圖1 模糊聚類算法的框架

①定性決策變量的處理。定性變量的處理主要由三角模糊數(shù)［32］評價客戶訂單中收集的客戶決策變量。包含4個有序步驟：

（a）規(guī)定5 個語言術(shù)語，包括“很高”、“高”、“中”、“低”、“很低”，分別表示與客戶需求模式相對應(yīng)的5種服務(wù)水平，如表1所示。

表1 5個語言術(shù)語的模糊數(shù)表示

（b）根據(jù)反映客戶需求的真實數(shù)據(jù)，采用5個語言術(shù)語評價與每個客戶有關(guān)的變量決策。事實上，這些評價可以從最新時間段的訂單中收集。

（c）根據(jù)表1提出的映射關(guān)聯(lián)，每個語言術(shù)語由適當(dāng)?shù)娜悄：龜?shù)表示，如（0，0，0.25）表示“很低”，（0.75，1，1）表示“很高”，因此，對于客戶i的每個給定的語言決策變量k可由3 個數(shù)字表示為

（d）對用模糊數(shù)表示的第k個決策變量，分別計算不同客戶屬性之間的相似度。模糊數(shù)相似度的計算方法有很多［33-35］，并被廣泛應(yīng)用于決策和數(shù)據(jù)分析的各個方面。任意2個客戶對于第k個決策變量的相似度可采用文獻(xiàn)［33-35］中的方法來確定。假定客戶i、j的第k個決策變量的語言評價分別為：

式中，

②定量決策變量的處理。本文采用下述方法求解任意2 個客戶對于第k個決策變量的相似程度。為了使定量決策變量的相似度在［0，1］之間，首先對實際的決策變量數(shù)據(jù)進(jìn)行歸一化，然后將定量化的決策變量視為一種特殊的模糊數(shù)，采用和上面類似的方法計算任2個客戶屬性之間的相似度。對定量決策變量r，假定客戶i、j的值分別為、，則它們之間的相似度

③7個決策變量的綜合處理。在構(gòu)造了每個決策變量的相似性后，就可以對任意2個客戶之間的相似度進(jìn)行計算，即

式中，w k表示決策變量k的重要性且滿足

1.2.2 模糊相似矩陣的產(chǎn)生 在得到每2個客戶之間的相似性后，就可以構(gòu)造一個隨時間變化的N×N模糊相似矩陣Ω（p）=［cij（p）］N×N，其中元素cij（p）表示客戶i、j之間的相似性。Ω（p）可由下式表示：

1.2.3 客戶聚類程序 根據(jù)客戶的屬性，與其他組的客戶相比，分配在同組的客戶將具有相對較高的類似處。圖2提出了客戶分組的程序。

圖2 客戶分組程序圖

（1）計算步驟。

步驟1初始化客戶聚類數(shù)。令初始聚類數(shù)k=1，輸入步驟評估的模糊聚類矩陣式（5）。

步驟2初始化計算循環(huán)。令初始循環(huán)數(shù)n=1。

步驟3從模糊聚類矩陣Ω（p）中選定第j列開始循環(huán)，從Ω（p）中刪除與客戶j對應(yīng)的行（Ωj（p））T。

步驟4設(shè)m為Ωj（p）中與客戶j分配在一起的客戶數(shù)量，令m=0，sn m=j。

①找到Ωj（p）中的最大值cij（p），然后依次進(jìn)行下面的聚類步驟；

②令m=m+1，sn m=i；

③如果條件

雙向配送，即既送貨又取貨

成立，則將客戶i、j分配在一組，并在矩陣Ω（p）中刪除與客戶i對應(yīng)的行（Ωi（p））T；

④返回①，繼續(xù)檢查Ωj（p）中的其他元素，直到?jīng)]有元素滿足上述聚類條件；

⑤從矩陣Ω（p）中刪除Ωj（p）；

⑥如果該階段分配了一些客戶，則分別令sn l（l=1，2，…，m）為目標(biāo)客戶，即j：=sn l，并令n=n+1。返回步驟3，處理Ω（p）中與目標(biāo)客戶相聯(lián)系的元素。

步驟5終止程序，結(jié)束聚類分組。

①如果矩陣中不存在列，則停止聚類程序；

②否則，令k=k+1，返回步驟2，進(jìn)入下一個循環(huán)。

（2）決定某一客戶組k終止的2個判定準(zhǔn)則。

①客戶組中任一元素cij（p）小于預(yù)定的客戶相關(guān)類似的極限λ，即

λ是決定循環(huán)次數(shù)n和聚類數(shù)目k的一個因素，取決于服務(wù)的有效性和物流配送業(yè)務(wù)中的運輸工具。由于λ受制于實際應(yīng)用問題中可得到的服務(wù)和運輸車輛，最好通過試驗測試，如果缺乏試驗數(shù)據(jù)，建議λ＞0.5［29］。

②配送車輛容量限制。

（a）單向（送貨或取貨）物流配送問題。客戶組的需求（供應(yīng)）量之和大于大車容量，即

（b）雙向（既送又取）物流配送問題。客戶組的需求量與供應(yīng)量中的較大者之和大于大車容量，即

由式（4）可知，不同的權(quán)重向量（w1，w2，…，w8）可以產(chǎn)生不同的相似矩陣，從而得到不同的客戶聚類結(jié)果。如果某一權(quán)重為1.0，就成為考慮單一因素的客戶分類方法。特別是當(dāng)?shù)臋?quán)重為1.0時，就成為通常的“范圍配送”和“時間配送”。

需要說明的是，如果客戶i要求將貨物送達(dá)時間與將貨物取走時間不同，應(yīng)事先將該客戶拆分為2個單獨的客戶參加相似度的計算和聚類。一個客戶表示需求客戶，其需求量為原客戶的需求量，供應(yīng)量為0，要求服務(wù)時間為原客戶的需求時間；另一客戶表示供應(yīng)客戶，其供應(yīng)量為原客戶的供應(yīng)量，需求量為0，要求服務(wù)時間為原客戶的供應(yīng)時間；2個客戶的位置均與原客戶相同。

2 算 例

下面通過一個單、雙向混合配送線路選擇問題來說明本文所提模糊系統(tǒng)聚類方法的有效性和實用性。

設(shè)某一物流中心的配送網(wǎng)絡(luò)中有24個客戶，從客戶的訂單中收集了5個需求屬性，分別為訂單的到達(dá)時間和客戶要求的最晚服務(wù)時間、客戶與物流中心的相對距離、客戶的需求（供應(yīng)）量、客戶期望的服務(wù)質(zhì)量以及產(chǎn)品的外部相似性，如表2所示。圖3形象直觀地反映了物流中心和客戶位置。物流中心擁有兩種車型，容量分別為2.0 t和3.5 t.運用本文提出的模糊聚類方法為客戶分組，要求每組客戶只需1輛車進(jìn)行配送。

計算步驟：

步驟1確定每個需求屬性的權(quán)重w k（k=1，2，3，4）；w1、w2、w3、w4分別為客戶要求的最晚服務(wù)時間、客戶與物流中心的相對距離、客戶期望服務(wù)質(zhì)量以及產(chǎn)品外部相似性的重要性。

步驟2計算2個客戶之間的期望服務(wù)質(zhì)量和產(chǎn)品外部相似性的相似度。

（1）分別用三角模糊數(shù)評價每個客戶的期望服務(wù)質(zhì)量和產(chǎn)品外部相似性，如表3所示。

表2 客戶的需求屬性

圖3 客戶的地理位置分布

（2）根據(jù)式（1）計算2個客戶之間的相似度。

步驟3根據(jù)式（3）計算2個客戶之間的距離和要求最晚服務(wù)時間的相似度。

步驟4根據(jù)式（4）計算確定權(quán)重下的2個客戶之間的相似度。

步驟5根據(jù)步驟4計算的相似度構(gòu)造模糊相似矩陣。

步驟6客戶聚類。

（1）規(guī)定客戶相關(guān)類似的極限λ=0.7；

（2）客戶組的載貨量范圍：

（3）根據(jù)1.2節(jié)客戶分組步驟對24個客戶進(jìn)行聚類，聚類結(jié)果如表4所示。表中列出了各種分配權(quán)重下的客戶分組結(jié)果，包括每個客戶組的需求量、供應(yīng)量及其載貨量（確定車型的依據(jù)）。由表4可見，通過改變4 個需求屬性的權(quán)重，運用編制的Matlab程序，可以產(chǎn)生不同的分組結(jié)果。

表3 客戶期望服務(wù)質(zhì)量和產(chǎn)品外部相似性的三角模糊數(shù)評價

表4 各種分配權(quán)重下的客戶分組結(jié)果

3 結(jié)語

本文根據(jù)模糊聚類技術(shù)提出了一種反應(yīng)客戶定性、定量需求屬性的新的行前聚類方法，不僅有益于供給方的有效動態(tài)車輛管理，而且可以對客戶需求的多樣性快速做出反應(yīng)。首先，通過分析客戶的需求屬性和較廣范圍的問卷調(diào)查，確定決策變量。然后利用從客戶處收集的標(biāo)準(zhǔn)決策變量，對客戶進(jìn)行聚類。該方法共進(jìn)行3個連續(xù)步驟，包括數(shù)據(jù)處理、相似度計算和模糊相關(guān)矩陣的生成以及客戶分類。最后，運用前面所提模糊系統(tǒng)聚類方法求解單、雙向混合配送線路選擇問題，計算結(jié)果表明，通過改變決策者對客戶需求屬性的權(quán)重可以得到不同的聚類結(jié)果。因此，本文提出的行前客戶聚類方法既有效又實用，適用于任何類型（包括單向、雙向或單、雙向混合）的物流配送線路選擇問題，為物流配送線路優(yōu)化提供了新的思路。