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

韓世蓮

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

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

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

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

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

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

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

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

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

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

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

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

1.1 決策變量的確定

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

1.2 算法

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

圖1 模糊聚類算法的框架

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

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

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

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

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

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

式中，

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

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

式中，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對應的行（Ωj（p））T。

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

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

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

③如果條件

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

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

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

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

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

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

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

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

（2）決定某一客戶組k終止的2個判定準則。

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

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

②配送車輛容量限制。

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

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

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

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

2 算 例

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

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

計算步驟：

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

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

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

表2 客戶的需求屬性

圖3 客戶的地理位置分布

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

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

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

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

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

3 結(jié)語

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