-
摘要: 为了提高车辆配送初始解获得的效率, 在不确定条件下, 研究了上海世博会行李跟随系统需求点的空间特性, 提出了基于空间特性的车辆调度方法, 建立了需求点的空间特性SLINK聚类分析方法和聚类分析结果评估方法。计算结果表明: 在需求点群聚状态下, 采用基于空间特性的聚类分析法的调度初始解总距离为583, 而传统SWEEP扫描法的调度初始解总距离为595, 因此, 在对车辆调度问题进行求解时, 对需求点的空间分布特性进行分析有助于不确定环境下车辆调度问题的最终求解。Abstract: In order to improve the efficiency of initial solution for vehicle routing problem(VRP), the spatial characters of demand points for hands-free travel system in Shanghai World Expo were studied under uncertainly conditions.Vehicle routing method was put forward based on the spatial characters, and the Single-LINkage(SLINK) clustering method for the spatial characters and the estimation method for the clustering analysis result were built.Computation result indicates that the Single-LINkage clustering method can get the total distance of 583 for the initial solution, and the SWEEP method gets 595 when the demand points are clustering, so the analysis of spatial character for demand points contributes to the last solving for the VRP under the uncertainly conditions.
-
表 1 类别中心点初始坐标
Table 1. Initial coordinates of categories centre
类别 1 2 3 4 x 5.00 5.00 63.00 67.00 y 6.00 64.00 69.00 5.00 
下载: 导出CSV
表 2 类别中心点收敛坐标
Table 2. Convergence coordinates of categories centre
类别 1 2 3 4 x 19.09 18.09 50.37 49.69 y 21.41 54.38 54.53 21.89
下载: 导出CSV
表 3 聚类分析的评估指标值
Table 3. Evaluation index values of cluster analysis
评估指标 评估值 评估指标 评估值 群聚1的密度率 0.392 156 群聚1的凝聚率 0.617 647 群聚2的密度率 0.153 699 群聚2的凝聚率 0.540 540 群聚3的密度率 0.217 171 群聚3的凝聚率 0.695 652 群聚4的密度率 0.274 853 群聚4的凝聚率 0.578 947 群聚1、2的鉴别率 0.676 580 群聚2、3的鉴别率 0.482 656 群聚1、3的鉴别率 0.058 471 群聚2、4的鉴别率 0.049 163 群聚1、4的鉴别率 0.620 248 群聚3、4的鉴别率 0.000 000
下载: 导出CSV
-
[1] 杨东援. 2010年上海世博会交通系统规划研究[R]. 上海: 同济大学, 2005. [2] 杨东援. 现代物流学讲义[M]. 上海: 同济大学出版社, 2000. [3] CLARK P J, EVANS F C. Distance to nearest neighbour as ameasure of spatial relationshipsin populations[J]. Ecology, 1954, 35: 445-453. doi: 10.2307/1931034 [4] DONNELLY K P. Si mulations to determine the variance andedge effect of total nearest-neighbour distance[C]∥Cambridge University. Si mulation Studies in Archaeology. Cambridge: Cambridge University Press, 1978: 91-95. [5] 王本洋, 余世孝. 种群分布格局的多尺度分析[J]. 植物生态学报, 2005, 29(2): 235-241. https://www.cnki.com.cn/Article/CJFDTOTAL-ZWSB200502008.htmWANG Ben-yang, YU Shi-xiao. Multi-scale analyses of population distribution patterns[J]. Acta Phytoecologica Sinica, 2005, 29(2): 235-241. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZWSB200502008.htm [6] JAI N A K. Data clustering: a review[J]. ACM Computing Surveys, 1999, 31(3): 264-323. http://www.cs.ecu.edu/~dingq/CSCI6905/readings/jain99data.pdf [7] 陈荣昌, 林育臣. 群聚演算法及群聚参数的分析与探讨[J]. 朝阳学报, 2003(8): 327-353.CHEN Rong-chang, LI N Yu-chen. The analysis and research of clustering algorithms and clusters parameters[J]. TheJournal of Chaoyang University of Technology, 2003(8): 327-353. (in Chinese) [8] CHRISTOFIDES N, MI NGOZZI A, TOTH P. The vehicle routing problem[C]∥CHRISTOFIDES N, MI NGOZZI A, TOTH P, et al. Combinatorial Opti mization. New York: Wiley, 1979: 315-338. -
点击查看大图
图(5) / 表(3)
计量
- 文章访问数: 205
- HTML全文浏览量: 79
- PDF下载量: 241
- 被引次数: 0
