基于网络Voronoi图的物流配送路线优化的研究-物流管理.doc
5页
基于网络Voronoi图的物流配送路线优化的研究■物流管理基于网络Voronoi图的物流配送路线优化的硏究刘欣摘 要：物流配送路线优化是物流活动中重要的环节，能短时高效的配送货 物是空间数据优化问题在空间数据处理方面‘Voronoi图理论已经成为研究区 域离散数据的有力工具，能够解决地理设施选址布局、服务范围划分、物流园区 界定模型本文引入Voronoi图定义，构建岀了基于网络Voronoi图的物配送 路线优化的模型关键词：物流配送 网络Voronoi图 动态构造基金项目:河北省高等学校科学技术硏究项,编号为QN20131159 ,承德市 软科学研究计划项目（承德市公交线路的发展现状与优化分析）:201422123o1＞背景简介配送中心是现代物流系统的重要组成部分，是联系制造商与用户的物流节 点，对产品实行储存、配送、流通、加工等活动,配送却是一种固定的形态，甚 至是一种有确走组织、确走渠道，有一套装备和管理力量、技术力量,有一套制度的体制形式，物流配送路线优化是物流活动中重要的环节，能短时高效的配送物品，是空间数据优化处理问题在空间数据方面,Voronoi图理论已经成为硏究离散数据的有力工具，能够解决地理设施选址布局、服务范围划分、物流园区界定模型。
本文引入Voronoi图定义，构建出了基于网络Voronoi图的物配送路线优化的模型1.1 Voronoi 图定义作为计算几何的分支Voronoi图因理论和实际应用的需要而迅速发展起来越来越多学者关注此算法，Voronoi图的算法被广泛用于气象学,生物学，地质学等学科网络Voronoi图是它的一个重要概念，可用于城市规划、行政区域划分、物流园区设定，及公路和铁路网络建设等亨而色；J Voronoi图在欧几里第亨而I •的有般数■的不冋 点P={a.亠・•••・ J12
图2给出加权Voronoi图的一个例 子，图中数字分别表示生成元的权数 2、网络Voronoi图的构建思想假设在欧几里德平面上有生成元点 我们将构建加权网络Voronoi图首先,□□我们分配不同的颜色给不同的生成点，以黑色为网络再取生成元点为中心，画 圈圈从中心铺开是在同一个时间同一个加权相加网络距离我们只对用黑颜色 的点分配色彩，将极大提高构造效率,当屏幕上的所有黑色点都被标记颜色则程 序结束,我们得至啲加权相加的网络Voronoi图3.应用于物流配送路线优化硏究现在我们把物流网点视为生成元3点，采用离散算法构造加权网络Voronoi 图网络Voronoi图的生成过程,及网络分布如图3-4所示首先，我们给不 同的生成元点分配不同的颜色，并对网络取黑颜色，网络是用虚线表示，以生成 元为中心和加权网络距离为半径求出边界点（图3 ）,当屏幕上的所有黑色点都 被标记为三种不同颜色（红、蓝、绿），则程序结束，我们得到的网格加权网络Voronoi图（图4 ）,不同颜色的路线即为3个网点各自的最佳配送路径 A frj-"一…叫 J3o11卩L皿111XT :巧F 、久％巧 \r 1P31 11 1■X■1 1■ 丄! ^9 •W3给出各生成元和半松图4加权网络Voronoi RR4、评价对加权网络Voronoi图的离散结构克服很多传统的缺点，不需要考虑网络分 布情况,因此,在网络Voronoi图构建的独特优势,在物流路线优化上具有很 高的应用价值，可推广到公路、铁路路线网络的设计问题。
参考文献[l]F.Aurenhammer:An optimal algorithm for constructing the weighted Voronoi diagram in the plane [J].Pattern Recognition z vol.l7(1984) , pp.251-257.[2]张有会，浅也哲夫，小保方幸次.关于一般图形Voronoi图的近似构造法的研究•数值计算与计算机应用[J].2OO2 , 9(3):216-225⑶吴壮志,杨钦等.Power图的性质及构造算法研究[J].计算机辅助设计与 图形学学报.2001 , 13(12):1057-1062[4] Franco P. Pre pa rata , Michael Ian Shamos 著,庄心谷译.计算几何导论[M].北京:科学出版社.1990[5]周培德，卢开澄.计算几何一算法分析与设计[M].清华大学岀版社，广西科学技术出版社.2000.作者简介:刘 欣（1977.6 -几女，承德石油高等专科学校社科数理部讲师，硕士，研究方向：应用数学,计算几何,数学建模作者单位：承德石油高等专科学校 河北承德市061000 ）。
