关于SUE

dragonren

下面引用由csjts在 2005/06/07 04:26pm 发表的内容：
启发式算法一般在NP-hard问题中才用，如果能有最优化算法，而且计算时间可以接受，为什么还要用启发式算法？再说了，容限算法启发性实在太低了，即使是启发式算法，也不是什么好启发式算法，哈哈。

我倒不赞成上述观点。
最短路径问题研究得够透了吧，各种版本的最优化算法可以说多如牛毛，但是启发式算法照样大行其道。没有人敢肯定一个算法对于任何情形、任何需求都有很好的表现，最优路径问题如此，交通分配亦是如此。

csjts

最短路径问题使用启发式算法，主要是考虑在大规模网络中应用的计算时间问题，特别是在有客户端查询的系统中，为了不让用户等待太长时间（所谓的实时响应），因此需要加入方向等启发式信息。而求解一个大规模网络中的随机平衡分配问题耗时几小时一般是可以接受的，但在导航用的动态交通分配中又另当别论。因此我认为求解平衡分配问题还是用最优化算法为好，容限这种方法的确没什么优势。即使要优化，也应该从求解非线性规划的下降算法角度优化以提高效率，减少迭代的总次数。再有就是从最短路径搜索算法方面进行优化，这方面搞图论和GIS的人研究的很多，主要是从数据结构角度做的，但在交通中用的还很少。最短路径算法的时间复杂度从立方阶降到对数阶，这个节省的计算时间是很可观的，远远大于容限相对于F-W算法节省的时间，因为分配问题求解中基本没步都要求最短路径。

csjts

虽然我一直在说容限方法不好不好，但事实上我们是都应该肯定王老板在交通分配领域研究这块的功绩的，不能用现在的眼光去评判当时的问题。王老板搞这些东西是在90年左右，90年PC机是什么价？我一个朋友送我一块90年的硬盘，520M，说当时卖9000多一块，概念可能相当于我们现在的磁盘阵列：）93年我见到第一台个人电脑，内存4M，是8条512K的，据说是当时的尖端PC机了。当时那种环境下，王老板一年的收入可能都买不了一台机器。所以那年月机器资源远比人力（脑力？）资源价值要高很多。因此最重要的问题是在尽可能缩短上机时间的前提下，更精确的求解分配问题。所以说当时王老板的贡献应该是很大很大的，最起码在国内实际的工程项目中真真切切的进行预测，这是最重要的。我看过一个资料，De CEA. Joaquin(著名的交通专家德*华金)1986年在智利圣地亚哥地铁规划项目中，在一台有96M内存的DEC3000计算机（小型机）上整整运行了12小时，才计算出整个交通网络(260个小区、11种交通方式)的平衡解！而王老板的程序(可能是Transtar的前身吧)1989年在南京的220个节点的网络中运行容限分配过程，在PC机上运行只需要一个小时，在当时应该说是很实用的方法了。现在过去十多年了，计算技术依照摩尔定律飞速发展，PC机早已降到了白菜价，王老板一个小时的收入都比这多：)因此我们再讨论这些问题事实上意义也已经不大了，着眼点应该放在如何能更真实、更贴切的描述交通现象上，比如微观、时变的网络交通流研究等。关于计算速度，谁知道明天会快成什么样？并行计算、网格计算、生物计算，变成机械公敌也说不一定，赫赫。

lovellhe1

这是个好帖子，可以了解基本的ue 分配问题。
每一个问题，每一种方法在人类的认识进程中，都会以各种不同的形式
反复出现，今天被抛弃的，明天也许又要拾取！
关键是怎么拾取？何时拾取？