英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
目录
文献翻译
摘要：本文研究的问题是探索多种接近最佳的不同空间的路径，作为决策进程中可供考虑的方案，以此找到最优的走廊来建构一条新的道路。我们进一步考虑技术的组合用于降低成本与计算相关的成本并提高成本制定的精确度。用五种算法求解不相似多路径问题的数值结果表明，“双向方法”是最快的运行时间和最健壮的算法。进一步修改算法以减少运行时间已经过测验，结果表明在不保证结果质量的前提下，运行时间平均可以降低56%。
copy;2015年，本文由爱思唯尔有限责任公司（Elsevier.B.V）及国际运筹学协会(IRORS)的欧洲运筹协会(EURO)发布，并保留所有权利。
- 介绍
道路设计的早期准备中，为新建道路选择最佳路线在传统上是一项冗长的国家基础建设工作。多种因素会要求道路工程师需要设计多种路线方案作为备选考虑。早期研究已经开发了道路成本的建模方法以及计算最优校准的方法（Trietsch,1987b; Turner,1978）。虽然该软件为道路工程师提供了有用的洞察方法，但仍不能满足寻找多个道路路径方案来进行审查。需要一种算法，能够有效地计算出多个近乎最优的，但明显不同的路径，以作为最经济的路径替代方案。
本文主要研究道路设计过程中的第一步：走廊选择。最初的路径可以被细化，利用相关技术（来自Mondal、Lucet和Hare(2014), Hare, Koch, and Lucet(2011), Hare, Hossain, Lucet, and Rahman(2014a), Hare, Lucet, and Rahman(2014b) 或引用其他相关文献）来优化走廊的水平排列。
为了确定初始通道的位置，我们将地形建模为三维网格点来构造空间图然后使用Dijkstra算法的适应形式来选择一组空间不相似的走廊，同时使得土方和路面的估算成本值最小化。另外用于降低运行时间的技术也已经被开发。其中包括一种A*算法的适应形式以及两种加强高度限制的方法，以避免花费时间寻找那些不现实的路线方案。
-
- 道路设计
早期道路线形选择工作已经创建了多个离散模型。最简单且最普遍的是一个规则网格模型（Turner,1978）,其中每个网格单元的中心都被给定一个顶点，且边缘由八个相邻的网格单元的顶点定义。这个模型限制了可能的道路轨迹有八个方向。另一种方法是由Trietsch（1978a），Trietsch（1978b）所提出的，使用的是一种蜂巢形的网格，它允许在30度的多倍数值的角度。在许多以前的离散模型中，每个相邻的顶点之间的空间小到200米，最高可达2公里（Trietsch,1978a;1987b;Turner,1978）,不允许对一个单元的给定区域进行详细和精确的成本评估。许多模型还对道路方向的建造成本进行了独立地规（Trietsch, 1978a）。
在水平对齐的问题上，Huber和Church(1985)深入研究了如何降低与路径规划相关问题的成本评估中的错误，例如在路线设计问题中，可以采取增加运动的可能方向的数量的方法。之后，Lee, Tsou和Liu（2009）采取了一种邻域搜索技术，利用一个分段线性曲线使近似满足水平对齐。在一次测试中，他们选择了一段水平对齐方式，将其细化为平滑的路线以满足道路标准，例如曲率限制等。Easa and Mehmood (2008)使用了不同的道路类型的碰撞频率数据来提高水平对齐的安全性。Kang, Schonfeld, and Jong (2007)通过将搜索路径限制为可利用的进出方法，改进了现有的水平对齐优化模型(HAO) 。
Kang (2008) 使用遗传算法选择与现有高速公路网相交的新建高速公路路段。他们开发了一种双级的方法，首先利用遗传算法相对应的中间解来选择候选路径，然后对其进行流量优化评估(Kang, Jha, amp; Schonfeld, 2012; Kang, Yang, Schonfeld, amp; Jha, 2010)。
Jha (2003) 研究了遗传算法的道路设计问题。进一步的整合地理信息系统（GIS的工作已经完成，包括土地边界成本、环境影响、地形、通行时间以及城市附近高速公路的杂音和空气污染等(Jha amp; Kim, 2006; Jha amp; Schonfeld, 2004。Jha, Schonfeld, Jong, and Kim (2006) ,并且回顾了，成本制定以及公共道路设计优化算法。继续这项工作 (Yang, Kang, Schonfeld, amp; Jha, 2014)采用遗传算法寻找替代线路。 Bosurgi等人在考虑环境约束的条件下利用粒子操作 (Bosurgi, Pellegrino, amp; Sollazzo, 2013)。他们还补充提出了新类型的曲线，并提供遗传算法的方法以降低相关参数(Bosurgi, Pellegrino, amp; Sollazzo, 2014)。 Shafahi 和Bagherian 提出了一种自定义的粒子群优化算法 (Shafahi amp; Bagherian, 2013)。而Jong 和 Schonfeld (2003)考虑了另外一个由进化算法解决的三维高速公路校准模。还值得一提的是博士Jong的理论 (Jong, 1998)。
针对道路设计问题，提出了界面设计方案。Church, Loban,和 Lombard (1992)设计了一种使用多目标的模型，以便找到最佳和可替选的路径方案。
早期的许多道路设计最优方法侧重于寻找单一的路径或走廊。在实践中，道路设计属于国家建设，在这一过程中不可能提前确定和评估所有环境与政治成本的因素。本文的没有使用会造成一套不完整的成本与约束的多目标模型，而是关注于寻找成本上近乎相同，而在空间上不同的路径，并可以由一个委员会的工程师、政治家或环卫人员针对额外费用和影响进行审查。
-
- K -最短线路算法
关于在网络上K个最短路径的问题已经做了大量研究(Branderamp;Sinclair,1995;Eppstein,1998; Hoffman amp; Pavley, 1959; Lawler, 1972; Yen, 1971).通常有两种不同的方法：删除算法(Branderamp;Sinclair, 1995; Lawler, 1972; Yen, 1971)和偏差算法(Eppstein, 1998; Hoffman amp; Pavley, 1959)。删除算法建议使用传统的路径查找算法，如Dijkstra算法, 以找到最优路径。从图表中以此删除了最优路径的边缘并重新运行寻路算法生成一组二级路径。其中最经济的方案会被选择并重复这个流程。
偏差算法利用由最短路径树生成的信息到达目的地，从而探索出K-最短路径的频繁位置 (Eppstein, 1998; Hoffman amp; Pavley, 1959)。他们从最经济的路径开始，而后搜索能够提供最小增长成本的偏差值。虽然K-最短路径的特性使它能够获得最具竞争力的时间复杂度，但也提供了它独有的洞察力事实上任传统的k-最短路径算法都不适合解决空间不相似的多路径问题。
当将K-最短路径应用于一个密集的、具有寻找空间不相似路径的额外复杂性的空间图①中，算法的两族在解决多路径道路设计问题上都表现不佳。
图.1.一个统一的成本网格和四个可能的路径，描绘了一个K最短路径算法的预期行为。最经济的路径是p1，可能的路径中第二、第三、第四经济的路径依次是p2、p3、p4。
①我们称一个空间稠密图为，一种除边界外有26度的顶点的空间图。
作为一个学术的例考虑在同一个成本网格上的K最短路径算法的行为 (粗略地近似于平坦的大草原).全局最优路径将是图1所示的路径p1，而路径p2, p3, 与p4 可以认为是等价的，它们中的任何一个都可能被认为是第二个路径，这取决于算法如何打破联系。在这三个选项中，p4是最理想的，因为它于p1最不同。但是当使用一个精细化的网络时，p4几乎与p1相同，因而这些路径中没有哪一种路径能够被认为是可接受的作为p1的备选路径。
将这些算法应用到多路径道路设计问题的最简单的方法是迭代生成路径，直到找到满足空间不相似标准的K路径。由于这种方法早期阶段是在空间上相似的路径因此在找到合适的替代路径之前，该方法必须进行大量迭代。因此这种方法在实践中表现不佳。
相异路径问题在有关高速公路网络运输危险材料的论文中被广泛提及 (Dellrsquo;Olmo, Gentili,amp;Scozzari,2005;Johnson,Joy,Clarke,amp;Jacobi,1992;Kang,Batta,amp;Kwon,2014)。不相似多路径问题的目标是在源头与终点之间寻找一组空间不相似路径。各种各样的不相似指标已经被用于解决这个问题。对于两个给定的路径，它们中的许多定义了共享路径长度与非共享路径长度之间的关系 (Akguuml;n, Erkut, amp; Batta, 2000; Kang等人, 2014;
全文共28168字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13107]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
