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

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

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

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

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

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

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

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

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

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

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

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

圖1 多級(jí)分揀配送體系

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

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

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

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

2 BIRCH 聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)樹結(jié)構(gòu)限定為三層:根結(jié)點(diǎn)、中間結(jié)點(diǎn)、葉結(jié)點(diǎn),因?yàn)樽罱K目標(biāo)是m-均衡劃分,使用三層即可.

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

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

具體算法步驟如算法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)的一個(gè)樣本點(diǎn)獨(dú)立為一個(gè)新的子簇,并歸入這個(gè)葉結(jié)點(diǎn),如果當(dāng)前葉結(jié)點(diǎn)的子簇個(gè)數(shù)小于閾值L,轉(zhuǎn)入4).否則轉(zhuǎn)入3);3)分裂葉結(jié)點(diǎn):選擇葉結(jié)點(diǎn)中距離最遠(yuǎn)的兩個(gè)CF條目獨(dú)立為兩個(gè)新葉結(jié)點(diǎn)的第一個(gè)CF條目,將其余CF條目按照距離遠(yuǎn)近歸入對(duì)應(yīng)的葉結(jié)點(diǎn);4)更新從子簇向上到根的路徑上所有的C F四元組,檢查中間結(jié)點(diǎn)的容量W是否超過容量閾值H,超過則按3)所述分裂規(guī)則分裂中間結(jié)點(diǎn);5)若還有未處理樣本,轉(zhuǎn) 1),否則檢查中間結(jié)點(diǎn),將容量小于H/2 的中間結(jié)點(diǎn)所含樣本點(diǎn)重新處理,使所有中間結(jié)點(diǎn)的容量大于H/2小于H.

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

作為對(duì)照,使用k=19和k=1的K-means算法同樣得到19座末端快遞站和1座二級(jí)區(qū)域分揀中心的選址決策.并通過以下三個(gè)指標(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ù)目.

實(shí)驗(yàn)結(jié)果見表1.

表1 算法效果對(duì)比

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

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

5 結(jié)語

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