（系统工程专业论文）公路规划方法和评价模型研究.pdf

柄蔓 摘要 公路是一个国家经济发展的重要基础设施保障，为加快我国公路的发展必 须系统合理地对我国公路网进行规划。本文研究了公路规划的方法、算法和评 价模型，并对公路布局优化进行了研究。主要工作有以下几个方面：给出了道 路选线的层次分析法；提出了采用d i j k s t r a 算法进行公路网系统最优路线规戈0 的方法和算法，并进行了仿真研究；建立了地理信息系统与遗传算法相结合的 公路综合优化决策模型：在深入研究公路建设项目有关理论和方法的基础上， 构建了公路建设项目的评价指标体系，采用神经网络理论来研究公路建设项目 评价方法，并建立了公路建设项目综合评价模型。 关键词：公路规划，d i j k s t r a 算法，遗传算法，神经网络，地理信息系统 西北t 业人学顺_ _ f = 论殳摘受 a b s t r a c t h i g h w a yi sak i n do fi m p o r t a n tb a s i ce s t a b l i s h m e n t i no r d e rt oe x p e d i t et h e d e v e l o p m e n to ft h eh i g h w a y , w eh a v et om a r ko u ti ts u i t a b l gi nt h i sp a p e rih a v e c a r r i e do u tt h et h e o r i e so f h i g h w a y - p l a n n i n ga n du s e dt h ed i j k s t r aa l g o r i t h mt op l a n t h er o a d1h a v ec o m b i n e dt h eg e o g r a p h yi n f o r m a t i o ns y s t e mw i t ht h eg e n e t i c a l g o r i t h m st os e tu pt h eo p t i m i z a t i o nm o d e la n da p p l i e dt h et h e o r i e sa b o u tn e u r a l n e t w o r kt os t u d yt h em e a n so f h i g h w a yc o n s t r u c t i o ne s t i m a t i o n k e y w o r d s ：h i g h w a y - p l a n n i n g d i j k s t r aa l g o r i t h m g e n e t i ca l g o r i t h m s n e u r a ln e t w o r k g e o g r a p h yi n f o r m a t i o ns y s t e m 2 西北工业大学硕士论文第章绪论 第一章绪论 1 ，1 论文选题意义 公路的发展水平是一一个国家经济实力和经济发展水平的重要标志之，同 时也是一个国家经济发展活力的重要标志。改革开放以来，我国的公路建设取 得了举世瞩目的成就。交通部统计数字显示，1 9 9 8 年至2 0 0 4 年间，交通固定 资产投资以年均2 3 的速度增长，占全社会固定资产投资的比重上升到1 0 左 右，占国民生产总值的比重达到4 左右。例如，2 0 0 4 年湖北省计划投资6 0 多 亿元，修建公路9 2 0 0 公里，使全省公路形成网状。用这笔钱新修干线公路1 2 0 0 公里，县际及县通乡公路3 0 0 0 公里，通利公路5 0 0 0 公里，使全省路网等级进 一步提高，路网结构得到优化。由此可见，我国的公路建设增长速度之快，路 网调整之快，在世界公路发展史上都是少见的。 但是，与其它国家相比，我们还存在较大的差距。主要表现在：第，从 总体上讲我国公路基础设施总量不足，密度偏低。在公路密度方面，我国与美 国、英国、法国、日本相比差距很大，就是与印度相比也有较大差距；另外， 从每万人拥有公路长度方面来看，我围我国与美困、英国、法国、日本、印度 相比差距也很大。第二，我国公路总量明显偏少。美国，加拿大国土面积与我 国差不多，但是其国内的公路总里程却远远高于我国。第三，从路网密度来看， 目前我国的路网密度大约为美国的1 4 ；从技术等级上讲，我国目前二级以 二 公路占公路总里程的比例很小，而西方发达国家“般都在6 0 以上，甚至是 1 0 0 ，另外我国东西部公路发展也存在着巨大的差距。第四，从公路的实际需 求看，现有的公路也远远不能满足社会经济发展的要求，特别是在经济发达的 沿海省份，中西部地区部分交通t 线上，交通拥挤情况十分严重，阻碍了商品 的流通和经济的发展。 从这个意义上讲，如何系统合理的利用有限的资金对我国公路网进行规划， 是当前公路规划的重点内容。本论文正是基 二此点展开研究的。 西北工业大学硕士论文第一章绪论 2 公路网系统规划的重要性 1 2 1 公路网基本概念 所谓公路刚是指一定地域内的公路系统。在这样的系统中，城市和集镇以 及其他运输集激点( 大型工矿，农业，军事基地等) 可视为些节点，各节点 之间以一定等级的道路相连，形成网状整体，构成公路嗣。公路网应具有必要 的通达度和里程长度，要有与交通量相适应的道路技术等级和质量，同时，应 具有经济合理，箍洁明了的平面网络结构形式。 一个地城内1 _ 】公路网建设，应该结合铁路，水运，航空及管道等运输方式， 综合考虑公路网在整个交通系统中的作用和地位，按其所在地域的社会，经济， 政治和人民生活需要等方面，结合自然环境条件，制定其按等级划分的公路网 规划。公路网规划从行政方面通常分为国道，省道，县道和乡道，从技术等级 方面可划分为。i 速公路，一级，二级，三级和四级公路等5 个级别。不同等级 的公路网组合在一起，共同构成区域公路网。此外，一些重要的大型厂矿，林 区等也常有自己的道路网并且与外部区域公路网相连接。 制定公路网攫划是一项复杂的工作。地域内各方面情况不断变化，例如政治、 经济、军事暂战略性的变化，国家或地方政府建设发展指导性政策的转变，资 源的开发，l = = 】岸、商埠经济的发展，城乡人民生活水平、生活方式的提高和改 变，其他运输方式的发展变化等，都将直接影响到公路网规划的制定和实施。 我国的慝道趣捌；b 困家交通部门掌握，省以下公路规划由各级地方政府交通部 门掌握。在制定公路网规划时，应事先充分掌握各方茴的资料，进行有充分预 见的可行性研究，作出符合地域内发展方向和发展需求的公路网规划，然后有 计划按步骤的分期付诸实现。同时注意在实施过程中不断跟踪检查，根据实际 情况对路网，。渚陋e 个别路线、路段进行调整。 1 2 ，2 公路网规划与设计的基本原则 ( 1 )明确发展目标与规模 西北1 二业= = 学坝l ：论卫第一革绪论 在制定公路网规划时，要对区域内的社会经济特征，土地利用性质，国民 经济发展计划和规划做深入的研究，对公路运输在5 种交通运输方式( 即铁路， 水运，航运，公路及管道运输) 中所处的地位，其他运输方式的现状及发展等 要进行全面、系统的分析，论t f 和咨询。在此基秘h 上，明确公路网发展的目标 及规模，即将公路网运输置于大交通环境之中，使各种运输方式形成一个相互 协调、配合的整体，互为补充，充分发挥各自优势，以达到综合交通运输的最 佳效益。 ( 2 ) 实事求是，讲求科学 公路网规戈0 应充分体现国民经济持续，稳定，协调，健康发展的方针，使 公路网发展服从于社会经济发展的总战略、总目标，服从于生产力分布的大格 局。公路网规划是宏观控制和决策的需要，亦是合理建设公路，实现公路网建 设最优化的保证，必须从我国实际国情出发，动态规划，分期实施，滚动发展。 对规划区内原有的各条公路应尽可能加以利用，通过改善措施逐步达到规划等 级和标准，既要有长远战略思想，又要满足公路建设适应区域发展的交通需求， 对当前而言是经济实用的，对今后发展又是合理可能的，即作到科学合理，切 实可行。 ( 3 ) 以经济指标为准绳，讲求良好经济效益 公路网规划建设受到多种因素的影响，如社会经济，政治，国防，交通运 输状况，车辆保有量，自然环境，技术及建设力量等，而且各影响因素又有时 间和空间方面的差异。但在任何情况下，贯彻经济原则，实现网络运输最佳效 益目标，应足始终不渝的。一般情况下，区域公路网规划的工作可概括为：预 测，评价，网化和择优。交通量是公路建设最重要的基础资料，而远景交通量 的预测其主要依据就是区域的经济发展，由此不难理解公路网规划中以经济指 标作为量化标准的必要性。公路网综合评价是对公路刚的技术和经济等与面的 全面评价，规划的路网能否发挥期望的经济效益( 直接经济效益和间接经济效 益) ，将是网络方案比较和确定的重要依据。网络化是指公路网的平面布局和规 划效果，择优是指规划成果的决策。实际上，以经济指标为准绳和讲究良好的 经济效益，包含着极其= f 富的内容，贯穿体现与路网规划的全过程。 明北1 = 业凡学坝 论文第一节绪论 1 2 3 公路网规划与设计的主要内容和程序 公路网规划的主要任务是通过深入的凋查，必要的勘测和科学的定量分：l ! f 亍， 在剖析、评价现有公路网状况，揭示其内在矛盾的基础上，根据客货流分布特点、 发展趋势及交通量、运输量的生成变化特征，提出规划期公路发展的总目标和 大布局；划分不同路线的性质，功能及技术等级，拟订主要路线的走向和主要 控制点，列出分期实施的建设序列，提出确保实现规划目标的政策和措施，科 学的预测发展需求，细致的研究合理的稚局。 公路网规划应采用系统分析的方法，用定性与定量相结合的方法，以国民 经济发展规划，区域国土规划以及综合交通运输发展规划为依据，并参考有关 的行业发展规划，合理的制定公路网规划和实旌方案。 图卜l 发展预测工作框图 制定公路网觇划一般需要进行以下5 个阶段的t 作 4 里型兰王些尘! ：燮丝塞 塑二翌堂堕 ( ) 数据采集与整理 采集和整理规划区域内的政治、经济、军事、人口及交通运输等多方 面的资料。 ( 2 ) 发展预测 对规划区域的社会经济发展，综合交通运输发展，公路运输发展以及 公路建设资金等进行预测。其工作框图如图l 一1 所示。 ( 3 ) 方案设计 根据规划期内的公路交通量以及公路建设资金状况，制定公路网建设 布局方案与实施方案，方案设计的工作框图如图卜2 所示。 图l - 2 方案设计工作框图 ( 4 ) 综合评价 公路网建设方案综合评价是进行建设御局与实施方案优化比选的依 据，也是对已确定的公路网建设方案进行困民经济、社会效益等方面的评 价。 第一章绪论 ( 5 ) 跟踪凋整 公路网规划实施周期长，在此期间，由于经济发展速度、生产力布局、 投资结构或国家有关政策发生变化，导致运输结构和公路交通量与预期情 况不符，致使公路网结构，规模及路线等级对运输需求的适应性发生变化。 此时，应区别情况，对公路网规划进行全网、区域、局部或个别线路、路段 的调整，以充分利用有限资源，使运输供给最大可能地满足运输需求的变 化。 1 3 论文主要工作 道路系统规划涉及方方面面的知识，是一个复杂的系统工程。本文仅研究道 路系统规划的核心内容之一：交通系统道路选线优化，依据一定的原理，对道路 系统进行道路选线及定线，根据地理信息系统可以提供的地理属性，计算相关成 本，进行优化决策，使总成本最小。 d q 北t 业大学顺 ：论史 第j 帝道路选线 2 1 道路选线概述 第二章道路选线 馏线方案是路线设计的最根本的问题。路线方案是否合理，不仅关系到公 路本身的工程投资和运营效益，还关系到公路的使用功能和国家的路网规划， 国家的政策及国防要求等。因此路线基本走向的选择，应根据指定的路线走向 ( 路线起，终点和中间主要控制点) 和公路等级及其在公路网中的作用，结合 铁路、航运、空运、管道的布局和城镇、工矿企业等资源状况，以及水文、气 象、地质、地形等自然条件，由面到带，从所有可能的路线方案中，通过调查、 分析、比选，确定一条最优路线方案。 影响道路选线的自然因素较多，地形条件的不同决定了选线条件，并在很 大程度上影响道路的技术标准。根据地形的相对高差，地面坡度等条件将地形 分为平原微丘区地形，重丘区地形和山岭区地形。平原微丘区地形起伏不大， 路线平，纵面基本上不受地形限制；山岭、重丘区地形变化复杂，路线平，纵 面大部分受地形限制。 气候情况直接或问接的影响着地面水的数量，地下水位高度，大气降水量 及其强度和形态，路基水温状况，泥泞期，冬季积雪和冰冻延续期，并在一定 程度上限制了施工期限和条件。 水文情况决定排水结构物的数量和大小，水文地质情况决定了含水层的厚 度和位置，地基或路基岩层滑坍的可能性。 地质条件决定地基及路基附近岩层的稳定性，确定有无滑坍，碎落和崩坍 的可能；同时也决定土石方工程施工难易和筑路材料的质量。 二 = 是路基与路面基层的材料，它对路基形状和尺寸及路面结构形式的确定 有影响。地面的植物覆盖影响暴雨径流，水土流失程度，并在一定程度上影响 路基的水理和热理状况。 l 述的各种自然条件都是密切的午目互联系又相互制约，并且处于相互作用 和不断变化的过程当中。因此道路选线时要认真研究，充分考虑备种自然条什， 7 西北t 业火学颤l 论文 第一荦道路选线 认真研究将来的自然条件改变对道路建成后的影响，保证道路在复杂的自然条 件下安全和畅通，最大限度的服务于社会经济的发展。 本论文只针对平原地区的城市公路系统进行设计。 2 2 道路选线的一般原则 能否发挥道路功能和能否起到其应有的作用，选线是否合理是其前提条件。 正如前所述影响路线设计除自然条件外尚受到诸多社会因素的制约。选线要综 合考虑多种因素，妥善处理好各种因素的关系，其基本原则如下： ( 1 )在路线设计的各个阶段，应运用各种先进手段对路线方案做深入、 细致的研究，在多方案论证、比选的基础上，选定最优路线方案。 ( 2 )路线设计应在保证行车安全、舒适、快捷的前提下，做到工程量小、 造价低、营运费用省、效益好，并有利于施工和养护。在工程量增 加不大时，应尽量采用较高的技术指标，既不要轻易采用极限指标， 也不应片面追求高指标。 ( 3 )选线应注意同农田基本建设相配合，作到少占田地，并应尽量不占 高产田，经济作物田等。 ( 4 )通过名胜、风景、古迹地区的道路，应注意保护原有自然状态，其 人工构造物应与周围环境，景观相协调，处理好重要历史文物遗址。 ( 5 )选线时应对工程地质和水文地质进行深入勘测调查，弄清他们对道 路工程的影响。对于滑坡、崩坍、岩堆、泥石流、岩溶、软土等严 重不良地质地段和沙漠，多年冻土等特殊地区，应慎重对待，一般 情况下应设法绕避。当必须穿过时，应选择合适位置，缩小穿越范 围，并采取必要的工程措施。 ( 6 )选线应重视环境保护，注意由于道路修筑，汽车运营所产生的影n 向 和污染等问题，如： a 路线对自然景观与资源可能产生的影响； b 占地、拆迁房屋所带来的影响； c 路线对城镇布局、行政区划、农业耕作区、水利排灌体系等现有 登! ! 三些查兰塑! 堡兰 塑三翌篁堕塑垡 设施造成分割引起的影响： d 噪音对居民的影响： e 、汽车尾气对大气、水源、农田所造成的污染及影响： f 对自然环境资源的影响和污染的防治措施及其对策实施的可能 性。 2 3 道路选线的步骤 一条路线的起始点、终点确定以后，它们之间有很多可能的走法( 方案) 。 选线的任务是在这众多的方案中选出一条符合设计要求，经济合理的最优方案。 因为影响选线的因素很多，这些因素有的互相矛盾有的又相互制约，各因素在 不同场合的重要程度也不尽相同，不可能一次就选出最合理的方案来。通过不 同的测试阶段，由粗到细，反复比选确定。选线一般按工作内容分三步进行。 ( 1 ) 路线走向选择 路线走向选择主要是解决起始点、终点问路线基本走向问题。此项工作通 常是先在比例尺( i ：i 0 0 0 0 一i ：5 0 0 0 0 ) 地形图上从较大面积范围内找出各种可能 的方案，收集各种可能走向方案的有关资料，进行初步评选，确定几条有进一 步比较价值的方案。当没有地形图时，可采用调查或踏勘方法现场收集资料， 进行方案比选。 ( 2 ) 路线走廊带选择 在路线基本方向选定的基础上，按地形，地质，水文等自然条件选定出一 些细部制点，连接这些控制点，即构成路线走廊带。这些细部控制点的取舍是 通过比选的办法来确定的，路线布置一般应该在1 ：2 0 0 0 1 ：1 0 0 0 0 比例尺的地形 图上进行。只有在地形简单，方案明确的路段，才可以现场直接选定。 ( 3 ) 具体定线 经过上述两步的工作，路线雏形已经明显勾画出来。定线就是根据技术标 准和路线方案，结合有关条件在有利的走线带内进行平、纵、横综合设计，具 体定出道路中线的工作。 ( 4 ) 路线方案选择主要工作内容 西北t 业大学顺i j 论文 苎三兰望堕生垡 交通运输的现状及发展 水文、地质、地震、气 收集与路线方案有关的规划、计划、统计资料， 资料，项目建设条件及各种比例尺的地形图、航策图、 象等资料。 根据确定了的路线起讫点和公路等级，先在小比例尺的地形图上，结合 收集的资料，初步研究各种可能的路线走向。 按室内初步研究提出的方案进行实地调查： a 凋查项目区域社会经济状况及发展趋势，交通运输现状及发展，建设的 必要性。 b 调查相关公路的交通量构成，分布特点，交通运行特征等。根据社会经 济及交通调查资料，进行交通量预测。 c 调查地形、地质、水文、筑路材料及运输条件；社会环境，拟建项目与 其他交通衔接情况调查等。 d 分段提出采用技术标准和主要技术指标意见，初步确定路线起讫点及主 要控制点的具体位置，并征求当地政府意见。 e 进行方案比选，提出推荐意见。对影响工程方案的主要控制因素及可能 的路线方案予以说明。 分项整理调查成果。 2 4 道路选线方法 2 4 1 道路选线层次分析法概述 对于道路选线问题，由于限制条件多，影响因素复杂，所以采用分层次的 方法加以讨论，层次结构模型就是一种普遍实用的定性定量相结合的多准0 决 策( 评价) 方法。本章讨论层次结构模型在道路自动选线中的应用。 层次分析法( a n a l y t i ch i e r a r c h y p r o c e s s 缩写为a h p ) 【1 】，是一种普遍实 用的定性定量相结合的多准则决策( 评价) 方法。a h p 以其系统、灵活、简便 以及定陛定量相结合等特点，一再国内外受到广泛重视，并迅速应用到备领域 的多准则决策( 评价) 活动中。尽管a h p 的应用需要掌握+ 些简甲的数学工具， l 【1 堕! ! 三些查兰竺! ：堡兰 笙二! 堕堕垄垡 尽管从数学原理上a j p 有深刻的内容，但从本质上讲a h p 是一种思维方式。 它把复杂问题分解成各个组成因素，又将这些组成因素按支配关系分组形成递 阶层次结构，通过两两相对比较的方式确定同层次中诸因素的相对重要性， 然后综合决策者的判断，确定备选方案相对重要性的总排序。整个过程体现了 人的决策思维的基本特征，即分解、判断、综合。a h p 又是一种定性与定量相 结合，将人的主观判断用数量形式表达和处理的方法。在一般情况下，决策者 可自己使用a h p 进行决策，改变了长期以来决策者与决策分析者分离且难以沟 通的情况，从而大大提高了决策的有效性和可操作性。 a h p 大体上可分为一下四个步骤： 1 ) 分析系统中各因素之间的关系，建立系统的递阶层次结构： 2 ) 对同一层次的各元素关于上一层次的某准则的重要性进行两两比较，构 造两两比较的判断矩阵； 3 ) 由判断矩阵计算被比较的元素对于准则的相对权重； 4 ) 计算各层元素对系统总目标的合成权重，并进行排序。 a h p 是美国运筹学家，匹兹堡大学萨迪教授( t ，l ，s a a t y ) 于7 0 年代提出来 的。在1 9 8 2 年1 1 月召开的中美能源、资源、环境学术会议上，由萨迪的学生 高兰尼柴( h g h o l a m n e z h a d ) 首先介绍给中国学者。十几年来，层次分析法像 雨后春笋股在各行各业中得到广泛应用。1 9 8 8 年在我国召开了第一届a h p 国 际学术会议，在中国系统工程学会下设立了层次分析法专业学组，刨办了决 策与层次分析法专业刊物。层次分析法已成为决策( 评价) 工具中最为普及 的一种有效方法【l l 】。 要实现计算机自动选择路线诸元，最为重要和困难的是要体现一定的原则 和要求。在人工指定的方式下，决策人员可以根据对情况的判断，运用自己的 经验来选择路线。若要用计算机来完成路线生成，就要求路线诸元具有可操作 性，使计算机能够执行。目前可采用定性与定量相结合的方法，首先让计算机 选择一条路线，然后根据实隋资料，通过一定的分析计算，判断这条路线是否 登些! ：些查堂型i ：堕= ! j ! ； 竺= 三里堕堕望垡 满足有关原则，如果满足，则选择这条路线，否则必须重新选择。当然路线选 择的原则通常有很多项。可是从实际情况看，要满足所有原则往往是不可能的， 决策人员在处理这种问题时，可以根据不同的情况分出轻、重、缓、急，首 先满足最主要的原则和要求。为此，必须把选择路线的多项原则和要求，根据 具体情况，定出不同的“权”值，按“权”值的大小和先后顺序，由计算机逐 条判断。当然，“权”值的大小的确定离不开有经验的决策人员的参与，应事先 征求他们的意见，此“权”值是一经验值，是可操作和调整的。 对生成的各条路线按照最环保、最快、运费最少、综合性能最优等不同目 标函数进行比较，对每条路线进行评分，计算机可按得分的高低把n 条路线进 行排序。排序越靠前的越好。决策人员可根掘计算机选出的路线最后指定一条 或数条路线以供使用。 2 4 2 建立路线选择递阶层次结构模型 自动路线生成是一个复杂的系统问题，我们可以把公路路线选择问题看成 一个“系统”，首先弄清楚这个“系统”内部各部分之间的关系及其相互关系， 使之条理化。图2 1 给出层次结构模型，是根据影响路线选择的各因素之间的 关系构造的。 对于有序集e 中的任意元素x ，所有受x 支配的元素集合用x 一表示，所 有支g g x 的元素集合用x + 表示，即有： 定义2 1e 为有序集( 有序集e ，若e 中的元素满足自反性，对称性和 传递性，则称e 为有序集；如果再满足连通性，则称为整体有序集，否则称为 局部有序集) ，v x ，y e ，记 x 一- - y l x x 酉e y ，y e j x 4 - = 移i y 支酉h ，y e ) 堕i ! 三些叁兰堕：! = 堕苎 堡兰要堕堕堕些 定义2 2 设h 是带有唯一最高元素的( 对v x e ，c e ，若z 均为c 的 下层元素，则称为c 的最高元素。) c 的有限的局部有序集，h 称为一个递阶 层次，如果它满足： ( 1 ) 存在的_ _ 个划分往。 = 1 ，2 ，m ) ，其中厶= c ，每个划 分上t 成为一个层次： ( 2 ) 对于每个z l k ( 1 尼m 一1 ) ，x 一非空且x 一l ； ( 3 ) 对于每个z l k ( 2 k ) ，z + 非空且x + l ： 由定义2 2 不难推得递阶层次结构具有下述几个性质： ( 1 ) h 中的任意一个元素一定属于一个层次，且仅属于一个层次，不同 层次元素集的交集是空集； ( 2 ) 同一层次中任意两个元素之间不存在支配或从属关系： ( 3 ) l k ( 2 七m ) 中任意一个元素必然至少受中的一个元素的 支配，且只能受三t i 中元素的支配：同时，l k ( 1 k 垅一1 ) 中 每个元素至少支配三+ 1 中一个元素，且只能支配三t + 1 中的元素； ( 4 ) 属于不相邻的两个层次的任意两个元素之间不存在支配关系。 图2 - 1 给出了路线选择的层次结构模型。首先我们把“公路路线选择”列 为第一层，即目标层( 厶) 。其次，根据公路路线选择的基本原则，将影响公路 路线的众多因素归纳成路线距离”( 厂) ，“车辆的技术经济性能”( 厂：) ，“中 转车站设施情况7 ( 厂，) ，“公路交通管制”( 厂。) ，“汽运公司的运营保障( 厂，) ， 等五个方面，并将其作为准则列为第二层旺：) 。然后将影响第二层( 即准则层) 的多种因素列为篇三层，即子准则层，( 三，) ，共有1 3 个因素，另外将各卜要因 些i 生! ：些查堂塑! ：堡苎 笙= ：主熏塑生生 素按其性质分为强、中、弱或大、中、小等级，列为第四层，即子准则层口旺；) 。 最后一层为方案层，即根据判断准则得到的个公路路线可行方案。 图2 - 4 1 路线选择层次结构模型 托三审公路埘划埋沦- ，疗法体系 第三章公路规划理论与算法分析 3 1 规划理论与算法综述 公路网规划的基本理论与方法，作为公路网规划j 作的基石，目前国内外已 作了不少研究。 国外学者各自根据本国的经济发展和交通状况，提出了不同的方法。如在道 路合理发展规模方面，前苏联学者研究建立了地区发展水平、运输量和公路网合 理长度之间的相关关系，提出了公路网合理长度的计算公式，另外还采用多元回 归和相关分析法，建立了地方公路网密度的线性函数：日本学者提出了国土系数 理论，认为道路密度与人口平方根成正比，国道网线路长度与该地区的交通需求 成正比，与建设及养护费用成反比，并提出了各种模型的地区参数，为国道网规 划提供了理论基础和计算方法。在公路网布局方面，前苏联科学院院士b “ o6pamob 提出了运输费用最小的支线连接法，以后又有m a p0mah ehko 教授提出了星形组合法，r a on h koba 提出了渐近优解法。近 年来又有图论法等，其特点是以经济效益最佳为原则，选取运输转量、行程时间 及营运费用，作为目标函数来选定干道方向、支线偏角及最佳分向线。总之，国 外学者在公路规划理论研究方面，虽缺乏系统性，但这些局部的研究对我国的公 路网规划工作和理论研究起到了积极的作用。 我国学者根据我国的特点，也提出了适合我国国情的公路网规划的理论和方 法。特别是自1 9 8 5 年以来，交通都组织开展运输网络规划方法的研究后，取得了 大量的研究成果。这方面的文献主要有：全国性的交通系统动态仿真及网络规划、 运输通道理论和方法，省级的辽宁、江苏、河北区域公路网规划理论与方法，以 及市域和县域的公路网规划理论和方法等。 此外，国内学者还在公路网规划的各个环节上做了许多有益的尝试，取得了 一系列阶段性或局部性的成果。例如在总结了前苏联的规划方法的基础上，提出 了道路网规划的动态规划方法。动态规划方法系根据5 0 年代初美国学者 r b e l l m a n 提出的动态规划原理来优化公路例规划方案的- - 9 中方法，这种方法体 现了系统观点与优化思想。类比工业区位。j 农、i k 区位学说，提出了交通区位原理， 15 ! 型蔓! 竺生兰：竺! 三堡兰 一 兰兰至茎堕塑型竺堡! 垄鲨：堡垒 并依此进行了公路网的布局方案设计：利用已知的一些经验信息( 如局部o d 间查 信息及运输方面的资料等) 和现状路段交通量来推断公路交通量o d 分布；在区位 理论的基础上，通过借用测量学中的等高线概念，绘制路网交通量增长等直线图， 并由此进行路网交通量的预测；运用多目标规划原理进行道路网的技术等级结构 优化。此外还在弗内斯模型、重力模型及交通量分配模型的标定与应用方面， 在道路网的合理发展规模、投资决策模型、预测模型及评价指标体系、评价方法 等方面，都做过较为深入的研究并取得了富有创见的成果。 目前，我国在公路交通网络规划技术的研究方面也取得了很大的成绩，本文 将阐述一下d i j k s t r a ：算法在公路交通规划技术方面的应用。 3 2 求某车站到其它各车站最优路径的算法 d i j k s t r a ( 1 9 5 9 ) 是当前普遍采用的一个较好算法，这个算法的主要思路 是用逐点增长的方法构造一棵路径树，从而得到从树根( 指定点) 到其他点的距 离。下面介绍这一思路。 设求从指定点v o 到某一点v 的最优短径。 从v o 出发沿着弧的方向第一个到达而且路径最优的一点，一定是所有与v 0 有弧关联且弧的长度摄小的那个点，这是与v o 距离最优的一点，称为第一优路径 点，如果这个点就是v 则问题解决。如果不是v 而是男一点v 1 ，那么从v o 出发的第 二条最优路径会到达哪一个点呢? 一定是与v o 有弧相关且孤的长度最小的那个 点( v l 除外) ，或者是由v o 通过v 1 再经过与v 1 关联的长度最小的弧所到达的点， 设为v 2 ，如果v 2 即为所求的v ，问题即得到解决，否则继续寻求从v o 出发第三优 路径到达的点，第四优路径到达的点，如此继续下去直到路径的终点是v 为止。 一般来说，设t 为已求得的第一、第二、第k 条路径的终点的集合，即 t = v l ，v 2 ，v k ，贝u 有l ( v o ，v 1 ) l ( v o ，v 2 ) l ( v o ，v k ) 那么 第k + 1 条优路径( 设其终点为w ) 或者是弧( v o ，w ) ，或者终点是t 外的某一点w ， 但路径的中间结点一定都是t 中的结点( 即已到达过的结点) 这是显然的，如果 从v o 到w 的路径中有一中问点i 不在t 中，由于l ( v 0 ，i ) l ( v o ，v k ) 则i 点必然 作为v o 到w 的路径更优的一条路径终点先行加入t 中。因此按照这种路径逐步增 氏的过程，我们将得到一棵以v o 为根的树，如图3 1 2 所示，从树根到各节点的 型二坐兰堕l 堕苎 塑三兰竺些塑型些堡! 生竺壁墨 路径长度即是们到该点的距离； 根据以上分析我们可以得出求路径端点的算法。 设已求出从v o $ 发长度依次递增的k 条路径，他们的端点各为v l ，v 2 ，v k ， 并归入已到达的端点集合t 中，并将v 0 到v i 的距离简记为l ( v i ) ，对t 外的任意结 点v i ，计算数值。 v 8 图3 - 2 ，1 从树根到各节点的路径 v 1 3 l ( v i ) - = r n i n l ( v i ) + w ( v i ，v j ) ) 0 i k ( 3 - 2 1 ) 式( 3 2 1 ) 中约定l ( v o ) = o 若( v i ，v j ) e ，则令w ( v i ，v j ) = o o ( 在计算机中则用某一允 许的最大值代替0 0 ) 。 因此第k + l 条优路径，其端点一定是t ：q f 各点中l ( v ) 最小的那个点( 这罩已将 v o j j n 入t 中) ，设为点v ( k 十1 ) ，则 l ( v ( k + 1 ) ) - - m i n l ( v i ) v i t ( 3 - 2 2 ) 式( 3 - 2 - 1 ) 和( 3 2 2 ) 给出了求第k + l 条优路径终点的公式，然而直接用公式 ( 3 - 2 i ) 计算是很麻烦的，因为每求一条路径的终点，都要反复的对已通过的 节点进行计算和比较，我们可以加以改进，即在求最优路径的过程中，不断修改 为通过点的路径参数，于是得到如下算法： d i j k s t r a 最优路径算法： 1 f o ra l lv u l ( v ) - - w ( u ，v ) 2 l ( u ) 一0 3 卜f u ， 4 w h i l e t v d o b e g i n 5 找一点v i t e t 对所有v t l ( v i ) l ( v ) 6t t u v i ) l7 两北川l 人学硕 论文 第二帚登路脱划耻蹬厅法体系 7f o ra 1 1v t t h e n l ( v ) 一l ( v i ) + w ( v i ，v ) e n d 算法说明： 算法中指定结点设为u ，w ( u ，u ) = o ，t 为通过的结点集合，初始值为 u ，当t = v 是表示图的所有结点已通过，计算结束。计算从第四行循环语句开始，在不属于 t 的结点中选路径最优的点v i ，将v i 3 j h 入t 中并根据v i 修改不属于t 的结点的路 径长度，如此反复进行直到所有结点都加入t 中为止。因此这一算法是从指定点u 到所有其余结点的距离，其值通过结点v i 的l ( v i ) 给出。如果只需要求u 到某些点 的距离，那么只要对第四行的循环语句稍作修改即可达到目的。这一算法的复杂 性主要消耗在第四行开始的循环体中，而循环次数不会超过( n 一1 ) ，在循环体中， 第5 行和第7 行的执行时间是0 ( n ) 级的，总的运算时间是o ( n 。n ) 级的。 算法过程每个节点从源节点沿已知最佳路径到本节点的代价或距离来标注 ( 在括号内) 。开始，一条路线也不知道，故所有节点都标注为。随着算法的 进行和不断找到了路径，标注也不断改变，使之反应较好的路径。一个标注可以 是暂时性的也可以是永久性的。当发现标注代表了从源节点到该节点的最短可能 路径时，就使它成为永久性的，不再进行修改。 冉二疆公路川划型i 仓i ，力d 法体系 b ( a ) e hg r 6 a 1 g f 6 a 、 b ( c ) h f ，1 g f 5 e 、 ( e ) h f 9 g 1 h 卜) g f 5 e 、 ( d ) ( f ) 蚓3 - 2 1 最初5 部计算从a 到d 的最短路 图3 - 2 1 中箭头指向永久节点，星号指向工作节点。 为了说明加标注算法是怎样工作的，参阅图3 2 1 ( a ) 所示的加权无向图， 其中线上的标记代表代价，我们不防假设为距离。我们要找的是从a 至i j d 的最优 路径。我们先将节点a 涂黑作为一个永久节点。接下来检查与a 相邻的每一个节 点( 此时，a 是工作节点) ，并用到a 的距离标注这些节点。当重新标注一个节点 时，也标注上此次检查所依赖的基准节点，以便我们可以在以后重建最终路径。 检查完与a 相邻的每一个节点后，把图中被临时标记的节点中具有最小标记的节 点变为永久性节点。如图3 - 2 。1 ( b ) 所示，这个节点b ( 2 ，a ) 成为新工作结点。 我们现在开始检查所有与他相邻的节点，如果节点b 上的标记与b 到某个节 点的和比该节点的标记要小，那么我们就得到一条更优的路径，而该节点会被匝 1 9 些竖l 些查竺堕! 二堡兰 笙：要竺堕些型些堡! 互鲨竺墨 新标记。任意节点标记中的距离都是从源节点a 起始计算的。 当所有与工作结点相邻的节点都被检查并且可能修改的临时节点都已经被 重新标记后，这时候就会在全图的临时标记节点中找到具有最小标记值的节点。 该节点变成永久节点，并且成为下一个检查周期的：亡作结点。 为了说明算法的正确性，我们考察图3 2 1 ( c ) 。在这里我们刚刚把e 变为永 久节点。假定还有一条比a b e 更优的路径a x y z e ，那么有两种可能性：节点z 已经是永久性节点，或者还不是。如果z 已经是永久性的，那么e 必然已经被检 查( 在节点z 变为永久性的那个工作周期之后) ，所以这种情况下路径a x y z e 没 有逃过我们的检查。 现在考虑z 仍然是临时节点的情况。z 的标记要么l g e 的标记大或者相等，要 么小于e 的标记。如果z 的标记大于或等于e 的标记，那么路径a x y z e 就不可能 l g a b e 短。如果z 的标记小于e 的标记，那么使z 而不是e 将先成为永久性节点， 因为z 的标记会使全图的临时标记节点中具有最小标记值的节点。这就是上一段 讲的由z 检查e 。 算法的复杂度和可行性： 下面讨论算法的复杂度和可行性：假设路线图中共有n 个节点，既个除了起 点和终点外由n 2 个车站，汽车在路线中相邻两个车站之间按直线行驶。第i 个车 站与他周围m i 个车站相连( 显然m i n ) ，又因为永久性节点不再计算，就计算小 于m i 次加法。那么，算出一条路线最多检查n 1 个节点，共计算加法m i 次。 显然总次数小于n + ( n 一1 ) 2 。对于有2 0 0 0 个车站的路线图，算出一条路线也小于 2 0 0 ，0 0 0 次加法。而且绝大多数情况是每个车站与他周围1 0 0 或更少的车沾有联 系，加法数就小于1 0 ，0 0 0 次，而且绝大多数情况是不必搜索所有节点就能找到 最佳路径，计算量还会降低。 有上可知该算法是简单的可行的，不存在组合爆炸问题。 3 3 任意两车站问的最优路径生成 3 ，31 可通行路线点集构成 整个公路规划面积中可能包括各种复杂地形( 例如高山、湖泊、滑坡、崩坍、 2 0 两北丁业人学顺i j 论空 = 帚公路规划耻论与力洼体系 岩堆、泥石流、岩溶、软土等) 与自然保护区域( 其中包括名胜、风景、古迹等) ， 在规划过程中我们应该充分考虑这些因素，呵将它们用圆形来标示，即为公路不 可穿越区( 保护区) 。保护区确定下来后，就可依据它们的布局确定两车站之间 的可通行的路线点。考虑到路线最优，可通行路线点的选取一般遵循下而原则： 选择两两保护区最中间的一点( 这样选择就会同时兼顾到两个保护区所受到 的一些影响) 。 ” 首先，可通行路线点的坐标值计算方法如图3 3 1 所示。图中 0 。，y ，) ，( x ：，y ：，吒) 表示菜两个威胁的截面参数，r l , r 2 分别为某两个保护区的截 面半径，( x ，y ) 表示可行节点，( ，y ，) 表示上节点，即两保护区截面中心连线与 上保护区截面边界的交点， 。，y ；) 表示下节点，即两保护区截面中心连线与下 保护区截面边界的交点。 图3 3 一l 可行节点的坐标值计算图 依据图中的几何关系，计算上节点坐标( j ，y ，) 和下节点( x ；，y ；) 坐标分别如 下所示： y 3 = j 1 + ( 纛广 工一工 x 一= 。 y 2 一y l + y ( 3 - 3 1 ) ( 3 - 3 2 ) 两l e l l = 业大学顺卜论史 旃二帚公路埘射麒论。，方法体系 y 4 。y 2 一 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ j ，+ ( y x ：2 一- - y 1 。) 2 x ，一x ， x 3 x ，一l x y2 一y 1 。、_ 。_ - _ _ 。_ _ 。_ 。1 ，。1 1 j l + ( 嚣) 1 ( 3 33 ) f 3 3 4 ) 由上节点坐标( x ，y 。) 和下节点( 。4 ，y 。) 的坐标值就可推导可行节点 的坐标( x ，y ) 为： 工2 ( 鼍+ z 。) 2 ( 3 3 5 ) y = ( y 3 + y 4 ) 2 由以上过程我们就得到了可通行路线点集。 3 3 。2 有向图构成 可通行路线点集构成后，我们就可求出两两路线点之间的权值( 即公路建设 中每一段路线的总投入) ，以用来构成带权值的有向图。 3 3 2 i 公路建设中总投入的计算 ( 1 ) 与公路长度有关的直接成本的计算 与公路长度有关的直接成本可用下式计算： c l = k l 一( 3 3 6 ) 式中，c 。为一条公路的总建设成本， k 。为公路单位建设直接费用( 元米) ， 。为公路长度。 公路单位建设直接费用可表示为： 丘= k p + k m ( 3 3 7 ) 式中，k 。为公路单位初建成本， k 。为公路单位维修成本。 7 7 两：l e 工业大学坝l 论立 篇三章路州划理- 仑与方法体系 在不考虑高差的情况下，公路长度可由f 式计算： 三= ( # 一x + 。) 2 + ( y 一y 。+ ) ! + r ，。_ ( 3 3 8 ) = oi = 1 式中，( ，y 。) 为在公路沿线上第i 个与曲线相交的切线的切点坐标， ( x ，y 。) 为在公路沿线上，第i 个曲线与切线相交的切点坐标， r 为在公路沿线上，第i 个曲线的半径， ：为在公路沿线上，第i 个曲线的弦对弧的夹角， n 为公路起始点间交点总数。 ( 2 ) 与位置有关的直接成本的计算 公路用地成本及环境成本是与地理位置有关的成本。以往的研究多是通过 按一定间隔划分长方形网格进行计算，但这种处理方法难以对不规则的形状进 行分析计算，而且它是将公路按分段直线处理的，从而降低了计算准确性，因 此，有必要建立能准确反应各实体面积的算法。在该研究中，地理信息系统读 取从遗传算法中传来的构成中心线的点，并产生一条与公路同宽的带。这条带 代表看待建公路，其所覆盖的土地面积即成本可应用地理信息系统本身的程序 进行计算。在计算之前，要首先对地理信息进行处理。即地理数据必须以数字 化的形式提供。然而，目前国内地图数字化的程度还不普及，因此，可在扫描 图的基础上进行简单的数字化。如可在扫描图各实体的中心点储存如面积、单 位成本、中心点坐标等信息，并存储在属性表中。现有公路可视为封闭的实体， 并赋予较低的成本，因为扩建比完全新建公路征地造价相对较低。滑坡等区域 也可视为封闭的实体，并赋予昂贵的成本，从而避免在这些区域新建公路。滑 坡、湿地等环境因素将产生额外的成本，在优化中应尽力避开这类地区，然而 环境数据与属性数据不在同一分层，因此，应将二者结合：1 ) 将环境分层叠加 到路网层。2 ) 重画环境特性如滑坡、湿地等，并将其视为分离的区域。这需要 将某些属性分割，并调整单位成本。3 ) 将新的区块( 将其环境属性表示为不可 占用) 赋予昂贵的成本。从而与公路位置有关的直接成本可用下式计算： 蒴! 章公路煳划埋论，方法体磊 c 。= e 。s 。一( 3