英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

公路路径选择的最小成本路径算法设计

摘要:公路线路设计是一个复杂的环境结构设计过程。地形和自然地理对象构成了公路建设的障碍。另一方面，成本参数和环境保护是规划人员必须考虑的两个主要问题。因此，公路路线的优先次序应根据要求和期望来决定。在这一点上，最小成本路径算法(LCPA)使得研究公路路线的最小成本路径成为可能。这一成本可以分配为建设成本，如避免斜坡和沼泽地区或环境目标，例如保护森林和不破坏农田。当成本参数确定后，LCPA可以计算出从起点到终点的最小成本路径。在本研究中，采用经济、环境和混合方法对科尼亚市新的公路路线进行了调查。根据公路施工要求生成成本参数和相关表面，然后利用LCPA计算出三条不同的线路。生成了结果图，并对三种方法从环境及成本参数进行了比较。

关键词:最小成本路径算法，地理信息系统，选址，高速公路项目

介绍

高速公路规划在经济与环境方面有些矛盾。考虑到成本参数对森林示范区、改变水资源流向、建筑废弃物的污染、空气污染和噪声等因素可能会对环境和栖息地产生负面影响。另一方面，环境导向型公路项目由于坡高值和长度的增加而增加了成本。

由于公路工程对环境的负面影响，工程造价大幅度增加。在研究最适宜的高速公路路线时，必须考虑高速公路项目的环境和成本优先次序。以环境或成本为导向的公路项目可以用层次分析法(AHP)来定义。

层次分析法是多准则分析中提到最多的方法，是一个通用术语，指的是通过从不同数据集群中进行选择来确定最适合实际问题的解决方案的应用程序(Arentze和Timmermans，2000)。为了确定最合适的公路位置，层次分析法包括灵活、有效和可调整的结构，以提供用户定义的解决方案。因此，可以调整、评估和测量环境和成本导向方法的结果(Kara和Usul，2012)。

除层次分析法外，利用最小成本路径分析(LCPA)算法确定高速公路的路径选择。LCPA为用户提供了一条最便宜的路线，该路线通过考虑多种标准确定的成本面连接两个地点（Hassan和Effat，2013）。成本面可以通过地理信息系统(GIS)生成，成本准则可以通过层次分析法进行评价和加权。有关LCPA的一些研究涉及选择坡度最小的最快路径（Stefanakis和Kavouras，1995），在目的地和起点之间选择三个备选方案（Hassan和Effat，2013），确定北极全天候道路（Atkinson等人，2005）、从多个目的地和起点出发的最佳路线（Lee和Stucky，1998）、基于多标准的成本曲面（Collishonn和Onber，2000）和（Douglas，1994）。

研究表明，应采用层次分析法和生命周期分析法相结合的方法确定合适的公路位置和路线，以获得实际的解决方案。虽然层次分析法确定了最合适的位置，但LCPA根据层次分析法计算的参数权重确定了路线。层次分析法为生命周期评价提供了环境、经济、社会等成本面，因此，可以根据所需的面向参数的方法，用生命周期评价法确定路径。

在本研究中，利用层次分析法确定了最适宜的高速公路位置，并根据环境、经济和层次分析法(环境与成本参数相结合的层次分析法)确定了需要新建高速公路的3条线路。

2. 材料和方法

2.1 研究区域

科尼亚市位于土耳其中部，面积40814平方公里，是土耳其最大的城市，有31个区(图1)。根据2014年的人口普查(URL1)，科尼亚市的人口为2.108.808。大量的人口住在城市中心，人口以6%的趋势在迅速增加。

2.2 最小成本路径算法

在实际应用中，大多数路由方法都是基于最小成本算法。链接成本是在每对节点之间的两个方向上定义的。针对分组交换网络，提出了几种最小成本路径算法。特别是Dijkstra算法和Bellman-Ford算法，是最有效和应用最广泛的算法(Nader，2006)。

2.3 Dijkstra算法

Dijkstra算法是一种集中的路由算法，它在一个中心位置维护信息。目标是找到从指定源节点到所有其他节点的最小成本路径。该算法通过多次迭代优化成本，确定从源节点到目标节点的最小成本路径。Dijkstra算法如下:(Rees，2004)，

1、为目标单元格匹配一个明确的零成本。

2、识别目标单元的所有邻近单元格，并将它们放入“活动”单元格列表中，对于每一个单元格，计算并分配到达目标单元格的成本，并分配一个指向目标单元格的指针；

3、找到列表中的成本最低的单元格，将该单元格命名为C，成本为k；

4.确定C的所有相邻单元格为S。对于S中的每个单元格Crsquo;，计算移动到C的成本l。

4.1如果C不包含在列表中，使用成本k l和指向C的指针将其添加到列表中。

4.2如果C已经是列表中的成员，那么将k l的值与这个单元格的临时成本进行比较。如果k l大于或等于临时成本，则什么也不做。但是，如果k l小于临时成本，则更改单元格C的属性，使其成本现在是k l，并且其指针现在是指向单元格C。

5.将单元格C的属性从临时更改为确定，并将其从列表中删除。

6.重复从(3)到列表为空(Rees，2004)，（Dijkstra，1959)。

2.4 成本距离是如何工作的(ArcGIS例子)

在一个节点和下一个节点之间移动的成本取决于节点的空间方向。单元格的连接方式也会影响移动的成本(URL2)。拓扑结构在成本计算中很重要。当从一个单元移动到它的四个直接连接的相邻单元之一时，成本可以计算为；

a1=(cost1 cost2)/2

地点:

成本1，单元格1的成本

成本2，单元格2的成本

a1，从单元1到单元2连接的总成本

累计成本可由下式确定：

累计成本=a1 (成本2 成本3)/2

地点:

成本2，单元格2的成本

成本3，单元格3的成本

a2，从单元2移动到单元3的成本

累计成本：从单元格1移入单元格3的累计成本

如果移动是对角的，则可以计算通过链接的成本;(1.41421=)；

a1=1.414214(成本3 成本2)/2

在确定对角移动的累计成本时，必须使用以下公式

累计成本=a1 1.414214(成本2 成本3)/2

使用图论创建成本距离光栅可以看作是识别成本最低的单元的一种尝试。这是一个从源单元开始的迭代过程。每个单元格的目标是快速分配到输出成本距离光栅(URL2)。

在第一次迭代中，源单元被标识并分配O，因为没有累计成本可返回给自己。接下来，激活所有源单元的邻居，并使用上面的累积成本公式将成本分配给源单元节点和邻近单元节点之间的链接。要分配给输出光栅，单元格必须具有指向源的下一个最低成本路径（URL2）。

累计成本值排列在从最低累计成本到最高累计成本的列表中（图6）。

从活动累计成本单元格列表中选择最低成本单元格，并将该单元位置的值指定给输出成本距离光栅。活动单元格的列表扩展到包括所选单元格的邻居。因为这些单元格现在有一种到达源的方式。只有那些可能到达源的单元格才能在列表中处于活动状态。移入这些单元格的成本是使用累计成本公式（URL2）计算的。

同样，选择列表中成本最低的的活动单元后，扩展邻域，计算新成本，并将新的成本单元添加到活动列表中。不需要连接源单元格。所有断开连接的源对活动列表的贡献相同，只有累积成本最低的单元格被选中并展开，而不管它将分配到哪个源(URL2)。

这个分配过程将继续。此外，如果通过将新的单元位置添加到输出光栅（URL2）创建新的、更便宜的路线，则会更新活动列表中的单元。

虽然输出成本距离栅格标识每个单元返回到最近的源位置的累计成本，但它不显示返回到哪个源单元，也不显示如何到达那里。成本回收链接过程返回一个方向栅格作为输出，基本上是提供路线图的内容，该路线图标识从任何单元格获取的路线，沿着成本最低的路径，返回最近的源（URL3）。

计算反向链接光栅的算法为每个单元分配一个代码。代码是从0到8的整数序列。值0用于表示源位置，因为它们本质上已经达到了目标(源)。值1到8以从右边开始顺时针方向编码。下面是应用于方向输出的默认符号，并伴有一个与颜色符号的方向箭头匹配的箭头图3(URL):

2.5层次分析法的应用

标准的选择反映了公路建设的要求、期望和限制。公路工程的主要标准可分为环境标准和经济标准两大类。每项标准都将采用层次分析法进行加权，根据所定义的评分来确定最适宜的公路路线。根据经济标准评估，公路路线应位于相当平坦的土地上，以避免挖掘成本。高度准则与坡度准则有关，考虑到气候条件，定义了公路路线的特征。如果公路高度较高，冬季的感知、雪、风、冰等气候条件会对公路产生不利影响。高度也增加了挖掘成本和公路路线的坡度。这意味着燃油消耗增加，特别是对运输车辆。

环境标准对于公路线路保护环境和栖息地至关重要。公路建设会破坏森林和肥沃的农田。此外，由于车辆流量、声音、废气排放和相关的空气污染物，动物的栖息地和迁徙路线也可能受到破坏。首先，必须表明项目目标的目的，即优先保护环境或成本。层次分析法可以很容易地用成对比较矩阵来定义这种区别（Saaty，1977）。Saaty（1977，1980）概述的程序将每个标准的重要性从1到9进行了比较。

定义了主准则、准则和子准则的成对比较平方方阵来确定权重。比较矩阵的对角线元素是1。将比较矩阵的每个元素除以各自列和的和，生成公式1的归一化矩阵。

归一化矩阵和的每一列等于1，然后，将归一化矩阵的每一行和除以矩阵顺序。和的平均值表示成对比较矩阵（公式2）中每个标准的权重。

必须计算成对比较矩阵的一致性，才能确定标准比较是否一致。综合所分配的偏好值，以确定相关因素的排名，其数值相当于每个参数的权重。因此，计算了揭示数据矩阵模式重要细节的平方对比比较矩阵的特征值和特征向量。认为只计算最大特征值产生的特征向量就足够了，因为该特征向量包含了足够的信息以考虑参数的相对优先级的（Saattyamp;Vargas，1991）。

一致性指标(CI)是确定成对比较矩阵一致性系数的方法之一。CI采用公式3计算(Saaty，1994)。

计算一致性指数取决于ʎ最大值（本征值）与公式4（Saaty，1994）。

此外，必须计算随机指数(RI)值来确定一致性指数。对于每个矩阵顺序，RI值如表1所示。

表1根据矩阵顺序的RI值

计算CI和RI后，一致性比(CR)可由公式5计算。如果CR超过0.1。基于专家的知识和经验，Saattyamp;Vargas(1991)建议修订具有不同值的成对比较矩阵。(Saaty，1980)。

选择公路路线时应考虑几个标准。本研究在环境和经济两个主要标准中考虑了7个标准。影响公路项目成本的主要经济指标包括坡度、距公路的距离、高度和人口标准。与定居点的距离、土地利用和地质标准与环境有关(图11)。

根据图11所示的定义的类别，对每个标准进行映射，然后用ArcGIS软件重新分类。这些被定义为子标准和AHP权重。对第一阶段的主要准则、准则和子准则进行计算，用表3、4给成对比较矩阵对环境和经济主要标准进行了加权。

表2主要标准重量

A=公路适宜性，C1=环境，C2=经济，CR=0.0000，W=C1和C2的权重

主标准权重计算为C1为0，40，C2为0，60(表2)。因此，对于这个研究来说，经济标准比环境标准更重要。

在第二阶段，根据主准则分别计算准则权重。所有比较的CR值均小于0.10，说明权重的使用是合适的(表3，4)。

表3经济的标准重量

B1=经济标准，C3=斜率，C4=高度，C5=地质，CR=0.0009，W=C3，C4和C5的重量

表4环境标准的重量

B2=环境标准，C6=土地，C7=人口，C8=居民点距离

C9=高速公路距离，W=C6、C7、C8和C9的重量

2.6最小成本路径算法的应用

利用空间分析扩展技术，利用ArcGIS软件生成最小代价路径算法。总共使用LCPA计算了3条路线，利用AHP确定了最需要的高速公路位置（图12）。确定了三个成本面，LCPA计算出从原点到终点的最小成本路径。通过对区内现有公路交叉口的计算，确定了交叉口的起点和终点。

成本最低的路径分别由为经济、环境和AHP计算确定。使用AHP确定的权重(表2、3、4)生成成本曲面。成本表计算如下，

经济成本面=[(0.49981坡度) (0.25804高度) (0.24215地质)]

环境成本面=[(0.40156土地利用) (0.24719人口) (0.18646距离部落的距离) (距离公路的距离0.16479)

AHP成本面=[(0.30坡度) (0.1548高度) (0.145地质) (0.1606土地利用) (0.0988人口) (0.074距离部落的距离) (0.0658距离公路的距离)

决定最合适的路径需要根据长度、坡度、土地利用和人口对路径进行比较。层次分析法路线可以称为混合路线，因为它将经济标准和环境标准结合在一起。层次分析法路线按60%经济标准和40%环境标准计算。根据目标，这些权重可以根据成本或环境导向的公路建设等要求进行调整。图12给出了层次分析法、面向经济和环境导向的成本面。

起点和终点的定义考虑了现有公路和连接各地区的公路交叉口。必须生成反向链接光栅才能计算出最小成本路径。反向链接栅格通过考虑原点和终点，包括栅格单元之间的方向。栅格如图13所示。

确定的合适位置用于为面向经济、环境和层次分析法的方法生成LCPA路径（图14）。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[609764]，资料为PDF文档或Word文档，PDF文档可免费转换为Word