12Braess悖论与交通系统流量分配优化模型

12Braess悖论与交通系统流量分配优化模型悖论与交通系统流量分配优化模型；刘奇志聂永革；（空军指挥学院，北京）；摘要本文在分析悖论现象的基础上，探讨；法，通过讨论可以使我们对交通泉统的管理有更深捌的；关越词交通景坑藏量优化模曩悍论；（；锄明悖论与交通系统流量分配优化模型刘奇志聂永革（空军指挥学院，北京）摘要本文在分析悖论现象的基础上，探讨了交通系统中流量的优化分配模型及求解方法，通过讨论可以使我们对交通泉统的管理有更深捌的认讽关越词交通景坑藏量优化模曩悍论（，嘶吨）锄明，“矗，黯曲赡。”，叩，一、前言交通系统是整个社会体系的重要组成部分，随着经济的发展和汽车保有量的增加，交通拥堵已成为国内外大中城市常见的个通病。比如，近年来，日益严重的堵车问题已成了北京交通的难题。造成交通拥堵的直观原因是城市道路建设速度赶不上机动车增长的速度。即车与路的矛盾。然而，如果车量不变，单靠扩充交通网络中道路的通行能力，就一定能缓解交通拥挤，减少交通阻塞吗？交通悖论正是从这个角度向我们提出了值得深入研究的问题。交通悖论原意是指：在交通网络中扩建道路，反而可能引起交通时间增加的现象。这个现象。听起来使人费解。实际上悖论并不限于交通，在其它许多系统中（例如在经济系统、电路网络系统等）都有可能象运输系统一样产生相同的悖论行为。年悖论提出以后，有许多专家（），（）、和（）、（）、和（）、和（）、（）等）对悖论从不同的角度进行过深入的研究。但他们的研究多限于悖论的成因。本文利用系统工程的方法，在分析悖论成因的基础上，提出交通系统流量分配优化模型并探讨了模型的求解方法。二、问题描述一个交通系统可以概瞎地分为两个侧面，一是使用道路的主体，即通过道路系统的流（包括需要运送的人员、物资及装载人员、物资的车辆）。另一方面是承担交通流的客体。即道路系统的状况，也就是哪些点之闻有道路相联，这些道路的质量如何。二者之间还会相互作用，如通过某路段的通行能力可能会随流量的增大而变弱道路系统可用网络圈（，）表示，其中是结点集，是弧（路段）集，为叙述方便，在一般情况下总假定两点之间没有相重的弧，即（。对于使用交通系统的主体而言，假设他们有一个出发点和一个目的地，而且有一定的运输量。穿越网络的运输量构成了一个“流”。所谓“流”是指定义在上的一个非负函效，（），厶满足：对不是出发点和目的地的点而言，流入的量必须等于流出的量，即厶，一乙对于一切，成立对出发点，流出量等于总流量同样，对目的地：，流入量也等于总流量。即厶一厶一，在这个网络上，假设对任一条弧（，），流量凡遵过它的时间为：一口。其中为路段（，）上的通行时间为路段（）上的自由交通时间它是一个常数，体现了路段的长短；风为路段（，）上的耽误系数（即在路段（。）上，每增加一个单位流量所增加的交通时间）它也是一个常数，体现了路段的质量如何使用交通系统，用什么指标来度量交通系统的效率，站在不同的立场观察同题可以得出不同的结论。但大致可分为四种情况对于使用系统的个体而言，它总是希望自己能够尽快地通过网络，如果个体用户不能得到交通系统的变化信息，则总是选那些自由交通时间最短的路，即一般意义下的最短路。，如果所有用户都能了解交通系统中各路段的拥挤情况，允许个体自由竞争而不加任何限止，其结果是在从出发点到目的地的所有路上所花的时同都相等时，系统达到平衡。对于整个系统的管理者而言，不能仅考虑某个个体通过网络的快慢，丽是考虑系统的整体效益，度量系统的效益可能有多种指标，一种常用的指标是全部流量通过网络花费的总代价。驿（，）乙，。?）其寺。啦。用全部流量通过网络时所花费的总时间作为度量目标。、即（）。点，【?）其中是从出发点到目的地的所有流量不为的路的集合。作为系统的管理者，总是希望兼顾和中两个指标，即总代价不要太大，总的通过时间不要太长。三、悖论的启示年，用一个四边网络指出了悖论现象。现在用本文给出的表达式叙述最初的示例。假设有一个四边网络（如图所示），出发点为，目的地为，从出发点到目的地有两条可能的路（，），（，）。当增加一条新的路段（户，），从出发点到目的地有三条可能的路和（，），（，）和（，）。（如图所示）户图假设在路段（户，幻和（，），自由交通时间相等且为：耽误系数相等为：卢，艮在路段（，）和（，）上，自由交通时间及耽误系数亦分别相等且为：，又设从到的总流量在图所示的网络上，假设个体知道全局信息，允许个体自由竞争，最终导致从出发点到目的地的两条路上花的时间相等，以此为条件求出各路段弧上的流量，知九，鼍一这时，总流量平均分配到路（，）和（，），总代价为：。埘一，一，一花的总时间为：丁当增加路段（，）后，设，。，。一，变为图所示的五边网络。仍假定自由竞争以三条路上的通过时间相等为条件求出各路段弧上的流量，知一，；号（），。，告结果也是总流量平均分配到三条可能的路（，），（，）和（，）上。这时，总代价为：厶如。，十，所花总时间变为因此出现了在交通网中增修一条新的路段，反而引起通过时间延长的现象。在图的五边网络上，由于多了（，），而对四边网络自由竞争而达平衡的结果而言（即（）式的流），在这条路上的时间仅花，。这条路对使用个体而言，显然具有诱惑力，但是使用这条路的结果却食得其反。自由竞争的结果是（）式中的流，用户的通过时间都增加判，使每个使用者都延误了通过时间。悖论是指，存在看起来省时间但不能用的路。它是站在用户的立场上观察问题时出现的现象，也是允许用户自由竞争出现的结果。这种现象指出单靠扩充道路的通行能力而改善交通状况的不合理性。以往讨论悖论的文章多是研究悖论出现的条件（即流量变化范围、道路参数之间的关系），但作为系统的管理者更关心的是如何提高系统的效益，下面讨论为了达到理想的效益指标，而应如何分配流量。四、交通系统的流量分配优化问题从系统的管理者而言，流量的分配应使管理指标能达到最优值。现在分别讨论这些模型。总代价最小的单目标模型设对一个给定的交通网络，当总流量为时，有二次规划问题（其中岛（，），和风为非负常数。；凡（）对于一切，成立，厶。解二次规划（）可以得到总代价最小的流，及最小总代价。总通过时间最少的单目标模型在网络上考虑非线性规划问题：嘶川曲警。荟产对于一切，诤钉成立其中，岛，丘，（，），和为非负常数。，。（）；，：是到的流量非的路的集合。这个非线性规划问题的最优值即为最小通过时间。在一般情况下，求解最小通过时间所对应的非线性规划问题（）比较困难总代价最小和总时间最少舶双目标模型及解法根据上文的分析，交通流的最优指标有两个，即要求总代价小，总的通行时间少，对这个双目标问题，可以合并（）（）而给出形式化的描述，但直接求解是比较困难的。由于问题（一）比较好解因此我们先求解（）得出总代价下界，然后逐步减少总通过对间，最后得出一个满意解，其求解步骤如下：步骤：求解二次规划（），得到总代价下界厂。及流。步骤：对流，。，在网络上去掉那些流量为的弧，得到一个新的网络，在。上可以找出从出发点到目的地所花时间最长的路一及所花时间最短的路。，并算出通过尸。旺的时间和通过尸田的时间血，即为总代价为。时所花的总通过时间丁（，），为总代价为时最早到达终点的个体所花的时间。如果一，则已求得最优解，停止。否则，若管理者认为一太长而需要改进，则执行步骤。步骤：给出一个期望值；（；）则求解非线性规划问题：（，）其中岛，（，），和风为非负常数。、厶对于一切，成立，、乙。乙。厶一凡步骤：如果总代价值太大，或者（）无解，则可用对分法调整；，重复执行步骤，直到提出一个可以接收的总代价值和总时间值为止。对最优解，当时，则正巧得出的解对两个目标函数（总代价和总时间）均达最优，这时（），如果丁（，）还能减少，则，（厂）亦可减少，与，是最优解相矛盾。但这时如果在上（而不是在上）存在一条路，在这条路上的时间要比。小，则这时便出现了悖论现象。当确定出满意的指标值后，也求得了达