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

1 算法原理

1.1 改進的K-means聚類算法

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

Step1求普通物流地點a到各個物流中心的歐式距離．記普通物流地點a對應的坐標為(x0,y0)，其他物流中心的坐標為(xi,yi)(i=1,2,3,…），點a到其他各個物流中心的歐式距離為

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

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

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

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

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

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

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

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

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

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

那么，令

Floyd算法代碼為：

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

1.3 結合K-means聚類算法改進的Floyd算法

1.3.1 前期準備前期準備過程為：

Step1通過改進的K-means聚類算法將各普通物流地點聚類到對應的物流中心，并存儲以便反復調(diào)用；

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

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

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

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

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

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

Step1確定物流運輸?shù)钠瘘ca和終點b所在物流子區(qū)域所對應的物流中心；

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

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

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

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

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

2 規(guī)劃實例

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

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

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

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

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

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

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

3 結語

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

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