地图上所有非物流中心的样本点，称为普通物流地点．由物流中心所管辖的普通物流地点的集合称为物流子区域．假设存在一个属于物流子区域A（以点A为聚类中心的物流子区域）的点a，若a与属于其他物流子区域的点直接相连，则称该点a为区域间相连点，被点a相连的两个物流子区域称为相邻物流子区域．

1 算法原理

1.1 改进的K-means聚类算法

相较于传统的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将所有普通物流地点依据其所最近的物流中心进行分区．

Step4对所有物流中心所划分的物流区域内的所有普通物流地点进行内部检查．提取出其中的异常点，重新进行聚类（此后的聚类排除以当前物流中心为聚类中心的情况）．

Step5将聚类结果存储，以便之后使用Floyd算法时调用．

对于点X，若当点X被聚类到以点A为聚类中心的区域中时，X与区域A内的其他点未直接相连，则称X为异常点．图1中的点4即为异常点．

若存在一个属于物流子区域A的点a，点a与属于物流子区域B的点b直接相连，则称点a与点b为区域间相连点，两个物流子区域A和B称为相邻物流子区域．图1中的点2和点6即为两个物流子区域A和B间的相连点，A和B为相邻物流子区域．

以图1为例说明如何排除异常点．利用邻接矩阵的深度优先遍历算法[8]，遍历各个物流中心的物流子区域是否存在路径（路径上的点均在物流子区域内）．对于物流子区域A，其邻接矩阵为，通过深度优先遍历可以得到在以点A为物流中心的物流子区域内与物流中心间存在路径的普通物流地点仅有1,2,3,5，剩余的普通物流地点4为异常点．对普通物流地点4重新聚类，将其划归到以点B（点B为与点4欧式距离其次小的物流中心点）为中心的物流子区域．以点B为聚类中心的物流子区域的邻接矩阵为，通过深度优先遍历可以得到在以点B为物流中心的物流子区域内与物流中心间存在路径的普通物流地点有4,6,7,8.

1.2 传统的Floyd算法

在传统的Floyd算法中，假设从点a到达点b间最短路径距离为Xmin，且点a与点b间存在i个节点X1,X2，…，Xi．分别记点a到节点X1的距离为x1，节点X1到节点X2的距离为x2，以此类推，节点Xi到点b的距离为xi+1．那么应该满足

如果存在另一路径，点a与点b间存在j个节点Y1,Y2，…，Yj，分别记点a到节点Y1的距离为y1，节点Y1到节点Y2的距离为y2，以此类推，节点Yj到点b的距离为yj+1，使得

那么，令

Floyd算法代码为：

可以发现，传统的Floyd算法的时间复杂度为O (n3).

1.3 结合K-means聚类算法改进的Floyd算法

1.3.1 前期准备前期准备过程为：

Step1通过改进的K-means聚类算法将各普通物流地点聚类到对应的物流中心，并存储以便反复调用；

Step2遍历所有物流点，得到各个相邻物流子区域的区域间相连点，用传统Floyd算法[9]求出物流中心到物流子区域内各相连点间的最短路径和距离；

Step3利用Step2得到的物流中心、区域间相连点和两者间最短距离以及区域间相连点的距离构造邻接矩阵，将所有物流点构成的物流区域降维，使用传统Floyd算法得到物流中心间的最短路径．将得到的数据进行存储，以便反复调用．

1.3.2 物流子区域内的路径规划

在物流子区域内进行路径规划时，仅需对该物流子区域内的普通物流地点使用传统Floyd算法进行路径规划即可．

1.3.3 物流中心间的路径规划

当物流运输的终点不在出发点所在物流区域时，需要提前计算各个物流中心间的最短路径，并将得到的数据进行存储，以用于跨区域路径规划．具体过程为：

Step1确定物流运输的起点a和终点b所在物流子区域所对应的物流中心；

Step2调用前期准备Step3得到的数据，确定起点a与终点b所属物流中心A,B间的最短路径；

Step3构造物流子区域内的邻接矩阵，用Floyd算法规划起点a到物流中心A的最短路径；

Step4利用各物流中心间最短距离构造新的邻接矩阵（此时邻接矩阵考虑的节点仅为物流中心），再根据该邻接矩阵与Floyd算法规划物流中心A到B的最短路径，得到物流中心间的最短路径，实现物流子区域间的转移；

Step5记录最后一个区域间相连点，即物流中心间最短路径上第一个属于终点所在物流子区域B的节点q;

Step6根据物流子区域B的节点构造邻接矩阵，再次进行Floyd算法，规划点q到点b的最短路径．

2 规划实例

假设存在物流运输地图（见图2），按照改进的K-means聚类算法进行物流子区域的划分，结果见图3．经过物流中心间的路径规划，可将全地图简化．以物流中心A,B为例，简化结果见图4.

2.1 物流子区域内的路径规划

在物流子区域A内，规划起点为点a，终点为点2的最优路径．传统Floyd算法求解最短路程为40，路径为a→A→1→2．使用结合改进K-means聚类算法的Floyd算法求得的最短路程同样为40，路径为a→A→1→2.

算法复杂度分析：此情况下传统的Floyd算法考虑了所有物流子区域中的所有节点，其算法复杂度[10]为O (n3),n为所有节点的总数．而改进的Floyd算法则只需考虑物流子区域所有节点数量，其算法复杂度仅为O((k n)3),kn为该物流子区域内的节点数量(0

2.2 物流子区域间的路径规划

假设起点b在物流子区域B内，终点6在物流子区域C内．传统Floyd算法求解最短路程为125，路径为b→B→3→4→C→5→6．使用结合改进K-means聚类算法的Floyd算法求得的最短路程同样为125，路径为b→B→3→4→C→5→6.

算法复杂度分析：此情况下传统的Floyd算法考虑了所有物流子区域中的所有节点，其算法复杂度为O (n3),n为所有节点的总数．而改进的Floyd算法则的算法复杂度分为三个部分．第一部分，起点b到物流中心B路径规划，其复杂度为O((k1n)3),k1n为物流子区域B内的节点数量；第二部分，物流中心B到C的路径规划，其复杂度为O((k2n)3),k2n为物流中心的总数；第三部分，最后一个区域间相连点q到终点6的路径规划，其复杂度为O((k3n)3),k3n为物流子区域C内的节点数量，这里0

3 结语

传统的Floyd算法需要考虑全地图中的每个普通物流地点与物流中心．假设物流点的总数为n，则此时传统Floyd算法的时间复杂度为O (n3)，故随着地图规模的增大，其计算所需时间将快速增长．

结合K-means聚类算法的Floyd算法其时间复杂度为O((k n)3)(0