European Journal of Operational Research 248 (2016) 415–427
Contents lists available at ScienceDirect
European Journal of Operational Research
journal homepage: www.elsevier.com/locate/ejor
Discrete Optimization
Multiple-path selection for new highway alignments using discrete algorithms
Yasha Pushak a, Warren Hareb, Yves Lucetc,lowast;
a ASC 303, Computer Science, Unit 5 Arts amp; Sciences, UBC Okanagan, 3187 University Way, Kelowna BC V1V 1V7, Canada
b ASC 353, Mathematics, Unit 5 Arts amp; Sciences, UBC Okanagan, 3187 University Way, Kelowna BC V1V 1V7, Canada
c ASC 350, Computer Science, Unit 5 Arts amp; Sciences, UBC Okanagan, 3187 University Way, Kelowna BC V1V 1V7, Canada
a r t i c l e i n f o a b s t r a c t
Article history:
Received 24 October 2014
Accepted 16 July 2015 Available online 22 July 2015
Keywords:
Horizontal alignment optimization Shortest path
Alowast; algorithm
k-shortest path
OR in road design (natural resources)
This paper addresses the problem of finding multiple near-optimal, spatially-dissimilar paths that can be considered as alternatives in the decision making process, for finding optimal corridors in which to construct a new road. We further consider combinations of techniques for reducing the costs associated with the com- putation and increasing the accuracy of the cost formulation. Numerical results for five algorithms to solve the dissimilar multipath problem show that a “bidirectional approach” yields the fastest running times and the most robust algorithm. Further modifications of the algorithms to reduce the running time were tested and it is shown that running time can be reduced by an average of 56 percent without compromising the quality of the results.
copy; 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
Introduction
In preliminary road design, selecting the best path for a new road is traditionally a long and political process. A variety of factors can require that road engineers design multiple alternative paths to be considered. Previous research has developed methods of modeling the roadrsquo;s costs as well as computing the optimal alignment (Trietsch, 1987b; Turner, 1978). While this software provides useful insight for road engineers, it does not satisfy the need to find multiple road path options for review. There is a need for an algorithm that can effi- ciently compute multiple near-optimal, but distinctly different, paths that can serve as alternatives to the cheapest path.
This paper is concerned with the first step of the road design pro- cess: corridor selection. An initial path can then be refined, optimiz- ing the horizontal alignment within the corridor, using techniques from Mondal, Lucet, and Hare (2014), Hare, Koch, and Lucet (2011), Hare, Hossain, Lucet, and Rahman (2014a), Hare, Lucet, and Rahman (2014b), or citations therein.
To locate the initial corridor we model the terrain as a three dimensional grid of points to construct a spatial graph. Adapted forms of Dijkstrarsquo;s Algorithm are then used to select the set of spatially-dissimilar corridors, while minimizing an approximation of the earthwork and pavement costs. Additional techniques to reduce
lowast; Corresponding author. Tel.: 1 250 8079 505.
E-mail address: yves.lucet@ubc.ca (Y. Lucet).
the running time have also been developed. These include an adapted form of the Alowast; algorithm and two methods of imposing height restric- tions, to avoid spending time searching for unrealistic roads that are far from the ground.
-
- Road design
Previous work on road alignment selection has developed a num- ber of discrete models. The simplest and most common is a regular grid (Turner, 1978), where the center of each grid cell is given a vertex and then edges are defined by the vertices of the eight adjacent grid cells. This model restricts possible road trajectories to having eight directions. Another method, presented by Trietsch (1987b), Trietsch (1987a), used a honey-comb grid, which allows for angles in multi- ples of 30 degree. In many previous discrete models the space be- tween each adjacent vertex was as small as 200 meters and up to 2 kilometers (Trietsch, 1987a; 1987b; Turner, 1978), which does not allow for detailed and accurate assessment of costs in a given region of a cell. Many models also formulated the construction costs inde- pendently of the roadrsquo;s direction (Turner, 1978).
On the horizontal alignment problem, Huber and Church (1985) took an in-depth look at minimizing the errors in the cost evaluation associated with path planning problems, such as road design, by in- creasing the number of possible directions of movement. Later, Lee, Tsou, and Liu (2009) applie
利用离散算法对高速公路进行多路径选择
关键词：水平对齐优化最短路径，离散算法，渐次短路线，道路设计(自然资源)
摘要：本文探讨了在决策过程中寻找多个近似最优的、空间不同的路径，以寻找最优的路径，从而构建一条新的道路。我们进一步考虑了降低成本的技术组合，提高了成本制定的准确性。用五种算法求解不相似多路径问题的数值结果表明，“双向方法”是最快的运行时间和最健壮的算法。对算法进行进一步的修改，以减少运行时间，并显示运行时间可以平均减少56%，而不会影响结果的质量。
背景介绍
在初步的道路设计中，选择一条新路的最佳路径传统上是一个漫长的政治过程。各种各样的因素可以要求道路工程师设计多种可供选择的道路。以前的研究已经开发了道路成本的建模方法以及计算最优校准的方法。虽然该软件为道路工程师提供了有用的洞察力，但它并不满足需要找到多个道路路径选择来进行审查。需要一种算法，它可以有效地计算多个近乎最优的、但明显不同的路径，可以作为最便宜路径的替代。
本文主要研究道路设计的第一步:通道选择。最初的路径可以被细化，优化在走廊内的水平排列，使用来自Mondal、Lucet和Hare(2014)、Hare、Koch和Lucet(2011)、Hare、Hossain、Lucet和Rahman (2014a)、Hare、Lucet和Rahman (2014b)的技术，或者其中的引用。
为了确定初始通道的位置，我们将地形建模为三维网格点来构造空间图。然后使用Dijkstra算法的适应形式来选择一组空间不相似的走廊，同时最小化对土方和路面成本的近似。还开发了减少运行时间的其他技术。包括一种适应形式的lowast;算法和两种方法的高度限制一下,,避免花时间寻找不切实际的道路远离地面。
1.1道路设计
以往的道路对齐选择工作已经发展出了一种离散模型。最简单和最常见的是一个规则网格(Turner, 1978)，其中每个网格单元的中心都被给定一个顶点，然后边缘由八个相邻网格单元的顶点定义。这个模型限制了可能的道路轨迹有八个方向。另一种方法是Trietsch (1987b)， Trietsch (1987a)，使用了一个honey-comb网格，它允许在30度的多元组中形成角。在许多以前的离散模型中，每个相邻的顶点之间的空间大小为200米，最高达2公里(Trietsch, 1987a;1987 b;特纳，1978)，不允许详细和准确地评估一个特定区域内的成本。许多模型还对道路的方向(Turner, 1978)进行了详细的阐述。
在水平对齐的问题上，Huber和Church(1985)深入研究了与路径规划问题相关的成本评估中的错误，例如道路设计，通过将可能的运动方向的数量增加。之后，Lee, Tsou，和Liu(2009)将邻域搜索技术应用于ap-近似水平对齐，并采用分段线性曲线。一旦他们选择了水平对齐，他们就将其细化为一条平滑的路径，以达到像曲率限制这样的道路标准。Easa和mehmood(2008)使用了不同道路类型的碰撞频率数据。提高水平对齐的安全性。Kang, Schonfeld和jong(2007)改进了现有的水平对齐优化。为了模型通过限制搜索空间和可行的大门。Kang(2008)使用遗传算法选择与现有公路网相交的新公路。提出了一种双级ap- proach方法，该方法首先选择了具有媒介作用解决方案的候选路径，然后对其进行评估。
交通流优化通过遗传算法解决了道路设计问题。进一步的工作是整合地理信息系统，包括土地边界成本、环境影响、地形、旅行时间和城市附近高速公路的噪音和空气污染。Jha、Schonfeld、Jong和Kim回顾了成本制定以及公共道路设计优化算法。继续这项工作采用遗传算法寻找替代路线，Bosurgi等人使用粒子群操作考虑了环境约束。他们还增加了新的曲线类型，并提供了一种遗传算法来降低参数(Bosurgi, Pellegrino amp; Sollazzo, 2014)。Shafahi和Bagherian提出了一个定制的粒子群优化算法(Shafahi amp; Bagherian, 2013)，而另一个由进化算法解决的三维高速公路校准模型由Jong和Schonfeld(2003)考虑。值得一提的是郑大世的博士论文(Jong, 1998)。针对道路设计问题，提出了用户界面设计方案。Church、Loban和Lombard(1992)设计了一个使用多目标模型的方法，以便找到最佳和可选的路径。
许多以前的道路设计优化方法都是用在寻找单一路径或走廊上。在实践中，道路设计是一个政治过程，在这个过程中，不可能提前确定和消除所有的环境和政治成本因素。这篇论文的重点是寻找一个由工程师、政治家和/或环保人士组成的董事会，以获得额外的成本和影响，而不是用一个多目标的模型来确定成本和约束的不完整的集合。
1.2 k-最短路径算法
在网络中找到k-最短路径的问题已经做了大量的研究(Brander amp; Sinclair, 1995;o艾普斯坦,1998;霍夫曼amp; Pavley,1959;Lawler,1972;日元,1971)。通常有两种不同的方法:删除算法(Brander amp; Sinclair, 1995;Lawler,1972;日元，1971)和偏差算法。删除算法建议使用传统的路径查找算法，如Dijkstra算法，以找到最优路径。从图中依次删除了最优路径的边缘，并重新运行寻路算法生成一组二级路径。其中最便宜的被选中，流程迭代。
偏差算法利用由最短路径树生成的信息到目的地，利用k-最短路径的频繁位置(Eppstein, 1998;霍夫曼amp; Pavley,1959)。它们以最便宜的路径开始，然后搜索提供最小增长成本的偏差。虽然k-最短路径的特性使它们能够获得最具竞争力的时间复杂度，但它也提供了关于为什么它，以及任何传统的k-最短路径算法都不适合适应于空间不同的多路径问题的见解。
在应用于多路径道路设计问题时，算法的两个家庭都表现得很差，这对应于一种应用于稠密空间图1的k-最短路径问题，该问题与寻找空间上不同的路径的复杂性有关。作为一个学术的例子，考虑在统一成本网格上的k级最短路径算法的行为(松散的ap-近似于一个平坦的大草原)。全局最优路径是图1所示的直线p1。路径p2、p3和p4的价格都是一样的，所以它们中的任何一个都可能是第二个路径，这取决于算法如何断开连接。在这三个选项中，p4是最理想的，因为它与p1最不同。然而，当使用一个精细化的网格时，p4仍然几乎与p1相同，因此这些路径都不应该被认为是可接受的候选替代路径到p1。
将这些算法应用于多路径道路设计问题的最简单方法是迭代生成路径，直到找到满足空间不同标准的k路径。由于早期的这一方法将是空间相似的路径，因此在找到合适的替代路线之前，该方法必须进行相当广泛的迭代。因此，这种方法在实践中表现不佳。在公路网络中运输有害物质的文本中经常提出不同的路径问题(Dell #39;Olmo, Gentili amp; Scozzari, 2005;约翰逊，乔伊，克拉克，和雅可比，1992;Kang, Batt amp; Kwon, 2014)。不同的多路径问题的目标是在源和目标之间找到一组空间上不同的路径。为了解决这个问题，已经采用了各种不同的不同指标。对于两条给定的路径，它们中的许多定义了路径的共享长度和路径的非共享长度之间的关系。该方法适用于危险品(危险品)目标函数，其依据是风险价值而非运输成本。它产生的局部最小值在空间上是多种多样的。与标准的k-最短路径算法相比，不同的路径算法更适合于寻找道路设计的备选路径。然而，在道路设计的背景下。该方法将找到如图1所示的p4路径。这些路径将共享最小长度，但由于道路设计网格的密集性，将在空间上非常相似。实际上，最小化路径的共享长度最适合于现有的高速公路网络，其中的备选路径由不同的公路选项组成。Dell #39;Olmo et al.(2005)，也在HazMat运输的背景下，通过定义在每条路径周围的区域缓冲区，并计算由重叠区域确定的一个指数，对之前的不同指标进行了有趣的修改。这种方法在危险品运输中特别有用，因为缓冲区可以被计算为受事故影响的预期区域。
Marti、Campos、Resende和Duarte(2015)、Marti、Velarde和Duarte(2009)使用的另一个指标是一个可能的选项，它可以为道路设计提供有意义的备选路径。Marti使用的距离度量计算从p1到p2的每个顶点的最短距离的平均值，反之亦然。每条路径的平均距离通过各自路径的长度进行标准化，然后将两条路径的平均值作为不同的索引。
虽然前两种方法都有可能为道路设计提供有意义的备选路径，但我们选择了另一种不同的标准，类似于Lombard和Church(1993)的建议。他们用一种类似于计算两个曲线下面积的绝对差的方法来观察两个路径之间的区域差异。这一方法是从三种方法中选择出来的，因为它具有提供显著不同路径的潜力，同时需要最少的计算费用。文献中大多数不同的路径算法都使用了与路径共享长度相关的dis-相似性准则，许多方法只比较单一最便宜路径的替代路径，而不是相互比较。本文利用两个路径之间的面积差作为度量，以保证路径在空间上是不同的。这一类型的度量是用于道路标记模型的稠密图所需要的，因为它确保了在图1中所见的小偏差不被替代路径所接受。本文还对每条路径之间的面积进行了测量，以确保没有两种路径在空间上是相似的。
1.3不同路径的生成
几种不同的算法已经被用来为不同的不同标准生成路径。其中一个标准方法是迭代惩罚方法(Akgun等，2000;Johnson et al .,1992;鲁法尔，兰加比，埃尔德索基，和Smight, 1996)。Turner (1978) ap-在多路径道路设计问题上采用了一种类似的方法——将原路径边缘的权值压平。在4.2节中，我们采用空间密集图的方法来适应道路设计问题。Marti等(2015)，Marti et al.(2009)提出了一种基于路径关联的贪婪随机自适应搜索过程(抓取)问题。Jha(2003)利用遗传算法对道路设计问题进行求解，并将中间解决方案作为候选的alter- nate路径。后来，Kang et al. (2012)， Kang et al.(2010)利用遗传算法生成路径选择，设计与现有公路网相交的新公路。Yang et al.(2014)利用多目标模型和修改Ge- netic算法在此基础上构建。遗传算法也被Zhang和Armstrong(2005)用于多目标的走廊问题。我们没有研究遗传算法，也没有掌握，在这篇论文中，我们更倾向于阻止- ministic算法。未来的研究应该探索比较的方法和不确定性的方法，以及探索混合方法的可能性。Dell #39;Olmo et al.(2005)采用了一种不同的多目标回廊方法，找到了非主流路径的pareto-最优集合。尽管我们提出了不同的目标，但在第4.3节中我们提出了类似性质的al- gm。
一个常见的策略是生成一组大的候选路径，然后根据所选的不同crite- ria来减少这个集合。Kuby等人(1997)使用极小极大方法选择了路径的集合，该方法最大化了路径之间的最小分散性，这是一个众所周知的NP-hard问题(Duarte amp; Marti, 2007)。在HazMat运输(Kang et al.，2014)中，使用常规k-最短路径算法生成初始路径集。这适用于他们的问题，因为他们的目标函数主要是基于风险而不是旅行费用。这个目标函数，不像一个基于建筑成本的函数，通常会产生空间上不同的第k条最佳路径。
Church et al. (1992)， Lombard and Church(1993)引入了网关最短路径方法，作为一种生成一组空间上不同的候选路径的方法。我们在第4.4节中使用了类似的路径生成方法。最近的一种方法被Scaparra, Church和Medrano(2014)用一个多网关的shortest-path方法进行了测试。该算法显示了生成大量候选路径的承诺，但需要额外的时间，重新查询图中每个顶点的最短路径算法。考虑到道路设计网络中顶点的密度，这种方法将花费太长的时间来运行，并且会生成更多的路径，而不是选择合理的替代方案。
我们在第2节介绍了我们的道路设计模型，并讨论了两个高度限制，以减少2.4和2.5节的运行时间。第3节包含了我们的cor- ridors所需的不同约束。提出了五种不同的多路径算法，并讨论了它们的理论性能。在第5节中收集并总结了数值结果。第6节包含了一些关于进一步改进未来工作的结论和观点。
建立模型
2.1．2 d-omega;模型
为了实现精确的成本评估和现实路径，我们使用一个非常密集的网格，每个顶点大约有10米。然而，随着模型细节的增加，一个新的挑战出现了:在一个非常短的空间中，两个顶点之间的一个90度旋转(或更多)的对齐将不得不发生。这种突然的转弯通常会违反道路安全曲率的限制，使这些排列不可行。我们从内省开始，这是一条最尖锐的弯路，任何道路都可以用45度的角度。虽然这一限制可能足以应付一些紧急情况，例如伐木道路，连续两个45度转弯仍然会产生不安全的公路路线。然而，这种方法仍然足以产生一个初始的通道，在这个通道中，进一步的曲率约束可以在hori- zontal优化过程的微调过程中得到应用。
简单地存储当前方向并应用此限制将导致有限的最短路径问题。为了使用clas-sic最短路径算法,如Dijkstra算法的算法,我们创建一个新的基于增广2 d-omega;模型图的最短路径解决方案对应一个解决约束最短路径问题。Trietsch (1987b)采用六边形网格的方法将曲率约束应用于初始道路设计。增广图每个(x, y)点有8个顶点，每个顶点对应于一个传入的边缘方向，如图2所示。提取这些信息是考虑旅行的方向作为另一个轴,让这句话作为omega;h-axis,水平orienta,。每个方向可以分配一个坐
全文共23423字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15036]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
