当前世界环境

介绍

道路正在考虑成为国家的首都之一;目前已有一些关于低成本路由的研究。在有限的预算下尽可能多的设计。缩短道路的理想方法，是以最低的成本为基础的。成本可以包括环境成本、土地所有权成本、道路建设成本、道路使用者和维护成本，对成本参数的量化已经做了各种研究(Hatefi, 2006)。由于本研究的目的是设计基于代价参数的路由算法，本文列出了对结果进行分析的假设网络，并在给定的网络上实现了该算法。

过去研究的回顾

在该算法中发表的文章最多的是静态网络中最快的路由。具有固定拓扑结构和成本的网络，通过平均旅行时间固定是最好的。在本研究中，不同于传统的栅格GIS网络方法的使用。栅格GIS网络具有处理能力，网络分析较少为人所知。软件中有各种光栅分析功能。它开始于1736年，当时欧拉的著名问题提出了哥尼斯堡桥。问题是，在城市的某一点找到一条路之后，哥尼斯堡的七座桥中的每一座都是历史上值得注意的数学问题。1735年莱昂哈德·欧拉对它的否定解析奠定了图论的基础，预示了拓扑学的思想。

1979年，Pang & Dew列出了最快方法的算法列表(Husdal, 2000)。在1958年，已有222多种不同的路由算法被开发出来。他们有很好的研究，并对每一类算法进行了简要的描述，并对具体算法进行了比较。其中一些路由方法是具有特定代价通道的静态网络。

一些算法被开发出不同的数据结构，因此在1959年Dijkstra算法被发明(Dijkstra, 1959)。Dijkstra算法是由计算机科学家Edsger Dijkstra提出的一种图搜索算法，它解决了具有非负边路径代价的图的单源最短路径问题，产生了一棵最短路径树。该算法常用于路由和其他图算法的子程序。

对于图中给定的源顶点，算法找出该顶点与其他顶点之间成本最低的路径(即最短路径)。它也可以用来计算从单个顶点到单个目标顶点的最短路径的代价，一旦确定了到目标顶点的最短路径，就停止算法。例如，如果图中的顶点表示城市，边路径成本表示由直路连接的对城市之间的行驶距离，那么Dijkstra算法就可以用来找到一个城市与所有其他城市之间的最短路线。

1995年，为了改善锯齿形运动的覆盖范围，许和Lathrop(许等, 1995)。根据Xu和Lathrop非相邻单元的累计成本，每个单元x到y作为每个单元在x到y方向上的几何距离的总累计成本。McIlhagga引入了“成本固定距离”这个新词。

McIlhagga (McIlhagga, 1997)算法开发Ron Eastman方法。当您有多个目标时，将使用此算法。也就是说，如果找到所考虑路径中的所有目标，则该算法为代价最优水平。从最低成本路径的巧合来看，支柱观点也很有趣。这个想法是只基于网络最便宜的路线采取行动不是,这个想法是通过陡坡和连接成本,因此成本的这种想法陡坡上的路线知道超过成本的转嫁陡坡(Collischonnet al .,2000)。他们确定净成本的算法是成本-斜率函数。这个算法的输出不是一条直线上的山路和上山的圆山。

Barry使用的概念与Tomlin (Berry, 2000)的概念相似。他称这个算法为splash, splash算法创建8个相邻细胞的表面位移，用于其他任何地方。估计了8个可能步骤的累积距离和相对成本。该步骤在总成本到位移。然后从任何起点出发的最优路径作为指定水平面上最陡的滑道(山上的同一通道)。为了找到两个点之间的最优路径，Barry建议将两个点的累积成本相加。

Barry还发明了多点之间路由的概念。他把这种练习叫做累积步。点1到点2之间的路径计算，点2到点3之间的路径计算为路由。这个过程在整个过程中相互重复，尽管这种方法不是位于路径沿线区域的最佳选择，但它的优点是它们在路径上出现的顺序我们已经计算了所有可能的聚合步骤的级别组合并选择它们的最佳组合。这一概念可用于连续计算最优路线。

成本水平

根据成本水平的定义，每个单元显示对称和不对称的单元成本水平的成本传递的映射(Eastman, 1997)。

将一级转换为网络

在栅格GIS中定义了表面上的间隔，以便表面上特定属性的值可以变化。为了进行通信和处理，网络结构上的每个细胞都应视为一个节点。这些单元中每个节点单元的成本代表。这些值中的每一个都被认为是权重单元有一个最小代价路径来找到它们。通过这些值的阻力或摩擦或困难的重量可以被认为是考虑的最成本区间。

计算从特定的目的地开始，并延伸到周围和相邻的每个单元，通过相邻的单元累计总成本计算，根据累计成本从每个单元到目的地的最小成本路径获得(Douglas, 1994)。该方法的缺点是最初交付的直线(水平或垂直)被定义在网络上，得到的路径将是曲折的路径。

求最短路径的a -星算法

决定每个单元格是否具有下列形式的特权的基本方程:

F = g + h (1)

其中G是基于Dijkstra算法的原点距离的函数，H估计每个单元到目的地的距离。对下游H的估计导致处理算法的进程减慢，以增加处理范围。如果H是对上游剩余路径的估计，其中一种方法就是曼哈顿距离。在严格基于水平和/或垂直路径(即沿着网格线)的网格中两点之间的距离，与对角线或“直线”距离相反。曼哈顿距离是水平分量和垂直分量的简单相加。该方法的缺点是与g参数的测量方法不太符合。

实现

路径效用参数

从用户的角度来看，两点之间的最优路径是一条直线。应用本研究的效用参数，每个细胞的起点和终点中心的总距离，乘以其获取成本，细胞将替代成本。这个方法也被认为是实用路径。例如，在图1中，两个点p和q具有相同的效用。因为p和q总共是7单位距离，p和q总共是10单位距离和14单位距离，成本和单位成本是5，所以两者都是效用70。

图1:path Parameter实用程序 点击这里查看图

如图2所示，每个cell的效用(U)乘以cell的所有权成本(C)。从起源cell (d1)到目的地cell (d2)的总距离可以得到:

G

G根据到原点单元的距离计算，Dijkstra算法计算如下:

根据(3)，g_我表示到单元格i, U的路径成本_我，表示第I单元格的效用为第I单元格，第j单元格的效用为距离d_ij

H的估计方法

首先，将每个单元作为源单元和目标单元的算法来计算成本。其次，基于Dijkstra算法计算目标到所选单元的成本。比较两种方法的第一和第二H至少是选择性的函数F被认为。

图2:研究示意图 提出算法的步骤 点击这里查看图

最短路径算法

如图2中的图表所示，在第一阶段为所有单元定义了成本函数。每个细胞的成本可以是定量的或定性的结果成本，所有这些都是一个已经计算和记录的小数字。然后计算函数F、G和H，确定结果。该算法是基于Dijkstra的算法，将一旦成本计算到目标单元和一旦单元目标成本之间的最小值作为参数H之间的值提供。图3显示了在给定数据上实现算法的各个阶段。

图3:实现的各个步骤 本文提出的算法是基于上述假设的 点击这里查看图

算法的实现和测试

为了实现这个算法，假设网络使用50 × 50，单元尺寸为1 × 1米。使用Python编程语言的过程。该算法的最终输出是一个函数F，其值表示通过起点和目的地之间的单元格路径的每个单元格的代价。图4比较了该算法实现结果所示的结果。如图4-c所示，建议的路径是根据用户视图的效用参数来确定的，即到中心的某条路径。

图4:对比的结果 提出的算法和可用的算法 点击这里查看图

讨论

新算法能够实现水平曲线的路径成本，因此，我们可以根据可用的预算设计最优路径，并尽可能地添加缓冲效用函数，即效用也可以看作是一个点。例如，如果某一特定团体或组织愿意在公路上投资，可以影响资金的数量，以缓冲新路线的设计。该算法可以被设置为回答，这可能是一组关于可用的可访问的资本数量的答案。该算法创建水平曲线路径成本的最大性能是在起点和终点之间。

建议

1. 多目的地源路由算法设计的算法开发
2. 将该算法与粒子群算法进行集成，并对其结果进行比较
3. 将该算法与遗传算法相结合，并对其结果进行比较
4. 研究长路径的简化算法

确认

本论文是基于马什哈德伊斯兰阿扎德大学马什哈德分校技术和职业培训学院支持的工作。本文提出的任何意见、调查结果、结论或建议都是作者的观点，并不一定反映伊斯兰阿扎德大学马什哈德分校技术和职业培训学院的观点。

参考文献

1. 基于GIS模型的地图分析。空间信息系统公司(2000)。
2. 王志强，王志强。基于最小代价路径算法的道路与运河优化设计。地理科学进展，29(4)，457 - 461(2000)。
3. 关于图的两个问题的注释。计算数学，1(1)，269-271(1959)。
4. GIS中使用累积成本面和坡度的最小成本路径。地图学:国际地理信息与可视化杂志，31(3)，37-51(1994)。
5. Eastman, R. Idrisi for Windows User 's Guide (Worcester, MA, USA: Clark University)(1997)。
6. 基于迭代过程和地理信息系统的寻径。马什哈德大学，伊朗(2006)。
7. 动态交通网络中最快速路径问题的研究。未出版，莱斯特大学地理信息系统理学硕士课程。(2000)。
8. 基于固定成本距离的多目标最优路径规划。未发表的论文，卡尔顿大学，渥太华，美国(1997)。
9. 基于栅格的地理信息系统中扩展现象的仿真。国际地理信息系统杂志，9(2)，153-168(1995)。