【分享】城市交通网络均衡分配的模型与算法，学术报告讲稿，供参考--黄海军

csjts

对Beckmann用户均衡模型的行为学解释
最近一直在拜读黄海军老师发在本版的《城市交通网络均衡分配的模型与算法》这篇讲义，感觉受益匪浅。但对其中的一个问题一直存在疑惑，即Beckmann提出的等价于Wodrop第一原理的UE数学规划模型。黄老师的文章中说“目标函数是路段时间函数的积分，本身并没有什么直观的经济含义或行为学解释，纯粹是一种用来推导UE条件的数学构造”。我看了一些国内其他交通规划的教材大致上也是这么说的，例如陆化普老师的《交通规划理论与方法》，邵春福老师的《交通规划原理》等。但通过深入分析Wodrop第一原理，我认为事实上该模型的目标函数可以从出行者路径选择行为的角度导出。我把我的推导过程写出来，不知道正确与否，请黄老师及各位版友批评指正。
（HTML不能输入公式太痛苦了，不过估计熟悉这类问题的版友都能理解）
考虑一个rs间只有一条路径（路段）的简单交通网络，该路径的时间函数为ta(xa)，事实上该时间函数总可以描述为t0+F(xa)，即零流时间t0与某关于流量xa的增函数F(xa)的和。考虑流量xa是一个离散量，则当有n个出行者准备在此网络中出行时，假设他们按照严格的先后顺序进入网络，则网络中的流量xa应该随时间按照1、2、3、……、n依次递增。同时假设该路段是单车道的（不允许超车），则第n个进入网络的出行者的走行时间只受前n-1个流量的影响，而不受后续进入网络流量的影响，即第n个出行者的行驶时间为t0+F(n-1)。因此，对于先后进入网络的n个出行者来说，总的出行时间应该为：
T = t0+ F(0)+ t0+ F(1)+ t0+ F(2)+……+ t0+ F(n-2) + t0+ F(n-1)
假设F(xa)为一线性函数，即F(xa)=b*xa，(b为常数)，则上式可以简化为：
T = n*t0+b*[0+1+2+3+……+(n-2)+(n-1)] = n*t0+b*(n*n/2-n/2)
根据Wodrop第一原理，所有的出行者在选择路径时都希望自己的出行时间最小，则可以对上式构造数学规划模型(约束同Beckmann模型，略)：
min T =n*t0+b(n*n/2-n/2)
在这里n（即xa）是离散变量，如果将xa考虑为连续变量，则对上式先求微分再进行0到xa之间的积分后，目标函数性质不变，有：
min T =∫[(t0)+b*xa-b/2]dxa
由于t0+b*xa=t0+F(xa)=ta(xa)，同时-b/2是常数可以在目标函数中略去，则上式变化为：
min T = ∫ta(xa)dxa
此时再将交通网络扩展到一般化的情景，即对于所有OD对间的出行者都希望自己选择的路径走行时间最短，则上式也可以扩展到一般化的情况，即网络达到UE平衡状态时，对于所有的路段a，有：
min Z=∑∫ta(xa)dxa
该目标函数与Beckmann平衡模型的目标函数具有一致的形式。
该解释的含义事实上与黄老师讲义中给出的含义是一致的，即在UE条件下每个出行者都只考虑自己体验的时间，而不会考虑自己对路段上已经存在的出行者产生的拥挤时间贡献（边际贡献），因此也造成了UE与SO配流结果的差异。
上述是我从出行者路径选择行为角度对Beckmann用户均衡模型做出的解释，我认为该解释符合Wodrop第一原理的内涵，同时与SO模型的解释正好相互对应，对理解平衡分配问题应该是有帮助的。不过我知道我的推导过程不是很严格，例如时间函数假设为线性与事实情况不符合，但目前我还没找到更好的方法。
此外，黄老师的讲义中提到的Beckmann的原文（Beckmann, M.J., McGuire, C.B., and Winsten, C.B. (1956). Studies in the Economics of Transportation. Yale University Press, New Haven, CT.）由于年代久远，实在找不着，不知道Beckmann本人是从什么角度导出该模型的，如果我的想法与其类似，只能说是我孤陋寡闻了。不过我是初学者，不怕贻笑大方，赫赫：）
请黄老师及各位版友指正!

shoregh

期刊网上有两篇文章可以借鉴一下
对网络交通量分配非平衡模型的探讨
交通网络用户平衡模型解释初探

csjts

这两篇文章我倒是看过，不过我觉得《交通网络用户平衡模型解释初探》这里边从流体势能的角度解释很牵强啊，没有反映出出行本身的特征来。而我的解释是从用户路径选择角度作出的，核心是假设用户选择路径前只考虑现有流量对走行时间的影响，并由此导出了UE模型，如果用户选择路径时还可以考虑自身对路段走行时间的影响，则可以导出SO模型。我觉得这样可以在一个推导框架下把UE和SO统一起来，因为SO模型的解释很明确，这样处理能使人更容易理解UE模型的含义。同时对路经诱导（动态网络分配）的建模也应该是有帮助的。不过这方面内容太深了，现在正在学习中。

csjts

[这个贴子最后由csjts在 2005/04/22 06:26pm 第 1 次编辑]

千辛万苦，终于找到了Beckmann的原文（Studies in the Economics of Transportation）！google太好了，赫赫。
感兴趣的朋友可以去这个地址下载：
http://www.rand.org/publications/RM/RM1488.pdf
仔细看了一下，Beckmann本人的确也没解释清楚UE模型的含义........
此外还找到了黄老师说的关于UE与SO之间差异的文章，不知道那个博士生是Tim Roughgarden还是Andreas Schulz？不过他们两人的个人主页我都找到了（http://www.cs.cornell.edu/timr/和http://web.mit.edu/schulz/），上边有很多关于这类问题的电子文档，其中比较有意思的是这个：
Effective Route Guidance in Traffic Networks(http://web.mit.edu/schulz/www/ibm-2003.pdf )
我觉得这个问题确实挺有意思的，这里边水的确很深啊。准备深入学习下下！也希望感兴趣的版友能多来讨论啊！

huanghaijun

csjts,厉害！找到老祖宗的文章了。UE本身是好解释的，直接用效用和对策论就可以解释UE。 许多人想知道的是，Beckmann的那个公式有什么经济含义，象SO的公式那样明了。比方，对f(x)dx求积分， 显然是曲线f(x)下面的面积， 因为很直观地知道，那个大块的面积是所有小条的面积之和，而每一小条的面积就是f(x)dx. Beckmann的公式可以这样对应地解释吗？
csjts对UE与SO的差别的解释完全正确。解释UE已经没有什么疑问了。
不过， 我觉得， 去追问Beckmann变换的机理，没有什么价值，把时间花在这上面可惜。一是，如果这里面有得做，人家早就做了，用不我们中国人现在才去挖掘！二是，变换就是变换，是一种技巧，数学里这样的事情很多，拉式变换，富里叶变换。
Roughgarden是学生，导师是Tardos. Selfish routing离SO到底有多远，是理论家特想回答的问题， 不仅在交通科学里，到处存在！

csjts

[这个贴子最后由csjts在 2005/04/23 11:28am 第 2 次编辑]

感谢黄老师的指点！顺着黄老师的思路，我又看了下数值积分方面的内容，把我的思路画成图形贴在下面，包括对SO与UE之间差异的理解，不知这种思路对不对。对于这个问题我有很大的兴趣，希望黄老师不吝赐教啊：）

huanghaijun

你的推导里,为什么n个人的成本各不一样? 在UE里, 一条路段上所有人感受的成本都是一样的,即流量为x时, 这x个人都感受t(x).你的图形中却是, 第一人感受t(1),第2人感受t(2),...

csjts

因为我假设认为出行者是先后进入路径的，第n个出行者选择路径前只会考虑路径上已有的n-1个流量导致的感受时间t(n-1)，而不去考虑后边还可能进入路径的出行者（包括第n个出行者自身）带给自己的感受时间增加。当然实际上这个感受时间是增加了，当达到UE时，该路径上所有的出行者感受时间应该都是t(x)，但每个出行者在选择路径前是不会知道t(x)将会是多大的（这应该就是Selfish routing吧？）。如果t(x)能够被提前感知，系统平衡时就应该是SO了，我理解这正是UE与SO的差异。因此若想让系统达到SO，必须提前让出行者了解这个t(x)可能会达到多大，而这只有实施了路径诱导系统（网络交通流的实时动态预测？）后才能达到。不知道这样理解对不对。（不过这又好象快扯到DTA上去了，DTA刚开始接触，太难了，正在学习中：）
此外这两天在看Roughgarden的博士论文（http://www.cs.cornell.edu/timr/papers/thesis.pdf），一方面在感叹作者思路的开阔和巧妙，另一方面自己也在思考UE和SO的差异在更一般的情况下（包括黄老师提到的非线性时间函数、弹性需求等）究竟有多大？不过我的功底太薄了，很多问题实在是想不清楚。我想请教黄老师的是，如果采用计算机仿真的手段研究这个问题，在不同的网络结构、时间函数、需求条件等情况下分别求解UE与SO的总费用，如果能找到统计意义上的费用差异曲线，这个有没有实际或理论价值？不过我估计意义也不大，自己瞎想的，黄老师见笑了，嘿嘿：）

huanghaijun

所以,Beckmann的积分讲的是一个过程, 但最后的解却讲的是一个点态, 在这个点态,每个人的成本都是按照一样的公司计算的, 并不是第一个人是t(1), 第n个人是t(n). 问题就在这里. 所以,怎么解释这个积分,都得不到满意的答案, 这也是国际上的学者都放弃了试图去解释它的原因, 反正就是一个数学变换吧, 这么变换一下, 有利于问题的描述和求解.
有一种思路, 从disequilibirum 到equilibirum, 描述这一过程, 阐述均衡态的产生过程和里面的特性,当然要用到DTA. 你隐隐约约感觉到的就是这种思路.
用大量的计算模拟来统计UE与SO的差异, 是很有趣的. 高自友教授的研究小组正在做,工作量很大. 第一,网络必须是随机产生的, 网络上的路段函数也是随机定义的; 第二,OD需求矩阵是随机产生的; 第三,要有很好的算法和软件快速求解UE与SO. 关键是如何产生随机结构的网络, 又如何在数学上描述它们.

csjts

感谢黄老师的点化！经黄老师这么一说，我现在感觉有点真正理解这个问题了，看来以前还是学的不透啊！
我本科是在北交大上的，不过我是学铁路运输的，高自友老师没给我们上过课，只有幸听过他的报告（其实我上学的时候也是见过黄老师地，嘿嘿）。看来我说的这个计算机模拟手段研究UE与SO差异还是有点意思了，有机会回去打探一下。

csjts

此外关于黄老师提到的随机结构网络的描述，我觉得从计算机模拟这个角度应该不难做到。我以前看过一篇论文（B.V.Cherkassky, A.V.Goldberg, T.Radzik. Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming, vol.73, pp.129-174, 1996.）是关于比较各种最短路径搜索算法的效率的，文中的网络结构和阻抗就是随机生成的。当然交通网络和一般网络特性上的差异还是比较大的，实际的交通网络节点连接度一般较低，总体上应该还是稀疏网络。我觉得这个问题的关键还是在于如何提高UE模型求解算法的效率。F-W算法的软件我自己写过，感觉理论上可行，实际操作起来效率上的确有很大问题：一方面是求可行解的最短路径子算法，Dijkstra算法效率太低，我看了一些关于最短路径算法效率改进方面的文章，不过这些改进主要是从数据存储结构的角度来做的，但感觉网络交通流和这块研究结合的不太好，GIS领域应用的似乎更多一些；再有就是F-W算法的迭代过程，越接近收敛时越慢，可能基于方向的方法都这样，值得改进。但这方面的文章看得不多，黄老师能不能推荐一些相关的读物？再次感谢！

huanghaijun

你好! 关于算法,许多数学家在做,什么锥,交,割的,一大堆概念,甚至扰动呀, 或者到了最优点附近用非传统算法再杂交一把的, 我的兴趣不在这,所以提供不了什么帮助,高教授是行家.
我赶兴趣的是,比方说, 给定1000个节点,2000条路段, 可以构成无数的网络结构, 如规则的, 随机的, 无标度的, 到底那种结构的最好? 其UE离SO最近, 其能够承载的需求最大? 其稳定性最高? 可以经过大量的模拟和统计给出基本的结论吗? 如果能够回答将是一个好的理论成果.

csjts

看过高自友老师关于平衡交通网络设计的书，感觉黄老师说的这个问题类似交通网络设计的问题，是设计什么样的网络结构才能使用户“自私”选择下的系统总费用与SO费用差异更小的一个问题。这个的确很有理论价值和实际意义。不过要真算的话，这个随机结构网络的可能组合数实在大的惊人啊，别说模拟，光枚举组合估计都NP Hard了，如何生成和描述这样的网络的确是个关键！

qdliutl

附件为NE Stier-Moses的博士论文《Selfish versus coordinated routing in network games》，2004，导师为Andreas S. Schulz。
摘要：
   A common assumption in network optimization models is that a central authority con-trols the whole system. However, in some applications there are independent users, and assuming that they will follow directions given by an authority is not realistic. Individ-uals will only accept directives if they are in their own interest or if there are incentives that encourage them to do so. Actually, it would be much easier to let users make their own decisions hoping that the outcome will be close to the authority';s goals. Our main contribution is to show that, in static networks subject to congestion, users'; selfish decisions drive the system close to optimality with respect to various common objectives.This connection to individual decision making proves fruitful; not only does it provide us with insights and additional understanding of network problems, but it also allows us to design approximation algorithms for computationally di±cult problems.
    More specialcally, the con°icting objectives of the users prompt the de¯nition of a network game in which they minimize their own latencies. We show that the so-called price of anarchy is small in a quite general setting. Namely, for networks with side constraints and non-convex, non-di®erentiable, and even discontinuous latency functions, we show that although an arbitrary equilibrium need not be e±cient, the total latency of the best equilibrium is close to that of an optimal solution.
    In addition, when the measure of the solution quality is the maximum latency, equilibria in networks without constraints are also near-optimal. We provide the ¯rst analysis of the problem of minimizing that objective in static networks with congestion. As this problem is NP-hard, computing an equilibrium represents a constant-factor approximation algorithm. In some situations, the network authority might still want to do better than in equilibrium. We propose to use a solution that minimizes the total latency, subject to constraints designed to improve the solution';s fairness. For several real-world instances, we compute tra±c assignments of notably smaller total latency than an equilibrium, yet of similar fairness. Furthermore, we provide theoretical results that explain the conclusions derived from the computational study.
主要工作：
    One of our main contributions is an extension of the results of Roughgarden and Tardos to networks with side constraints and to latency functions that are non-convex,non-di®erentiable, and even discontinuous. Side constraints are especially useful in traffic networks. For example, they can be used to model arc capacities, which has been recognized as an important means to provide a more accurate description of tra±c °ows.
Moreover, real-world transportation models often include such constraints, not only to prevent arcs from carrying arbitrarily large °ows, but also as a way to calibrate the network model and bring its solution into agreement with anticipated results. In this more general model, multiple user equilibria might exist and an arbitrary user equilib-rium does not need to be close to a system optimum.
    Nevertheless, we characterize a particular equilibrium that we call Beckmann user equilibrium, which turns out to be e±cient. De¯ning the coordination ratio of a solution as the ratio between its total travel time and that of the system optimum, we show that the coordination ratio of a Beckmann user equilibrium is not higher than the price of anarchy in the model without side constraints. Beckmann user equilibria arise from an extension of the mathematical programming formulation used to compute user equilibria in the model without side constraints, due to Beckmann, McGuire, and Winsten (1956). Besides having relatively small total travel time, Beckmann user equilibria are attractive because they can be computed e±ciently. This also shows that game-theoretic concepts successfully o®er a way of computing approximate solutions to hard problems. Although there are mul-tiple equilibria and computing the best equilibrium is di±cult, a  provably good user equilibrium can be computed in polynomial time.
    We have just argued that, in the worst case, equilibria are not too ine±cient. But what happens in the average case? Or at least in real-world examples? It turns out that equilibria are even closer to system optima, which is good news. But not quite.

qdliutl

下面引用由csjts在 2005/04/27 10:51am 发表的内容：
看过高自友老师关于平衡交通网络设计的书，感觉黄老师说的这个问题类似交通网络设计的问题，是设计什么样的网络结构才能使用户“自私”选择下的系统总费用与SO费用差异更小的一个问题。这个的确很有理论价值和实 ...

在Tim Roughgarden的博士论文中提到
the “steepness” of a network’s latency functions is in some sense the only cause of the inefficiency of Nash equilibria, and that the complexity of the network topology plays no role.
   ue与so的差异真的与网络结构没有多大关系吗？