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