L M N O P Q R S T 6095 498 2664 394 3761 8879 23419 13653 13118 5262 4 159 5071 8403 16579 8327 10237 12461 4067 2727 1726 4447 2093 6834 7040 14753 9127 10731 4074 2088 2136 2680 10881 13885 4179 12880 499 8 22 3274 1971 2348 1746 17983 7446 0 0 0 0 0 0 0 0 0 0 0 469 0 0 490 1751 24 0 26654 7311 7128 15322 18908 46011 56168 60829 55032
5.1.6 确定某个区域内卸货点的位置
为了安排该城市的配送方案，我们需要知道每个区域货车的需求量（车次）以及货车的最佳行驶路线，即找到使行驶总路线最短的方法，这明显是一个图论的问题。
接下来，我们针对某个区域的情况做进一步的分析。我们选定图中紫色区域即区域N1进行分析。区域N1中包含的用户位置见附表一。其中共包含112个用户。
一、聚类分析[3]确定卸货点覆盖区域
首先。我们采取相邻用户去同一卸货点取货的方式（暂时不考虑卸货点需要租用地点和工作人员看守的事宜，直接由货车司机看守等待用户取货），利用聚类分析的原理确定7个卸货点覆盖区域。聚类分析是研究如何对指标或样本进行分类的一种多元统计分析方法。描述变量之间亲疏关系的统计量有很多，目前应用最多的是距离和相似系数。研究样本或变量的亲疏程度的数量指标有两种，一种叫相似系数，性质越接近的变量或样本，它们的相似系数越接近于1或-l，而彼此无关的变量或样品它们的相似系数则越接近于0，相似的为一类，不相似的为不同类；另一种叫距离，它是将每一个样品看作p维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。
1.定义距离的准则
如果用dij表示第i个样品和第j个样品之间的距离，那么对一切i，j和k，dij应该满足如下四个条件： ①当且仅当i=j时，dij=0 ②dij>0
③dij=dji（对称性）
④dij≤dik+dkj（三角不等式）
2.Euclidian距离
欧氏距离（ Euclidean distance）也称欧几里得距离是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。
在二维和三维空间中的欧式距离的就是两点之间的距离，二维的公式是
d=sqrt(x1-x2)^2+(y1-y2)^2)（8） 转化为本题中的经纬度计算为：
2）（i,j=1,2,3??Dij?{[111*(xi?（x9?[111*cos?112*(）yi ?yj)]2}j)]
10
其中i,j为两个不同的用户位置， Dij为ij两个用户位置之间的距离。
在matlab中将距离相近的点聚类，将区域①中的112个用户分散到7个区域中。具体结构详见excel表格。
二、精确重心法[4]确定卸货点位置
重心法是将物流系统的需求点看成是分布在某一平面范围内的物体系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心将作为物流网点的最佳设置点， 利用确定物体中心的方法来确定物流网点的位置。
本题中我们希望每个卸货点区域中，卸货点到所有用户位置的距离之和D总最短。
D总= n 1/2 （10）
22 [(x?x)?(y?y)]?isisi?1（xs,ys）为卸货点位置，n为该卸货点覆盖区域的用户数注：(xi,yi)为每个用户的位置，
量。
精确中心法目标函数为双变量系统，分别对xS和yS求偏导，并令岛数为零，求得隐含最优解的等式为：
（11）
（12）
（13）
一、Excel规划求解
1.在Excel中输入数据，并且假设原点坐标为（1，1），以覆盖区3为例，在K1中输入“=SQRT((111*($B$1-B9))^2+(99.25*($C$1-C9))^2)”，并将右下角的十字光标下拉复制公式。
11
2.规划求解，利用excel工具栏中的加载宏“规划求解”，对卸货点位置进行迭代，得到最佳卸货点位置。
3.第100次迭代求得卸货点坐标为（107.8923,26.37949），此时总路程为2.12666KM。
4.七个卸货点均用此方法算出最佳位置，并计算出每个卸货点每天的需货量，图下表所示。
表7 卸货点信息表 卸货点 纬度 经度 周一货量 周二货量 周四货量 合计2 1 107.8788317 26.4090417 0 1270 0 1270 2 107.8466432 26.42715803 0 66 26 92 3 107.8923015 26.3794931 0 228 0 228 4 107.8230497 26.37831175 0 228 0 228 5 107.8082125 26.32132914 50 2695 0 2745 6 107.8564249 26.30397829 0 70 0 70 7 107.8269235 26.28442958 40 210 0 250 合计1 90 4767 26 4883 由此可知一周之内该区域总共需要4883箱货物，根据计算我们可知一辆小型货车一周往返一次(一个车次)即可满足运货需求，并且小型货车在市区行驶灵活，减少交通污染。如果货车走完该区域用时远小于8小时，则回到出发点后进行其他区域的运货任务（相当于另外一辆车）。
接下来我们只需确定货车在一个区域的最短行驶路线即可。
12
5.1.8运用Floyd算法[5]确定每两个卸货点之间的最短距离
要给出将货物送到七个卸货点并返回的最短路线，我们将卸货点之间的距离求出。利用图论中的Floyd算法和哈密尔顿圈求解往返最短路线问题，在matlab中可以得出它的最佳路线和最短路程。
首先，我们绘制用户位置、卸货点以及其附近交通道路的图像，如图3所示。
图3 卸货点位置图
配送中
由图可知，卸货点均选在用户密集的地点，即卸货点选择正确。 然后，我们需要利用Floyd算法，计算每两点之间的最短距离。
Floyd算法是一种用于寻找给定的加权图中顶点间最短路径的算法。我们可以通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；??；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
为了简便计算，我们寻找离卸货点最近的公路节点作为“真实卸货点”，由此可知卸货点之间经历的公路编号和ID。
从而我们可以知道七个卸货点之间的最短距离，注意此距离并非是卸货点间直线距离，而是通过floyd算法而得到的公路折线距离。
例如卸货点1到卸货点2之间的最短距离为 KM，其间一次经历的公路编号为： 11947?11948?11949?11950?11951?11952?11953?11953?11953?11953① ?
?12105?11907?12956?12204?14245?14272?14271?14270?14269?14268
?14259?14266?② 具体情况如下表所示。 表8 卸货点间距表 起点 终点 距离（KM） 0 1 22.20958
13
0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4 5 5 6
2 3 4 5 6 7 2 3 4 5 6 7 3 4 5 6 7 4 5 6 7 5 6 7 6 7 7 24.29047 24.36157 28.18446 33.59556 32.58055 35.66729 3.458314 29.60301 6.192421 44.33731 16.65842 20.34785 25.14470 2.734107 32.62384 13.2001 16.88954 22.41059 23.98946 11.94460 8.255160 29.88973 10.46599 14.46599 19.42374 15.73430 3.689438 14