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

刘欣

摘要：物流配送路线优化是物流活动中重要的环节，能短时高效的配送货物是空间数据优化问题。在空间数据处理方面，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个网点各自的最佳配送路径。