乘权Voronoi图的构成及其在物流网点选取上的应用

刘欣 LIU Xin

（承德石油高等专科学校社科与数理部，承德 067000）

摘要： 乘权Voronoi图由于权值的设定公式非常复杂，在传统的算法中，当生成元或乘积发生改变时，程序运行会异常复杂。本文给出了乘权Voronoi图的动态构造算法，改进了传统算法的缺点，因而更省时高效，具有较高的理论价值。本文还给出乘权Voronoi图在北京市区选取物流网点时的应用。

教育期刊网 http://www.jyqkw.com
关键词 ： 乘权Voronoi图；动态构造；物流网点选取

中图分类号：TP274 文献标识码：A 文章编号：1006-4311（2015）17-0061-02

基金项目：河北省高等学校科学技术研究项目QN 20131159；承德市软科学研究计划项目（承德市公交线路的发展现状与优化分析）：201422123。

作者简介：刘欣（1977－），女，河北承德人，承德石油高等专科学校社科数理部讲师，硕士，研究方向为计算几何，算法设计等。

1 背景简介

普通Voronoi图（泰森多边形），是计算几何的一个重要分支,在计算几何理论和应用中起着重要作用。而普通Voronoi图的算法划分区域，有很大的局限性。为扩展Voronoi图使其应用在更广泛的领域，在Voronoi图中引入了权的概念。传统的乘权Voronoi图的算法，运算效率与母点个数有密切关系。而动态构造算法几乎与母点个数无关,且母点个数越多,其相对效率越高。进行构造时，对以不同颜色区分Voronoi区域的乘权Voronoi图进行横向扫描，在扫描过程中，如果某像素与其后续像素颜色不同，就将该像素置为指定的颜色（例如黑色）；否则置为另一种颜色（例如白色）；再进行纵向扫描，处理同上。两次扫描完成后，其结果便为由指定颜色画出的乘权Voronoi图。

2 传统算法

2.2 动态的乘权Voronoi图的构造

现在我们以9个生成元分为例，用离散算法构造乘权Voronoi图。图1、图2显示了其动态生成过程，括号中的数字代表该生成元的权重。首先分配不同的颜色代表不同的生成元点，然后以画圆圈的点为中心，以生成元乘权距离为半径（图1），最后得到乘权网络Voronoi图（图2）。

3 北京地区物流配送中心网点

乘权Voronoi图的动态构造算法能克服多种缺点，因为我们只需要考虑生成元变化。所以结果表明，它比传统的算法更简单，高效，并具有广泛的应用价值，能较好地解决加权Voronoi图在地理信息处理、城市规划、最优化配置等许多领域的问题。以下给出乘权Voronoi图为韵达快递公司在北京市区物流配送中心网点设置上，当生成元为18，以生成元乘权距离为半径，以画圆圈的点为物流配送中心，即北京地区物流配送中心网点数可设置为18个，而非按照行政区域设定，便于达到日常配给及应急物流配置要求。图3-图4对比传统Voronoi图与加权Voronoi图所得分割的部分区域，可见，加权Voronoi图，有效解决了分割区域边界的连续问题，乘权Voronoi图在配送中心服务范围划分上，比传统的行政区域界定物流配送中心服务范围的方法更符合物流市场的实际情况。

图中数字代表的北京各区名称如表1所列。

4 物流网点选址模型评价

通过上述优化实例得到以下结论：

①与已有的定量划分方法相比，将Voronoi图和加权Voronoi图相结合，反映出不同等级物流节点服务范围的层次关系，对于物流网点空间服务范围的划分，也可基于货物的竞争力、广义费用等因子进行动态划分，具有较强的实际价值。

②当不考虑规模优化时，物流网点布局方案中企业布局假定为均匀，层次性不明显；当考虑规模因素时，物流网点布局方案中企业布局呈不均匀布置，层次性较为明显．此变更可调整模型权数的取值不同，值越大，表明企业布局对其服务范围和布局优化的影响越大。

③在物流网点选址及布局规划中，考虑到物流需求不是均匀分布的，且物流网点的配送范围受到需求点广义费用的影响，在实际应用中，可分析各需求点到物流网点的实际运输距离、运输时间以及费用来综合表达各网点的势能模型，将更具有实际意义和操作价值。

教育期刊网 http://www.jyqkw.com
参考文献：

[1]F.Preparata,M.I.Shamos著.计算几何导论[M].庄心谷，译.北京：科学出版社，1990.

[2]王新生，郭庆胜，等.Voronoi图的扩展、生成及其应用于界定城市空间影响范围[J].华中师范大学学报（自然科学版），2002，36（1）：107-111.

[3]周德培.计算几何-算法分析与设计[M].北京：清华大学出版社，2000.

[4]王新生.Voronoi图和非数值随机优化算法在城市与区域规划中的应用研究[D].武汉：武汉大学，2002.