基于K-means聚類方法的物流多配送中心選址優(yōu)化研究

王 勇，黃思奇，劉 永，許茂增

(1.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074；2.電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院，四川 成都 611731)

0 引言

物流配送中心選址問題是城市物流配送網(wǎng)絡(luò)優(yōu)化的初始環(huán)節(jié)，是指在一定數(shù)目的備選址位置中選擇一定數(shù)量的地址作為配送中心的規(guī)劃過程。基于聚類方法的多配送中心選址問題研究，是將涉及選址多重影響因素的聚類方法與選址決策方法相結(jié)合，選擇合理的配送中心數(shù)量和位置作為優(yōu)化目標(biāo)，進(jìn)而保證物流系統(tǒng)規(guī)劃的可持續(xù)發(fā)展。

國內(nèi)外學(xué)者在配送中心選址問題研究方面已取得了較多研究成果。部分學(xué)者通過目標(biāo)函數(shù)和約束條件構(gòu)建定量化的數(shù)學(xué)模型進(jìn)行選址問題研究，并通過啟發(fā)式算法進(jìn)行求解，Dan和Yu[1]提出了應(yīng)用隨機(jī)規(guī)劃模型研究不確定需求下配送中心的選址問題。李東等[2]設(shè)計(jì)了貪婪取走的啟發(fā)式方法用于研究設(shè)施失效情況下的軍事物流配送中心選址問題。姜燕寧和郝書池[3]構(gòu)建了以系統(tǒng)總成本最低為目標(biāo)的庫存配置與選址決策模型，研究了隨機(jī)需求情形下多級(jí)配送網(wǎng)絡(luò)的庫存-選址優(yōu)化問題。李明等[4]根據(jù)產(chǎn)銷平衡的思路建立相應(yīng)的數(shù)學(xué)模型研究了多物流配送中心的選址問題。Ye[5]研究了基于梯形直覺模糊信息的多準(zhǔn)則群決策，提出了將語言屬性通過模糊數(shù)轉(zhuǎn)化，從而進(jìn)行定量計(jì)算。而對(duì)于一些難以應(yīng)用數(shù)據(jù)進(jìn)行衡量的問題，定性研究體現(xiàn)了優(yōu)越性。Awasthi等[6]提出在選址因素不確定條件下運(yùn)用模糊集理論進(jìn)行選址問題研究。王勇等[7]人提出先建立多配送中心評(píng)價(jià)指標(biāo)體系的方法，再結(jié)合三角模糊數(shù)和語言變量值來研究多配送中心的選址問題。樓振凱和戴曉震[8]應(yīng)用模糊層次分析法和改進(jìn)的理想解排序法(TOPSIS)研究了模糊條件下的物流配送中心選址評(píng)價(jià)問題。賈瑞玉和宋建林[9]應(yīng)用K-means方法研究了基于聚類中心優(yōu)化的最佳聚類數(shù)確定方法。梁昌勇等[10]設(shè)計(jì)了基于TOPSIS方法的多屬性群排序方法，并將其應(yīng)用于配送中心的選址排序問題研究中。然而，考慮城市物流多配送中心選址過程的多重因素影響，并進(jìn)行方法融合方面的研究設(shè)計(jì)較少。

針對(duì)城市多配送中心選址過程需要考慮較多因素且因素間具有復(fù)雜相關(guān)性的問題，首先，應(yīng)用模糊理論集理論，將語言變量模糊數(shù)和梯形模糊數(shù)相結(jié)合，在建立的綜合評(píng)價(jià)指標(biāo)體系下對(duì)各指標(biāo)權(quán)重及其各指標(biāo)進(jìn)行評(píng)價(jià)；其次，應(yīng)用K-means聚類方法對(duì)備選配送中心進(jìn)行分類；最后，應(yīng)用TOPSIS方法進(jìn)行各聚類中心備選址的排序計(jì)算，得出多配送中心的優(yōu)化選址方案，并進(jìn)行了實(shí)例驗(yàn)證。所提的多配送中心選址優(yōu)化方法，為城市物流網(wǎng)絡(luò)優(yōu)化中的選址優(yōu)化相關(guān)問題提供了新的研究思路。

1 配送中心選址的評(píng)價(jià)指標(biāo)體系和相關(guān)語言變量

1.1 配送中心選址的評(píng)價(jià)指標(biāo)體系

配送中心選址過程涉及到的自然環(huán)境因素(氣候條件、地質(zhì)條件、水文條件和地形條件)和經(jīng)濟(jì)因素(建設(shè)費(fèi)用、運(yùn)輸費(fèi)用和運(yùn)營成本)屬于確定選址的前提條件和外部因素，而選址過程涉及的交通運(yùn)輸因素(道路設(shè)施、可達(dá)性和公共設(shè)施狀況)和信息質(zhì)量(信息基礎(chǔ)設(shè)施和信息準(zhǔn)確性)等是確定選址的決策因素，同時(shí)配送中心業(yè)務(wù)活動(dòng)質(zhì)量和客戶服務(wù)質(zhì)量屬于配送中心選址確定并建立后運(yùn)營中的管理范疇，因此，將配送中心評(píng)價(jià)體系分成兩級(jí)指標(biāo)，并分別從自然環(huán)境因素、經(jīng)濟(jì)因素、交通運(yùn)輸因素、信息質(zhì)量、配送中心業(yè)務(wù)活動(dòng)質(zhì)量、客戶服務(wù)質(zhì)量這6個(gè)方面對(duì)配送中心進(jìn)行綜合評(píng)價(jià)，具體如圖1所示。

圖1 多配送中心選址的評(píng)價(jià)指標(biāo)體系Fig.1 Evaluation index system for location selection of multiple distribution center

運(yùn)用梯形直覺模糊數(shù)[11-12]表示各配送中心二級(jí)準(zhǔn)則指標(biāo)下的各屬性權(quán)重值和各專家對(duì)配送中心評(píng)價(jià)指標(biāo)下各屬性的評(píng)價(jià)值。運(yùn)用模糊集成的方法，將其評(píng)價(jià)值集成到一級(jí)指標(biāo)上，最終得到綜合評(píng)價(jià)值。

1.2 語言變量和對(duì)應(yīng)的模糊數(shù)設(shè)計(jì)

根據(jù)建立的配送中心綜合評(píng)價(jià)指標(biāo)體系，將相關(guān)語言變量和相應(yīng)的梯形模糊數(shù)，得到表1的對(duì)應(yīng)關(guān)系，運(yùn)用其描述配送中心評(píng)價(jià)指標(biāo)體系下各屬性權(quán)重的重要度及其權(quán)重。

表1 語言變量值及對(duì)應(yīng)的模糊數(shù)表

運(yùn)用上述語言變量值，結(jié)合相應(yīng)的梯形直覺模糊數(shù)值，對(duì)綜合評(píng)價(jià)指標(biāo)體系中不同屬性的重要度進(jìn)行評(píng)價(jià)，從而確定屬性權(quán)重。對(duì)各準(zhǔn)則指標(biāo)權(quán)重進(jìn)行評(píng)價(jià)時(shí)，將語言變量值中的poor替換為low，fair替換為moderate，good替換為high，而其梯形直覺模糊數(shù)值不變，即將表1中的語言變量值縮寫轉(zhuǎn)變成 VL-VH。

2 基于配送中心評(píng)價(jià)指標(biāo)體系的聚類研究

2.1 相關(guān)定義

針對(duì)表 1 中的語言變量及相應(yīng)模糊數(shù)表，邀請(qǐng)多位專家對(duì)備選配送中心在綜合評(píng)價(jià)指標(biāo)體系下的二級(jí)準(zhǔn)則指標(biāo)進(jìn)行評(píng)價(jià)，并對(duì)二級(jí)準(zhǔn)則指標(biāo)的自身權(quán)重進(jìn)行綜合評(píng)價(jià)，相關(guān)定義和符號(hào)如下：

定義1 參與指標(biāo)評(píng)價(jià)的專家人數(shù)為s，p表示參與評(píng)價(jià)的專家集合：p={pi|i=1,2,…,s}。

定義4設(shè)定備選配送中心的個(gè)數(shù)為n，D表示備選方案的集合是D={DZ|z=1,2,…,n}，通過聚類算法可將備選方案分為F類，C表示備選方案的聚類集合：C={Cg|g=1,2,…,F}。

定義6 備選配送中心的聚類數(shù)據(jù)集表示為：w=(x1,x2,…,xn)，其中選出的k個(gè)聚類中心表示為：(β1,β2,…,βk)，每個(gè)聚類對(duì)象到聚類中心的距離使用歐式距離表示為：

d(xi,xj)=

(1)

定義7Y為一個(gè)給定的數(shù)據(jù)集，假定在數(shù)據(jù)集Y中有n個(gè)聚類子集，分別表示為：y1,y2,…,yn，其中，每個(gè)聚類子集中的樣本數(shù)量表示為：k1,k2,…,kn；每個(gè)聚類子集均有一個(gè)聚類中心點(diǎn)，其聚類中心表示為：g1,g2,…,gn。因此，設(shè)定誤差平方和準(zhǔn)則函數(shù)公式E為：

(2)

2.2 模糊聚類方法

備選配送中心的聚類方法包括以下兩個(gè)步驟：(1)運(yùn)用模糊集成方法，對(duì)備選配送中心評(píng)價(jià)指標(biāo)評(píng)價(jià)體系中的二級(jí)指標(biāo)進(jìn)行模糊評(píng)價(jià)，再結(jié)合二級(jí)指標(biāo)體系中各自的權(quán)重，將二級(jí)指標(biāo)的評(píng)價(jià)值集成到一級(jí)指標(biāo)上。(2)將集成到一級(jí)指標(biāo)上的指標(biāo)值，通過K-means算法同模糊聚類算法結(jié)合，對(duì)備選配送中心進(jìn)行聚類。

2.2.1二級(jí)準(zhǔn)則指標(biāo)下的模糊集成方法

(3)

式中，s為參與評(píng)價(jià)的專家人數(shù);tk為一級(jí)指標(biāo)屬性t下包含的二級(jí)準(zhǔn)則指標(biāo)的個(gè)數(shù);⊕為矢量相加，?為矢量之積。

2.2.2模糊K-means聚類方法

模糊K-means聚類方法的具體實(shí)現(xiàn)步驟如下：

(1)若梯形模糊數(shù)的表示形式為：w=(a,b,c,d)，則可將p(w)表示為梯形模糊數(shù)的集成數(shù)值：

(4)

(5)

(3)首先從備選的配送中心中選擇k個(gè)對(duì)象作為初始的聚類中心，確定簇的數(shù)量為k。

(4)將ej,1，ej,2，ej,3作為聚類的輸入，運(yùn)用歐式距離公式計(jì)算出聚類對(duì)象到k個(gè)聚類中心的歐式距離d(xi,xj)，根據(jù)歐式距離并結(jié)合各聚類中心位置劃分不同的聚類單元。

(5)在已劃分好的聚類單元中，重新計(jì)算各個(gè)聚類單元的樣本平均值，并將其值作為聚類單元的新中心。

(6)重復(fù)上述步驟(4)和(5)，并進(jìn)行聚類結(jié)果的比較分析，進(jìn)而計(jì)算公式(2)中的E值，E值越小，表示聚類結(jié)果越理想，當(dāng)聚類中心不再改變或達(dá)到指定的迭代次數(shù)時(shí)，則聚類結(jié)束并得到聚類結(jié)果。

2.3 模糊聚類方法的有效性指標(biāo)

應(yīng)用模糊K-means聚類方法[13]進(jìn)行計(jì)算時(shí)，由于k值是事先擬定的，為了評(píng)判最終聚類結(jié)果的合理性，需要對(duì)聚類結(jié)果的有效性進(jìn)行評(píng)價(jià)驗(yàn)證。聚類結(jié)果有效性[13]的評(píng)價(jià)指標(biāo)可以包括兩個(gè)方面，一方面是外部標(biāo)準(zhǔn)，若得出的聚類結(jié)果與參考準(zhǔn)則保持一致，則為合理的聚類結(jié)果，否則，為不合理的聚類結(jié)果；另一方面是內(nèi)部指標(biāo)，即通過聚類有效性指標(biāo)確定最佳的聚類數(shù)。通常應(yīng)用內(nèi)部指標(biāo)評(píng)價(jià)聚類結(jié)果具有一定的科學(xué)性和合理性。設(shè)定DB樣本的類內(nèi)離散度和各聚類中心間距：

(6)

(7)

d(hi,hj)=‖υi-υj‖

(8)

式中，n為聚類數(shù)目；s(ni)和s(nj)分別為每類中的所有樣本到其聚類中心的平均距離；d(hi,hj)為類與類之間的中心距離；ni為類i中的樣本個(gè)數(shù)；υi，υj分別為聚類中心。由此可知，DB越小表示類與類之間的相似度越低，從而聚類結(jié)果越佳。

3 TOPSIS排序方法

結(jié)合模糊聚類方法得到的聚類結(jié)果，應(yīng)用TOPSIS排序方法進(jìn)行聚類單元內(nèi)的備選址評(píng)價(jià)排序[11]。若有h個(gè)評(píng)價(jià)對(duì)象和o個(gè)評(píng)價(jià)指標(biāo)，則原始評(píng)價(jià)矩陣可表示為：

(9)

對(duì)指標(biāo)進(jìn)行標(biāo)準(zhǔn)化和去量鋼化處理，具體計(jì)算公式如下：

(10)

(11)

(12)

(13)

TOPSIS排序方法[14]是檢驗(yàn)各評(píng)價(jià)對(duì)象和正理想值、負(fù)理想值距離進(jìn)行排序。其中，正理想值由待評(píng)價(jià)對(duì)象中每個(gè)屬性值的最優(yōu)值組成，而負(fù)理想值由待評(píng)價(jià)對(duì)象中每個(gè)屬性值的最劣值組成，進(jìn)而計(jì)算出每個(gè)方案與最優(yōu)和最差值的距離。最優(yōu)值和最差值分別表示為Z+和Z-，則n個(gè)評(píng)價(jià)方案的歐式距離公式如下：

(14)

(15)

4 算例分析

4.1 實(shí)例相關(guān)數(shù)據(jù)

以某企業(yè)在重慶市選擇配送中心為案列，經(jīng)過考察后有20個(gè)備選配送中心，分別用D1，D2，…，D20來表示。同時(shí)邀請(qǐng)5位專家對(duì)建立的指標(biāo)體系中二級(jí)準(zhǔn)則指標(biāo)下的備選配送中心的選址評(píng)價(jià)及二級(jí)準(zhǔn)則指標(biāo)權(quán)重進(jìn)行評(píng)價(jià)，其中5位專家用P={P1,P2,P3,P4,P5}表示。專家運(yùn)用表1中語言變量值的模糊數(shù)，對(duì)指標(biāo)評(píng)價(jià)體系下的二級(jí)準(zhǔn)則指標(biāo)的權(quán)重進(jìn)行評(píng)價(jià)(如下表2所示)。運(yùn)用2.2節(jié)中提到的二級(jí)準(zhǔn)則指標(biāo)下的模糊集成方法，應(yīng)用模糊集成方法將相應(yīng)的二級(jí)準(zhǔn)則指標(biāo)的權(quán)重值和專家對(duì)其的評(píng)價(jià)值集成到一級(jí)指標(biāo)上，然后，運(yùn)用2.2.2節(jié)中提到的方法將集成到一級(jí)準(zhǔn)則指標(biāo)上的值重新拆分成3個(gè)屬性值，并表示為：qej,1,qej,2,qej,3。

表2 各專家對(duì)二級(jí)準(zhǔn)則指標(biāo)權(quán)重的評(píng)價(jià)

通過表2中二級(jí)準(zhǔn)則指標(biāo)權(quán)重的評(píng)價(jià)值和表1中的模糊數(shù)表相結(jié)合，得到二級(jí)準(zhǔn)則指標(biāo)下的評(píng)價(jià)值，通過模糊集成方法，將二級(jí)準(zhǔn)則指標(biāo)下的評(píng)價(jià)值集成到一級(jí)準(zhǔn)則指標(biāo)上。得到各備配送中心的綜合評(píng)價(jià)值，由表3所示：

4.2 聚類和選址方案

結(jié)合選址方案的時(shí)效性和合理性，本研究將聚類數(shù)目設(shè)定在3到5之間。根據(jù)上述聚類有效性指標(biāo)的計(jì)算公式(6)，(7)，(8)，具體的聚類結(jié)果和不同聚類結(jié)果的聚類有效性指標(biāo)如表5和圖2所示。

表3 備選多配送中心選址方案的綜合評(píng)價(jià)

表4 備選配送中心的隸屬度函數(shù)值

表5 聚類數(shù)為3-5的聚類結(jié)果

圖2 不同聚類數(shù)目的聚類有效性指標(biāo)Fig.2 Clustering Validity Indicators of different cluster numbers

當(dāng)DB越小時(shí)，其聚類效果越好，表明聚類單元中同類別個(gè)體間的差距越小，而不同類別個(gè)體間差距越大。因此當(dāng)聚類數(shù)為3時(shí)得到最佳聚類數(shù)目： {D1, D2,D4,D7,D11,D13,D14,D15,D16}，{D6,D8,D12,D18}，{D3,D5,D9,D10,D17,D19,D20}。為了進(jìn)一步驗(yàn)證聚類結(jié)果的有效性，分別應(yīng)用文獻(xiàn)[17]提出的一種基于Spark框架的改進(jìn)DBSCAN聚類算法和文獻(xiàn)[18]提出的BIRCH聚類算法進(jìn)行聚類比較分析，如表6所示。

表6 3種聚類方法的聚類結(jié)果和有效性指標(biāo)

應(yīng)用模糊K-means聚類方法后，在每個(gè)聚類單元中運(yùn)用TOPSIS排序方法選取一個(gè)配送中心為最終配送中心。根據(jù)上表中的計(jì)算數(shù)值，可知當(dāng)η值越小，其評(píng)價(jià)結(jié)果越高。因此，選取最小的η值作為各類中的最優(yōu)評(píng)價(jià)值，即選出最優(yōu)配送中心為D6，D9，D16。結(jié)合圖2可知，此方法選出的配送中心位置合理。因此，基于模糊K-means聚類算法的物流多配送中心選址方法，將集成后的隸屬度函數(shù)重新拆分成多個(gè)隸屬度函數(shù)子屬性值，能夠挖掘有效的聚類屬性特征和劃分更合理的聚類方案，可以保證最終得到較優(yōu)的配送中心選址方案。綜合比較上述方法，本研究所提方法更具實(shí)踐應(yīng)用性。

表7 聚類數(shù)為3的選址排序

5 結(jié)論

研究了物流網(wǎng)絡(luò)中的多配送中心選址問題，首先，對(duì)一系列備選配送中心建立了評(píng)價(jià)指標(biāo)體系，通過對(duì)備選配送中心在指標(biāo)體系中的二級(jí)準(zhǔn)則指標(biāo)及其權(quán)重進(jìn)行綜合評(píng)價(jià)，并將語言變量模糊數(shù)和梯形模糊數(shù)相結(jié)合，得到二級(jí)準(zhǔn)則指標(biāo)及其權(quán)重的評(píng)價(jià)值；其次，應(yīng)用模糊集成方法將二級(jí)準(zhǔn)則指標(biāo)的評(píng)價(jià)值集成到一級(jí)準(zhǔn)則指標(biāo)上，并通過隸屬度函數(shù)進(jìn)行屬性拆分；最后，將拆分屬性值作為模糊K-means聚類方法的輸入，并通過聚類有效性指標(biāo)值選取合理的備選配送中心聚類方案，進(jìn)而應(yīng)用TOPSIS方法計(jì)算出聚類后各聚類中的排序，從而選出最優(yōu)配送中心選址方案。最后，應(yīng)用實(shí)例驗(yàn)證了所提方法的有效性，該方法也能應(yīng)用到多級(jí)物流網(wǎng)絡(luò)的配送中心選址過程中。