應(yīng)用聚類分析實(shí)現(xiàn)物流配送網(wǎng)絡(luò)的優(yōu)化

[摘 要] 研究了物流配送網(wǎng)絡(luò)的優(yōu)化問題，通過對配送貨物采用聚類預(yù)處理，增加了系統(tǒng)處理實(shí)際問題的規(guī)模，提高了配送網(wǎng)絡(luò)的優(yōu)化性能。測試結(jié)果表明該方法有效地降低了配送的成本，提高了效率。

[關(guān)鍵詞] 物流 配送網(wǎng)絡(luò) 聚類分析

一、引言

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

二、聚類基本理論

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

假設(shè)一個要進(jìn)行聚類分析的數(shù)據(jù)集包括n個對象，這些對象可以是人、房屋、貨物等?；趦?nèi)存的聚類算法通常都采用差異矩陣[1]的數(shù)據(jù)結(jié)構(gòu)。

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

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

所采用的測量單位可能會對聚類分析產(chǎn)生影響。例如：將測量單位(對于高度屬性)從英尺變?yōu)槊?，?對于重量屬性)從英磅變?yōu)榍Э?，都會?dǎo)致不同的聚類結(jié)果。通常采用一個較小的單位表示一個屬性會使得屬性的取值范圍變大，因此對聚類結(jié)構(gòu)就有較大的影響。為幫助避免對屬性測量單位的依賴，就需對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化。所謂標(biāo)準(zhǔn)化測量就是給所有屬性相同的權(quán)值。這一做法在沒有任何背景知識的情況下是非常有用的。而在一些應(yīng)用中，用戶會有意識地賦予某些屬性更大權(quán)值以突出其重要性。例如:在對貨物進(jìn)行聚類分析時，可能就會給時間屬性賦予更大的權(quán)值。

為了實(shí)現(xiàn)標(biāo)準(zhǔn)化測量，一種方法就是將初始側(cè)量值轉(zhuǎn)換為單位變量。給定一個屬性(變量)f，可以利用以下計(jì)算公式對其進(jìn)行標(biāo)準(zhǔn)化：

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

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

(2)計(jì)算標(biāo)準(zhǔn)化測量(Z -分值）

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

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

三、配送網(wǎng)絡(luò)的優(yōu)化

配送網(wǎng)絡(luò)的底層結(jié)構(gòu)由下述五個主要元素構(gòu)成:

1.Facility(設(shè)施)

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

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

Facility之間配送的項(xiàng)目。在網(wǎng)絡(luò)中，Delivery代表了在特定時間窗(即，從貨物準(zhǔn)備好到要求送達(dá)目的站之間的時間段)之內(nèi)、從起點(diǎn)到終點(diǎn)、有一定體積和重量、要運(yùn)送的貨物。不同類型的Delivery可能代表了，從起點(diǎn)到終點(diǎn)、有不同的服務(wù)標(biāo)準(zhǔn)的貨物(例如，從北京到上海的特快專遞)。

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

3.Batch(班次)

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

4.Leg(班次的一段)

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

5.TriP(行程)

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

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

由于物流配送網(wǎng)絡(luò)的Facility既能作為起點(diǎn)，也能作為終點(diǎn)，因此每個Facility可能既集中貨物也分發(fā)貨物。相應(yīng)地，一個Batch可能同時需要搜集和分發(fā)貨物。假設(shè)將要優(yōu)化的物流配送網(wǎng)絡(luò)已經(jīng)簽訂了一些班次。即優(yōu)化的目標(biāo)是判斷哪些班次繼續(xù)留用，那些班次應(yīng)該提前解除合同。

在模型優(yōu)化之前，必須把原始數(shù)據(jù)轉(zhuǎn)化成標(biāo)準(zhǔn)的數(shù)據(jù)格式輸入模型。這個步驟包含分析數(shù)據(jù)和清理數(shù)據(jù);依照特定的內(nèi)容、結(jié)構(gòu)和格式的要求準(zhǔn)備好輸入數(shù)據(jù)文件。在預(yù)處理時，對數(shù)據(jù)進(jìn)行徹底的檢查。數(shù)據(jù)的錯誤、矛盾之處都得到更正。預(yù)處理過程中，最重要的一步就是進(jìn)行聚類預(yù)處理。

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

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

由于要把時間和類型都類似的貨物進(jìn)行聚類，所以選用貨物的類型、貨物就緒時間和要求送達(dá)時間等屬性為聚類的權(quán)重屬性。屬性和算法都確定好了之后，可編寫Java程序?qū)崿F(xiàn)DBSCAN聚類算法。輸入不同的貨物數(shù)，輸出聚合好的Delivery。通過每個Delivery可以查詢到每個原始的貨物。見表1：

使用Java程序編制配送網(wǎng)絡(luò)的優(yōu)化系統(tǒng)，系統(tǒng)主要由以下幾個部分構(gòu)成：搜索行程、構(gòu)建CPLEX模型、使用CPLEX進(jìn)行優(yōu)化。將表1的數(shù)據(jù)輸入該優(yōu)化系統(tǒng)，得到測試結(jié)果見表2：

在近似于實(shí)際問題規(guī)模(120個站點(diǎn)，300個班次，502段，10000個配送貨單)的時候，可以看出，優(yōu)化系統(tǒng)還是可在一分鐘左右完成計(jì)算。

四、結(jié)論

通過比較測試結(jié)果可以發(fā)現(xiàn)，使用優(yōu)化系統(tǒng)的總花費(fèi)要比傳統(tǒng)方法少20%，極大地降低了配送的成本。證明通過聚類分析對配送貨物進(jìn)行預(yù)處理可有效提高配送網(wǎng)絡(luò)的優(yōu)化性能。

參考文獻(xiàn):

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

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

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