毕业设计（论文）-基于最大流算法的高速公路通行能力研究.doc

河南农业大学 本科生毕业论文（设计） 题 目 基于最大流算法的高速公路通行 能力研究 学 院 机电工程学院 专业班级 交通运输09级1班 学生姓名 王克楠 指导教师 曲建华 撰写日期：2013年 5 月 20 日摘 要高速公路以其大流量、快速、安全、舒适等特点已在道路交通中扮演了重要的角色并得到迅速发展，为改善我国交通运输状况及推动国民经济的发展做出了巨大贡献。然而，实际通行能力降低以及因此引起的许多问题严重阻碍着高速公路效益的发挥。应根据高速公路实际通行能力与最大通行能力之间的关系，对其进行合理的控制与管理。本文在以最大流算法为基础的条件下，对高速公路的通行能力进行深入研究。首先，介绍了研究的意义和背景。其次，说明高速公路通行能力的基础理论，从系统的角度对高速公路通行能力的基础理论进行研究，明确了通行能力的概念和分类。而后，对运筹学中的最大流算法给出了系统的、详细的介绍，说明了其基础理论构成和一些重要理论。重点说明了通过运筹学中的最大流算法计算高速公路通行能力的方法，将其转化为可用运筹学中的最大流算法进行具体计算的数学模型；介绍了对于此类问题采取的最大流算法具体步骤，并且举出算例说明问题。最后，论文总结全文的研究工作，并对今后的研究方向进行了展望。关键词：最大流算法；高速公路通行能力；计算模型The Study on High Way Traffic Capacity Based on The Maximum-Flow AlgorithmAbstract Characterized as large flux，high speed， safety and comfort，highway develops rapidly and plays more and more important role in road-based transport system， and has made great contribution to improving the existing transportation situation and promoting the development of the national economyHowever,the highway capacity reduction and the problems resulting from it have constrained badly the effect of highway transportationAccording to relevant study and practices，the traffic control and management to freeway is effective way to solving these problems Based on the maximum-flow algorithm based on the conditions, in depth study of highway capacity. Firstly, introduces the significance and background of the research. Secondly, illustrate the basic theory of the highway capacity, study the basic theory of the highway capacity from the point of view of system, defines the concept and classification of capacity. Then, for a given maximum flow algorithm in operations research system, in detail, described the basic theory and some important theories. Focusing on the calculation method of the highway capacity by maximum flow algorithm in operational research, transforming it into the mathematical model can be used to the maximum flow algorithm in operational research for concrete calculation; introduces the maximum flow algorithm is presented for such problems to illustrate the problem, and a numerical example. Finally,conclusions of all research efforts in the paper are drawn and further research directions are prospectedKey Words: The Maximum-Flow Algorithm; Highway Traffic Capacity; Computational Model目 录1 引言12 研究意义23 高速公路通行能力理论43.1 概述43.2 高速公路交通流特性53.2.1 交通量特性63.2.2 速度特性73.2.3 密度特性93.2.4 车头间距和车头时距103.3 高速公路通行能力理论113.3.1 理论最大通行能力113.3.2 理想条件下的通行能力124 高速公路通行能力的最大流计算方法144.1 最大流算法介绍144.2 最大流问题的数学描述154.2.1 网络图定义154.2.2 最大流最小割定理154.3 几种最大流算法的实现和比较164.3.1 Ford-Fulkerson 算法164.3.2 衍生割集网络极大流算法164.3.3 辅助图最短路算法164.4 高速公路道路网的简化174.5 高速公路通行能力计算问题描述174.5.1 多起点、多讫点路网的数学描述174.5.2 多起点、多讫点路网通行能力184.6 算法194.6.1 算法思路194.6.2 算法步骤194.7 算例194.8 算法小结225 结语235.1 本文主要工作235.2 本文的一些创新方面245.3 后续工作和研究方向24参考文献25致谢261 引言 近年来，我国公路建设特别是高速公路建设迅猛发展，公路交通网络已经基本形成，快捷、安全、便利已经成为公路交通管理的首要任务，通行能力是衡量公路交通运输能力的重要指标，公路通行能力研究对于科学、合理发挥公路交通运输功能，最大限度的满足公众需求有着重要的作用。 相对于普通公路而言，高速公路己取得了巨大成功，带来了巨大的经济与社会效益，使服务水平大大提高。但随着国民经济的飞速发展，汽车数量急剧增加，人们对交通的需求大幅度增长，造成了交通供求关系的不平衡，尤其是交通高峰期的市区高速公路。因而，高速公路在运行中始终存在着交通拥挤、交通安全和环境污染等问题。 交通拥挤是指交通需求(一定时间内想要通过道路的车辆数)超过某道路的交通容量时，超过部分的交通滞留在道路的交通现象。交通拥挤的根本原因是交通供求关系不平衡，在造成交通拥挤的许多需求因素中，大部分可归纳为二类：(1)常发性的过大交通需求；(2)偶发性暂时通行能力降低，如发生交通事故或进行公路养护等。与之相对应，交通拥挤可分为常发性交通拥挤和偶发性交通拥挤。常发性交通拥挤是指在某些特定时期经常发生的交通拥挤现象；偶发性交通拥挤是指由于诸如事故或其它特殊事件等随机事件造成道路实际通行能力下降而引起的交通拥挤现象。 引起高速公路常发性拥挤的原因主要分为两类：运行因素和几何因素。与拥挤有关的运行因素有：(1)交通需求超过容量：拥挤是供应和需求关系的一种直接结果，交通量过大的高速公路必将发生拥挤。(2)不受限制的入口匝道：高速公路的瓶颈和伴随出现的拥挤经常是由于入口匝道不受限制的结果。在这种情况下，匝道上的车辆，加入高速公路上的交通流时，将产生超过容量的需求，在高速公路主线上产生交通拥挤，并导致瓶颈上游车辆出现排队现象。(3)出口匝道排队：高速公路主线上的拥挤，有时是由于出口匝道车辆排队引起的。当出口匝道上的需求超过了能处理通过汇合区交通的能力，或超过了匝道下流的一个交叉路口通过交通的能力，或者匝道本身缺乏存贮停车的能力时，最终的结果是车队一直排到高速公路上，引起主线拥挤。(4)收费站收费：高速公路主线上或匝道上拥挤经常由于收取过路费，车辆在收费站停下来交费引起的。另一种引起常发性交通拥挤的原因是由于道路几何上的缺陷(例如：在直行车道末端出现“车道减少”等)造成的通行能力降低。这些称为几何瓶颈路段的通行能力低于高速公路邻近路段的通行能力。当瓶颈上流的交通需求超过瓶颈路段的通行能力时，就产生交通拥挤并在高速公路上游车道形成排队现象。 随机事件造成道路容量下降而引起的延误和危险，构成了另一类同样严重的高速公路交通拥挤问题。这类问题称为高速公路偶发性问题，包括交通事件、交通事故、不利的气候条件及道路的维护等。通常偶发性问题将会引起交通量的减少，造成交通拥挤和延误。 通行能力分析与交通量适应性分析，不仅可以确定公路建设的合理规模及合理建设模式，为公路网规划、公路工程可行性研究、公路设计、公路建设后评估等方面提供更为科学的理论依据，还可以为公路交通管理、控制提供信息支撑，为交通诱导系统、紧急调度系统、出行服务系统提供决策支持。通行能力研究因其在智能交通体系中属于基础支撑性作用而显得尤为重要，通行能力测试与评估对于通行能力适应性分析更是不可缺少的，其研究工作有着很强的理论价值和现实作用。基于上述背景，作者开展论文课题研究。本课题主要采用运筹学中的最大流算法，对高速公路通行能力的计算方法进行研究，得出有关高速公路通行能力的相关结论。2 研究意义 交通运输无论是过去、现在和将来，都是人类进步的重要物质基础。随着改革开放的深化，我国的国民经济实力不断增强，交通运输也得到空前迅猛发展。1990年，全国公路总里程突破100万公里，达到102万公里，1992年，我国年产汽车量突破100万辆，1999年底，高速公路总里程突破1万千米。截止2000年底，全国公路总里程为140万公里，其中，高速公路1.6万公里，仅次于美国、加拿大，居世界第三位。根据交通部“十二五”计划和2020年长远规划，在最近的十多年间，我国的公路里程还将大幅度增加，到2020年，全国公路通车里程将达到230万公里，其中，高速公路将达到5.5万公里，二级以上公路比重达到20和25。高速公路建设投资巨大，每公里造价高达20005000万元，建造一座普通立体交叉口需投资2001000万元左右。而道路基础设施建设的主要决策依据为预测交通量及道路设施的通行能力。由于我国目前还没有科学的通行能力分析方法与标准体系，道路设施通行能力的分析不够准确，导致公路建设标准过高或平行建设，以致建设资金超前投入而造成巨额经济损失。此外，由于对某些已有道路或交叉口的通行能力估计过高，使得在交通严重阻塞时仍得不到改建，或在建成后不久就产生严重交通阻塞而影响公路运输效率，造成巨大经济损失。因此，合理确定公路建设的规模和标准，将是公路建设中成本控制的关键，而确定公路建设规模与标准和设计总体方案的重要依据之一便是道路通行能力。作为道路交通建设的一项基础性工作，通行能力分析与交通量适应性分析，不仅可以确定公路建设的合理规模及合理建设模式，还可为公路网规划、公路工程可行性研究、公路设计、公路建设后评估等方面提供更为科学的理论依据。工程项目后评估路网管理公路通行能力研究交通流特性研究交通构成 车速分布 三参数关系换算系数通行能力研究 基本路段 交叉路口公路勘察设计可行性研究公路网规划图2-1 道路通行能力研究意义及结构框图 从高速公路运营管理层面看，高速公路面临的主要问题就是交通拥挤。交通拥挤造成旅行时间无法预测、运行成本增加、事故率提高、能源浪费和环境污染加剧等不良的影响，从而形成巨大经济损失。因而如何避免拥挤或减轻拥挤造成的影响，保持高速公路高速、安全、舒适和高效的特性，不仅是发达国家也是我国高速运营中要解决的主要问题。解决此类问题有二种途径：一是通过几何改善和路网建设来改善瓶颈路段的通行能力，从而扩大交通供给。其基本解决方法是通过路面和路肩的重新划分或通过整个横断面的改建来增加车道，与在原有的线路上附加支线。例如在美国，前后共花了30年修建和改造州际高速公路网。此种方法费用较高，且受资源和环境的制约。第二种途径是对现有的高速公路进行交通控制和管理，从而达到减缓交通拥挤和提高通行能力的目的。此方法经济有效、不受资源和环境的制约。且随着运筹学的兴起和发展，逐渐成为研究和解决高速公路运行问题的主要途径。3 高速公路通行能力理论3.1 概述 道路通行能力又称道路容量。简言之，是指道路的某一断面在单位时间内所能通过的最大车辆数。美国HCM对道路通行能力给出了如下定义：通常，一种设施的通行能力，规定为在一定时段和通常道路、交通、管制条件下，能合情合理地期望人和车辆通过车道或道路的一点或均匀断面上的最大小时流率。HCM还将通行能力分为基本通行能力、可能通行能力和设计通行能力。 基本通行能力是指道路和交通都处十理想条件下，由技术性能相同的一种标准车，以最小的车头间距连续行驶的理想交通流，在单位时间内通过道路断面的最大车辆数。也称理论通行能力，因为它是假定理想条件下的通行能力，实际上不可能达到。 可能通行能力是指考虑到道路和交通条件的影响并对基本通行能力进行修正后得到的通行能力，实际上是指道路所能承担的最大交通量。 设计通行能力是指用来作为道路规划和设计的标准而要求道路承担的通行能力。 通行能力影响因素主要有： (1) 道路条件 道路条件指的是街道或公路的几何特征，包括：交通设施的类型及其所处环境、每个方向的车道数、车道和路肩宽度、侧向净空、设计速度以及平、纵线形。 其中，交通设施类型是关键，是否存在不问断交通流，双向交通流之间是否有中央分隔带等都明显地影响交通特性和通行能力。 (2) 交通条件交通条件是指交通流中车辆种类的分布(交通组成)、设施中可用车道的交通量和交通分布以及交通流的方向性分布。车辆类型的分布是影响道路通行能力的主要交通流特性。如重型车辆，由于其动力性能较小客车差，尤其是加速、减速和保持上坡车速的能力不如小客车，因此在很多情况下不能保持跟上小客车，从而在车流中形成的大间隙很难由超车来填补，这就造成无法完全避免的道路空间的低效利用。也正是基于此原因，高速公路在坡度较大的上坡路段要考虑设置爬坡车道。 车道使用和方向性分布是影响通行能力的另外两个因素。一般而言，每个方向的交通流各占50左右时，交通运行条件最好。力向性分向很不平衡时，通行能力就会下降。车道分布则体现出靠路肩的车道承担的交通量较其他车道少。 (3) 管制条件 间断流设施(如平面交叉口)对交通流流向实行有效的时间管制，是影响道路通行能力的另一关键因素。这类交通设施中最关键的控制设施是交通信号。使用的控制设备、信号相位、绿灯时间分配和信号周期长度均影响车辆运行。 停车和让路标志也影响通行能力，但不起决定作用。停车或让路标志将优先通行权永久分配给主要道路或街道，次要道路的车辆必须在主线交通流中寻找间隙穿越。因此，次要道路的通行能力就取决于主要道路的交通条件。能显著影响通行能力的管制条件还有限制路边停车，车辆转弯限制以及车道使用管制等。如限制路边停车能增加公路或街道的有效车道数。转弯限制能消除交叉口车流的冲突点而提高通行能力。车道使用管制可给各种流向明确地分配有效道路空间。它们既可以在交叉口使用，也可以在关键的干道上开辟变向车道。3.2 高速公路交通流特性 道路中运动车辆构成的车流称之为交通流。人(驾驶员)、车(车辆)、路(道路)是构成交通流的三个基本要素。行驶在道路上的各种车辆，其运行状态随道路条件，交通环境和驾驶员特性而有不同的变化。尽管这种变化很复杂，但通过大量观测分析，发现它们是具有一定特征性倾向的。交通流运行状态的定性、定量特征称为交通流特性。用来描述和反映交通流特性的物理量称为交通流参数。这些特性参数在道路交通的规划、设计和管理中部有重要使用价值。 交通流参数可分为两大类：宏观参数和微观参数。 宏观参数，描述交通流作为一个整体表现出来的特性，包括：交通量(流率或流量)、速度和密度。微观参数，描述交通流中彼此相关的单个车辆之间的运行特性，如车头时距和车头间距。3.2.1 交通量特性 交通量是指单位时间内，通过道路某个地点或某个断面的车辆数。 交通量是一个随机数，不同时间、不同地点的交通量都是变化的。交通量随时间和空间而变化的现象，称之为交通量的时空分布特性。交通量时刻在变化，在表达方式上通常取某一时间段内的平均值作为该时间段的代表交通量。 （1） 日交通量 日交通量是以一天为计量单位的交通量(辆/d)，在交通流的宏观分析中，通常以所观测到的日交通量为基础。一年中，在指定地点的平均每日交通量，称为年平均日交通量AADT(Average Annual Daily Traffic)。在全年所有的工作日内，在指定地点的平均交通量，称为年平均工作日交通量AAWT(Average Annual Weekday Traffic)。在少于一年的某个时间段内，在指定地点的平均每日交通量，称为平均日交通量ADT(Average Daily Traffic)。平均日交通量可用半年、一个季度、一个月、周或几天作为一个时间周期末测定。在少于一年的某个时间周期内(一个季度、一个月或一周)，在指定地点所有工作日的平均每日交通量，称为平均工作日交通量AWT(Average Weekday Traffic)。（2） 小时交通量日交通量在道路规划中有一定参考价值，但它不能单独地作为道路设计、计算和分析的依据。小时交通量是以小时为计量单位的交通量(辆/h)，在一天的24h内，小时交通量的差异很大。一天中，具有最高小时交通量的那一小时称为“高峰小时”。高峰小时交通量通常是指单向的，上行和下行两个方向的交通量要分别统计。（3） 流量 在不足1h的时间内所观测到的交通量可以扩大为与之等效的小时交通量，称为流量。流量与小时交通量的区别在于：交通量是在一段时间间隔内，通过一点的观测或预测得到的实际车辆数，而流量则表示在不足l h的间隔内通过一点的“当量小时车辆数”。 在进行交通分析时，采用多长时间作为观测的最小时间间隔并没有统一的标准。有的采用1分钟那样短的时间段，有的采用30分钟那样长的时间段。时间间隔过短，流量的变化规律不稳定，很难看出它与小时交通量的联系：时间间隔过长，又极易与小时交通量重合。以50辆/h作为统计流量区间，以15分钟、5分钟和1分钟三个统计间隔进行了速度和密度的平均计算。比较以15分钟和1分钟作为统计间隔的统计结果发现：1分钟的平均速度与15分钟的平均速度相比基本都偏大，密度相对偏小：而各流量区间的速度差和密度差的均值分别为-2.1 km/h和0.6 pcu/km，标准差分别是2.8km/h和O.4 pcu/km。可见这两组统计结果己经发生了偏差，特别是速度，但变化幅度不大。与15分钟的统计结果相比，以5分钟作为统计间隔时，从总体的速度、密度上比较，其统计结果基本一致；而当1分钟作为统计间隔时，相应的统计结果存在差异。3.2.2 速度特性 车速是指车辆在单位时间内通过的距离。 设行驶距离为Z，则车速可用Z以形式表示。按Z的取值不同，可定义各种不同的速度： （1） 地点车速 这是车辆通过某一地点时的瞬时车速，因此观测时Z取尽可能短，通常以2025m为宜，用作道路设计、交通管制规划资料。 （2） 行驶车速 这是从行驶某一区间所需时间(不包括停车时间)及其区间距离求得的车速，用于评价该路段的线形顺适性和通行能力分析，也可用于计算道路使用者的成本效益分析。 （3） 运行车速 是指中等技术水平的司机在良好的气候条件、实际道路状况和交通条件下所能保持的安全车速，用于评价道路通行能力和车辆运行状况。 （4） 行程车速 行程车速又称区间车速，是车辆行驶路程与通过该路程所需的总时间(包括停车时间)之比。行程车速是一项综合性指标，用以评价道路通畅程度，估计行车延误情况。要提高运输效率归根结底是要提高车辆的行程车速。 （5） 临界车速 这是指道路理论通行能力达到最大时的车速，对于选择道路等级具有重要作用。 （6） 设计车速 设计车速是指在道路交通与气候条件良好的情况下仅受物理条件限制时所能保持的最大安全车速，用作道路线形几何设计的标准。 行车速度与交通量一样，也是一个随机变量。研究表明在乡村公路和高速公路路段上，运行车速一般呈正态分布，在城市道路或高速公路匝道口处，车速比较集中，一般呈偏态分布。 在交通流中，每辆车(统计学中称“个体”)的速度都不尽相同。因此，交通流本身不可能用一个精确的速度值来表示，只能用若干单个车辆的速度分布来表示。对离散型的车辆速度分布，可用统计学的处理方法，即用平均的或有代表性的数值(集中趋势的描述值)来近似地代表特定的交通流整体。 平均车速可以用两种方法来计算，这两种方法的本质涵义及计算结果都有所不同。 时间平均车速是指在特定的时间区间内，通过道路某一地点的所有车辆点速度的算术平均值。 区间平均车速是指在特定的时间区间内，占据一定道路区间的所有车辆的速度平均值。 实质上，时间平均车速是点的量测；而区间平均车速是与道路长度有关的量测。 在数学上，区间平均车速是一种调和平均值；而时间平均车速则是各个车辆速度的算术平均值。 通行能力研究中采用的速度标准是平均行程速度。平均行程速度可由区间观测法直接观测得到，其原理是：采用牌照法(录像回放记录)记录观测路段两端所通过的车型、车号(取后四位数)及通过的时间，然后根据同一车号的每辆车的行程时间，再由被观测路段的长度，可算得： (31)式中： V路段平均运行速度； L路段长度； 第i辆车的行程时间： N观测的车辆数。地点速度和区间速度的关系为 (32)式中： 路段平均行程速度(区间速度)； 地点速度； 地点速度均方差。3.2.3 密度特性 密度是指特定长度道路上瞬间存在的车辆数。通常用每公里车辆数或每车道每公里车辆数来表示。密度是一个描述交通运行的重要参数，它表示车辆之间相互接近的程度，反映了交通流中驾驶的自由程度。 流率、速度和密度之间的宏观关系表达式为： (33)式中：C交通量； V行车速度； D交通密度。图3-1 速度、密度和流率关系示意图 密度在这三个交通流参数中是最重要的，因为它直接反映了交通需求量。尽管交通工程中常用每秒通过多少辆车这个评价指标，但对于交通需求说，这个指标不够形象。交通需求是指在有限长度的道路上，存在多少数量的交通工具，用密度来表示更为确切，更易于理解。密度还可以近似地用来衡量驾驶员操纵车辆的舒适性和灵活性。 密度有三个特征值：最佳密度、零密度和阻塞密度。最佳密度定义为流量达到最大时的密度。在实际交通流中，并不存在零密度和阻塞密度两种极端理想状态。只要道路开放，密度始终介于这两种极端密度之间。 由于密度是瞬时值，随观测的时间或区间长度的变化而变化，而且反映不出与车辆长度和速度的关系，尤其当车辆混合行驶时，密度的高低，并不能明确地表示出交通流的状态，所以在交通工程中又引用了车道占有率的概念来表示车流密度。车道占有率包括空间占有率和时间占有率两种。（1） 空间占有率 在道路的一定路段下车辆总长度与路段总长度之比的百分数称为空间占有率。车流密度只能表示车流的密集程度，而空间占有率则能反映某路段上车队的长度。 （2） 时间占有率 在道路的任一路段上，车辆通过时间的累计值与观测总时间的比值，以百分数表示，即为时间占有率。任何已知交通设施的最大流量就是它的通行能力。这时出现的交通密度称为临界密度，相应的速度称为临界速度。当接近通行能力时，流量趋于不稳定，因为交通流中有效间隙更少。达到通行能力时，交通流中不再有可利用的间隙，并且车辆进出设施，或在车道内部改变形式所带来的任何干扰，都会产生难以抑制或消除的障碍。除通行能力外，任何流率能在两种不同的条件下出现：一种是高速度和低密度，另一种是高密度和低速度。曲线的整个高密度、低速度区间是不稳定的。它代表强制流或阻塞流。曲线的低密度、高速度区间是稳定流范围，通行能力分析正是针对这个流量范围进行的。3.2.4 车头间距和车头时距 流量、车速和密度都是交通流的宏观参数，它们是对给定的时间和区间内的交通流，用一个数值在整体上予以描述。车头间距和车头时距则是交通流的微观参数。车头间距是指一条车道上前后相邻车辆之间的距离，用车辆上有代表性的点来测量，如前保险杠或前轮。车头时距是前后两辆车通过行车道上某一点的时间差，也是用车辆上有代表性的点来测量。车头间距和车头时距与宏观参数的关系如下： （3.4） （3.5） （3.6）式中：平均车头间距（m）； 平均车头时距（s）；3.3 高速公路通行能力理论3.3.1 理论最大通行能力根据Green-shields关于速度与密度之间的线形研究关系式可得： V=（1-D/Dj） （3.7）式中：V速度(km/h) D度(pcu/ln/h) 自由流速度(km/h) 阻塞密度(pcu/ln/h) =1000/（） 汽车车身长度 汽车刹车的安全距离由式3.3和3.7可得： C=（1-D/）D （3.8） C=（1-V/）V （3.9）令/d D=0，可得最大通行育肇力条件下的车辆行驶临界密度=/2。令/d V=0，可得最大通行育肇力条件下的车辆行驶临界密度=/2。则理论最大通行能力为：=0.25以设计车速为自由流速度，按照公路工程技术标准的规定，车辆的长度:小客车6m、载重汽车12m、鞍式列车16m，前后车的安全距离取5m。则不同设计车速下的理论最大通行能力见表3.1。表3-1 理论最大通行能力车辆类型设计速度km/h车头间距m车辆阻塞密度pcu/km通行能力pcu/(ln*h)小客车1201190.9127271002273801818601363载重汽车801758.82117660882鞍式列车802147.6195260714利用抛物线模型计算的理论通行能力远大于实际测到的最大交通量，且不能反映通行能力与自由流密度的关系。在实际应用中，一般根据实测数据回归所得的自由流速度和阻塞密度整理后计算通行能力。3.3.2 理想条件下的通行能力通行能力是指在正常的道路、交通、管制条件下，在规定时段内，人和车辆能合理地期望通过一条车道或道路某一断面或均匀路段所能达到的最大小时流率。对于高速公路来说，影响通行能力的主要因素有道路条件(道路设施等级、车道数、车道宽度、路肩宽度和侧向净空、设计速度及道路平纵面线形)，交通条件(车辆的类型、车道使用和方向分布)。高速公路车辆运行状况为非间断交通流，其交通特性为交通流中车辆之间，以及车辆与道路线形、道路外部环境之间的相互影响。非间断交通流的理想条件为车行道宽度366m，车行道与路边或中央分隔带最近障碍物之间的距183m，交通流中车辆均为小客车。（1） 基本通行能力 基本通行能力为理想道路与交通条件下，一条车道单位时间内所能通过的最大车辆数，由车辆的行驶速度和前后车头间距决定。 车头间距由前车的车辆长度，两车间的安全距离、驾驶员采取刹车措施的反应距离及前后两车刹车的距离差组成。 驾驶员的制动反应时间与获得的信息是期望的还是非期望的以及信息量的多少不同而不同。根据Johann-son和Ru-mar对驾驶员制动反应时间的测定，中位数上驾驶员对期望信息的反应时间为066347s，对非期望信息的反应时间l4.5s，对单纯需采取制动的信息，其期望信息的反应时间约为1.12s，对非期望信息的反应时间为1.54s。第85百分位上驾驶员对期望信息的反应时间为l5.1s，对非期望信息的反应时间为1.357.7s，非期望信息的反应时间增加约为35%。对单纯需采取制动的信息，取期望信息的反应时间约为1.64s，非期望信息的反应时间为2.5s。 对于车头间距。当K=1时，前车为瞬时停车，其车头间距最大，定义为充分安全间距；此时下辆的行驶不受前车的任何影响，车辆的速度可认为是自由交通流速度。当K=0时，前后车采取了相同的制动特性，是实际行车过程中的最理想状态，其车头间距定义为基本安全间距；此时，道路的通行能力最大，交通流中的任何变化都将对行车速度产生影响。从道路交通实际运行情况看，前车发生瞬时停车的可能性很小，车辆之间的间距主要由驾驶员根据道路条件、交通变化、环境条件、车辆的操作性能、驾驶的熟练程度以及主观愿望选择行车间距，实际行车间距应介于充分安全间距与基本安全间距之间，定义为期望安全间距，K=01。为满足驾驶员自身安全感的需要，当行车间距与期望安全间距不同时，驾驶员会采取措施调整行车间距。（2） 基本安全间距的通行能力基本安全间距是车辆在正常行驶条件下，车流处于基本稳定的跟车状态时车头之间的间距。在基本安全间距下，道路条件对前后车的影响相同，通行能力计算与道路条件无关。此时，交通流中没有可用的间隙，是稳定交通流能适应的最小车头间距，车辆在交通流中行驶受到限制，对驾驶员提供的身、心舒适水平非常差，交通流中的任何扰动，都会波及整个交通流，其V/C值接近1.0，服务水平相当于四级。因此，从行车安全和车流稳定角度分析，基本安全间距下的通行能力应为高速公路的基本通行能力。（3） 充分安全通行能力 充分安全间距是车辆处于自由交通流行驶状态下的车头间距。交通流中车辆的行驶性能几乎不受影响，给驾驶员的身心提供了较高的舒适度，行车中的干扰很容易消除，较小的交通行车障碍可能会降低服务水平，但服务水平可迅速得到恢复。但也反应出在充分安全间距下，最大通行能力对应的临界车速约为设计速度的50，不能体现高速公路作为快速通道的作用，而在充分安全间距下的通行能力曲线在达到最大值后下降十分缓慢，因此，宜采用理论通行能力曲线与充分安全间距曲线相交处的车速作为临界速度(相当于一级服务水平的车速)计算其通行能力。（4） 期望安全间距通行能力 当车头间距大于基本安全间距时，驾驶员处于保守行驶状态；当车头间距小于基本安全间距时，驾驶员处于冒险行驶状态，这时驾驶员通常会通过调整车速以保证行驶期望的安全间距。一般的驾驶行为其车头间距应处于基本安全间距与充分安全间距之间。在基本安全间距下，车辆超车，可能会导致车流处于不稳定状态。由于国内车辆性能差距较大，超车现象不可避免，且互通式立交车流汇入处对主线的车流也造成干扰，驾驶员也不可能一直处于紧张的驾驶状态，因此，期望安全间距的确定要保证一定的超车频率，应在基本安全间距的基础上增加一定的安全系数，为驾驶员提供较为宽松的驾驶环境。根据一般等级公路双车道理想情况应提供30的超车机会和为驾驶员提供一定的驾驶舒适度，将基本安全间距的1.5倍作为期望安全间距是比较合适的。期望安全间距的确定与车辆实际行驶速度、车辆密度及道路条件相关。4 高速公路通行能力的最大流计算方法4.1 最大流算法介绍 高速公路是国民生活的命脉，有效的高速公路网络对实现城市的功能和促进城市社会经济的发展起着至关重要的作用。近几年，随着国民经济的增长和城镇人口的增加，城市化进程明显加快，城市中居民出行总量增加，出行机动化程度越来越高，加之交通设施建设的相对不足和交通管理的滞后，使城市诸多交通问题日渐突出，如最明显的交通拥挤问题、交通安全问题、交通引起的环境污染问题和交通对土地、燃料等资源的消耗问题等。目前，国家已确立汽车产业为支柱产业，小汽车开始走进普通居民家庭，这将使我国的城市交通面临更加严峻的挑战。此时，对高速公路通行能力的问题进行研究也就显得势在必行。 高速公路通行能力是城市交通规划与评价的一项重要指标。对城市道路网容量问题进行研究，可以对城市交通系统的供求平衡进行分析，对指导和确定城市合理的发展规模，制定路网规划方案以及制定可持续发展的交通战略等方面有着重要的理论和实践意义。研究道路网容量的方法有很多种，本文是以图论中的网络最大流理论为基础的最大流算法为基础来研究城市道路网的容量问题的。4.2 最大流问题的数学描述4.2.1 网络图定义最大流问题是建立在有向图(网络)上的一种数学模型:即给定有向加权图G(V，E）,其中V代表图的顶点集合V=n；E代表边的集合E=m。边(i，j)上的权值称做容量，记为u（i，j)。在图中指定2个项点s和t，分别称为源和汇。最大流问题是在网络G上确定一个函数x，使另一个函数f最大化。其中x和f满足如下关系： 其中边(i，j)对应的向量x（i，j）称为该边上的流。记所有边上的流的集合为x，相应的值f称作x的流量。满足上式的流称为可行流。最大流即流量最大的可行流(记为和)。尽管网络中边的容量u（i，j）可以是任意的，但数学模型是为解决实际问题而建立的。因此，在研究过程中，一般只考虑边的容量u（i，j）为整数。最大容量U=maxu(i，j)E为网络节点数的多项式量级网络上的最大流问题。4.2.2 最大流最小割定理 把一个网络流的顶点集划分成2个集合S和T，使得源点sS且汇点tT，割(S，T）的容量C（S，T）=，其中uS且vT。 从直观上看，截集(S，T)是从源点s到汇点t的必经之路，如果该路堵塞则流从s无法到达t。于是我们可以得到下面的定理：任意一个流网络的最大流量等于该网络的最小的割的容量。4.3 几种最大流算法的实现和比较4.3.1 Ford-Fulkerson 算法 标准的Ford-Fulkerson算法是通过对节点进行标号的方法寻找增广路。 算法基本思路：（1）寻找增广链；（2）确定增广链上可能增加的附加流量，加到该链的各弧上，然后重复此过程，直到不能再找到增广链为止. 路网上某边的流量等于路段通行能力的弧就是最小割集中的弧。路网容量为所有割集的通行能力之和。 该算法是最早的最大流算法，受当时数学和计算机发展的限制，由于此算法不适合大规模编程，影响了其应用推广。4.3.2 衍生割集网络极大流算法衍生割集网络极大流算法（Evolving Cut Set Method，简称ECS法）是专门解决复杂的、随机开放型网络问题的。该模型的原理是：给定初始发点集和收点集后，从发点集开始逐步扩大衍生源集，衍生源集与衍生源集的邻接点集之间不断构成网络的s-t割集，在衍生源集逐步扩充的过程中，网络上各中间点先后由发点转化为收点，直至到达最后的收点集（即最初给定的收点集）。该算法对运输网络的容量分析比传统的网络流模型更为实用；利用该方法不但可以求出最小割集容量，而且可以求第二小割集容量、第三小割集容量等等，这也是别的网络流模型难于做到的；而且根据最小割集的位置，可以找到制约网络总体容量的关键路段，从而决定规划、建设的优先权。根据次小割集、第三小割级等与最小割集容量相近的割集位置，判断在最小割集容量扩充后，关键路段将如何转移，这样，为路网规划布局的均衡性提供了依据。不仅如此，ECS算法可以方便地求出网络的最大容许流量，与网络上实际的流量比较，可以判断网络的总体负荷，交通网尚存的服务潜力。4.3.3 辅助图最短路算法 最短路与最小割集具有对偶性，通过集合理论中的De-morgan律，两者间是可以互相转化的，因此网络G的任意最小割集都可以通过求其辅助图的发点到收点的最短路得到（具体介绍从略）。此方法适用于多收点与多发点的路网系统，无向路网或混合路网。4.4 高速公路道路网的简化本文中的高速公路网指的是城市中承担大量客、货运交通的平面主要道路网络。首先，根据图论中的基本概念，城市道路网中的双向路段可以简化为连接路段的两个端点、方向相反的两条弧，单行道为一条单向弧，交叉口对应网络中的顶点。这样，城市道路网就是点(交叉口)和弧(路段)都有容量约束的混合容量网络。为方便研究，需要将点容量转化为弧容量。按各交叉口的容量情况对路段容量进行折减，使折减后的顶点不再有容量限制，而此时的弧容量是综合考虑了交叉口和路段容量后的新容量。这样一来，城市道路网可以被简化为只有弧容量约束的有向网，用D=(V，A)表示，其中V是网络中节点的集合，A是网络中弧的集合。交通问题里，交通流的起、终点具有随机性，也就是说交通流的源点集(起点集)和汇点集(终点集)是随机的。由于城市中重要的交通集散点(就业区、商业中心、居住区、城市出入口道路、车站、码头、货场等)是相对固定的，为了简化计算，假定一段时间内运输网的源点集和汇点集是确定的。并用S表示源点集，T表示汇点集。经过以上简化，城市道路网的容量问题图论中给定源点集和汇点集的有向网的最大流问题。4.5 高速公路通行能力计算问题描述4.5.1 多起点、多讫点路网的数学描述通过对多起点、多讫点交通路网图的交通特性分析，可将其看作平面有向赋权连通图。图的n个顶点（i=1，2，n）表示路网交叉口，（ j=1，2，m）表示路网的m 个起点，（k=1，2，q）表示路网的q个讫点，图的有向边表示路网的路段，用表示，i表示路段起点，j表示路段终点，所有路段集合记为E，则路网记为G（V，E）。在路网G（V，E）中，各路段的最大允许交通量为C（e）=C（，）。4.5.2 多起点、多讫点路网通行能力 对于这种路网增设和两个虚拟顶点，且用正向路段将与路网中所有起点相连，用正向路段将所有讫点与相连。此时将作为新路网的单起点，将作为新路网的单讫点，同时指定增设的虚拟路段最大允许交通量为正无穷大（M）。这样就将路网改造为单起点、单讫点路网图，把问题归结为求一个发点和一个终点的网络最大流算法。 （1）路网中的路段交通量 在路网G（V，E，C）中，定义=，并称为路段的路段交通量，简记。若以v（f）表示路网从至的流，且满足：0以及当i=s时，=；当is时，=0；当i=t时，=-，则称为路网G（V，E，C）中至的可行流，式0为任意路段最大允许交通量限制。当i=s时，=；当is时，=0；当i=t时，=-三个条件统称为交通量平衡条件。（2）路径交通量调整值 确定出一条由至的有向路径，即所有路段的方向与该路径的方向一致。该路径上各路段的最大允许交通量和路网中的路段交通量，按下式确定该路径的交通量调整值：=min（-）式中的初始值为0。在路网中所有至的路径中，调整值最大的称为最大调整值 ，该路径称为最大可行调整路径。（3）路网简化将路径上所有路段交通量加上f，该路径中至少存在一条路段达到最大允许交通量，在路网中删去该路径上交通量达到饱和的路段，使路网简化。对路网中路段权值进行修改：4.6 算法4.6.1 算法思路 利用人工智能搜寻方法，寻找所有由至的有向路径，然后计算每条路径的调整值，选取最大调整值所在路径进行路网简化，再在简化的路网中重复运算，直至路网中没有由至的有向路径从为止。此时得到的各路段的交通量分配就是起点至讫点达到最大出行量时的方案，也就是整个路网的最大交通量。4.6.2 算法步骤 （1）先将路网改造为单起点、单讫点路网，将各路段的当前交通量置为零。 （2）搜集由至具有最大调整值的路径。 （3）简化路网。 （4）在简化后的路网中若存在可径路径，转（2），否则转（5）。（5）将由起点出发的所