基于加权Voronoi图的连续型物流节点布局优化＊

王 伟 封学军

（河海大学港口海岸与近海工程学院水运规划与物流工程研究所1） 南京 210098）（长沙理工大学公路工程省部共建教育部重点实验室2） 长沙 410004）

国内外学者采用调查法、雷利法则、引力模型、需求势能理论、系统建模等方法［1－4］研究了物流节点的合理服务范围划分；相关学者还基于物流节点服务范围的分析，基于重心法、鲍姆尔－沃尔夫法、双层规划、混合整数规划、图论等方法构建了物流节点布局优化模型［5－6］，系统地研究了物流节点数量、选址、规模的综合优化问题.现有的研究虽能概要性确定物流节点服务范围，但未能综合反映物流节点对服务区域的吸引，难以满足动态性、系统性的要求，且只是粗略的划分，在一定程度上限制了物流节点布局优化研究的深度和准确性.

本文采用引力模型来确定物流节点对区域空间的吸引力，引入加权Voronoi图来实现物流系统空间服务范围的动态精确划分，在此基础上，构建连续型物流节点布局优化模型，提出模型的高效求解算法.

1 加权Voronoi图

加权Voronoi图［7］的定义如下：

设P＝（P1，P2，…，Pn），3≤n＜∞为二维欧氏空间上的一个控制点集；λi（i＝1，2，…，n）是给定的n个正实数，则

将平面分成n部分，由V（pi，λi）（i＝1，2，…，n）确定的对平面的分割称为点上加权的Voronoi图，称λi为pi的权重.

加权Voronoi图的生成可采用离散生成算法，此方法无需复杂的计算，容易实现［8］.同时，考虑到物流节点存在多层级情况，假设物流节点的竞争只存在于同级别的节点之间，对于多层级物流节点服务范围的划分可以转化为多个单层级内物流节点服务范围划分问题，通过多次离散生成法来实现.

2 物流节点服务范围划分的引力模型

物流节点服务范围的划分要考虑到内外部环境中的诸多因素，物流节点服务范围的确定与节点的层级、功能、规模、服务对象紧密关联，提出如下假设：物流节点的功能是一致的；只考虑同层级物流节点之间的竞争；物流节点对服务区域的吸引力也存在“规模效应”和“递远递减”的现象.构建物流节点的吸引力模型来解决物流节点服务范围划分的问题［9］，设有n个物流节点（同一层级），s个需求点（可将区域物流系统服务区域划分为若干个小区），则物流节点i对需求点j的吸引力为

式中：mi为物流节点或其所在区域的“质量”，即物流节点的竞争力，这里选择物流节点规模、区位交通条件、技术作业水平及效率和所在区域的经济总量4个因素来确定物流节点综合竞争力

其中：si，qi，ei，gi分别为物流节点i的规模、区位交通条件、技术作业水平、所在区域的经济总量，Si，Qi，Ei，Gi分别为其归一化后的值；b1，b2，b3，b4为权重系数，b1＋b2＋b3＋b4＝1，可采用 AHP法确定.

dij为需求点j到物流节点i的广义费用，这里取运输里程、运输时间和运输费用3个主要因子构建路权函数，dij＝a1Lij＋a2Tij＋a3Fij＝其中：lij，tij，fij分别为需求点j到物流节点i的运输里程、运输时间、运输费用，Lij，Tij，Fij分别为其归一化后的值；a1，a2，a3为权重系数，a1＋a2＋a3＝1，可采用AHP法确定；

k为引力系数；θ为引力衰减指数，以［1，2］为宜.

同时，考虑到物流节点作业能力限制等条件，对物流节点服务范围划分可采用多次划分的方式，即当物流节点i饱和度大于1时，对需求点j到物流节点 的广义费用进行动态调整，进行动态划分.

3 物流节点布局优化

物流节点布局优化问题可描述为：在规划目标年负荷分布已知的情况下，以最小的投资和年物流运行费用为目标函数，确定物流节点的数量、位置、容量以及物流节点的服务范围.优化流程如下：首先，根据目标年物流总需求、已有物流节点供给容量以及候选物流节点规模与类型确定新建物流节点的最大个数nmax和最小个数nmin，利用整数规划技术得到新建物流节点的容量组合；在确定了新建节点的个数及容量组合之后，采用最大空心圆策略产生新建节点初始选址方案，基于加权Voronoi图和最大空心圆策略，结合模拟退火算法实现新建物流节点的选址、规模与布局的方案优化［10－12］.

3.1 确定初始方案

基于Voronoi图最大空心圆定位策略的基础上，给出根据已有节点及负荷分布情况产生新建物流节点初始选址的方法，具体步骤如下.

步骤1以已有物流节点位置为顶点，产生Voronoi图.

步骤2求出各节点对应的最大空心圆.

步骤3根据规划目标年负荷分布情况及负荷密度来确定阈值常数ε（ε是2个新建节点间距离的最小允许值），比较节点qi与qj（i≠j；j＝1，2，…，r）间的距离dij；若dij≤ε，再比较qi与qj对应的最大空心圆的半径，将半径较小的最大空心圆所对应的节点删去.

步骤4若新建节点个数为n，取半径较大的前n个最大空心圆所对应的节点作为新建节点初始选址.

3.2 方案分析及评价

评价函数如下

式中：Ccost为年物流成本；Si为第i个新规划物流节点的规模；f（Si）为第i个新规划物流节点的投资；u（Si）为第i个新规划物流节点的年运行费用；wij为第i个物流节点至第j个需求点之间的单位运输费用；lij为第i个物流节点至第j个需求点之间的运输距离；pij为第i个物流节点与第j个需求点间的需求量；r0为贴现率；α为折算系数.

3.3 方案优化步骤

结合加权Voronoi图与进化策略算法进行多物流节点选址与规模优化的具体步骤如下.

步骤1以已有节点选址和新建节点初始选址为顶点构造加权Voronoi图，初始权重取1.

步骤2在新建物流节点对应的V曲边形中，基于模拟退火算法以总物流费用最小为准则对新建节点选址及其规模进行优化.算法步骤如下.

（1）初始化.

（2）生成初始方案S，步骤如下.

①采用Voronoi规则确定各物流节点的位置.

②根据Voronoi规则划分的物流节点服务范围需求点的总需求作为节点的规模.

③反复进行②直到各物流节点前后两次迭代生成的规模相差不大时终止，输出初始方案.

（3）对k＝1，2，…，L做第（4）至第（7）步.

（4）生成一个新的解S′，步骤如下.

①任去掉一个规划节点，对其位置重新按照Voronoi图的原则选择最佳位置采用Voronoi规则确定物流节点的位置.

②根据Voronoi规则划分的物流节点服务范围需求点的总需求作为节点的规模.

③反复进行②直到各物流节点前后两次迭代生成的规模相差不大时终止，得到新的解S′.

（5）计算增量Δt＝C（S′）－C（S）.

（6）若Δt＜0则接受S′作为新的当前解，否则以概率exp（－Δt／T）接受S′作为新的当前解.

（7）若满足终止条件则输出当前解作为最优解，结束程序.终止条件取为连续若干个新解都没有被接受时或迭代次数达到预计次数时终止算法.

（8）T逐渐减少，且T趋于0，然后转第（2）步.

对于物流节点需求超过物流节点供给能力限制时采用惩罚函数法进行处理，对于在可行范围之外的方案进行惩罚.

步骤3再以优化得到的新建节点站址和已有节点站址构造加权Voronoi图，并计算各物流节点的需求量和负载强度.

步骤4如果新建节点选址变动距离和小于阈值，则结束迭代.

步骤5否则，返回步骤2.

4 实证分析

以区域物流节点布局优化为例进行实证分析，假设规划区域为640×360的矩形，规划区域内的每个方格作为一个物流需求点，假设其物流需求量是均匀分布的，各物流节点与需求点间的广义费用采用物流节点与各网格需求点间的欧式距离来表示。设已有物流节点为10个，其位置见表1，各节点规模服从［100，200］的均匀分布，由计算机随机生成，规划节点为40个。通过在Delphi和SQL Server2000平台下编写了多级物流节点布局优化系统，在实验过程中，根据调查情况调整系统参数。

表1 已有物流节点地理位置

1）假设规划物流节点的规模保持在100，不考虑规划节点规模优化，重力模型参数θ分别取1和2，现有节点的服务区域划分结果如图1所示，生成如图2所示的初始方案，其目标函数值为126 4762（θ取1）和179 575.5（θ取2）；优化参数为温度T＝100；Markov链长度取50，迭代次数为30次，温度衰减系数0.95，优化运行过程见图3.当20次迭代后趋于最优解，其目标函数值为1271 155（θ取1）和179 908.7（θ取2），最终解见图4.

图1 已有物流节点服务区域划分结果

图2 初始方案物流节点服务区域划分结果

2）考虑规划节点规模的优化，重力模型参数θ分别取1和2，则生成如图5所示的初始方案，其目标函数值为224 488.2（θ＝1）和227 459.3（θ＝2）；优化参数为温度T＝100；Markov链长度取50，迭代次数为30次，温度衰减系数0.95，优化运行过程见图6.当θ＝1时，4次迭代后趋于最优解，其目标函数值为266 022.3；当θ＝2时，12次迭代后趋于最优解，其目标函数值为261 239.7.

图3 规模保持不变情况下的优化过程图

图4 规模保持不变情况下迭代20次以后的优化方案

图5 加入规模优化后的初始方案物流节点服务区域划分结果

图6 加入规模优化后的优化过程图

通过上述优化实例可以看出：

1）与已有的定量划分方法相比，将GIS技术中的加权Voronoi图和引力模型相结合，可以实现由多个物流节点构成的区域物流系统动态服务范围的精确划分，可以通过多层区域物流体系反映不同等级物流节点服务范围的层次关系，对于区域物流系统空间服务范围的划分，可以基于不同物流节点的功能或者货种的竞争力、广义费用等因子，对其进行动态划分，此方法可用于任意复杂区域物流系统的动态服务范围划分，具有较强的实际价值.

2）当不考虑规模优化时，物流节点布局方案中节点布局较为均匀，层次性不明显；当考虑规模因素时，物流节点布局优化方案中的物流节点呈不均匀布置，物流节点的层次性较为明显.通过重力模型参数θ的取值不同，可以看出当θ取［1，2］时，θ的值越大，表明物流节点规模对其服务范围和布局优化的影响越大.通过不同参数条件下SA优化过程对比表明，Markov链越长，解质越好但计算时间越长；较小的温度衰减系数r可以明显加速算法的进程，但增加了算法陷入局部最优解的可能性.

3）在区域物流节点布局规划中，考虑到物流需求不是均匀分布的，可以对需求点对应的方格定义一个需求属性值来表达对应需求点的物流需求量，同时，考虑到物流节点的辐射范围受到节点到需求点广义费用的影响，在实际应用中可以在GIS系统中表达区域物流网络，分析各需求点到物流节点的实际运输距离、运输时间以及物流费用来综合表达各物流节点的引力模型，将更具有实际意义和应用价值.

5 结束语

对物流节点空间服务进行合理划分能促进物流节点及其服务范围内相关产业的和谐发展并带动区域经济的发展.基于GIS技术中的加权Voronoi图实现物流节点动态服务范围的划分，将加权Voronoi图与引力模型相结合，充分地考虑了影响物流节点服务范围的众多因素，实现了物流节点服务范围的精确划分；在此基础上，构建连续型物流节点协调布局优化模型，结合最大空心圆定位策略和模拟退火算法提出模型的高效求解算法，对解决连续型物流节点资源优化配置是一种尝试.从算例可以看出，本方法效率高，结果合理，特别是对于区域物流系统，该方法具有其特殊的优势.

［1］汤宇卿.城市流通空间研究［M］.北京：高等教育出版社，2002.

［2］邱慧芳，郝生跃.基于引力模型的配送中心服务范围研究［J］.物流技术，2010（2）：82－84.

［3］任冠星，王 转.需求势能理论在多级物流网络预选点中的应用［J］.物流技术，2005（12）：34－36.

［4］张得志，谢如鹤，李双艳.物流园区布局优化模型及其求解算法研究［J］.武汉理工大学学报：交通科学与工程版，2008，（6）：1 048－1 051.

［5］杨 勇.国内物流中心选址研究方法综述［J］.物流技术，2008（1）：34－36，43.

［6］黎青松，袁庆达，杜 文.一个结合库存策略的物流选址模型［J］.西南交通大学学报，2000，35（3）：315－318.

［7］梁 婷.区域物流中心分工布局规划［D］.长沙：中南大学交通运输工程学院，2007.

［8］秦 进，史 峰，缪立新，等.考虑随机需求和库存决策的多商品物流网络设计的优化模型与算法［J］.系统工程理论与实践，2009，29（4）：176－183.

［9］Kobayashi K，Sugihara K.Crystal voronoi diagram and its applications［J］.Future Generation Computer Systems，2002，18（5）：681－692.

［10］赵志辉，李 平，黄晓芹.加权Voronoi图的离散生成［J］.计算机应用与软件，2007，24（1）：12－16.

［11］丁鹏飞，王远飞.基于Relly法则与加权Voronoi图的连锁超市商圈分析［J］.上海商学院学报，2005，6（4）：135－139.

［12］葛少云，李 慧，刘 洪.基于加权Voronoi图的变电站优化规划［J］.电力系统自动化，2007，31（3）：29－34.