曲面最短路径.DOC

地形起伏条件下的枝状管网布局优化 周军 李晓平 温凯 冉明鑫 宫敬 摘要：针对过去树状管网优化布局研究在二维平面条件下，难以贴近真实环境的情况，以管网长度最小为目标，采用最小生成树算法完成平面枝状结构布局，将管网布局结果置于模拟地形下，采用遗传算法，寻找具有连接关系的两点间的曲面最优路径，得到管网布局。为使结果进一步接近整体最优解，提出了考虑地形起伏的枝状结构布局优化模型，并给出了模拟算例分析，结果表明该方法能够有效布置管网结构，寻找管道最优路径，降低管道总长度。 关键词：设计优化；管网布局；曲面路径；枝状管网；遗传算法 枝状结构[1]是油气田地面集输管网一种常用结构形式[2]，确定有管网结构和合理的路径走向是集输管网设计的重要内容。集输管网中的井、阀组、集气站等对应着图中的节点，集输管路对应图的边[3]，图中的树枝结构即枝状管网，枝状管网优化转变为求平面下的图中的最小生成树问题[4]，而在起伏区域，管网布局优化问题包括连接关系优化和两节点间的最短路径优化两个问题。 1 曲面最短路径 求解曲面最短路径问题的一般思想是用变分法求解析解，但是这些算法往往极度依赖于曲面函数形式，鲁棒性一般极不理想，而且往往难于处理约束，而在现实问题中，地形曲面复杂，且采用观测数据拟合或者是空间地形数据，无法采用曲面函数描述。 1.1 数学模型： 约定曲面： 为凸集 曲面最短路径问题就是在曲面上给定点和点间沿曲面的最短路径，数学模型如式（1）。 （1） 可以在给定曲面函数的基础上采用泛函优化的方法求解以上数学模型，但在很多情况下不知道曲面函数的解析表达式，比如敷设管网的起伏地面一般是不能用某一函数表示的，只能用实际采集的地面高程数据进行离散化描述。 1.2 求解算法 研究者采用多种智能算法[5-7]求解曲面最短路径问题，遗传算法是常用的智能算法之一，遗传算法的框图如图1所示。 图1 遗传算法框图 考虑某起伏地面区域中的管道起点为和终点为，由到的路径有很条，假设管道建设投资与长度成正比，寻找到的最短路径就是使管道建设投资最少的路径。将点到点横坐标间分为等分（或者纵坐标间分为等分），纵坐标范围为（或者横坐标范围为），每一等分中确定一点，加上起点和终点共个点，连接这些点，形成起点和终点间的一条路径，其中变量为x和y，z值由曲面函数或者地形离散点数据得到，决策变量数目为n个。 初始种群含m条路径，第k代第i条路径表示为： （2） 第k代第i条路径的长度表示为： （3） 适应度函数 （4） 遗传算法中采用实数编码，选择方式为轮盘赌选择，并采用单点交叉，单点变异进行计算，直至找到最佳个体。 1.3 优化结果 采用以上算法，使用模拟数据对算法进行验证，采用文献的地形模型函数。 （5） 地形函数的参数如表1所示。 表1 地形函数的参数值 n 1 2 3 4 5 6 7 8 xc 25 64 34 77 94 65 15 93 yc 87 28 53 92 55 24 11 14 p 1.5 2 3 2 3 1.5 3 3 q 1.5 3.5 2 2 3 1.5 2 3 u 30 65 21 6 11 13 11 13 v 20 12 13 25 14 9 16 11 h 57 19 -32 38 24 -22 -14 -17 给定和，内插点9个，初始种群规模20，复制概率0.1，交叉概率0.7，变异概率0.1，最大进化代数300，图2和图3分别显示了在地形曲面上两点间的最优路径投影图和曲面两点间最优路径三维图，黑线表示两点之间的曲面路径投影为直线的连线，红线表示采用以上算法的优化路径投影，直线的曲面投影长度为217.49，优化路径长度170.24。 图2 曲面两点间最优路径投影图 图3曲面两点间最优路径三维图 2 管网布局 2.1 平面条件下的管网布局 枝状管网布局优化问题的目标是使连接节点的管线投资总额最小，该问题可以转变为图论中的最小生成树问题。 采用Prim算法[8]，对给定坐标的、、、和五个点，得到如图4所示的平面最小生成树。 图4. 平面条件下的管网布局图 2.2 给定节点连接关系前提下的曲面管网布局 将优化得到的平面条件下的管网连接关系置于起伏地形中，采用曲面路径寻优确定两点之间的起伏地形下的曲面最短路径，可以得到基于最小生成树的管网曲面走向图，管段路径长度如表2所示，地形高程下的结果如图5所示。 图5. 曲面条件下管网布局投影图 表2 管段路径长度 管段 A-C B-D C-D D-E 总长度 两点间投影为直线的路径度 65.14 66.72 73.69 68.16 273.71 两点间最优路径长度 55.7