一种基于阻抗等级划分的整体最优空间位置分配方法

郭文月，刘海砚，余岸竹，刘晨帆

（信息工程大学 地理空间信息学院，河南 郑州450001）

地理位置通常被视为影响服务设施运转效率的关键因素［1］，良好的地理位置有助于保证成本稳定低廉，提高设施点对需求点的吸引力。空间分析是依赖分析对象位置信息的技术［2－3］，空间位置分配根据地理实体的空间位置、空间关系和属性特征，结合用户需求，研究和确定空间对象的最优位置和资源分配，为用户提供辅助决策依据。位置分配的目的是以合适的方式定位设施点，从而保证最高效地满足需求，顾名思义，位置分配是定位设施点的同时将需求点分配给设施点的双重问题。

解算整体最优空间位置分配问题的方法主要有启发式 算 法［4－6］、蚁 群 算 法［7－8］等。这 些 算 法 从 不同角度考虑空间位置分配问题的影响因素，并以总成本最小为原则实现对整体最优空间位置分配问题的解算，但在解算效率、参数选取等方面仍可进一步改进。本文在解决整体最优空间位置分配问题时，将通过设施点和需求点间的网络元素所要消耗的成本整合为阻抗，用阻抗大小作为影响成本的因素，并在解算时引入等级划分的方法，提出基于阻抗等级划分的空间位置分配算法，有效提高解算效率。

1 整体最优位置分配及算法

整体最优空间位置分配问题是以指定区域内若干需求点与设施点间的整体成本最优作为求解标准，实现整体资源配置最佳化，旨在解决多条件、大范围、多数量的空间点位分配分析问题，用于设施点的宏观部署和整体利益优化。目前，常用于解决此类问题的算法——贪婪取走启发式算法，该算法需多次扫描比较数据集，在运算效率方面还有较大提升空间。

1．1 基于阻抗的整体最优位置分配表达

判断某一候选设施点的优劣时需要考虑的影响因素随用户需求的不同而不同，总体来说，用户希望尽可能减少从设施点到需求点的成本消耗，因而将通过设施点和需求点间的网络元素所要消耗的成本整合为阻抗，将其表示为

式中：i，j为需求点和设施点序号；Nj为设施点；x为需求点为设施点与需求点间可行路径长度；ωi为需求点权重；fij为设施点与需求点间单位路程运费。设施点对需求点的吸引力与两点间的阻抗成反比，阻抗值越大，表示该设施点对某需求点的吸引力越小。在可提供货物与服务的候选设施点以及消耗这些货物及服务的需求点已经给定的情况下，从候选设施点中选取用户指定数量的点作为设施定位点，并将需求点分配给选出的设施点，使得各个需求点与所分配到的设施点间阻抗总和最小。基于阻抗的整体最优空间位置分配问题表示

式中：m为需求点的数量；k为最终确定的设施点数量，且由用户指定；nk为分配到第j个设施点的需求点数量；δ为分配时允许的最大阻抗。整体最优空间位置分配问题是选择候选设施点集N的子集P，使得所有需求点到其分配设施点之间的阻抗总和最小。

1．2 贪婪取走启发式算法

贪婪取走启发式算法是解决上述整体最优空间位置分配问题的常用算法之一［5－7］，其解算步骤：

步骤1：假设设施定位点集合P＝N，即选中所有候选设施点；

步骤2：将各个需求点分配给与该需求点间阻抗最小的候选设施点；

步骤3：选择并取走一个候选设施点Nj，将其取走并将其对应的需求点，按照阻抗最小原则分配给其它候选设施点，总阻抗增加值最小；

步骤4：从P中删除点Nj，重复步骤3，直到剩余的候选设施点数目与用户需求相同。

贪婪取走启发式算法从候选设施点集合中逐一删除对最优整体阻抗值影响最小的候选设施点，直到剩余的候选设施点个数满足用户需求。这种算法保证了每次迭代时的整体阻抗值最小，有效实现设施点的选取，但该算法每排除一个候选设施点就需要至少一次扫描数据集，当候选设施点数目远远大于需求设施点数目时，该算法的解算效率明显过低。为提高整体最优空间位置分配问题的解算效率，本文在贪婪取走启发式算法基础上提出一种基于等级划分的解算方法。

2 空间位置分配方法

本文采用等级划分的方法，将候选设施点与需求点间的阻抗按照值相近的原则聚合为若干等级，在求解计算时，用阻抗等级替代阻抗值，这样的等级划分方法实现了在保证整体最优的前提下，较大程度地减少了空间位置分配问题求解的运算量。

2．1 阻抗等级划分

采取等差划分的方法，假设n个候选设施点与m个需求点间所有小于阻抗中断的阻抗值为｛d11，d12，…，dnm｝，找出其中的最大值dmax和最小值dmin，根据阻抗值大小和用户需要选择的设施点数目k，确定划分阻抗等级数目h，那么每个阻抗等级跨度

根据等级跨度，确定每个阻抗等级的分界值，最终将阻抗值划分为h个等间隔的区间：

根据这些区间，将阻抗值聚合为D1，D2，…，Dh个等级，在求解计算中用阻抗等级代替阻抗值。

2．2 求解算法

基于阻抗等级的空间位置分配的解算思路：首先，根据各候选设施点和需求点间的阻抗值大小，以及设施点的数目将阻抗值划分成若干阻抗等级。解算时，先将各个需求点分配给阻抗等级最低的候选设施点，再依次选择并取走对总阻抗等级影响最小的候选设施点，并将其分配到的需求点分配给其它候选设施点，直至候选设施点数目满足用户需求，具体解算步骤为

步骤1：设候选设施点集合 N＝｛N1，N2，Nj，…，Nn｝，其子集 P＝｛P1，P2，…，Pk｝为最终确定的设施点集合，设需求点集合为x＝｛x1，x2，xi，…，xm｝，为每个候选设施点创建一个需求点分配集合Xj，用以记录分配给该候选设施点的需求点位置和数目，初始Xj＝φ；

步骤2按照各候选设施点和需求点的阻抗值大小，将所有小于阻抗中断的阻抗值进行等级划分，聚合成h个阻抗等级，按照阻抗值从小到大依次为D1，D2，…，Dh，大于阻抗中断的阻抗等级表示为∞；

步骤3：标记所有D1级阻抗，将需求点分配给D1级阻抗对应的候选设施点，若D1级阻抗对应多个候选设施点，则其为比较真实的阻抗值，选择真实值最小的候选设施点，并更新候选设施点Nj的需求点分配集合Xj；

步骤4：排除所有需求点分配集合为空的候选设施点，判断选出的设施点数目是否满足用户需求，则进行步骤5，否则，除去候选设施点Nj，将分配集合Xj中的需求点分配给其它候选设施点，总阻抗等级增加最小，直到剩余的候选设施点数目满足用户需求；

步骤5：结束计算，最终确定的设施点为P1，P2，…，Pk，各需求点的分配情况用分配集合X1，X2Xk表示。

3 实验与结果分析

3．1 模拟数据验证

为验证本文提出算法的合理性和高效性，进行模拟实验。选取平面区域内任意分布的10个点作为候选设施点，同一区域内任意分布的10个点作为需求点，模拟从10个候选设施点中选出3个作为设施定位点，并将10个需求点依总阻抗最小原则分配给这3个设施定位点。在模拟实验中为10个需求点分别赋予权重值，使得10个点的权重相加为1，设单位里程平均运费为5。

10个候选设施点位置如表1所示，10个需求点位置及权重如表2所示，为充分验证等级划分对运算效率的影响，分别将阻抗值划分为3个等级（三分法）和6个等级（六分法），并与直接运用阻抗值进行计算的贪婪取走启发式算法在运算结果和效率上进行对比。

表1 候选设施点分布位置

表2 需求点位置及其权重

根据式（1）计算得到各个设施点与候选设施点间的阻抗值，划分阻抗等级。两次不同等级划分方式的模拟实验结果均选取N6，N8，N10作为最终的设施定位点，如表3所示，运算结果、运用位置与贪婪取走启发式算法进行解算的结果一致，由于基于等级划分的空间位置分配算法将相近阻抗值聚合为同一等级，并在实际运算中用阻抗等级代替阻抗值进行结算，因而在排除候选设施点的过程中，比较范围不再是整个候选设施点集，而是缩小到迭代当时最小阻抗等级对应的候选设施点范围，这样既保证了分配需求点时整体阻抗最小，又大大提高运算效率，在模拟数据情况下，三分法和六分法对数据集的扫描对比次数分别为基于阻抗值的贪婪取走启发式算法的92%和78%左右。当数据量较大时，选择合适的等级划分可以更大程度地提高运算效率。但并非等级划分越精细，则解算速度越快，实际划分等级数目，根据用户候选设施点数目和阻抗值来确定。

表3 空间位置分配结果

3．2 模型构建与应用

空间分析依赖于空间分析模型，建立空间分析模型的过程是综合分析处理和应用空间数据的有效手段，也是开发分析决策性GIS不可或缺的步骤［9－13］。为验证本文提出的空间位置分配算法的可用性，实验利用Arc GIS提供的可视化模型构建工具——Model Builder及编程语言构建空间位置分配分析模型。构建好的模型如图1所示，将基于阻抗等级划分的空间位置分配算法写入到“位置分配”模块，其余基础环节直接调用Arc Tool box工具。

图1 可视化建模模型结构

利用某地区道路网络数据和点数据，分别选取快递投送站和重要客户所在位置作为候选设施点和需求点。该地区按照行政区划可分为10个行政区域，模拟从248个快递投送站候选位置中选出10个作为设施定位点，并将208个重要客户分配到这10个设施点，由于需求点在10个行政区划范围内不均匀分布，选出的10个设施点与行政区划模糊对应，且这10个快递投送站到各自分配到的重要客户的阻抗总和最小。图2为空间位置分配前候选设施点与需求点的分布情况，图3为设施点的选取和需求点的分配结果，解决快递投送站和重要客户间基于阻抗的整体最优空间位置分配问题。

图2 需求点与候选设施点分布

为验证实验结果的准确性，将全区域分为若干小区域，如图4所示，每个小区域内包含且仅包含一个已选设施点、分配到的需求点、以及未选中的候选设施点若干。分别将各个区域中的需求点分配给阻抗中断内除已选中设施点之外的候选设施点，计算总阻抗值，结果如图5所示，在每个区域内，第一个值为已选设施点到各需求点的阻抗和，其余点为该区域内未被选取的候选设施点到各需求点的阻抗和，数值证明，每个区域内已选设施点到各个需求点的阻抗和均小于其它候选设施点到各需求点的阻抗和，因而通过实验选出的设施点满足全区域范围整体阻抗最小。

图3 空间位置分配结果

图4 设施点及分配的候选设施点

实验证明，利用Model Buil der构建基于阻抗等级的整体最优空间位置分配分析模型，此模型可以解决本文提出的算法应用问题。本文提出的利用阻抗等级划分的空间位置分配方法可应用于多种类型的空间位置分配问题中，用数值的等级代替数值进行解算的方法在保证阻抗最小化原则基础上，缩小比较区间，能够较大程度提高问题的解算效率。

4 结 论

本文探讨基于阻抗的整体最优空间位置分配问题，提出一种利用等级划分的空间位置分配求解算法，实现整体最优化空间位置分配分析。用阻抗等级代替阻抗值，与贪婪取走启发式算法相比，较大程度缩小对比区间，提高解算速度，实现优化服务点部署，并通过可视化建模的方式解决选址中的实际应用问题。但是以下问题需要深入研究：

1）如何根据用户需求和实际数据，更加合理的确定阻抗等级和聚合区间；

图5 各区域内候选设施点与需求点的阻抗和对比

2）本文在进行位置分配分析时，没有将阻抗中断之外的需求点分配，而在很多实际问题中，仍需要考虑这些需求点。

［1］ 李炼，余代俊，曾涛．困难地区大型工程预选址新方法探讨［J］．测绘工程，2014，23（1）：61－64．

［2］ 边馥苓，朱国宾，余洁．地理信息系统原理与方法［M］．北京：测绘出版社，1996：149－172．

［3］ 纪晓东，王双龙，汪其志．基于工作流的地质信息空间分析模型的设计与实现［J］．测绘工程，2010，19（3）：20－23．

［4］ 刘璇．基于GIS的物流配送中心选址方法的研究［D］．长沙：中南大学，2012．

［5］ Arya V，Garg N，Khandekar R et al．Local Search Heuristics for P－median and Facility Location Pr oblems［J］．SIA M Jour nal on co mputering，2004，33（3）：544－562．

［6］ 关怀庆，张毕西，欧江艳．贪婪取走启发式算法在离散网络选址中的研究［J］．系统科学学报，2010，18（3）：49－52．

［7］ Deneubourg J L，Gross S，Franks N，et al．The Dynamics of Collective sorting robot－like ants and ant－like robot［A］．Proceedings of the 1stConference on Si mulation of Adaptive Behavior［C］．1990：356－363．

［8］ 秦固．基于蚁群优化的多物流配送中心选址算法［J］．系统工程理论与实践，2006（4）：120－124．

［9］ 程满，梁虹，冯涛．基于空间问题建模概念过程的空间分析建模与实现［J］．计算机工程与设计，2007，28（6）：4042－4045．

［10］方芳，徐世武，万波．GIS空间分析建模技术研究进展［J］．测绘科学，2010，35（6）：137－138．

［11］左兴东．三维GIS的数据结构探讨［J］．测绘与空间地理信息，2014，37（7）：120－122．

［12］董孟秋，李景文，张紫萍．基于面向对象数据模型的地理实体距离度量关系分析方法［J］．测绘与空间地理信息，2014，37（5）：64－67．

［13］周国清，陈昆华，何素楠，等．来宾市岩溶塌陷的时空分布特征分析［J］．测绘与空间地理信息，2014，37（4）：3－7．