應用聚類分析實現物流配送網絡的優化

[摘 要] 研究了物流配送網絡的優化問題，通過對配送貨物采用聚類預處理，增加了系統處理實際問題的規模，提高了配送網絡的優化性能。測試結果表明該方法有效地降低了配送的成本，提高了效率。

[關鍵詞] 物流 配送網絡 聚類分析

一、引言

配送是物流系統中一個直接與消費者相連的重要環節，優化配送網絡，進行合理的物流配送是實現運輸規模經濟、節省運輸費用的重要手段。物流配送網絡實際上由多個不同的網絡組成，每個網絡都服務于特定的目標，但每個網路又不是孤立進行運作的。確切地說，在不同的運輸網絡之間存在極大的重疊和冗余。因此通過配送網絡的優化，消除這些冗余是降低配送成本的有效手段。聚類分析又稱群分析，它是研究(樣品或指標)分類問題的一種統計分析方法。采用聚類分析的方法，可極大地提高優化的性能，增加所處理業務的規模。

二、聚類基本理論

“物以類聚，人以群分”，在自然科學和社會科學中，存在著大量的分類問題。所謂類，通俗地說，就是指相似元素的集合。聚類分析起源于分類學，隨著人類科學技術的發展，對分類的要求越來越高，僅憑經驗和專業知識難以確切地進行分類，于是數學工具逐漸地被引用到了分類學中，形成了數值分類學，之后又將多元分析的技術引入到數值分類學形成了聚類分析。

假設一個要進行聚類分析的數據集包括n個對象，這些對象可以是人、房屋、貨物等。基于內存的聚類算法通常都采用差異矩陣[1]的數據結構。

差異矩陣是一個對象-對象結構。它存放所有n個對象彼此之間所形成的差異。它一般采用n×n矩陣表示，如式(1)所示。

其中，d(i， j)表示對象i和對象j之間的差異(或不相似性程度)。通常d(i， j)為一個非負數，當對象i和對象j非常相似或彼此“接近”時，該值接近0，該數值越大，就表示對象i和對象j越不相似。由于有d(i，j) = d(j，i)且d(i， i) = 0，因此就有式（1)所示的矩陣。

所采用的測量單位可能會對聚類分析產生影響。例如：將測量單位(對于高度屬性)從英尺變為米，或(對于重量屬性)從英磅變為千克，都會導致不同的聚類結果。通常采用一個較小的單位表示一個屬性會使得屬性的取值范圍變大，因此對聚類結構就有較大的影響。為幫助避免對屬性測量單位的依賴，就需對數據進行標準化。所謂標準化測量就是給所有屬性相同的權值。這一做法在沒有任何背景知識的情況下是非常有用的。而在一些應用中，用戶會有意識地賦予某些屬性更大權值以突出其重要性。例如:在對貨物進行聚類分析時，可能就會給時間屬性賦予更大的權值。

為了實現標準化測量，一種方法就是將初始側量值轉換為單位變量。給定一個屬性(變量)f，可以利用以下計算公式對其進行標準化：

(1)計算絕對偏差均值S

其中，x1f，x2f，…… xnf是變量f的n個測量值，mf為變量f的均值，也就是

(2)計算標準化測量(Z -分值）

其中，絕對偏差均值sf要比標準差σf更為魯棒(對含有噪聲數據而言)。在計算絕對偏差均值時，對均值的偏差|xnf-mf|沒有進行平方運算，因此異常數據作用被降低。

一種有效的聚類分析計算方法是基于密度的算法(Density-based Methods），它與其它方法的一個根本區別是:它基于密度而非基于各種各樣的距離。這樣就能克服基于距離的算法只能發現“類圓形”聚類的缺點。這個方法的指導思想就是:只要一個區域中點的密度大過某個閾值，就把它加到與之相近的聚類中去。代表算法有:OBSCAN算法、OPTICS算法、OENCLUE算法等。

三、配送網絡的優化

配送網絡的底層結構由下述五個主要元素構成:

1.Facility(設施)

配送網絡中的站點(一般是物理的)。在網絡中，站點代表了貨物集中或分發的地點。例如，在郵政配送網中，它們可以是加工及分發站，調度中心，航空郵件中心和散件中心。

2.Delivery(一次投遞的貨物)

Facility之間配送的項目。在網絡中，Delivery代表了在特定時間窗(即，從貨物準備好到要求送達目的站之間的時間段)之內、從起點到終點、有一定體積和重量、要運送的貨物。不同類型的Delivery可能代表了，從起點到終點、有不同的服務標準的貨物(例如，從北京到上海的特快專遞)。

Delivery按是否可分開配送可以分成可分Delivery和不可分Delivery。可分的Delivery是可以被分成不同部分進行配送的。相反，不可分Delivery不能分成不同部分進行配送。

3.Batch(班次)

配送網絡中時間固定，經過的站點固定的運送貨物的路線。一個Batch的定義包括Batch的各個方面:運輸工具的容量或載重能力，Batch的類型(航空，公路，鐵路等)，Batch的工作日(一周里面哪天或哪些天有出發的安排)，到達和離開每個中間站點的時間(用時分秒表示，不牽扯日期)，簽訂一個班次的費用和提前解除班次合約的費用。

4.Leg(班次的一段)

Leg連接相鄰的兩個Facility，Batch由一系列Leg組成。Leg的定義包括：從屬的Batch，Leg起點，Leg終點，離開Leg起點和到達Leg終點的時刻(用時分秒表示，不牽扯日期)，Leg開始離Batch開始的天數，容量或載重能力，可變運輸成本(單位體積或重量的運輸成本)等屬性。當然，在一個Batch中，前一個Leg的終點要和后一個Leg的起點相同。

5.TriP(行程)

真正意義上用于移動貨物的途徑(路線)。Trip的構成形式是多樣的，我們既可以把一個Batch看成是一個Trip來配送Delivery，也可以取一個Batch的若干Leg作為配送Delivery的Trip，還能使用多個Batch的Leg作為Trip，只要它能在規定時間內把Delivery從起點運送到終點。Trip是為了方便建模而構建的一個虛擬的概念，配送網絡優化系統運行的時候，先使用搜索技術把每個Delivery的所有可行配選Trip找出來，再進行建模。

費用由Leg可變費用(可變運輸費用)，Trip遲到懲罰費用，Batch固定費用和Batch提前解約費用構成。優化的目標就是滿足“指派約束”和“容量和載重能力約束”的情況下，使總費用最小。

由于物流配送網絡的Facility既能作為起點，也能作為終點，因此每個Facility可能既集中貨物也分發貨物。相應地，一個Batch可能同時需要搜集和分發貨物。假設將要優化的物流配送網絡已經簽訂了一些班次。即優化的目標是判斷哪些班次繼續留用，那些班次應該提前解除合同。

在模型優化之前，必須把原始數據轉化成標準的數據格式輸入模型。這個步驟包含分析數據和清理數據;依照特定的內容、結構和格式的要求準備好輸入數據文件。在預處理時，對數據進行徹底的檢查。數據的錯誤、矛盾之處都得到更正。預處理過程中，最重要的一步就是進行聚類預處理。

在貨物數量龐大的配送網絡中，如果把每單貨物都看成一個Delivery(即把每單貨物都當成一個Delivery變量加入模型中)，模型的求解過程將耗費相當長的時間。所以在模型進行求解之前，我們可以使用一些成熟的聚類分析方法，把權重屬性值比較接近的貨物聚合成一個Delivery，從而減少模型的計算復雜度。模型的解在接近最優解的情況下，能極大地縮短計算時間。所謂權重屬性，就是用來權衡貨物是否能合成一個Delivery所參考的重要的屬性。

在實際中，一種較好的方法是采用基于密度的DBSCAN(Density-based Spatial Clustering of Application with Noise)聚類算法對貨物進行聚類。該算法通過不斷生長出足夠高的密度區域來進行聚類，它能從含有噪聲的空間數據庫中發現任意形狀的聚類。

由于要把時間和類型都類似的貨物進行聚類，所以選用貨物的類型、貨物就緒時間和要求送達時間等屬性為聚類的權重屬性。屬性和算法都確定好了之后，可編寫Java程序實現DBSCAN聚類算法。輸入不同的貨物數，輸出聚合好的Delivery。通過每個Delivery可以查詢到每個原始的貨物。見表1：

使用Java程序編制配送網絡的優化系統，系統主要由以下幾個部分構成：搜索行程、構建CPLEX模型、使用CPLEX進行優化。將表1的數據輸入該優化系統，得到測試結果見表2：

在近似于實際問題規模(120個站點，300個班次，502段，10000個配送貨單)的時候，可以看出，優化系統還是可在一分鐘左右完成計算。

四、結論

通過比較測試結果可以發現，使用優化系統的總花費要比傳統方法少20%，極大地降低了配送的成本。證明通過聚類分析對配送貨物進行預處理可有效提高配送網絡的優化性能。

參考文獻:

[1]Ian.H.Wjtten，EibeFrank，Data Mining：Pratical Machine Learning Tools and Techniques.Seeond Edition[M]. Elsevier Ine.2005

[2]韓家煒 堪博著 范 明 孟小峰 譯:數據挖掘：概念與技術(原書第二版)[M].機械 工業出版社.2007.03

[3]施建年:物流配送[M].北京:人民交通出版社，2003