【辣眼深评】-我国自主研发的交通系统仿真平台的全面深入讨论：DynaCASTIM VS TESS！

qdliutl

采用递归的数据存储表达方式，可以极大地较少路径存储的内存消耗吗？
     
     提供后台数据存储的是关系型数据库或者临时数据文件，搜到一个贴子也许可以提供帮助。
     [转载]树形结构的算法 http://myblog.boei.cn/index.php?show=blog&id=75
      产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？
     毗邻目录模式(adjacency list model)
     预排序遍历树算法(modified preorder tree traversal algorithm)
     ……     
     还是两种方法之比较
     ……
     总体来说，我个人比较喜欢用递归的方法，但一直担心递归对效率的影响，所幸还没有接触过规模较大的分类层次，递归用数组替代堆栈会是一种比较好的改进方法。而预排序树不失为一种解决简单树的高效方法，用习惯了，也应该是非常出色的，尤其是它从叶子节点到根节点的反向查找非常方便。
     ……
     用循环来建树已经实现了
     ……

46_树形结构的算法.doc (94 KB, 下载次数: 508)

2009-5-3 21:40 上传

点击文件名下载附件

[ 本帖最后由 水寿松 于 2009-5-3 21:40 编辑 ]

dragonren

上面某一楼给出了一些微观交通仿真软件的清单，其来源可能是某篇国内文章，其中掺杂了几个宏观软件。

这些软件的清单和比较情况源于由英国Leeds大学牵头的对微观软件进行比较和开发的SMARTEST项目，具体见http://www.its.leeds.ac.uk/projects/smartest/

附件是我结合网页资料、中文文章和同济邹智军博士论文整理的一点材料，可以对微观仿真软件有个初步印象

47_任刚.doc (155.5 KB, 下载次数: 344)

2009-5-3 21:41 上传

点击文件名下载附件

[ 本帖最后由 水寿松 于 2009-5-3 21:41 编辑 ]

xjtuits

谈谈DTA系统的路径搜索与储存问题。有版友提到Dijkstra算法效率太低，但最近看到一些文章，有人对18种最短路径算法进行了比较，结果最好的有三种，其中两种是Dijkstra算法的改进版。利用双端队列(Deque)的D算法有不错的性能，Hani S Mahmassani教授就将它用于搜寻时变的最短路径。我们也采用了该算法寻找k-最短路。如果OD对之间的合理路径是离线生成的话，那就得考虑很多情况，比如路段费用的随机波动、路段中断、交通事件等造成的通行能力降低、左转弯数量、高速路和普通城市道路所占比例等等，并分别针对这些情况生成k-最短路。离线计算结果可以保存到硬盘上。但DTA系统实际运行时，大量的路径需要调入内存，如果每条路径只是简单地采用节点序列进行储存的话，那消耗资源太多了！递归的存储方式尽管牺牲了一些计算效率，但通过采用合理的数据结构，可以找到效率和存储之间很好的折中。比如，任意一条路径可用<当前连接线编号、下游连接线编号、下游路径编号〉即可表示，采用STL里的map（基于红黑树的一种关联数据结构）,vector等数据结构，即可很好地存储与查找。

xjtuits

DynaCASTIM的中观交通仿真器已基本开发完成。车辆在路段上的运动分为自由运行阶段和排队阶段，其中自由运行阶段按照宏观交通流理论中的速度-密度模型决定运行速度，并假定在路段下游存在排队的情况下，车辆速度以线性递减地方式接近队列末端；将路口信号灯的配时参数转化为下游节点的出口流量约束（根据路口通行能力分析的一套算法得到）。仿真器已可为队列的形成、消散、回流等较复杂的交通行为建模。目前的测试结果如下：对一个具有63个节点、161条单向路段、549条车道、15个交通小区的路网，路网中容纳的最大车辆数为2000左右、车辆位置更新步长15秒时，仿真16个小时的交通状况，大约需要3分钟左右的机器时间（普通PC机）。可以肯定地是，中观交通仿真模型用于实时动态交通分配是可行的，它可以获得甚至较接近解析法的计算效率，同时可以为复杂的车辆运动行为建模。严格的仿真测试和现场测试是一个漫长的过程，有了新的测试结果，再奉献给各位版友。
附图是系统运行的画面，图中的黄色小圆块代表运行的车辆，每一个圆块可以代表一辆或多辆车，取决于对计算效率和计算精度的要求。

xjtuits

附图：


[ 本帖最后由 水寿松 于 2009-5-3 21:43 编辑 ]

lglabc

[这个贴子最后由lglabc在 2005/08/01 12:32pm 第 1 次编辑]

呵呵，看到这么好的题材，忍不住也来说两句
先声明一下，我不是学交通的，现在可以算是一个不合格的coder -__-
阴差阳错，我现在负责一个交通仿真软件的开发，我们有专门负责交通理论的人员
所以在理论上，我就是个白痴了 ^_^
看了帖子，觉得 DynaCASTIM 和 TESS 都还是宏观仿真的软件，和那个transtar有些像 [呵呵，外行的话]
而我们集中在微观仿真方向，是以vissim作为模拟对象的，也是用了CA作为基础
路网的构建是向vissim 学习的，以每条道路作为最小单元
同时我们也提供对行人、自行车等在无信号灯状态下的仿真 [特点哟！不要拍我。。]
还提供各种仿真数据的输出结果
现在已经可以构建 1 平方公里的路网了 [机器好的话，更大也可以] ^_^
作为商业软件，3D的显示这种花花的东西还是必须要有的。
我贴一个路网的局部图片吧！不能给出更细节的资料了 -__-
其实我很羡慕DynaCASTIM 和 TESS 的作者，有足够的专业知识，能够说清楚很多问题。不像我，很多东西做出来以后，并不知道是否是对的。郁闷。。。



[ 本帖最后由 水寿松 于 2009-5-3 21:43 编辑 ]

irico

上传一小段录像，只是说明TESS其实是微观的。里面还有很多bug。但是经过校正的模型模拟非ITS环境下的交通网络还是可能的。
正像黄老师说得，目前的困难就是simulation_DTA算法问题，效率太低：（

irico

下面引用由irico在 2005/08/10 05:13pm 发表的内容：
上传一小段录像，只是说明TESS其实是微观的。里面还有很多bug。但是经过校正的模型模拟非ITS环境下的交通网络还是可能的。
正像黄老师说得，目前的困难就是simulation_DTA算法问题，效率太低：（

sorry,刚刚没传上去

53_录像.rar (1.15 MB, 下载次数: 422)

2009-5-3 21:45 上传

点击文件名下载附件

[ 本帖最后由 水寿松 于 2009-5-3 21:45 编辑 ]

lglabc

[这个贴子最后由lglabc在 2005/08/10 05:40pm 第 1 次编辑]

呵呵，看了录像，感觉和我们做的东西很像 （可能由于我们负责交通理论方面的也是从tj出来的^_^）
现在的 TESS 就是并行的吗？本来我们也有这样的计划，不过由于既没有分布式的经验，也没有交通仿真程序的经验，所以就暂时放弃了，准备专攻单机，将来有机会再扩展。
在网络上找了很长时间，从没能找到这么切合的论坛，很开心^_^
希望能和这里交流经验 [当然得在我的权限范围内   ]
争取过一段时间也贴一段录像上来

xjtuits

看了irico和lglabc的帖子，感觉交通仿真定能在我辈手中发扬光大，前途一片光明：） 不过，我也要声明，DynaCASTIM和王炜教授的TranStar还是不同的，呵呵。实际上，DynaCASTIM和DynaMIT-R, DynaSmart-X相似；另外，和加拿大inro公司（EMME/2也是他们开发的）开发的Dynameq也有些像，不过Dynameq主要用于交通规划。
DynaCASTIM分为交通需求仿真和供给仿真两大部分，前者是微观层次的，细致地仿真出行者对出行方式、路径、时间以及中途对交通信息的响应行为；后者是中观层次的，和微观仿真的区别在于不考虑换道行为，建模精度降低，但带来计算效率的极大提高并减少了模型参数标定的困难和工作量。系统的理论基石是动态交通分配理论，采用中观交通仿真主要是克服解析DTA模型求解的困难及对车辆运动行为的假定有些脱离实际；其他的内容和采用的方法和DTA就差不太多了。
开发DynaCASTIM的主要目的是希望将解析DTA和实际工程应用结合起来，并且希望这是一套可以实际应用的系统。如果能够成功配置，以后公众在出门的时候，交通信息中心会告诉他应该选择何种出行方式、路径，并建议最佳出行时刻，准确预报到达目的地需要多少时间，还可对沿途的交通状况甚至路边风景等做出描述。希望DynaCASTIM提供的实时交通预报信息不要像天气预报那样经常不准。系统的开发已是艰巨任务，但对系统参数的离线、在线标定以及有效性验证将更艰巨，DynaMIT等系统原型开发花了3年，参数标定、模型验证等已花了超过7年的时间。最近读了MIT的rama博士发表在ISTTT 16th上的论文，主要是介绍DynaMIT参数标定和模型验证的文章，他和另一位博士分别将离线和在线参数标定拿来做博士论文，足见其难度和重要性。
对于微观交通仿真系统的代表作Paramics,Vissim,它们的参数标定是否能像MITSIM一样通过一些集合化的数据较方便地实现？迄今，很少见到有关这两套系统参数标定的文章。尽管打算将Paramics作为仿真实验平台，但未来进行严格现场测试仍是必须的。感觉国内许多地方都在研究微观交通模型并开发微观仿真器，甚至有的模型细致到快考虑各个地方风土人情的不同了（说得有点夸张了！），但真的应该考虑自己的实力以及开发的最终目的。有实力的单位开发这样的系统当然好，但如果仅仅是为了得到绚丽的动画界面，并不打算做成实用的系统，那确实应考虑这种重复性的研发投入是否值得。
我想，交通系统十分复杂，如果建模越细致、考虑的因素越多，则带来的后果可能是模型严重失真。谁能完全准确地描述车辆的运动行为？因此，建模时应该考虑究竟细致到何种程度，层次越高，模型越能体现集合化的交通流规律，因而更适宜于用数学模型去描述，标定参数越容易；相反，层次越低，越能体现车辆的个性差异，但此时数学模型是否还能真实地描述这些个性差异呢？

irico

下面引用由xjtuits在 2005/08/10 07:53pm 发表的内容：
看了irico和lglabc的帖子，感觉交通仿真定能在我辈手中发扬光大，前途一片光明：） 不过，我也要声明，DynaCASTIM和王炜教授的[quote]下面引用由xjtuits在 2005/08/10 07:53pm 发表的内容：
看了irico和lglabc的帖子，感觉交通仿真定能在我辈手中发扬光大，前途一片光明：） 不过，我也要声明，DynaCASTIM和王炜教授的TranStar还是不同的，呵呵。实际上，DynaCASTIM和DynaMIT-R, DynaSmart-X相似；另外，和加拿大inro公司（EMME/2也是他们开发的）开发的Dynameq也有些像，不过Dynameq主要用于交通规划。
DynaCAST

TranStar还是不同的，呵呵。实际上，DynaCASTIM和DynaMIT-R, DynaSmart-X相似；另外 ...
[/quote]
关于DynaCASTIM我想我还是理解的。Mahamasani以及Akiva的文章十年来的我看过得也很多，而且有师弟在他们那边，以我自己的感受和同杨齐等国外人士的交流，谈一点个人看法：
（1）计算效率问题。据DynaSMART那边的人说DynaSMART在实验室中测试几千个节点，在实时层面还是可以的。但是实际的应用效果怎样，不得而知。TESS现在运算杭州这样小的路网就比较吃力，所以我只打算做离线的。算法效率不仅是编程的问题，更是数学问题。
（2）分布式问题。TESS的分布式版本是基于HLA的，可以说是实现，但是离实际应用很有很大距离。DynaSMART和DynaMIT好像都是基于corba的，可以参考。
（3）参数校正问题。实际上关于微观模型参数校正的文章一大堆。我也曾经用什么GA、SA以及GSA做过VISSIM以及CORSIM和Paramics的。我问杨齐，他反倒没有考虑过这个问题。我觉得在仿真软件中可以加一个这样的优化模块，但是具体实施，我现在时间太紧张了：（
（4）基于实时信息的DTA系统实际上还有Visum－online。因为是商业软件，所以文章基本没有。但是在柏林已经实际应用。我得两个师弟会去德国学这个软件，以后可以向大家报告
（5）时间和经费问题。实际上有公司曾经出一期300万让我们这的李老板开发一套微观仿真系统。老李没敢接受，他很清楚这需要多大的人力和物力。杨齐从MIT到Caliper8年以后才出来一套接近商用的微观软件TransModler，而Caliper的技术实力是多强啊
我现在也比教迷惘，我改何去何从～～～

irico

说到兴头，补充几点：
（1）各个大的公司，目前都在朝集成和一体化的方向发展。如PTV的Visem，VISUM，VISUM－online以及VISSIM，互相之间都是有接口的；Caliper的TransCAD以及Transmodelr。Transmodler甚至可以在一个路网中同时以宏观－中观－微观形式模拟，我想以杨齐在MIT的经历，不会不考虑下一步的开发是否会朝X方向努力；Inro现在和TSS合作，搞得EMME/2、AIMSUN/2以及Dynameq；Citilabs开发CUBE系列等等。我想如果想考虑以后实际应用的话，一定考虑宏－中－微管一体化问题。
（2）关于交通预测。我觉得能够向天气预报那样准确就很好了。诚如杨超博士说得，预测交通就像预测股市那样，能准吗？我想MIT和Maryland的大牛们是不是这么多年的研究是不是可以在这两年先回答这个问题
（3）关于实验交通工程，最近我们老板让我忽悠实验交通工程，实质核心平台也是Visum－online类似的系统，只不过开发方法和理念又很大的不同。至于下一步怎么走，会有师弟、师妹冲上来的。
（4）关于活动链和仿真。这个是新的研究动向，不过更加的复杂和耗费运算资源。但是更加贴近现实，值得大家关注。
（5）TESS最初的开发设想是一个评价ITS环境下的交通运行，另一个是和老板其他的系统有机集成。采用XML格式的文件，实践证明这玩意效率很低，不过问题很可能是我们没有优化好

以上都是个人拙见，不对之处请指教。关于程序实现问题，本人知道甚少，见谅。

xjtuits

irico的帖子很好啊，我增长了不少见闻！准确地预报交通比天气预报还要困难，但MIT的研究者们似乎充满了信心。最快明年6月份，DynaMIT-R在Los Angeles的一个稠密的城市交通网络内的现场试验会完成，我们期待他们的测试结果；DynaSmart-X的结果要晚一些才能出来。另外，近期在弗吉尼亚一个城市交通网络的现场测试表明，DynaMIT-R在正常天气情况下，有非常高的短期交通预报精度（1小时内），而对于恶劣气候，效果较差。不难理解，MIT还没有考虑气候对交通模型的影响。从2003年的评价报告中看到，DynaMIT-R比DynaSmart-X有更好的性能。以前看到过报道，FHWA由于经费的限制，对于实时版本的系统只资助DynaMIT-R，而对用于交通规划的系统，只资助DynaSmart-P；但到现在好像这四套系统(DynaMIT-R, DynaMIT-P, DynaSmart-X, DynaSmart-P)均还在接受FHWA的资助。
对于实时交通预测，对高速路网或者环城快速路以及城市主干道，技术难度要小一些；对于稠密的城市路网，对出行者的出行选择以及信息响应行为的理解还处于起步阶段，预测交通状况有相当大的困难。德国的visum-online也是刚从irico的帖子中了解到，但不知道实际应用效果究竟怎样。
实验交通工程是由饭田恭敬教授倡导的吧？我没什么了解，查了一下资料，好像和王飞跃教授、汤淑明博士的人工交通系统有类似之处。人工交通系统的最终目的或许是要建立一个虚拟的交通世界，就像美国大片"Matrix"那样，但是这样的东东将是一个庞大的工程，让我望而生畏！：）

lglabc

irico 和 xjtuits 果然是这方面的专家，你们说到的很多领域我都没有听说过-__-
我也是这两年负责这个项目才接触了一些交通的知识，老实说，我研究生阶段做的是网络三维方面。。。说起来跨度真大呀。。。
扯远了，我们是公司，所以很多事情都是利益放在第一位上的（有时候觉得很不爽，可能是因为我刚毕业，还不习惯吧！）不过我们公司很小，也是通过合作来做这个项目的。。
irico 你们老板300万都不敢接，可我们的资金连这个1/10都不到：（
看来真是无知者无畏呀。。
我们现在也希望能就校正我们的模型，我们采用的模型都是那些公布的成熟模型，有利于实现，不过效果不好说。我们准备初步用Vissim来校正我们的模型，没有像你们一样用一个博士来校正模型，完全是因为利益的原因，如果我们8年才能校正一个模型，早就倒闭了：）
微观的模型确实很难校正，不像那些宏观理论中都是符合一些公式，微观的公式往往都不能准确的反映复杂的个体行为。我们在实现过程中就自己做了不少改进，呵呵，可能是因为我们不是这个专业的，所以才没什么顾忌。
irico 如果迷茫也是很正常的，这么广阔的领域，还是应该集中在一部分，否则不容易有什么大的成果的^_^

thickicesong

我现在美国德州跟随DynaSMART的主要研发者Dr.Chiu Yi-Chang从事研究工作并攻读学位。我这学期有一门课叫做Infrastructure Planning,从教学大纲上看将会讲到DynaSMART。我前几天也跟Dr.Chiu谈到了DynaSMART和DynaMIT的一些情况。这几天还要继续谈这个问题。届时我会向大家及时报告的。
H.B. Song