基于BIRCH聚類的物流配送設(shè)施選址算法①

李捷承,陶耀東,孫 詠,高 岑

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110168)

物流業(yè)近年來發(fā)展迅速,對促進(jìn)第三產(chǎn)業(yè)、帶動第一第二產(chǎn)業(yè)發(fā)展作用明顯.物流配送設(shè)施是快件集散的關(guān)鍵節(jié)點,在整個物流系統(tǒng)中起著承上啟下的作用,配送設(shè)施的選址對物流成本影響巨大,一個好的配送設(shè)施選址決策可以使得快件在匯集、中轉(zhuǎn)、分發(fā)、配送的過程達(dá)到最少的費用和時間[1].因而對物流配送設(shè)施選址進(jìn)行研究具有較大的經(jīng)濟意義和現(xiàn)實意義.同時隨著電子商務(wù)的興起,面向普通消費者的快遞物流業(yè)成為了新的爆發(fā)點,本文即是對面向普通消費者的物流業(yè)務(wù)的配送設(shè)施選址問題進(jìn)行研究.

針對一般設(shè)施的選址研究已有許多,主要有以下4種類型:1)基于專家咨詢的層次分析法(AHP)及模糊綜合評價法,該類方法主觀判斷占主導(dǎo)地位,決策會受到專家的經(jīng)驗、領(lǐng)域知識等因素的限制;2)將選址問題當(dāng)作整數(shù)或混合整數(shù)規(guī)劃進(jìn)行求解,但設(shè)施選址是NP-Hard問題,一旦數(shù)據(jù)規(guī)模較大,就會運算時間過長,難以求解出最優(yōu)解;3)重心法[2],將運輸成本作為唯一的選址決策因素,在單設(shè)施選址問題中實用性強,缺點是考慮因素單一,重心點可能位于己有建筑物、河流等無法建造配送中心的地方;4)聚類方法,應(yīng)用基于劃分的聚類算法如K-means算法等對客戶進(jìn)行聚類,每個類別的中心即所求選址方案,但這些聚類算法也有各自的缺點,K-means算法必須指定劃分?jǐn)?shù)目,容易陷入局部最小值,且對孤立點敏感.

雖然目前已有許多針對選址問題的求解算法,但物流配送設(shè)施的選址與傳統(tǒng)的單/多設(shè)施選址有所不同,傳統(tǒng)選址問題的研究大多未考慮到物流配送設(shè)施選址的實際特點,在具體實施中效果不佳,所以仍然有較大的優(yōu)化空間.

1 物流配送設(shè)施選址的特點

通過與物流企業(yè)溝通,并深入分析了配送中心對物流配送流程的影響因素,總結(jié)發(fā)現(xiàn)物流配送設(shè)施的選址有以下三個特點:

(1)配送設(shè)施選址與配送線路的規(guī)劃是相互影響的兩個NP-Hard問題[3].配送設(shè)施與各需求點之間的距離不是簡單的歐氏距離,考慮到配送車輛是進(jìn)行巡回配送的,不同的配送范圍劃分、不同線路選擇都對最終結(jié)果有影響.而傳統(tǒng)選址問題一般假設(shè)所選中心到需求點之間的距離是歐氏距離,同時假設(shè)配送設(shè)施與需求點之間是點對點服務(wù),這兩個假設(shè)與實際情況不符,使得選址的結(jié)果不盡如人意.

(2)物流配送設(shè)施的選址是一個多層級的選址問題.物流業(yè)歷經(jīng)多年發(fā)展,大多采用多級分揀配送體系:大區(qū)中轉(zhuǎn)倉庫→一級區(qū)域分揀中心→二級區(qū)域分揀中心→末端快遞站(→快遞柜).還要注意的是快件的集散過程中不會出現(xiàn)跨層運輸.

(3)多個配送設(shè)施之間所負(fù)責(zé)的快件數(shù)量的均衡性.物流業(yè)比較看重快件的流通速度,若使大多數(shù)快件集中在一個分揀中心,容易造成快件積壓,延長了所有快件的流通時間,極大影響配送效率和客戶體驗,所以在考慮配送設(shè)施與下層節(jié)點的運輸路徑成本的同時,還要考慮多個配送設(shè)施之間所負(fù)責(zé)的快件數(shù)量的均衡性.這一點在末端快遞站的選址上尤為重要.

綜上所述,物流配送設(shè)施的選址是一個多層級均衡選址問題.

圖1 多級分揀配送體系

對特點(1)的一個可行的解決辦法:先進(jìn)行配送范圍的劃分,再決策配送設(shè)施的位置,避免同時決策配送設(shè)施的位置和快件的配送線路這兩個NP-Hard問題.因為每天的快遞訂單數(shù)據(jù)會持續(xù)變動,而且快遞配送線路要根據(jù)配送設(shè)施位置和當(dāng)天具體的快遞訂單數(shù)據(jù)來進(jìn)行計算,所以同時決策配送設(shè)施的位置和未來快件的配送線路不是一個好的方法.較好地解決辦法是對配送范圍進(jìn)行劃分,再根據(jù)配送范圍和歷史訂單數(shù)據(jù)決策配送設(shè)施的位置,最后根據(jù)配送設(shè)施位置和當(dāng)天具體的快遞訂單數(shù)據(jù)規(guī)劃配送線路.

對特點(2)的解決:既然物流配送設(shè)施的選址是一個多層級的選址問題,易想到可以使用層次聚類來對數(shù)據(jù)進(jìn)行逐層聚類,但配送設(shè)施選址還有一個特點:快件的集散過程中不會出現(xiàn)跨層運輸,也即第N+1層的數(shù)據(jù)信息對于第N層的配送設(shè)施選址是有用的,但對第N–1層的配送設(shè)施選址就沒用了.所以直接套用常見的層次聚類算法并不適用,要對層次聚類算法進(jìn)行改進(jìn)使之更符合多層級的選址問題的應(yīng)用場景.

對特點(3)的解決:這個特點使得我們使用的算法要具有控制每個簇大小的能力.

本文針對以上物流配送設(shè)施選址問題的三個特點設(shè)計了一個基于BIRCH聚類的物流配送設(shè)施選址算法,融合了BIRCH聚類算法和基于Dijkstra距離的重心法,較好地解決了物流配送設(shè)施選址問題.

2 BIRCH 聚類算法

BIRCH算法[4]是一種層次聚類算法,采用自底向上的策略進(jìn)行聚類,并通過迭代重定位改進(jìn)結(jié)果.BIRCH算法只需要單遍掃描數(shù)據(jù)集就能進(jìn)行有效聚類,最小化數(shù)據(jù)集的輸入輸出,尤其適用于對大數(shù)據(jù)集的處理.BIRCH算法有兩個核心概念:聚類特征CF和聚類特征樹CF-Tree.

定義1.給定一個包含N個d維數(shù)據(jù)點的簇:{xi}(xi=1,2,···,N),則該簇的聚類特征CF是一個三元組:CF=(N,LS,SS),其中,N是∑簇中數(shù)據(jù)點的個數(shù),LS是N個數(shù)據(jù)點∑的線性和[5],即ni=1xi,SS是N個數(shù)據(jù)點的平方和,即ni=1xi2.

定義2.一棵聚類特征樹是一棵平衡樹,存儲了層次聚類的簇的特征.其每個結(jié)點代表一個簇,且對其每個子結(jié)點(/子簇)都包含一個CF條目.CF樹的形態(tài)由三個參數(shù)決定:非葉結(jié)點分支因子B、葉結(jié)點分支因子L和子簇最大半徑閾值T.分支因子B限定每個非葉子結(jié)點的最大孩子個數(shù);分支因子L限定每個葉子結(jié)點的最大子簇數(shù);最大半徑閾值T限定了子簇的最大半徑,保證簇的緊湊程度[5].如圖2所示.

圖2 一棵CF樹的例子(B=5,L=7)

聚類特征CF概括了簇的基本信息,并且是高度壓縮的,其中LS反映了聚類的中心,

x0為簇的中心,用于計算簇(/點)與簇(/點)之間的距離;SS反映了簇內(nèi)對象的平均距離(簇半徑),

而且CF滿足線性可加性,即

這是一個很好的性質(zhì),使得CF-Tree中結(jié)點的CF條目(N,LS,SS)值等于這個CF條目所指向的子結(jié)點的所有CF條目之和,使得更新CF-Tree的時候效率很高.

進(jìn)行BIRCH聚類的過程就是用所有的樣本構(gòu)建一顆聚類特征樹的過程,每個結(jié)點就是一個聚類的簇.BIRCH算法十分高效,處理大數(shù)據(jù)集時對內(nèi)存的需求也不高;但如果數(shù)據(jù)集的簇不是類似于超球體,或者說非凸的,則聚類效果不好[4];同時樣本的讀入順序會導(dǎo)致不合理的CF結(jié)點分裂,影響聚類效果.

結(jié)合本文所探討的多層級均衡選址問題,可以發(fā)現(xiàn):1)BIRCH 算法實現(xiàn)了層次化的聚類,但并沒有給出每個聚類的中心點;2)BIRCH算法根據(jù)參數(shù)B、L、T控制結(jié)點的分裂,限制了每個聚類的子類個數(shù),而我們需要的是對每個聚類大小的控制以實現(xiàn)同層聚類之間的大小均衡.所以BIRCH算法實現(xiàn)了對物流選址問題特點(2)的解決,并具有加以修改以實現(xiàn)特點(3)的潛質(zhì).于是本文基于BIRCH算法并結(jié)合基于Dijkstra距離的重心法,設(shè)計了基于BIRCH聚類的物流配送設(shè)施選址算法.

3 基于BIRCH聚類的物流配送設(shè)施選址算法

該算法先使用帶容量限制的BIRCH算法劃分配送范圍,再使用基于Dijkstra距離的重心法在各個配送范圍內(nèi)進(jìn)行單配送中心選址,兩步交替執(zhí)行完成從底層到頂層的全部選址決策.本算法避免了同時決策配送設(shè)施的位置和快件的配送線路;從底層到頂層逐層遞進(jìn)決策;在劃分配送范圍時保證了劃分的均衡性,對物流配送設(shè)施選址的三個特點都有較好的處理.

3.1 劃分配送范圍-帶容量限制的BIRCH算法

假設(shè)目前要對第K層配送中心進(jìn)行選址決策,首先進(jìn)行配送范圍的劃分.輸入數(shù)據(jù)為下一層的配送目的地和配送權(quán)重,即已求得的第K+1層的需求點(/配送中心)及其需求量.決策目標(biāo)是將第K+1層的需求點集合劃分成m個子集,使得各個子集在地理位置上足夠內(nèi)聚且互不相交,同時要滿足各個子集所包含的需求量大致相當(dāng),即滿足均衡性.

帶容量限制的BIRCH算法是在BIRCH算法的基礎(chǔ)上修改而來.BIRCH算法根據(jù)非葉結(jié)點分支因子B、葉結(jié)點分支因子L對結(jié)點大小進(jìn)行限制,限制了每個聚類的子類個數(shù)[6].而我們需要控制每個聚類的大小以實現(xiàn)同層聚類之間的大小均衡,所以作以下修改:

(1)對聚類特征CF增加一個屬性:容量W,表明該聚類的容量大小,,易知添加該屬性后CF依然滿足線性可加性.

(2)樹結(jié)構(gòu)限定為三層:根結(jié)點、中間結(jié)點、葉結(jié)點,因為最終目標(biāo)是m-均衡劃分,使用三層即可.

(3)不使用非葉結(jié)點分支因子B控制非葉結(jié)點的分裂,改用中間結(jié)點容量閾值H,當(dāng)中間結(jié)點的容量達(dá)到H,就進(jìn)行結(jié)點的分裂,分裂規(guī)則:選擇該中間結(jié)點距離最遠(yuǎn)的兩個CF條目(根據(jù)聚類中心x0計算)作為新中間結(jié)點的初始葉結(jié)點,其余葉結(jié)點CF條目依次合并到較近的新中間結(jié)點.

(4)依然使用葉結(jié)點分支因子L和子簇最大半徑閾值T來控制葉結(jié)點和子簇的大小,防止葉結(jié)點過大使中間結(jié)點分裂失敗.

具體算法步驟如算法1.

算法1.帶容量限制的BIRCH算法構(gòu)建聚類特征樹過程1)讀入新樣本x,根據(jù)其坐標(biāo)位置在所有子簇中尋找距離x最近的子簇D(根據(jù)公式(1)),將x加入到D中,如果x加入后,子簇D的簇半徑(根據(jù)公式(2))小于閾值T,轉(zhuǎn)入4).否則轉(zhuǎn)入2);2)分裂子簇:將子簇D中最遠(yuǎn)的一個樣本點獨立為一個新的子簇,并歸入這個葉結(jié)點,如果當(dāng)前葉結(jié)點的子簇個數(shù)小于閾值L,轉(zhuǎn)入4).否則轉(zhuǎn)入3);3)分裂葉結(jié)點:選擇葉結(jié)點中距離最遠(yuǎn)的兩個CF條目獨立為兩個新葉結(jié)點的第一個CF條目,將其余CF條目按照距離遠(yuǎn)近歸入對應(yīng)的葉結(jié)點;4)更新從子簇向上到根的路徑上所有的C F四元組,檢查中間結(jié)點的容量W是否超過容量閾值H,超過則按3)所述分裂規(guī)則分裂中間結(jié)點;5)若還有未處理樣本,轉(zhuǎn) 1),否則檢查中間結(jié)點,將容量小于H/2 的中間結(jié)點所含樣本點重新處理,使所有中間結(jié)點的容量大于H/2小于H.

此時所有中間結(jié)點容量大于H/2小于H,全部中間結(jié)點即為第K+1層需求點集合的m個均衡劃分子集,也即所求的m個配送范圍.下面要針對每一個配送范圍求解其配送中心.

3.2 配送范圍內(nèi)選擇配送中心-基于Dijkstra距離的重心法

對第K層進(jìn)行選址決策,在上一小節(jié)已經(jīng)將第K+1層的需求點集合劃分成了m個容量大致均衡的不交子集,第二步即是為每個子集選擇一個位置作為該配送范圍的配送中心.這個子問題即是連續(xù)區(qū)域單設(shè)施選址問題,采用常用的基于Dijkstra距離的重心法進(jìn)行決策即可.

重心法是連續(xù)區(qū)域單設(shè)施選址問題的最常用的一種方法,假設(shè)各個需求點的位置和需求量已知,優(yōu)化目標(biāo)是使運輸總成本最小[2].

可求得由各需求點構(gòu)成的超多面體的幾何重心即為單設(shè)施選址問題的最優(yōu)解.

重心法考慮因素單一,將運輸成本作為唯一的決策因素,未考慮城市交通狀況和地產(chǎn)價格等;以中心與需求點之間的直線距離作為運輸距離,與事實不符;只能用于單設(shè)施選址.優(yōu)點則是計算簡單.

基于Dijkstra距離的重心法采用Dijkstra距離作為運輸距離[7].Dijkstra距離是使用Dijkstra算法求得的結(jié)點間最短距離,符合快件配送時巡回配送的特點,比使用直線距離作為運輸距離的模擬效果要好許多.因此這里使用基于Dijkstra距離的重心法作為劃分了配送范圍后,在配送范圍內(nèi)進(jìn)行單配送中心選址的方法,具體算法步驟如算法2.

算法2.基于Dijkstra距離的重心法1)對要求解配送中心的子集D進(jìn)行初始化:相鄰結(jié)點之間的邊的權(quán)重為綜合考慮了運輸距離、交通條件的“虛擬距離”;2)計算任兩個結(jié)點之間Dijkstra距離,即使用Dijkstra算法迭代求得的最短距離;3)使用Dijkstra距離作為運輸距離代入公式(6),所求得的重心點即為該配送范圍的配送中心.

第K+1層全部m個劃分的重心點即為第K層的選址決策,接下來將之作為第K層的需求點,需求量為對應(yīng)配送范圍的總需求量,繼續(xù)進(jìn)行“劃分配送范圍-配送范圍內(nèi)進(jìn)行單配送中心選址”這兩步即可得到第K–1層的選址決策,如此循環(huán)可得從底層到頂層的全部選址決策.

4 實驗驗證

為了驗證本算法的有效性,選取了一次典型的案例:國內(nèi)某三線城市的物流配送設(shè)施選址規(guī)劃,利用2017年二、三季度的調(diào)研數(shù)據(jù)進(jìn)行一座二級區(qū)域分揀中心、若干末端快遞站及快遞柜的選址決策.

根據(jù)分揀中心和末端快遞站標(biāo)配的設(shè)備及人員,可以確定分揀中心日處理訂單數(shù)最多12 000件,末端快遞站日處理訂單數(shù)最多700件.本案例中需要決策兩級配送設(shè)施,在決策末端快遞站時,確定參數(shù)H=700,L=10,T=500;決策二級區(qū)域分揀中心時,確定參數(shù)H=12 000,L=10,T=50 000.最終得到 19 座末端快遞站和1座二級區(qū)域分揀中心的選址決策.另外,在決策末端快遞站時,對聚類后的子簇進(jìn)行篩選,容量足夠大的子簇說明樣本點足夠密集,可以選作快遞柜,在此選容量大于30的子簇建設(shè)快遞柜,共530處.

作為對照,使用k=19和k=1的K-means算法同樣得到19座末端快遞站和1座二級區(qū)域分揀中心的選址決策.并通過以下三個指標(biāo)比∑較兩種算法的優(yōu)劣.

(1)平均送貨距離d=d(xi,x0)/總件數(shù),其中xi為第i件快遞的配送目的地,x0為負(fù)責(zé)配送第i件快遞的配送站.該指標(biāo)用來衡量選址結(jié)∑果的內(nèi)聚性.

(2)快遞站日均負(fù)載均衡度 σ2=(xi?μ)2/N,即所有快遞站日均負(fù)載快件數(shù)的方差,μ為所有快遞站日均負(fù)載的均值.該指標(biāo)用來衡量選址結(jié)果的均衡性.

(3)超出負(fù)載的快遞站數(shù)目.

實驗結(jié)果見表1.

表1 算法效果對比

通過上述指標(biāo)可以看出,K-means算法的選址結(jié)果均衡性較差,導(dǎo)致在快件密集的城區(qū)快遞站不夠,超出負(fù)載的快遞站數(shù)目較多,使得平均送貨距離指標(biāo)也比較差.

另外從功能性上來說K-means算法無法實現(xiàn)不確定個數(shù)的快遞柜選址,而本文算法可以完成決策.綜上,本文設(shè)計的基于BIRCH聚類的物流配送設(shè)施選址算法較好的解決了物流配送設(shè)施的選址問題.

5 結(jié)語

本文通過分析物流配送設(shè)施選址的特點,通過改進(jìn)BIRCH聚類算法并結(jié)合基于Dijkstra距離的重心法設(shè)計了有針對性的物流配送設(shè)施選址算法,較好地解決了物流配送設(shè)施的選址問題[8,9].同時,該算法對如通訊基站、銀行營業(yè)網(wǎng)點、垃圾站等需要考慮到負(fù)載均衡的設(shè)施選址問題以及部門機構(gòu)選址等多層級選址問題有一定參考性.