物流规划课程设计 第 11 页 共 16 页
图4-3 聚类分布图
由spss软件进行聚类分析得到聚类中心的坐标位置为下表4-5
表4-5 最终聚类中心
最终聚类中心 x轴 y轴 1 4.0 8.9 2 9.0 8.0 3 12.5 6.4 聚类 4 5.0 2.4 5 11.6 3.3 6 2.9 5.7 7 7.9 4.7 4.2对聚类结果进行调整
聚类完成后，还应根据车载量这个约束条件对聚类结果进行判断调整。
Step1：计算每一个聚类内的便利店需求量的总和；
Step2：判断每一聚类内便利店的需求量的总和是否超过车载量； 如果未超过，说明符合条件。
如果超过车载量，选择该聚类中距离质心最远的点，将其拟归入距离其他类质心距离最近的类，归入某一类前，还必须判断如归入后该类的便利店需求量的总和是否小于车载量。如果小于，即将该数据归入该类，否则，选择欧式距离再次之的类作为拟归入的类，同样判断该类便利店需求量是否小于车载量是否小于车载量，如果小于则归，否则选择距离再次之的。
Step3：当所有的类零售户订单量总和都小于车载量时，暂告一段落。 调整完毕以后，每一类的便利店地理位置相对集中，且订单量总量小于车载
物流规划课程设计 第 12 页 共 16 页
重量。
聚类1：总需求量Q1=0.15+0.18+0.22+0.2+0.23=0.98<车载量 聚类2：总需求量Q2=0.25+0.27+0.13+0.22=0.87<车载量 聚类3：总需求量Q3=0.22+0.23+0.17+0.26=0.88<车载量 聚类4：总需求量Q4=0.28+0.19+0.18=0.65<车载量 聚类5：总需求量Q5=0.12+0.27+0.16+0.11=0.66<车载量 聚类6：总需求量Q6=0.18+0.25+0.25+0.29+0.22=1.19>车载量 聚类7：总需求量Q7=0.15+0.2+0.16+0.2+0.18+0.15+0.16=1.2>车载量
聚类6需求量总和超过车载量，选取聚类6中距离其质心最远的点为便利
店30，其需求量为0.25吨，将其归入距离其他其他聚类质心距离最近的类，为聚类4，计算将便利店30归入聚类4中后，聚类4的需求总量为0.9吨，小于车载量，所以聚类4为11、12、28、30:；
聚类7需求量总和超过车载量，选取聚类7中距离其质心最远的点为便利店23，其需求量为0.15吨，将其归入距离其他其他聚类质心距离最近的类，为聚类5，计算便利店23归入聚类5中后，聚类5的需求总量为0.81吨，小于车载量，但聚类7去掉点23后总需求量仍大于车载量，所以继续选取聚类7中距离其质心最远的点为便利店20，其需求量为0.18吨，将其归入距离其他其他聚类质心距离最近的类，为聚类5，计算便利店20归入聚类5中后，聚类5的需求总量为0.99吨，小于总车载量，同时此时聚类7的总需求量为0.87吨，也小于车载量，所以聚类5为20、22、23、24、25、26，聚类7为7、10、15、16、28。
对聚类进行调整后，新得到的聚类如下表4-6：
表4-6 改进后的聚类中心
聚类 1 2 3 4 5 6 7 所包含1、2、3、8、9、13、17、18、11、12、20、22、5、6、31、7、10、的便利4、29 14 19、21 27、30 23、24、32 15、16、店 25、26 28 4.3 对得到的聚类区域进行路线规划
首先对聚类1运用最近插入法：
物流规划课程设计 第 13 页 共 16 页
聚类1中各个便利店之间的距离为：
表4-7 聚类1各便利店的距离
便利店 v1 v2 v3 v4 v29 v1 v2 2.3 V3 1.6 0.9 v4 2.6 1.8 1.3 V29 1.3 2.5 1.5 1.8 从v2出发的所有路径的大小，c2/3=0.9为最小，这样，就由节点v2、v3构成一个子回路，T=（v2，v3）。
然后考虑剩下节点v1、v4、v29到v2和v3中某一个节点最小的距离：
c3/4=1.3，由于对称性，无论将4插到2和3之间往返路径中，结果都是一样的，构成一个新的子回路T=（v2，v3，v4，v2）。
接着考虑剩下节点v1、v29到v2、v3、v4中某一个节点的最小距离c3/29=1.5，节点v29有3个位置可以插入。现在分析将v29插到那里合适。 （1）插到（3，4）间 距离=1.5+1.8-1.3=2 （2）插到（2，3）间 距离=2.5+1.5-0.9=3.1 （3）插到（2，4）间 距离=2.5+1.8-1.8=2.5
比较上面3种情况的增量，插到（3，4）之间的增量最小，所以应将v29加入到（3，4）间，结果为：T=（v2，v3，v29，v4，v2）
重复上面的步骤，再将节点v1加入到回路中，就可以得到最近插入法所得的解，
T=（v2，v3，v1，v29，v4，v2） 这就是行驶最短路径的相对最优解。 对聚类2用最近插入法，同上，得最优路径。 T=（v8，v14，v13，v9，v8）
对聚类3用最近插入法，同上，得最优路径。 T=（v17，v18，v21，v19，17）
对聚类4用最近插入法，同上，得最优路径。 T=（v11，v30，v12，v27，v11）
物流规划课程设计 第 14 页 共 16 页
对聚类5用最近插入法，同上，得最优路径。 T=（v20，v22，v24，v26，v25，v23，v20） 对聚类6用最近插入法，同上，得最优路径。 T=（v5，v6，v32，v31，v5）
对聚类7用最近插入法，同上，得最优路径。 T=(v7，v15，v16，v28，v10，v7) 最终优化路线如表4-8,
表4-8 最终优化路线
聚类1 聚类2 聚类3 聚类4 聚类5 聚类6 聚类7 根据上表绘制最终优化线路图4-4。
优化后路线 2—3—1—29—4 8—14—13—9 17—18—21—19 11—30—12—27 20—22—24—26—25—23 5—6—32—31 7—15—16—28—10
图4-4 最终优化线路图
物流规划课程设计 第 15 页 共 16 页
5 小结
本文对国大便利店配送线路的优化问题提出了一个比较完整的解决方案，在实用方面实现了车辆的合理调度，减少了不必要的出车次数，提高了车辆的满载率，实现了配送车辆送货线路的最优化生成。基本上完成了本次课程设计的任务。在科学方面我们对国大配送路线进行了层层分析、细化，减少了问题的规模，得到可行解，具有可行性；在配送区域划分中采用了K均值聚类法，并对初始聚类点的确定方法进行优化改进，使聚类结果更加合理，效率更高；在配送区域划分时加上车载量限制条件，使最终结果真正有使用价值。
在此次课程设计中，我们学会了K均值聚类法及其应用，复习并巩固应用了最近插入法，并学习了spss软件的用法，同时也感到一些看似简单的问题在实际运用中还是会遇到很多困难，如数据的收集，聚类法在实际问题上的应用等。我们学习的理论在实际运用中有很大的局限性，在应用理论时，必须紧密联系实际，在基本理论的基础上突破陈规，最终使得理论和实际完美结合。
通过这次课程设计使我们认识到，一个人的力量是有限的，思维方式也存在很大的局限性，只有通过团队的合作才能更全面地去发现问题、思考问题、解决实际问题，得到的最终方案才会更具实际意义。同时，感谢李老师和靳老师对我们组的悉心指导，使我们的思路更加开阔，最终的方案也更加完善。
物流规划课程设计 第 16 页 共 16 页
参考文献
1. 董千里.物流工程，大连:东北财经大学出版社，2007。 2．蒋长兵.物流系统与物流工程，北京:中国物出版社资，2007。 3. 刘昌祺.物流配送中心系统选址选择与设计，机械工业出版社，2006。 4. 毛良伟.物流系统规划与方法，机械工业出版社，2006。 5. 蔡临宁.物流系统规划-建模及实例分析，机械工业出版社，2008 6．张可明.物流系统分析．北京:清华大学出版社．2004
7. 孙焰.现代物流管理技术—建模理论及算法设计.上海:同济大学出版社.2004 8. 张晓川.物流配送系统规划.北京:水利水电出版社.2007