现代交通规划学第二章.doc

第八章 交通网络设计前面几章分别讨论了交通规划的数据调查、相关模型的建立、出行预测，但这些都不是规划项目的委托者所关心的和需要的，他们真正需要的是交通规划的设计方案（如设计图纸等）。因此，交通规划的方案设计才是整个交通规划最终的着眼点和最关键的工作，前面的各项工作都只是为这个工作作准备。因为交通规划是研究中观层面的交通，其方案设计主要是两个内容：交通网络的设计和交通枢纽的设计，其中交通网络的设计是重点，也是难点。本章我们来研究交通网络的方案设计问题，下一章讨论枢纽的方案设计问题。从前面的内容可以发现，关于数据调查、相关模型的建立、出行预测都有建立在定量的模型之上的规范的科学方法，使得其所得的结果可靠。但是，非常遗憾的是，在我国传统的交通规划理论中，恰恰在规划方案设计这个关键的环节缺乏定量的模型和规范的方法，而只提出一些定性的方法和原则，用它们来指导方案设计。就交通网络的设计而言，目前我国规划工作者所采用的方案设计方法是：在交通分配的基础上，发现现状路网对规划年份预测流量的供求矛盾所在（缺陷所在），作为现状路网的改进提供依据；然后由多个规划者综合考察交通、社会、经济、地形地貌、城市风貌等各方面的因素，根据自己的感性知识和经验各自提出一套方案，这样就得到多套方案；然后用数学评价模型对各套方案进行评价分析，选出其中最优的一个作为最终的方案。这样做的缺点是，备选的方案只有极有限的几个，而真正可行的方案有许多个甚至无穷多个，所以即使所采用的评价模型正确，也只能在这有限的几个方案中选优，而不能全域选优，很难得到真正的最优方案。1973年，Morlok首次提出交通网络设计问题并展开研究以来，在北美和西欧，许多学者如Morlok、LeBlanc、Sheffi、Friesz、Marcotte、Bell等对交通网络的设计问题展开了深入的定量化的研究，提出了描述网络设计的数学模型、和许多相应的算法，形成了交通规划领域中的一个新的研究方向网络设计问题（NDPNetwork Design Problem）。1990年代以来，我国的一些学者如杨海（yang H）、黄海军、黄进仕（Wong S. C.）、刘灿齐等也等加入了这个研究行列。近30年来，在NDP方面，国际上已出现了许多很有意义的研究成果，有些还应用到了实际的公路网和城市道路网的设计上。考虑到定性的方案设计方法和原则在我国的交通规划中普遍采用，并且其中还是有一些概念性和规律性的内容可以遵循和参考，本章拟首先在第一节概括地介绍这些一般的方法与原则，然后在后续四节中，着重讨论定量的、模型化的交通网络设计问题。8.1定性的交通网络设计方法8.1.1 城市道路网设计1道路网布局城市道路网的布局有四种类型：方格网，环形放射网，自由网，混合网。1）方格网（棋盘式）每隔一定距离设置纵向的、和横向的接近平行的道路，但由于地形和历史等原因，方格网一般不一定是严格垂直和平行的，见图1。北京市、西安市、洛阳市等一些平原地区的地域是典型的方格式。这种布局的优点是：布局整齐，有利于建筑布置和方向识别；由于多为四肢垂直交叉口，简化了交通组织和控制。缺点是：道路非直线系数比较大，一般在1.271.4之间。这里，非直线系数=出行实距/PA点之间几何距离。方格网适用于地势平坦的中小城市以及大城市的局部地区的干道网。2）环形放射式环形放射式的道路网由若干条环线（不一定成圆形）和起自城市中心或环线上的某一点的射线组成，见图2。这种布局的优点是：有利于市中心与各分区，郊区的交通联系；非直线系数较小，一般在1.11.2之间。缺点是：因街道形状不够规则，交通组织比较复杂。 图8-1 方格式道路网 图8-2 环形放射式道路网环型放射式道路网一般适用于大城市和特大城市的主干道网。3）自由式受历史原因、山地、河流的影响，道路的线路走行无一定规则，形成自由式。这种布局的优点是：能充分结合自然地形；节约道路工程费用。缺点是：道路线路不规则，造成建筑用地分散，和交通组织困难。自由式适用于山区城市和河流较多的城市。4） 混合式：因地制宜，将上述两种、或三种道路网形式的混合在一起。混合式使用得当可以尽得各式样的优点、扬长避短。我国大多数城市采用方格式与环形放射式的混合式，如北京。2道路的类型（规格） 城市道路可分为快速路、主干路、次干路、支路、和自行车专用路、商业步行专用路等。小城市只分干路和支路两种，前四种道路是主要为机动车服务的，也是最常见的。对于它们，表8-1列出了设计指标。表8-1大中城市路路网规划指标城市规模人口（万人）快速路主干路次干路支路机动车设计速度（km/h）大城市3008060403030060-8040-604030中等城市-404030路路网密度（km/km2）大城市3000.4-0.50.8-1.21.2-1.43-43000.3-0.40.8-1.21.2-1.43-4中等城市1.0-1.21.2-1.43-4机动车车路条数大城市3006-86-84-62-43004-64-642中等城市42-42路路宽度（m）大城市30040-4545-5540-5015-3030035-4040-4530-4515-20中等城市35-4530-4015-20各种类型的道路的定义是：快速路：1）中间设隔离物分隔对向车流，或两个方向的车路分别设置在不同标高上； 2）两侧不设置大流量的公共建筑出入口； 3）两侧设护栏，严格限制非机动车，行人横穿； 4）两旁视野开阔，不可种高大乔木，弯度和坡度要小； 5）与其它道路立体交叉，有条件的城市，部分或全部路段可高架。主干路：1）机动车、非机动车路分隔，大部分路段设护栏； 2）两侧不设置大流量公共建筑的出入口。次干路和支路：注意满足公共交通线路行驶的需求。3 交叉口设计交叉口是城市道路网的主要组成部分，在设计道路网时，应该同时考虑交叉口的设计。交叉口的设计主要是个微观的设计问题，交通控制理论中已有详细深入的讨论，在此，我们只介绍交叉口的各种类型以及确定类型的标准。预先介绍两个概念：交叉口的进口道：路段上在靠近交叉口用于分离不同流向车流和停放排队车辆的部分。进口道的车道数是分流向的、并且一般多于路段的车道数。交叉口的通行能力：各个方向进口道单位小时可通过的最大标准车辆数（pcu）之和。平面交叉口的机动车通行能力列于表8-2。交叉口分类：从管制方式分，有：无信号灯、有信号灯。 从分隔方式分，有：平面交叉、立体交叉。表8-2 平面交叉口通行能力（1000pcu/h）相交道路等级交叉口形式T字型十字型无信号有信号无信号有信号主干道主干路3.3-3.74.4-5.0主干次干2.8-3.33.5-4.4次干次干1.9-2.22.2-2.72.5-2.82.8-3.4次干支路1.5-1.71.7-2.21.7-2.02.0-2.6支路支路0.8-1.01.0-1.2注：进口道车道数：主干道3-4条、次干道2-3条、支路2条。这里立体交叉口是指互通式立体交叉口。如果一个立体交叉口不是互通式的，不同方向的车辆就不能在此分流和汇流，这本身就不具有交叉口的全部含义，故这里不含盖这种交叉口。在下列情况下，可采用互通式交叉口： 快速路市郊高速公路； 快速路快速路； 快速路主干路； 快速路次干路； 主干路主干路、且交叉口交通量很大； 各进口道上流量之和大于或接近交叉口通行能力，而又无法通过改进交叉口几何布置来提高其通行能力的交叉口。城市的互通式立交形式有：苜缩叶式、部分苜缩叶式、菱形、环形、三路喇叭型、三路环型等，占地面积约为2.55公顷，总通行能力约为500010000pcu/h。各种形式的互通式立体交叉口的具体形态和特点请参阅道路交通设计的有关文献。应该根据相交的道路上的流量，在节省建设投资的前提下，选择最适合的交叉口。设计时还要注意：快速路、主干路、次干路、支路四级道路不能超级相交，如快速路不要与次干路相交；环形交叉口通行能力低于非环形平面交叉口，因此大城市较少采用，一般规定：当规划交通量2700pcu/h时，不宜采用环形交叉口。关于城市道路交叉口和路段设计的更详细内容可参阅张廷楷（1990）、周荣沾（1999）。8.1.2公共交通网络城市公共交通是指定时定线的公共汽车、公共电车、轨道交通（轻轨、地铁）、轮渡等交通方式。广义地说，出租车也属于一种公共交通，但因为它仍是一种个体交通，此处不包含它。本小节只讨论公共汽车、电车的网络设计问题，这是目前国内外使用最广泛的公共交通方式。1 公共交通网络形式有三种基本的公共交通网络类型： （1） （2） （3） 图8-3 基本公交线网类型有中央终点的放射形网（图8-3（1），中心点一般取市商业中心或长途汽车、火车站。常用于小城市。优点是：乘客只需要不多于一次换乘就可完成出行；且便于调度管理；还有利于促进市中心的商业繁荣和发展。缺点是：非直线系数大。：主干线与驳运线结合网，又称“鱼骨式”（见图8-3（2），多用于带形中等城市。：环线网（见图8-3（3）。优点是：减轻中心点的换乘压力。降低非直线系数。 （1） （2） 图8-4 组合形式的公共交通网络实际上许多城市的公交网络都不是上述单独的某种类型，而是两种或多种基本类型的组合形式。如图8-4（1）是环线式与放射式的组合网；图8-4（2）是鱼骨式、放射式与环线式的组合网。2 技术规格公共交通应遵循如下技术规格：线路长度及单程时间宜为3050min，大城市可略大一些，但最好不超过60min。过长会导致车辆准时率低，过短则会增加乘客换乘次数。中等城市的公共交通线路密度：市中心区 45km/km2；郊区、市边缘区23km/km2。大城市略高于此值，小城市略低于此值。非直线系数不超过1.5。车队规模：大城市8001000人/辆，中小城市12001500人/辆。3 服务水平参数出行者是否选择公交方式主要由公共交通的服务水平决定。刻画公共交通的服务水平可用下面四个参数：非直达系数（又称“换乘系数”）： K=（公交乘客总量-直达乘客量）/公交乘客总量。非直达系数越低，服务水平就越高。实载率：h=车内实际乘客数/车内座位数。实载率越低，服务水平就越高。平均营运速度： n=线路长度/出发点至终点时间（含中途停车）。平均运营速度越高，服务水平就越高。发车间隔。发车间隔越小，服务水平就越高。4 公交车站与站场设计首末车站：用地10001400 m2，含车辆排队停车场地、调度、休息室、乘客排队空间。中间车站：对于同侧换乘，几条线路可用同一个站点，如果线路太多，也可同侧设两个站点，两站点之间相距应50m；对于对向或相交道路上的换乘的站点，相距应150m。车站应该设在离交叉口50m的地方，以免影响交叉口的通行效率。在主干道快或速道上，公交站应设为港湾式，上下行对置车站，迎面错开3050m。站距：一般线路：市区500800(m) 郊区8001000（m） 快车线路：市区15002000（m） 郊区15002500（m）保养场：公共汽、电车的保养场的面积规模和每辆车的保养用地指标见表8-3。 表8-3 保养场的面积规模和每辆车保养用地规模（辆）50100200300单节车用地（m2/辆）220210200190铰接车用地（m2/辆）2802702602508.1.3 城市轨道交通规划1 城市轨道交通网络城市轨道交通又叫“城市快速轨道交通”。特点是：运量大，速度快，准时点，对城市发展拉动力强，使用寿命长（100年以上），建设费用高，建设时间长，建成后不可更改。常见的形式：地铁、轻轨、市郊铁路（郊铁），在市区内的主要是地铁和轻轨两种形式。因为地铁和轻轨的运营速度大于一般公交，又分别称作：大运量、中运量快速轨道交通。地铁：多在地下，但延伸到城市边缘地区或郊外时，也可将轨道铺设在地面和高架上，但必须做成全封闭线路。轻轨：多行于高架，但某些路段也可能是在地面，但必须做成全封闭线路，也允许部分区间线路进入地下。地铁与轻轨的区别主要不在于其是在地下还是在高架上（虽然地铁大多在地下，轻轨大多在高架上），而在于车体的轻重及编组车辆的多寡。地铁和轻轨的有关技术参数见表8-4。除大城市和特大城市适合建设轨道交通外，人口多于50万的带形中等城市也可考虑建设轻轨。 表8-4 轨道交通一些技术参数种类城市规模（人口：万）运营速度（km/h）最高发车频率(次/h)单向运能（万人）编组（辆）成本（1995年价：亿元/km）地铁300354020303.06.0685.0轻轨100300303540601.53.0363.0一般公交车152050900.81.0120.12 轨道交通网络设计原则1）由于轨道交通对未对城市用地布局、发展速度和规模具有很强的拉动力，在规划轨道交通网络之前，要深入研究一个城市未来的合乎可持续发展的用地形态；在此基础上，作出远景（20年甚至更远）的客流预测；然后才能进行轨道交通的网络设计。2）在进行网络设计时，要注意：线路尽量沿城市道路干线走向；应有贯穿市中心的直径射线；为防止城市不断摊大，应该慎重运用环线，一般边缘地区不用环线，概括地说，要少环多射。3）注重轨道交通与地面公交、对外客运交通的衔接，设计出方便完善的换乘系统。4）线路尽可能经过大型客流集散点，如机场、火车站、码头、大型商业区和住宅区、工业区等。8.1.3 公路网的设计在各种交通网络设计中，以城市的交通网络设计要求最多最高，如在网络形态、投资的成本效益比、甚至交叉口形式都有较高的要求。公路网的设计要求要粗一些，基本上都包含在城市交通网络的各项要求之中，因此可以参考上面关于城市交通网络的有关设计方法。如我国全国高速公路主干道网络就参考城市交通网络形态，设计成几横几纵的方格式，北京地区的公路干道网设计成放射式，上海地区的600公里高速公路网络设计成放射和方格的组合形式。公路的次要线路一般是在规划的建设资金允许的前提下，设计跟着需求走，即采用自由式。8.2 定量交通网络设计方法概述8.2.1 必要性上节介绍的定性的交通网络设计的方法，主要是凭感性和经验进行交通网络设计。虽然其中也包含一些定量的指标，但整体上来说，是定性为主，定量为辅。这种方法存在一些明显缺陷，主要有：头痛医头、足痛医足，往往把注意点孤立地放在某条路段，殊不知交通网络上的车流是均衡分配或随机均衡分配的，一条路段的拓宽或新建一条路段都会导致交通流在整个网络上重新分配，可谓“牵一发而动全身”；不能保证建设资金被投放在最需要的地方，也就不能保证最大的成本效益比；在确定拓宽或新修一条路段时，不能准确的确定出最佳的工程规模（如车道数）。因此有必要研究定量的交通网络设计方法。为了更清楚地说明这个必要性，我们来看两个例子。例8-1：图8-5（1）所示的是一个简单的交通网络，只含有四个节点、四条路段。设初始道路网产生点到吸引点的出行量为6，路段1、3的走行时间函数为： 路段2、4的走行时间函数为 可以算得，网上均衡配流的结果是：x1=x2=x3=x4=3；各路段的走行时间为：t1=t2=53, t3= t4=30；总的走行时间是：。现在这个初始网上加修一条从到的路段5（见图8-5（2），这样就出现了三条路径：f1（）、f2（）、f3（）。设路段5的走行时间函数为。可以算得，网上均衡配流的结果是：x1=x2=2，x3=x4=4，x5=2；三条路径的交通流量为：f1= f2= f3=2，走行时间为C1= C2= C3=92；总的走行时间是： 例完。 1 4 1 4 5 3 2 3 2 (1) （2） 图8-5 例8-1示图Braess诡异人们在现有交通网络上加修路段的目的是降低交通网络的拥挤程度，网络的拥挤程度降低的具体表现是车辆在网络上的总的出行时间减少。但在此例出现了一个奇怪现象：在交通网络上加修一条道路不仅不减少总出行时间，反而使之增加。这个例子是Braess提出来到，这种现象称作“Braess诡异”。Braess诡异说明：假定交通网络上各PA点对间的出行量不变，不能保证随意地添加路段都会使拥挤程度降低，也即：对PA需求矩阵相同的网络，并不见得路段越多，总走行时间就越小。下面的例子则提出另一个奇怪的现象。例8-2：图8-6所示的是一个只有两个节点两条路段（在这里也是路径）的简单网络，设路段的阻抗与流量无关，分别为t1=4，t2=2；从P点到A点的出行量为1000。设网络上的车流是随机均衡分配的。根据随机均衡模型，每辆车选择路径1的概率为： 故路径1上的流量为119。路径2上的流量为881，总阻抗为： T=1194+8812=2238。现对路段1进行拓宽，使其通行能力提高了，车辆在其上的行驶阻抗降低到t1=3，此时可以算得：P1=0.269，故路径1、2上的流量分别为：269和731，总阻抗为： T =2693+7312=2269。这样，拓宽路段1后，网络上的总阻抗不是减少了，而是增加了。例完。 路径1 P A 路径2 图8-6 例8-2示图新修道路和拓宽已有道路的目的都是缓和网络的拥挤程度，降低总的阻抗。但在上面两个例子中，一个是加修了路段、一个是拓宽了路段，结果都导致网络的总阻抗增加而不是降低，适得其反。当然这两个都只是理论上的反例，实际中虽不多见，但仍是确有其事。这至少说明了我们无法保证：“假定出行量不变，随意地进行交通网络扩建，都会使网络上总阻抗变小，至少不增加”。所以在进行网络扩建之前，有必要进行科学的、定量的分析，否则就可能不仅浪费了宝贵的建设资金，还将导致网络运行效率降低。8.2.2 研究现状1970年代以来，美欧等国一些交通工程学者所进行的基于最优化理论的交通网络设计问题（NDP）的研究，探讨了交通网络设计问题的数学模型及其算法，科学而严谨地解决了这个问题，并且其中一些理论成果已应用到了实际的、公路网络设计中，后来的运行情况表面，设计的效果非常好。细究起来，NDP所研究的问题可分两类：对已有路段改进，和添加新路段。前者被称作“连续型网络设计问题”（CNDPContinuous NDP）；后者被称作“离散型网络设计问题”（DNDPDiscrete NDP）。这里的“连续”是指路段通行能力的增加是连续的、渐进的，而离散则是指路段的通行能力的增加是跳跃性，例如新修路段，从无到有。但当对已有路段的改进是指增加车道时，由于增加车道所导致的通行能力的增加就不是一点点，也是一次跳跃，因此也可归入离散网络设计问题。然而从过去的研究来看，人们偏向于将这个问题归入连续型网络设计问题（CNDP），人们也较多的关注CNDP。这是因为CNDP中的目标函数是连续的，甚至还可以进一步要求它是可微的，这就便于数学处理；而离散型网络设计问题（DNDP）则没有这些特点，关于它的算法一般都是非常耗费计算时间的。在本章，我们将提出一个DNDP节省计算时间的近似寻优算法。 在下面的第3节，我们将讨论DNDP的模型和算法，在第4节介绍CNDP的模型及几种算法，最后在第5节简要介绍近些年国际上在NDP方面各种主要的研究成果，并分析尚存在的问题。近30年来的NDP研究都是建立在均衡交通分配理论的基础上的，在后面我们将看到所有的模型和算法都包含交通网络上的均衡分配模型和算法步骤，因此均衡分配的有关条件也就成为了这里NDP的当然条件。回忆第七章5、6两节的均衡分配理论，Bechmann模型存在唯一最优解的前提就是，各路段上的走行时间函数ta=ta (xa)连续、可微、而且严格单调递增。到目前为止，在各种交通运输方式中，只有公路网的走行时间函数被较好地描述出来，通用的是美国公路局（BPR）提出的走行时间公式： （8-1）其中，ea: 表示路段a的通行能力； aa：路段上的自由走行时间； ba：非负参数。而且这个走行时间函数确实也符合上述要求。因此，已有的NDP的研究成果真正适用的也就是公路网，城市道路网只可以参考，因为车辆在城市道路网上的走行时间还应该包括在交叉口的延误，而上面公式只指路段上的走行时间，目前尚无较理想的同时包含路段和交叉口的走行时间公式。8.3 离散网络设计问题本节首先提出两个离散型网络设计问题（DNDP）模型及其算法，然后探讨了求近似最优解的较省时的算法。先定义本节常用符号的意义。xa：路段a上的交通流量，它们组成的向量为x=(, xa, )；ya：路段a上投资决策变量，共m个，它们组成的向量为y=( y1, y2, , ym)；m：备选路段（待添加和待改进路段）的条数；ta：路段a的走行时间，ta=ta (xa, ya)，即路段a的走行时间是流量的函数；fkrs：点对（r，s）间的第k条路径的交通流量，其向量为f=(, fkrs,)；ba：路段上（预计）投资额，其向量为b=(, ba, )；S：预算总投资额上限；：路段路径相关变量， ；A：网络中路段的集合，包括已有路段和待添加的备选路段；qrs：点对(r, s)间的PA交通量；a、k、r、s：分别为路段下标、路径下标、出行产生点下标、吸引点下标。8.3.1 DNDP模型及其解法DNDP的模型可分为两种类型：预算约束模型，即投资额有限制的模型；和无预算约束模型，我们分别研究其模型和算法。1 预算约束的DNDP因为我们投资改造网络的目的是使网络的拥挤程度降低，产生的直接效益是减少出行者的出行成本，所以用户（出行者）的总阻抗值是NDP的目标函数，该目标函数取最小值就是最优化的目的。另外，就交通网络的管理者（规划者）和用户而言，规划的特点是假定管理者处于主动地位，用户处在适从地位。管理者以整个网络的系统最优（SO-System Optimal）为设计交通网络的依据；但是广大的分散的用户并不步调一致地服从管理者的愿望，一般都不愿意为系统或他人的最优牺牲自己的出行成本，都是选择最小阻抗或自认为是最小阻抗的路径出行，即他们的决策依据是用户最优（Users Optimal），总体上表现为：用户均衡（UEUsers Equilibrium）或随机用户均衡（SUEStochastic Users Equilibrium）。然而，管理者和用户又不能完全各行其事，用户是在管理者设计的网络上进行均衡或随机均衡分配，反过来，管理者在确定各路段阻抗时只能依据用户均衡分配或随机分配的结果。因此，我们采用管理者为领导者用户为跟随者的双层决策数学规划模型。上层： （8-2a） s. t.： （8-2b） （8-2c）其中，x*=(, xa*(y), )是下层数学规划的极值；下层： （8-3a） s. t. : （8-3b） （8-3c） （8-3d）其中，式（8-1a）、（8-2a）中的非备选路段的ya (a1, 2, , m)必为0。对上规划模型，我们采用“隐枚举法”来求解。满足式（8-1c）的向量共有2m个，分作（m+1）组:第1组只有一个向量：y=（1，1，1）;第k组有个向量（为组合值），它们都含有（k-1）个为0的分量，(m-k+1)个为1的分量；第（m+1）组只有一个向量：y=（0，0，0）。算法分两段，第一段算法是确定上层问题的可行解和非可行解，第二段算法是结合下层问题，寻找最优解。首先将m条备选路段的投资额按递增的顺序排列，并将决策变量也按这个顺序排列，不失一般性，设仍由和分别表示排序后的投资额向量和决策向量。用Fk表示第k组中不可行解的集合。算法8-1：第一段：找可行解。步1：对所有的k（1km+1），令Fk=（空集合）。步2：令y=（1，1，1），进入第一轮工作（每一轮工作是考察一组的向量）。问：ybTS？若是，则停止，这就意味着2m个向量都是可行解；否则，令F1=y，F1= F1，k=1。步3：设第k轮工作已完成，产生了第k组的不可行解集Fk。下面进行第(k+1)轮工作： 3-1：问：Fk=？若是，停止；否则，任取Fk 中一个解y，并令Fk = Fk y； 3-2：设y中为1的分量依次是第l1、lp个，其余分量均为0，令y j是除第lj个分量为0外其余分量与y相同的向量（对ij，有lii，都有y kbTS，即说明y i至y p都是第（k+1）层的可行解，此时，跳到3-3步；否则，将y i存入Fk+1，即令: F k+1=F k+1y i next i3-3：F k=？若是，第（k+1）轮工作已完成（第（k+1）组所有的不可行解已求得，组成集合Fk+1）令Fk+1 = Fk+1，k=k+1，返回3-1步；否则，从Fk中任取一个解y，并令Fk = Fk y，返回3-2步。第一段算法结束。寻找第（k+1）组不可行解是从逐个考察第k组不可行解（Fk的元素）着手的。第3步本身是个循环，每次循环考察Fk中一个不可行解，并用Fk存放Fk中尚未被考察的元素（不可行解）。第一段算法结束时，可能停止在（m+1）组向量的中间某一组（如第k组），而没有到达最底组（第（m+1）组）。这意味着，从第（k+1）组到第（m+1）组的向量都是上层问题的可行解。设第j组的向量之集为Gj，第j组的所有可行解的集合为Hj。显然，当1jk时， Hj=Gj Fj表示第j组的可行解之集；当kjm+1时，Hj=Gj。第二段：求最优解。步1：初始化。设N0=（K，A0）为原始网，令y0=（0，0），用F-W法在N上UE配流，得配流结果为：x*=(, xa*, )，令：，y*= y0。步2：求最优解。 2-1：令：j=m； 2-2：问：Hj=？若是，跳到2-6步；否则，任取一个可行解yH j，Hj=Hj-y。设网络N(y)=（K，A）是初始网N0加上y中等于1的分量所对应的备选路段后所构成的新网络（后同）。 2-3：用F-W分配法求N(y)上的UE配流，得配流结果为：x*=(, xa*, )，令：； 2-4：问ML？若是，令y*= y，L=M； 2-5：返回2-2步； 2-6：若j=1，输出y*，停止；否则令j=j-1，返回2-2步。第二段算法结束。 现在来对这个算法进行计算量分析。由于在整个算法的各个计算步骤中，当用固定的y值计算下层极值问题以求x*时，须作一次UE分配（这要调用F-W算法）。从第七章我们知道，每做一次UE分配都是比较费时的，而且对相同规模的网络（路段数相同），F-W算法的耗时基本相同。相比之下，算法中其它的计算工作（判断、赋值等）的耗时都很小，可以忽略不计。因此我们就用算法中所进行的UE分配的次数来衡量算法的计算量。就本算法而言，对每个可行解都要进行一次UE配流，设总共有K个可行解，故共需进行K次F-W运算。例8-3：在图8-5所示的交通网络中，有两条备选的新建路段5、6（见图8-7），路段6的阻抗公式为：t6=52+10x6，其它路段阻抗公式同例8-1。建设成本分别为y5 =10（成本单位：百万元，下同）、y6 =12，设预算上限为S=15。试解此网络设计问题。解：可用两种方法来求解。（1）直接在三个网络（原网络、添加路段5的网络、添加路段6的网络）上分别进行均衡配流，并计算各自的用户出行总阻抗，取其最小者。 1 4 1 4 1 4 5 6 3 2 3 2 3 2 (1) （2） (3) 图8-7 例8-3示图三个网络由例8-1的计算知，前两个网络的总阻抗分别为T1=498，T2=552，下面计算第三个网络上的总阻抗。由于在原网络上添加了路段6，使从点到点有三条路径：、。均衡配流的结果是：三条路径是阻抗均为72，流量都为2，同时可得：x1= x2= x3= x4= x6=2，得总阻抗为：T3=432。由于T3小于T1和T2，因此，第三个网络为最佳网络。（2）用模型（8-2）（8-3）和算法8-1，算得：y5=0，y6=1。其结果与上方法相同。例完。2 无预算约束的DNDP无预算约束并不意味着可以允许用于新路段的建设投资任意地大，而是将建设成本与用户的走行时间成本一起考虑，将两者之和作为目标函数，求最小值。其数学规划模型为：上层： （8-4a） s.t. （8-4b）其中，x*=(, xa*(y), )是下层数学规划的极值；下层： （8-5a） s. t. : （8-5b） （8-5c） （8-5d）其中，是因交通阻抗与投资额的物理量纲不同而设置的转换系数，最后用阻抗的量纲作为目标函数Z的量纲。解法：对于这个模型，不必预先确定上层问题的可行解，它的算法与上面预算约束模型的第二段算法基本相同，只是这里改令第j组所有的个y向量都是可行解，即：Hj=Gj（1jm）。这里不再重写这个算法，感兴趣的读者可以自行写出这个算法。不难发现，这样算法其实就是枚举式算法，要对所有的2m种方案进行UE配流计算，其计算量十分惊人。如当m=20时，就要进行一百多万次F-W均衡配流计算。前面的预算约束的DNDP的算法虽然不到2m次F-W均衡配流计算，但是因为它也是要对所有可行解进行F-W均衡配流计算，而不可行解只在最上面几组中出现，其所需进行的F-W配流计算次数仍然是很大的。因此上面两种算法都是非常耗费计算时间的。可否设计出一种较为省时的算法来计算这个模型？下面研究这个问题。8.3.2 省时的启发式算法人们的常识是：假定各PA点之间的出行量不变，当向一个交通网络添加路段时，交通拥挤程度总会有所降低，从而网络上总的走行时间变少。但上节例8-1所说明的Braess诡异却否定了这种常识的普遍真实性。好在它主要只是一个理论上的反例，实际中其实并不经常出现，如例8-1的反例中各路段的走行时间函数与公认的BPR走行时间公式相差很大，在实际中就很少出现。如果我们忽视Braess诡异出现的可能性，那8.3.1节中的算法就可以修改为很省时的算法。忽视Braess诡异就是相当于假定：若（表示y k中为1的分量，对应在y j中也为1，即网络扩张方案y j包含y k，也记作：），则 （8-6）我们把这个假定称为“反Braess假定”。1、预算约束的DNDP启发式算法首先定义饱和可行解和非饱和可行解：如果对模型（8-2）一个可行解y k，不存在可行解yj，使：，则称yk是模型（8-2）的饱和可行解；否则称为非饱和可行解。用Qk表示第k层的所有饱和可行解的集，仍然假定b=（b1，b2，bm）已按从小到大的顺序作了排序，仍用Fk表示第k层中不可行解的集合。算法仍分两段。算法8-2：第一段：求所有饱和解。步1：初始化。对所有的k（1km+1），令Qk = Fk =。步2：令y=（1，1，1），进入第一轮工作（每轮工作考察一组向量）。问：ybT S？若是，则令Q= Q1 =y，停止；否则，令F1=y，F1= F1，k=1。步3：设第k轮工作已完成，产生了第k组的饱和可行解集Qk和不可行解集Fk，下面进行第(k+1)轮工作。 3-1：问：Fk =？若是，集合即为所有饱和解的集合，停止；否则，从Fk中任取一个解y，并令Fk = Fk y； 3-2：设y中为1的分量依次是第l1、lp个，其余分量均为0，令y j是除第lj个分量为0外其余分量与y相同的向量。 For j=1 to p 问: ？若是，将y j、y j+1、y p都存入Qk+1，跳到3-3步；否则，将y j存入Fk+1，即令： next j3-3：Fk =？若是，第（k+1）轮工作已完成，第（k+1）组所有的不可行解已求得，组成集合Fk+1，令Fk+1= Fk+1，k=k+1，返回3-1步；否则，从Fk中任取一个元素y，并令Fk = Fk y，返回3-2步。第一段算法结束，得到所有饱和可行解的集合Q。第二段是求最优解。根据反Braess假定的式（8-6），非饱和可行解肯定不比包含它的饱和可行解更优，因此我们其实只要在饱和可行解集Q中寻找最优解。第二段：求最优解。步1：初始化。设N0=（K，A0）为原始网，令y0=（0，0），在N上均衡配流，得配流结果为：，令：，y*= y0。步2：求最优解。 2-1：问：Q=？若是，输出y*，停止；否则，任取一个饱和可行解yQ，并令：Q=Q-y。 2-2：在N(y)上的进行均衡配流，得配流结果为：x*=(, xa*,)，令：； 2-3：问ML？若是，令y*= y，L=M； 2-4：返回2-1步；第二段算法结束。2、无预算约束的DNDP启发式算法令H首先表示所有2m个解向量的集合（包括可行解和不可行解）。H中每个向量对应一个二进制数，将它们按对应的二进制数升序排列，这样y0=（0，0），。在算法中，每次循环考察H中的一个解是否比目前的最优解更优；H逐渐变小，H中保留着尚未被考察的解。算法8-3：步1：初始化。设N0=（K，A0）为原始网，令y=y0，用F-W法在N上作均衡配流（也可用迭代加权法（SMA）进行配流，这样更省时一些），得配流结果为：x*=(, xa*,)，计算： ，y*= y。步2：令j=2m。步3：求最优解。 3-1：在N(y j)上的均衡配流，得配流结果为：x*=(, xa*,)，计算：； 3-2：从H中删除y j； 3-3：问ML？若是，令y*= y j，L=M；否则，对H中所有的，依次考察： ？ （8-7）若是，则由式（8-6）知，必有，yk必不是最优解，没有进一步考察的必要，故从H中删除它。步4：从H中找下一个向量。 4-1：H=？若是，y*即为所求，输出它，停止； 4-2：j=j-1； 4-3：yjH？若是，返回第3步；否则返回4-2步。算法结束。算法中3-3步是节省计算时间的关键。如果3-3步中的ML，y j不比当前的最优解y*更优，对的向量y k，当式（8-7）成立时，yk肯定也不是最优解，因此就没必要再在Nk=（K，Ak）上进行UE配流计算了。实际上，当3-3步中的ML，一般有不少向量yk（）满足式（8-7）（尤其是j较大时，当j接近2m时，有大量的这样的向量yk），这些向量在3-3步都将被从H中删去，而式（8-7）中并不要进行配流计算，这样就节省了许多计算时间。但由于第3-3步的缘故，很难准确地估计循环次数，故不能准确地估计出计算工作量来。严格地说，当出现Braess诡异现象时，用此算法求得的y*不能肯定是最优解，而我们事实上并不能保证Braess诡异现象一定不会出现，因此本算法只能算是启发式算法，求得的解是近似最优解（尽管在绝大多数情况下，它就是最优解）。例8-4：如图8-8所示的12个节点的道路网，虚线表示备选待添加的路段，共有5条,其中（6，7）是对原有路段进行改进拓宽。设除改进后的（6，7）外所有路段（包括已有的和拟建的）的走行时间函数都为：，改进后（6，7）的走行时间函数为：。初始道路网各条路段的系数aij标在图上，四对PA点对之间的出行