英语原文共 22 页

同时优化的进化模型三维公路线形

Jyh-CherngJong，PaulSchonfeldB，

南京市南京东路171号中技工程顾问有限公司土木水利工程研究中心。

台北，台湾，中华民国土木工程系，马里兰大学，大学公园，MD20742，美国

1998年11月20日收到；2000年12月31日收到修订版；2001年3月29日接受

摘要：

优化公路路线是一个非常复杂的工程问题。这些在设计过程中考虑的因素是非常复杂且相互关联的。虽然有几种数学模型开发出用于解决线形优化问题，其中大多数都强调横断面或纵断面，只会产生问题的次优解决方案。同时优化的模型在文献中很少使用三维对准，它们的能力非常有限。在这篇论文中，一种进化模型（一种模仿自然演化过程的搜索算法），用于求解开发了三维线形优化问题。它克服了现有模型的一些缺点。其中的成本部分和处罚是全面的。拟议的算法可以优化复杂，全面和不可微分的目标函数。该模型也可以利用详细的地理信息进行公路分析。得到的线形在任何地方都很平滑并且可以有向后弯曲（即“回旋”）以更好地适应地形和土地利用模式。一个数字举例说明了所提出的模型和求解算法的形能

1. 简介

基本的公路设计问题是找到连接两个给定的基于地形、土壤条件、社会经济因素和环境问题的基点，同时满足一系列设计和操作限制。由于这种问题的复杂形，传统的公路设计需要有经验的工程师重复评估多种选择，以确定最有希望的那个。由于替代品的数量加入两个高速公路终点是无限的，手动设计可能只是令人满意解决方案而不是近乎优化的设计。

这种线形优化问题在过去三十年引起了很多研究兴趣。数学模型应该帮助工程师加快设计过程并找到更好的解决方案。然而，文献中发现的大多数模型都致力于优化水平线形或者垂直线形。自从大多数公路成本部分横断面和纵断面高度相关以来，分别考虑横断面和纵断面模型只会次优化问题。

很少发现用于同时优化三维线性的模型。帕克（1977）开发了一个选择路线走廊的两阶段方法，受坡度约束。他感兴趣的区域首先被划分为平均区域，其平均高程被认为是分区中心的地面高程。然后通过该区域构建光滑的表面质心高度使得端点之间的任何横断面都会与之相交具有满足坡度约束的纵断面的表面。在第二阶段，分区中心区域形成网格网络。然后使用多路径程序来导出一组最佳最小化绝对残差的路线（可以视为土石方的衡量标准）成本。Parker的模型忽略了平曲线和竖曲线曲率约束以及任何成本除了土石方。

在GCARS系统中可以找到与Parker类似的方法（Turner和Miles，1971;特纳，1978年）。通过建立覆盖该区域的成本表面来初始化该系统出于兴趣。然后通过不同的线形组合获得每个区域中的总成本具有相对权重的成本要素。最终由成本形成网格网络矩阵和最短路径技术用于找到最佳路径。在考虑时各种成本组件，特纳的模型忽略了车辆运营成本，即使他们的30年以上的现值折扣可能占建筑成本的300％至1000％（OECD，1973年）。GCARS未提供设计限制（例如，曲率和坡度）。帕克和特纳的模型都采用两阶段方法来确定最佳路径（即，在横断面图之前确定纵断面图），这可能只会次优化问题。此外，由此产生的线形（或更确切地说，走廊）是分段线形而不是平滑的。最后，两个模型都是离散的并且它们线形必须通过分区中心，因此忽略了问题的大部分搜索空间。

动态编程（DP）也被用于优化三维线形。DP模型的基本结构将阶段设置为起点和终点之间的等间隔平面从顶视图看，垂直于连接两端的线段的点线形点。在每个阶段，状态是二维平面上的搜索网格。Hogan（1973）提出了一个DP模型，OPTLOC，被美国林务局用于优化道路路线和剖面。通常最初使用粗搜索网格。然后精确搜索网格上的连续迭代可用于选择任何预期的精度。尼科尔森等人（1976）采用类似的方法来优化路线位置。在第一个阶段，模型搜索相对粗糙的点网格以进行初步线形。然后采用离散变分微积分方法来细化线形，使得线形结果可能偏离网格点。

应用DP来优化三维线性具有若干缺点。它难以处理回旋路线（即，其中高速公路偶尔会从最终的目的地转过90°以上）。其次，由此产生线形非常粗糙，处理平曲线和竖曲线很困难明确表达。第三，DP模型意味着阶段之间的链接成本是相加的，并且独立，这在公路设计中通常是不真实的。最后，存储要求可能会受到阻碍这种方法从开始时搜索更精细的网格。

最成功的三维模型大概是由Chew等人开发的（1989年）。它的线形由一系列三次样条函数参数化，问题最初表述为变异问题的微积分。然后将约束进一步转化为通过约束转录方法用于最优控制的一维约束理论。最后，该模型成为一个受约束的非线形编程结构样条函数的系数向量作为其决策变量。采用的解算法是准牛顿下降算法。可变缩放也被认为可以改善收敛表现。

与最短路径和DP方法相比，他们的方法的一个优点是结果线形到处都很平滑。另一个优点是该模型考虑了坡度和曲率约束明确。但是，水平曲率约束的制定他们的模型意味着非回旋线形，这在山区可能效率低下。他们的例子中唯一的成本部分是土石方成本和路面成本。该假设后者在感兴趣的区域内是恒定的，因此线形地依赖于总线形长度。其他费用，例如通行权，驾驶和旅行时间费用不考虑。很难将不平等的成本（例如，通行权成本）纳入其中不同的地块）进入该模型，因为它需要一个可区分的目标函数。此外，只有一个区域优化是被保证的。在实践中，基于不同的初始解决方案人类判断用于运行模型。但是，选择一个好的初始解决方案是非常具有挑战形，因为综合线形优化问题通常有很多局部最佳，特别是对于不规则地形。

在本文中，我们提出了一种不同的方法来同时优化三维-线形。所提出的模型旨在克服现有的一些缺陷楷模。该模型所需的功能包括（1）考虑各种成本要素，（2）满足重要约束条件，（3）产生实际线形，（4）处理回旋线形，以及（5）有效地找到合理的解决方案。因为我们寻求发展综合模型，由此产生的问题具有约束，非线形和非差异形通过诸如经典优化技术无法有效解决的可靠结构例如基于梯度的搜索方法。因此，我们开发了一个经过修改的进化程序从经典遗传算法（GA）来执行搜索。这里介绍的工作是摘自Jong（1998），详细讨论了所提出的模型和搜索算法可以被找到。

1. 用于描述感兴趣区域的数据格式

感兴趣的区域是连续的空间。在这项工作中采用矩阵格式进行存储整个区域的重要空间信息，同时最小化所需的内存。我们从一个矩形的研究区域开始，划分成一个相等的细胞网格，这个细胞足够小我们可以假设同质的内部特征（例如征地成本，土地利用模式，海拔和土壤条件）。通过对某些单元格施加非常高的成本，我们可以代表非常不规则形状的区域。线形可以通过区域中的任何点而不是被限制在最短路径和DP模型中的有限点集。

1. 三维线性的表示

现有模型表示与分段线形段（Turner和Miles，1971;霍根，1973年;Nicholson等，1976;帕克，1977年;Turner，1978）或三次样条函数（Chew等，1989）。这种方法仅产生粗略的线性。在这里，我们寻求产生更多现实的线形方式。线形首先由三个交叉点系列指定三维空间。然后，通过系列连接线形的起点和终点交点将在三维空间中产生分段线形轨迹。粗略由切线组成的横断面可以从正交投影中获得水平面上的分段线形轨迹。然后迭代过程拟合圆形曲线在水平面上的每个交叉点处，使得对准是平滑且连续的。为简化起见，省略了略微影响对准的螺旋过渡曲线分析。通过拟合抛物线曲线确定相应的垂直线形沿着纵断面上的每个交叉点，使用另一个交叉点获得平滑连续垂直剖面的程序。交点不是限于细胞的中心，可以位于研究区域的任何地方，从而增强线形的灵活形。

用于生成横断面和纵断面的两种算法被设计为模仿手动工程设计过程。在任何交叉角度非零的交叉点，圆形曲线（用于水平线形）或抛物线曲线（用于垂直线形）是交叉的。由于切线段由两个相邻的交叉点界定，因此它们的曲线长度是相互依赖的。由于切线段由两个相邻的交叉点界定，因此它们的曲线长度是相互依赖的。理想情况下，切线段必须足够长以容纳设计标准要求的曲线长度。如果切线太短，则两端的曲线长度必须减少以避免不连续的线形。为了充分利用所有切线段，曲线是从最不充分的切线的两端插入的。这个程序重复，直到每个交叉点的曲线交叉。（Jong，1998提供更多细节。）最终的线形始终是平滑和连续的，但可能违反设计规范。稍后使用惩罚（第4.2节）以避免违反约束。

1. 公路费用和设计限制
   1. 公路成本要素

在本文中，公路的成本根据他们的线形特形分为不同类别。完整的成本函数涉及复杂计算。详细的函数在Jong（1998）中给出。每个成本组件都是简要的讨论如下。

4.1.1与位置相关的成本

公路成本，如取决于线形位置的土地征用和土石方成本被分为与位置相关的成本。对于给定的线形，位置依赖成本是通过添加在线形的每个单元格中产生的成本来计算的传递（即，单元的单位成本乘以线形所覆盖的区域）。

4.1.2长度相关的成本

不同总路线长度成线形变化的公路费用分类为长度相关成本。公路路线的总长度相关成本由单元计算长度相关成本（包括单位建设和维护成本）乘以公路长度。假设沿着路线宽度是恒定的，则路面成本变为长度相关。环境成本，如空气和噪音污染，石油开采和化学废物处理依赖于车辆行驶里程（VMT）（DeCorla-Souza和Jensen-费舍尔，1994年）。如果给出了预计的交通需求（通常来自规划阶段中的预测），VMT相关成本也可以转化为与长度相关的成本。

4.1.3.土石方成本

本研究采用“平均末端区域”方法（Wright，1996）来估算公路项目土石方的量。要应用此方法，必须确定每个沿着横截面的驻地的填挖区域。横截面的计算区域需要每个桩点的道路和地面高程。路线高程可以从竖曲线的抛物线方程中计算出来。地面高程视为桩点所定下来的高程。

4.1.4用户成本

用户成本的主要组成部分通常包括车辆运营成本，差旅价值时间和事故成本。车辆运营成本可能包括燃油和油耗，轮胎磨损，和车辆折旧。最重要的部分被认为是燃料消耗。三参数模型（Jong，1998）被用来估算中型车的平均运行的燃料消耗率，还有2A单机卡车和3-S2柴油卡车的速度和道路坡度。燃料消耗模型以及平均运行速度，总线形长度和预计交通需求服从估测燃料消耗成本。出行时间成本由将单位时间值与总车辆小时数相乘计算出，这是总路线长度，平均运行速度和预计的旅行需求的一个函数。用于计算燃料消耗和行程时间成本的平均行驶速度是根据下方的线形几何结构估算的使用Polus等人开发的模型的不同条件。由于原因的复杂形和公路缺乏不存在的经验数据，评估事故成本是相对困难的。Zegeer等人开发的模型（1992）被用来估计曲线长度，曲率和交通量。然后通过计算总事故成本将事故率乘以单位事故成本。三个用户成本的净现值然后将合理期间（例如，30年）的计算结合到总成本函数中。

4.2设计限制

公路设计中最重要的约束是最大坡度，最小半径和最小竖曲线长度。最大坡度取决于道路的重要形以及建造高速公路的地形。最小半径是设计速度，超高和侧摩擦系数的函数。竖曲线的最小半径被视距和道路等级的改变控制。所有约束都是通过添加到总成本函数的外加惩罚功能来处理。

处罚方法不保证限制总是满意的。如果违规存在最终解决方案，它们通常非常轻微，可以通过设置轻松避免约束边界比必要的更紧密。但是，违反协议的限制处罚可能是过度严格规范的非常有用的指标。因此，如果解决算法是对（轻微）违规一些惩罚，它表示限制的影子价格很高，我们可能试图放松限制，例如通过减少速度限制。

1. 提出的解决方案算法

回想一下，所提出的模型的决策变量是三维空间里的一系列交叉点的坐标。所提出的模型的决策变量是三维空间里的一系列交叉点的坐标。相应的横断面和纵断面由两个迭代算法生成。计算高速公路的一些信息成本，例如相切点，曲率点，每个圆形曲线的半径，以及在生成线形之前，抛物线曲线的方程式不可用。因此，总成本成为一系列函数的决策变量。虽然在三维空间中找到线形，但问题在于搜索空间是一个超空间，因为决策变量的数量远大于三个。复杂的搜索空间和隐含的目标函数意味着目标函数是不可取分且非常混乱。因此，没有基于坡度的搜索算法适用于问题，只能用于直接搜索方法。不幸的是最经典的直接搜索方法不适用于众多局部最优的问题。因此，我们开发了一个解决这一优化问题的终极方法。

5.1综述

所提出的解决方案算法是从经典的GA中修改的。Gas是受自然选择原则和“适者生存”原则的推动的进化方法。在GA中，问题被视为环境，以及一系列可能的解决方案被视为人口。群体中的每个个体都被编码为一个字符串，成为染色体。在每一代，个人然后与每个人竞争。另外，根据他们对环境的“适应性”来衍生后代通过应用遗传算子（交叉或变异）。经过几代人的努力最适应的个体存活下来，而糟糕的解决方案最终会消失，而人口将最终收敛到最佳解决方案。GA的基本结构如图1所示。关于GA的详细讨论可以在Goldberg（1989）和Michalewicz等教科书中找到（1996）。

将GA与其他传统优化技术区分开来的区别在于：（1）Gas从人口而不是单一点进行搜索，（2）Gas仅评估目标功能，不需要辅助信息，如衍生物，和（3）GA使用随机运营商，但不是确定性规则（Goldberg，1989）。随着他们的随机性和基于人口的搜索概念，Gas不仅利用了之前动作的信息，而且还要更彻底地搜索空间（Michalewicz,1996）。因此，他们更多可能找到比传统技术更好的解决方案，如坡度搜索方案复杂和混乱的目标函数。

拟议的进化计划在很多方面与传统的GA不同。首先，我们使用浮点数而不是二进制数来编码。第二，最初人口的生成方式最有可能带来一些关于最优的有用信息解决方案。第三，我们开发了八

资料编号：[3788]