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

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

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

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

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

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

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

1 物流配送設施選址的特點

通過與物流企業溝通,并深入分析了配送中心對物流配送流程的影響因素,總結發現物流配送設施的選址有以下三個特點:

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

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

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

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

圖1 多級分揀配送體系

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

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

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

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

2 BIRCH 聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體算法步驟如算法1.

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

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

3.2 配送范圍內選擇配送中心-基于Dijkstra距離的重心法

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

重心法是連續區域單設施選址問題的最常用的一種方法,假設各個需求點的位置和需求量已知,優化目標是使運輸總成本最小[2].

可求得由各需求點構成的超多面體的幾何重心即為單設施選址問題的最優解.

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

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

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

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

4 實驗驗證

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

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

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

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

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

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

實驗結果見表1.

表1 算法效果對比

通過上述指標可以看出,K-means算法的選址結果均衡性較差,導致在快件密集的城區快遞站不夠,超出負載的快遞站數目較多,使得平均送貨距離指標也比較差.

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

5 結語

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