关于SUE

beyondmon

SUE和非平衡分配中的容量限制多路径分配方法最大的区别在哪？
向各位请教
最好详细点

dragonren

SUE的理论比较严谨，有等价的极值优化模型，求解算法通常有MSA（连续平均法）或者类似框架；
非平衡的容量限制多路径分配方法是从算法上对SUE解的近似，在理论上当矩阵被分解为子矩阵的数目K趋向于足够大时，这个方法的思路就同SUE一致了。
当然，两者的核心都是随机网络加载（就如同UE算法与非平衡算法的核心都是全有全无加载一样），Logit型加载通常用Dial算法，Probit型加载通常用用Monte Carlo模拟法。在以上随机网络加载算法的基础上，采用MSA框架进行迭代计算就能求出平衡解；反之，通过类似于容量限制法的手段，得到非平衡的解。

dragonren

[这个贴子最后由dragonren在 2005/05/31 08:11pm 第 1 次编辑]

“容量限制多路径分配法”这一叫法可能来自于王炜老师的书，实际上他给出的多路径分配法以及改进的节点分配法严格意义上不是Logit型随机网络加载算法。
严格的Logit路径选择概率公式P(k)=exp(-s.c(k))/（分子式对k求和），s为某个常量，   c(k)是连接某个OD对的路径k的实际阻抗，该公式是在路径估计阻抗相互独立且服从相同的Gumbel分布的前提下推出来的，而王老师的公式中，将c(k)换成了c(k)/c,c为连接该OD对的所有路径的实际阻抗的均值。这样一来消除了概率公式中s的量纲问题，但已不是严格的Logit公式，而且带来了一个问题：c如何计算？
细心的读者可能会发现，王老师给出的算法中并没有真的去计算c（这需要路径枚举），而是在最短路径的基础上做了某种近似。
我记得李志纯博士有一篇文章对以上问题有所讨论，但似乎没有分析透底。
以上分析供参考

itslu

对交通分配不太熟，想问一下，王炜老师提出的“非平衡容量限制多路径分配法”的作用和优势都是什么啊？

csjts

在目前计算资源已经不再是紧缺资源的条件下，其实已经没什么意义了。平衡分配方法肯定是主流。

traffic

SUE和非平衡分配中的容量限制多路径分配方法最大的区别在哪？
////////////////////////////////////////////////////////
下面是我对前面帖子的回复：
SUE它考虑了拥挤效应，即考虑路段费用函数是流量的函数！
而非平衡分配中的容量限制多路径分配方法，假定路段费用是固定的！不随流量发生变化！

dragonren

下面引用由traffic在 2005/06/04 12:57pm 发表的内容：
SUE和非平衡分配中的容量限制多路径分配方法最大的区别在哪？
////////////////////////////////////////////////////////
下面是我对前面帖子的回复：
SUE它考虑了拥挤效应，即考虑路段费用函数是流量的函数！
...

所谓“容量限制”恰恰就是考虑了拥挤效应，但是并非考虑拥挤就一定能求得平衡解

itslu

dragonren ， 非平衡容量限制多路径分配法是用于静态交通分配还是动态交通分配啊？多谢！

dragonren

"非平衡容量限制多路径分配法"是从静态交通分配角度提出的，诚如 csjts 所言，在目前计算资源已经不再是紧缺资源的条件下，平衡分配方法是主流，从追求数学结果而言，非平衡的方法没有多大意义（平衡法少迭代几次不就是非平衡法了嘛，当然反过来不一定成立），但问题是：平衡解是否就一定比非平衡解接近客观世界的真实？估计谁也说不清，因为平衡模型的理论基础就存在很多假设。因此，就工程实践而言，非平衡方法仍在使用。
由于对动态交通分配也不是了解很深，不敢妄下断论，但从算法上看，容量限制多路径分配的思路应该还是可以用到DTA中的。

qdliutl

下面引用由dragonren在 2005/06/04 08:04pm 发表的内容：
"非平衡容量限制多路径分配法"是从静态交通分配角度提出的，诚如 csjts 所言，在目前计算资源已经不再是紧缺资源的条件下，平衡分配方法是主流，从追求数学结果而言，非平衡的方法没有多大意义（平衡　...

"非平衡容量限制多路径分配法"既然不能平衡，也就失去了ue的本意，在很大程度上是系统集中控制下的结果。
dragonren提到的问题,即平衡解是否就一定比非平衡解接近客观世界的真实？，确实存在，但我认为也不能完全归结为平衡模型的理论基础存在很多假设这一事实。如果放宽一些关于信息集和司机的计算或记忆能力假设，更加贴近现实情况的话，司机根据自愿的规则长期重复的选择路径，其结果往往趋向于ue平衡。前些时间，我对这一方面做了一些探讨。国外关于日常路径选择行为的模拟或实验中经常可以看到这样的讨论。

itslu

通过上面的讨论，是否可以认为非平衡容量限制多路径分配法，是由于当时计算机资源受到限制，无法对模型进行求解，所以将迭代次数减少，故取名为非平衡容量限制多路径分配法。发过来说，如果当时采用并行计算技术，是不是就不会产生这个方法了啊？多谢回答！

shoregh

引用任老师博士论文中的一段话：
Beckmann变换式在理论上结构严谨、思路明确，但它是一个维数大、约束多的NLP问题。关于NLP问题的算法设计在数学上也是一个难度较大的问题，近年来一直是最优化理论领域的一个热门研究分支，并仍在发展之中。因此，在1975年由LeBlanc等将Frank-Wolfe算法用于求解Beckmann变换式获得成功之前，很多学者一直在探讨用模拟和近似的方法求解交通平衡分配问题；即使在此之后，由于受限于庞大的问题规模和当时相对落后的计算机技术，研究UE分配的近似算法依然是交通分配中的一个重要课题。由此得到了有别于寻求UE分配最优解的一些算法，通常称其为非平衡分配算法。由于这些算法在一定程度上是对真正的平衡分配算法的近似或者特殊化，它们对后者的研究有着启发和借鉴作用，因此我们将其归为求解平衡分配模型的启发式算法。反过来，这些启发式算法的研究同样受到了真正的平衡分配算法的影响。
容量限制（capacity restraint）分配法是一种不断更新路段阻抗、反复调用AON网络加载过程试图达到平衡状态的一种分配算法，也是一种启发式算法。

csjts

启发式算法一般在NP-hard问题中才用，如果能有最优化算法，而且计算时间可以接受，为什么还要用启发式算法？再说了，容限算法启发性实在太低了，即使是启发式算法，也不是什么好启发式算法，哈哈。

itslu

是啊，正如csjts 所说，启发算法指的是在算法中加入启发信息有助于问题求解，而上面提到的非平衡算法是启发算法，我觉得应该是概念上的错误。

qdliutl

上面提到的非平衡算法是启发算法应该属于启发式算法的范畴。
因为它的迭代中存在启发式信息，也就是算法中使用的Logit路径选择概率公式中，将c(k)换成了c(k)/c,c为连接该OD对的所有路径的实际阻抗的均值。
这个c值与司机掌握的路网信息有关系，有种长期路径选择博弈的思想在里边。将c(k)换成了c(k)/c,其实就是一种启发式规则。
一己之见。