基于网络Voronoi图的物流配送路线优化的研究.doc

基于网络Voronoi图的物流配送路线优化的研究 刘欣 摘要：物流配送路线优化是物流活动中重要的环节，能短时高效的配送货物是空间数据优化问题。在空间数据处理方面，Voronoi图理论已经成为研究区域离散数据的有力工具，能够解决地理设施选址布局、服务范围划分、物流园区界定模型。本文引入Voronoi图定义，构建出了基于网络Voronoi图的物配送路线优化的模型。 关键词：物流配送网络voronoi图动态构造 基金项目:河北省高等学校科学技术研究项，编号为QNxx1159，承德市软科学研究计划项目(承德市公交线路的发展现状与优化分析)：xx22123。 1、背景简介 配送中心是现代物流系统的重要组成部分，是联系制造商与用户的物流节点，对产品实行储存、配送、流通、加工等活动，配送却是一种固定的形态，甚至是一种有确定组织、确定渠道，有一套装备和管理力量、技术力量，有一套制度的体制形式，物流配送路线优化是物流活动中重要的环节，能短时高效的配送物品，是空间数据优化处理问题。在空间数据方面，Voronoi图理论已经成为研究离散数据的有力工具，能够解决地理设施选址布局、服务范围划分、物流园区界定模型。本文引入Voronoi图定义，构建出了基于网络Voronoi图的物配送路线优化的模型。 1.1Voronoi图定义 作为计算几何的分支，Voronoi图因理论和实际应用的需要而迅速发展起来。越来越多学者关注此算法，Voronoi图的算法被广泛用于气象学，生物学，地质学等学科。网络Voronoi图是它的一个重要概念，可用于城市规划、行政区域划分、物流园区设定，及公路和铁路网络建设等。 这平分线是一个点的轨迹线，满足从到之间的距离差异，且从距离为常数，该轨迹被称为以和为焦点的双曲线一部分。图2给出加权Voronoi图的一个例子，图中数字分别表示生成元的权数。 2、网络Voronoi图的构建思想 假设在欧几里德平面上有生成元点，我们将构建加权网络Voronoi图。首先，我们分配不同的颜色给不同的生成点，以黑色为网络。再取生成元点为中心，画圈圈。从中心铺开是在同一个时间同一个加权相加网络距离。我们只对用黑颜色的点分配色彩，将极大提高构造效率，当屏幕上的所有黑色点都被标记颜色则程序结束，我们得到的加权相加的网络Voronoi图。 3、应用于物流配送路线优化研究 现在我们把物流网点视为生成元3点，采用离散算法构造加权网络Voronoi图。网络Voronoi图的生成过程，及网络分布如图3-4所示。首先，我们给不同的生成元点分配不同的颜色，并对网络取黑颜色，网络是用虚线表示，以生成元为中心和加权网络距离为半径求出边界点（图3），当屏幕上的所有黑色点都被标记为三种不同颜色（红、蓝、绿），则程序结束，我们得到的网格加权网络Voronoi图（图4），不同颜色的路线即为3个网点各自的最佳配送路径。 4、评价 对加权网络Voronoi图的离散结构克服很多传统的缺点，不需要考虑网络分布情况，因此，在网络Voronoi图构建的独特优势，在物流路线优化上具有很高的应用价值，可推广到公路、铁路路线网络的设计问题。 参考文献 1F.Aurenhammer:AnoptimalalgorithmforconstructingtheweightedVoronoidiagramintheplaneJ.PatternRecognition，vol.17(1984)，pp.251-257. 2张有会，浅也哲夫，小保方幸次.关于一般图形Voronoi图的近似构造法的研究.数值计算与计算机应用J.xx，9(3):216225 3吴壮志，杨钦等.Power图的性质及构造算法研究J.计算机辅助设计与图形学学报.xx，13(12):10571062 4FrancoP.Preparata，MichaelIanShamos著，庄心谷译.计算几何导论M.北京：科学出版社.1990 5周培德，卢开澄.计算几何算法分析与设计M.清华大学出版社，广西科学技术出版社.2000