地圖上所有非物流中心的樣本點(diǎn)，稱為普通物流地點(diǎn)．由物流中心所管轄的普通物流地點(diǎn)的集合稱為物流子區(qū)域．假設(shè)存在一個(gè)屬于物流子區(qū)域A（以點(diǎn)A為聚類中心的物流子區(qū)域）的點(diǎn)a，若a與屬于其他物流子區(qū)域的點(diǎn)直接相連，則稱該點(diǎn)a為區(qū)域間相連點(diǎn)，被點(diǎn)a相連的兩個(gè)物流子區(qū)域稱為相鄰物流子區(qū)域．

1 算法原理

1.1 改進(jìn)的K-means聚類算法

相較于傳統(tǒng)的K-means聚類算法[6][7]，改進(jìn)后的K-means聚類算法的聚類中心是固定的．聚類過(guò)程為：

Step1求普通物流地點(diǎn)a到各個(gè)物流中心的歐式距離．記普通物流地點(diǎn)a對(duì)應(yīng)的坐標(biāo)為(x0,y0)，其他物流中心的坐標(biāo)為(xi,yi)(i=1,2,3,…），點(diǎn)a到其他各個(gè)物流中心的歐式距離為

Step2對(duì)所有的普通物流地點(diǎn)a到其他各個(gè)物流中心的歐式距離Di(i=1,2,3,…）進(jìn)行比較，找出其中與點(diǎn)a歐式距離最小的物流中心，兩點(diǎn)間的歐氏距離記為Dmin，即

Step3將所有普通物流地點(diǎn)依據(jù)其所最近的物流中心進(jìn)行分區(qū)．

Step4對(duì)所有物流中心所劃分的物流區(qū)域內(nèi)的所有普通物流地點(diǎn)進(jìn)行內(nèi)部檢查．提取出其中的異常點(diǎn)，重新進(jìn)行聚類（此后的聚類排除以當(dāng)前物流中心為聚類中心的情況）．

Step5將聚類結(jié)果存儲(chǔ)，以便之后使用Floyd算法時(shí)調(diào)用．

對(duì)于點(diǎn)X，若當(dāng)點(diǎn)X被聚類到以點(diǎn)A為聚類中心的區(qū)域中時(shí)，X與區(qū)域A內(nèi)的其他點(diǎn)未直接相連，則稱X為異常點(diǎn)．圖1中的點(diǎn)4即為異常點(diǎn)．

若存在一個(gè)屬于物流子區(qū)域A的點(diǎn)a，點(diǎn)a與屬于物流子區(qū)域B的點(diǎn)b直接相連，則稱點(diǎn)a與點(diǎn)b為區(qū)域間相連點(diǎn)，兩個(gè)物流子區(qū)域A和B稱為相鄰物流子區(qū)域．圖1中的點(diǎn)2和點(diǎn)6即為兩個(gè)物流子區(qū)域A和B間的相連點(diǎn)，A和B為相鄰物流子區(qū)域．

以圖1為例說(shuō)明如何排除異常點(diǎn)．利用鄰接矩陣的深度優(yōu)先遍歷算法[8]，遍歷各個(gè)物流中心的物流子區(qū)域是否存在路徑（路徑上的點(diǎn)均在物流子區(qū)域內(nèi)）．對(duì)于物流子區(qū)域A，其鄰接矩陣為，通過(guò)深度優(yōu)先遍歷可以得到在以點(diǎn)A為物流中心的物流子區(qū)域內(nèi)與物流中心間存在路徑的普通物流地點(diǎn)僅有1,2,3,5，剩余的普通物流地點(diǎn)4為異常點(diǎn)．對(duì)普通物流地點(diǎn)4重新聚類，將其劃歸到以點(diǎn)B（點(diǎn)B為與點(diǎn)4歐式距離其次小的物流中心點(diǎn)）為中心的物流子區(qū)域．以點(diǎn)B為聚類中心的物流子區(qū)域的鄰接矩陣為，通過(guò)深度優(yōu)先遍歷可以得到在以點(diǎn)B為物流中心的物流子區(qū)域內(nèi)與物流中心間存在路徑的普通物流地點(diǎn)有4,6,7,8.

1.2 傳統(tǒng)的Floyd算法

在傳統(tǒng)的Floyd算法中，假設(shè)從點(diǎn)a到達(dá)點(diǎn)b間最短路徑距離為Xmin，且點(diǎn)a與點(diǎn)b間存在i個(gè)節(jié)點(diǎn)X1,X2，…，Xi．分別記點(diǎn)a到節(jié)點(diǎn)X1的距離為x1，節(jié)點(diǎn)X1到節(jié)點(diǎn)X2的距離為x2，以此類推，節(jié)點(diǎn)Xi到點(diǎn)b的距離為xi+1．那么應(yīng)該滿足

如果存在另一路徑，點(diǎn)a與點(diǎn)b間存在j個(gè)節(jié)點(diǎn)Y1,Y2，…，Yj，分別記點(diǎn)a到節(jié)點(diǎn)Y1的距離為y1，節(jié)點(diǎn)Y1到節(jié)點(diǎn)Y2的距離為y2，以此類推，節(jié)點(diǎn)Yj到點(diǎn)b的距離為yj+1，使得

那么，令

Floyd算法代碼為：

可以發(fā)現(xiàn)，傳統(tǒng)的Floyd算法的時(shí)間復(fù)雜度為O (n3).

1.3 結(jié)合K-means聚類算法改進(jìn)的Floyd算法

1.3.1 前期準(zhǔn)備前期準(zhǔn)備過(guò)程為：

Step1通過(guò)改進(jìn)的K-means聚類算法將各普通物流地點(diǎn)聚類到對(duì)應(yīng)的物流中心，并存儲(chǔ)以便反復(fù)調(diào)用；

Step2遍歷所有物流點(diǎn)，得到各個(gè)相鄰物流子區(qū)域的區(qū)域間相連點(diǎn)，用傳統(tǒng)Floyd算法[9]求出物流中心到物流子區(qū)域內(nèi)各相連點(diǎn)間的最短路徑和距離；

Step3利用Step2得到的物流中心、區(qū)域間相連點(diǎn)和兩者間最短距離以及區(qū)域間相連點(diǎn)的距離構(gòu)造鄰接矩陣，將所有物流點(diǎn)構(gòu)成的物流區(qū)域降維，使用傳統(tǒng)Floyd算法得到物流中心間的最短路徑．將得到的數(shù)據(jù)進(jìn)行存儲(chǔ)，以便反復(fù)調(diào)用．

1.3.2 物流子區(qū)域內(nèi)的路徑規(guī)劃

在物流子區(qū)域內(nèi)進(jìn)行路徑規(guī)劃時(shí)，僅需對(duì)該物流子區(qū)域內(nèi)的普通物流地點(diǎn)使用傳統(tǒng)Floyd算法進(jìn)行路徑規(guī)劃即可．

1.3.3 物流中心間的路徑規(guī)劃

當(dāng)物流運(yùn)輸?shù)慕K點(diǎn)不在出發(fā)點(diǎn)所在物流區(qū)域時(shí)，需要提前計(jì)算各個(gè)物流中心間的最短路徑，并將得到的數(shù)據(jù)進(jìn)行存儲(chǔ)，以用于跨區(qū)域路徑規(guī)劃．具體過(guò)程為：

Step1確定物流運(yùn)輸?shù)钠瘘c(diǎn)a和終點(diǎn)b所在物流子區(qū)域所對(duì)應(yīng)的物流中心；

Step2調(diào)用前期準(zhǔn)備Step3得到的數(shù)據(jù)，確定起點(diǎn)a與終點(diǎn)b所屬物流中心A,B間的最短路徑；

Step3構(gòu)造物流子區(qū)域內(nèi)的鄰接矩陣，用Floyd算法規(guī)劃起點(diǎn)a到物流中心A的最短路徑；

Step4利用各物流中心間最短距離構(gòu)造新的鄰接矩陣（此時(shí)鄰接矩陣考慮的節(jié)點(diǎn)僅為物流中心），再根據(jù)該鄰接矩陣與Floyd算法規(guī)劃物流中心A到B的最短路徑，得到物流中心間的最短路徑，實(shí)現(xiàn)物流子區(qū)域間的轉(zhuǎn)移；

Step5記錄最后一個(gè)區(qū)域間相連點(diǎn)，即物流中心間最短路徑上第一個(gè)屬于終點(diǎn)所在物流子區(qū)域B的節(jié)點(diǎn)q;

Step6根據(jù)物流子區(qū)域B的節(jié)點(diǎn)構(gòu)造鄰接矩陣，再次進(jìn)行Floyd算法，規(guī)劃點(diǎn)q到點(diǎn)b的最短路徑．

2 規(guī)劃實(shí)例

假設(shè)存在物流運(yùn)輸?shù)貓D（見(jiàn)圖2），按照改進(jìn)的K-means聚類算法進(jìn)行物流子區(qū)域的劃分，結(jié)果見(jiàn)圖3．經(jīng)過(guò)物流中心間的路徑規(guī)劃，可將全地圖簡(jiǎn)化．以物流中心A,B為例，簡(jiǎn)化結(jié)果見(jiàn)圖4.

2.1 物流子區(qū)域內(nèi)的路徑規(guī)劃

在物流子區(qū)域A內(nèi)，規(guī)劃起點(diǎn)為點(diǎn)a，終點(diǎn)為點(diǎn)2的最優(yōu)路徑．傳統(tǒng)Floyd算法求解最短路程為40，路徑為a→A→1→2．使用結(jié)合改進(jìn)K-means聚類算法的Floyd算法求得的最短路程同樣為40，路徑為a→A→1→2.

算法復(fù)雜度分析：此情況下傳統(tǒng)的Floyd算法考慮了所有物流子區(qū)域中的所有節(jié)點(diǎn)，其算法復(fù)雜度[10]為O (n3),n為所有節(jié)點(diǎn)的總數(shù)．而改進(jìn)的Floyd算法則只需考慮物流子區(qū)域所有節(jié)點(diǎn)數(shù)量，其算法復(fù)雜度僅為O((k n)3),kn為該物流子區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)量(0

2.2 物流子區(qū)域間的路徑規(guī)劃

假設(shè)起點(diǎn)b在物流子區(qū)域B內(nèi)，終點(diǎn)6在物流子區(qū)域C內(nèi)．傳統(tǒng)Floyd算法求解最短路程為125，路徑為b→B→3→4→C→5→6．使用結(jié)合改進(jìn)K-means聚類算法的Floyd算法求得的最短路程同樣為125，路徑為b→B→3→4→C→5→6.

算法復(fù)雜度分析：此情況下傳統(tǒng)的Floyd算法考慮了所有物流子區(qū)域中的所有節(jié)點(diǎn)，其算法復(fù)雜度為O (n3),n為所有節(jié)點(diǎn)的總數(shù)．而改進(jìn)的Floyd算法則的算法復(fù)雜度分為三個(gè)部分．第一部分，起點(diǎn)b到物流中心B路徑規(guī)劃，其復(fù)雜度為O((k1n)3),k1n為物流子區(qū)域B內(nèi)的節(jié)點(diǎn)數(shù)量；第二部分，物流中心B到C的路徑規(guī)劃，其復(fù)雜度為O((k2n)3),k2n為物流中心的總數(shù)；第三部分，最后一個(gè)區(qū)域間相連點(diǎn)q到終點(diǎn)6的路徑規(guī)劃，其復(fù)雜度為O((k3n)3),k3n為物流子區(qū)域C內(nèi)的節(jié)點(diǎn)數(shù)量，這里0

3 結(jié)語(yǔ)

傳統(tǒng)的Floyd算法需要考慮全地圖中的每個(gè)普通物流地點(diǎn)與物流中心．假設(shè)物流點(diǎn)的總數(shù)為n，則此時(shí)傳統(tǒng)Floyd算法的時(shí)間復(fù)雜度為O (n3)，故隨著地圖規(guī)模的增大，其計(jì)算所需時(shí)間將快速增長(zhǎng)．

結(jié)合K-means聚類算法的Floyd算法其時(shí)間復(fù)雜度為O((k n)3)(0