内容发布更新时间 : 2024/12/23 18:07:06星期一 下面是文章的全部内容请认真阅读。

出路径。

同理，分别裁剪其余要素。最终结果如下：

3、投影转换

将球面坐标转化为平面坐标的过程称为投影。投影坐标系的实质是平面坐标系统，地图单位通常为米。投影坐标系在二维平面中进行定义。与地理坐标系不同，在二维空间范围内，投影坐标系的长度、角度和面积恒定。投影坐标系始终基于地理坐标系，即：

“投影坐标系=地理坐标系+投影算法函数“。

本实验选择的投影坐标系统为：WGS_1984_UTM_Zone_49N。

（1）定义投影。查看数据框，原有数据中部分数据为地理坐标系GCS_WGS_1984，部分没有定义投影如消防站点。选择“ArcToolBox——Data Management Tools——Projection and Transformations——Define Projection”工具，将投影定义为地理坐标系GCS_WGS_1984。

同理，定义未定义投影的要素。

（2）投影转换。为了将不同坐标系统的数据转换到统一坐标系下，方便对数据进行处理与分析，选择“ArcToolbox——Data management tools——Projections and transfomations——Feature——Project”工具进行投影转换。以道路为例进行投影转换，同理，将其余数据进行投影转换。

4、创建栅格图层

将人口的密度数据作为选址模型的服务对象数据，需将人口的面要素转换以人口密度为属性的栅格。修改数据框单位为米，测量展示的人口数据最大长度，为5541米左右。考虑到启发式算法的数据量的复杂性，设置人口栅格的精度为100米，大概3025个栅格。

（1）矢量转栅格。选择“ArcToolBox——Conversion Tools——To Raster——Feature to Raster”工具转换人口数据。（转换人口数据前需指定投影坐标系[上步]）输入要素为人口，字段为人口密度density，像元大小为100。

输出栅格如下，将栅格另存为人口_栅格.img。

（2）计算人口每个栅格距离道路的欧氏距离。

选择“ArcToolBox——Spatial Analysis Tools——Distance——Euclidean Distance”工具。设置环境，设置处理范围为人口_栅格.img，绑定栅格为人口_栅格.img

输入道路要素

得出人口距离道路的栅格如下，另存为dis.img

（三）确定网点布局优化方案

顺丰快递企业服务网点的选址问题可以用p中值问题来描述，即选定p个设施的位置，使多数或平均性能最优（成本最小，如使总的运输距离最小、总的运输时间最少，或者使总运输费用最小等）。常用算法有近视算法(myopic algorithm) 、交换启发式算法、邻域搜索算法等启发式算法、Lagrangian 松弛算法、禁忌搜索算法、模拟退火算法、遗传算法、神经网络和蚁群算法等现代启发式方法。本文采用贪婪栅格算法和蚁群栅格算法。

1、贪婪取走算法选址

1.1 算法原理

首先介绍贪婪取走选址，贪婪取走算法的原理在于从待定点中每次取走一个点，使目标函数的值增量最小（这个目标函数值就是选址方案的成本）。

在贪婪取走式算法中首先要明确求解目标以及制定一个可行的贪婪准则，然后以当前基础为最优选择，而不考虑各种可能的整体情况，从初始状态一步一步往下搜索，直到找到满足该问题的目标值，该方法具有模型简单，需要进行方案的组合个数少，计算量小，节约时间，易于进行定性分析和定量研究等优点。这种方法具有一定的局 限性，它得出的答案很难保证是最优的，一般情况下只能得到满意的近似解。

1.2 算法描述

贪婪取走启发式算法步骤如下：

（1）初始化，令当前选中设施点P=M，即将所有个备选设施点都选中； （2）将每个需求点指派给与运输成本最小的一个候选设施点；

（3）选择并取走一个设施点，需要满足以下条件：假如将它取走并将它的需求点重新分配后，总平均费用增加量最小；

（4）从备选点中删去取走点，令P=P-1，然后转第（3）步；

（5）重复步骤（3）（4），直到P=i,其中i为所需选择的配送中心数量。

1.3 算法实现与改进

贪婪取走算法的实现本身并不难，我们将它实现为一个类（类名PM），并提供了接口。使用它的方法，只包括初始化传入数据，调用选址接口，得到选址结果。 以下是使用例子：

PM pm = new PM(this.density, this.road);//初始化对象 pm.pMedian(targetNum);//选址 this.result = pm.getResult();//返回结果

但是算法本身的时间复杂度过大。栅格数据的数据量过大将导致运行时间令人难以承受。为了保证算法的可行性，我们从两个方面来改进算法：

（一）减少候选的栅格：选址就是从一个比较大的候选栅格集中选择出很少量的目标栅格，在栅格选址中，候选栅格的数目和需求服务的栅格数目一样多，但是这样是没有必要的。我们假想在一个3X3小区域中存在一个目标栅格，这个栅格在区域中的任意位置，将会带来的误差最多不过1.4个栅格边长大小。（例子：利用日常的生活经验，供应点和它的最佳位置有100米的偏差，在实际中并不会带来成本的较大影响）所以，我们将候选的目标栅格选择为所有8领域的中心。如果数据的范围更大，可以考虑扩大领域的大小，如果栅格的尺度过大，可以考虑缩小领域的大小。

（二）改进算法的实现，利用动态规划，增加空间复杂度来降低时间复杂度：在最初的实现中，没有对代码进行优化，做了很多无谓的操作，导致时间复杂度较大。考虑到空间成本相对于时间成本较低，我们在程序初期预先计算了所有候选供应点和需求点间的目标函数值，并且进行预先排序，得到成本表。这样以后的每次操作，除了，更新成本表的操作都被