作者:常丽君 来源:科技日报 发布时间:2013-9-18 10:00:00
选择字号:
科学家向高分子“交通网”学习治理交通拥堵

 

要找到一条最优路线是容易的,但要找到多条路线的最优组合就比较困难。从互联网即时通信、对等网络,到地铁交通、机场飞行管理、供水系统、传感器部署、军事后勤运输、旅行路线计划等,寻找全局最优路线组合的方法应用广泛。然而,要实现全局路线组合最优化,在计算上极为复杂,要考虑到所有路线的可能性。目前的一般路径算法是让每条路线单独达到最优,而最后的全局方案往往无法达到最优。
 
最近,英国阿斯顿大学和中国香港科技大学科学家合作,利用聚合体(由许多相同单体组成的高分子复合物)作用物理学和无序系统原理,来分析宏观层面的一般路线最优化问题。他们推导出一种简单的全局性路径算法,能用于伦敦地铁、全球航空网络和模拟互联网的随机路线图。而且分析显示,相变、比例法则、非单调增长及其他路径问题中出现的新现象都与物理学有关。
 
物理工具解决分析系统问题
 
“虽然用物理学工具解决分析系统的问题确实困难,但聚合体和路径之间的相似性却很容易理解。”研究员杨智浩(音译)解释说,“一个聚合体分子是一条长长的高分子链,就像一条有两个末端的绳子。假设用一个高分子来表示我的旅行路线:两端代表起点和终点,中间则是灵活可变的,取决于我们所选路线。如果每个旅行者的路线都如此表示,整个交通网中就有了一个聚合体系统。而交通网要尽量减少拥堵,我们在两个聚合体之间加入引力和斥力,引力表示鼓励旅行者选择相同路线,而斥力表示要尽量减少他们选择相同路线。”
 
假设所有高分子都拥有相同的网络构架,任意两个分子都可能发生路线重叠。“在高分子重叠时,它们之间会产生吸引或排斥作用,作用强度取决于重叠的程度,这又是一个涉及所有高分子的非局域问题。考虑到所有这些复杂性,我们要从所有可能的个别选择及重叠路线中找到最佳路线。”
 
“推导出理论之后,我们得到了直接的算法。”杨补充说,“我们还用几个数据库对它进行了测试,得到了很好的结果。一旦系统的分析问题解决了,要发现它的宏观特性就变得直接明了,比如平均路线长度、所需能源等。”
 
交通网的最优路线组合
 
有些人可能认为,最短路径总是最佳选择,实际上并非如此:当每个人都选择同一条路时,通常选最短路径都是糟糕的。比如在高峰时段,位于最短路径上的公共路线总是有更多车辆,这些路线就会比稍远些的路线行驶得更慢,造成延迟。
 
他们用伦敦地铁数据进行了模拟。结果发现,当所有乘客都选最短路线出行时,如果在乘客所选路线之间加入斥力,而且乘客接受了建议路线,平均路线长度会增加6%,但却能换来节约20%的预设成本。
 
“假如我们鼓励那些在非高峰时段出行的乘客选一般路线,而且允许大部分路线相同,这样,那些次级公交或火车线路(不太受欢迎路线)就会中止,从而节约大量能源。”杨智浩说,通过模拟聚合体系统之间的吸引力,能得到这种最优的共享路径组合。
 
当他们逐渐地将作用力从轻微排斥变成轻微吸引时,闲置节点的数量会急剧上升。“这就像其他物理系统的相变过渡期。”杨智浩说,“也就是说,只要在乘客所选的路线之间引入轻微吸引力,能在平均路径长度增加不多的情况下,大大增加闲置节点数量。这在交通状况较稀疏时,可节约大量资源。”
 
他们还用全球航空网络做了类似实验,也得到了类似结果。他们认为,在许多运输或通讯网络中,如果能更好协调每个人的出行路线,在节约能源方面会有很大改善。“这和普通的路线查询程序不同,那种程序只能简单地帮人们找出最短路线,并不涉及多人之间的相互作用。”杨智浩解释说,“以我们的算法为基础,可以开发出一种实时应用程序,为那些同时出行的人在全局范围协调路线选择,在高峰时段或高峰季节,实现高速路、地铁、火车或飞机使用平衡的目标。”
 
互联网的最优通讯路径
 
研究人员还将这种算法用于互联网中,用一种随机曲线来模拟互联网的覆盖网络,也就是在一个计算机网络上面建另一个网络,其中节点可看作是即时连接在一起的虚拟或逻辑连接,相当于一条路径,并与下层网络多个物理链接相连。加入斥力时,每条通讯路径就会避开其他路径,到最后几乎每个人都有自己的路径而不与他人路径重合;如果加入引力,通讯会集中在网络的一小块公共区域里,多人共享路径,留下大量节点和空置连接。如果把空节点看作是路由器,那么关闭它们就能节约大量能源。
 
“我们只是用一个简单的随机网络来演示,怎样通过加入的引力和斥力来找到最优通讯路径。”杨智浩说,“我们得到的是一个能实现多个目标的统一算法,只需改变聚合物之间控制引力和斥力强度的一个参数。它还可能用在其他方面,我们欢迎网络专家提出其他特殊的路线问题,来测试这种算法能否解决它们。”
 
杨智浩还指出,这种一般路线算法对任何有关路线选择和个体路线协调的问题都适用,希望本研究能有助于解决交通、通讯网络问题,帮助提高现有交通、通讯设施运营效率,减少重复建设。(原标题:《向高分子“交通网”学如何治堵》)
 
更多阅读
 
 
 
 
特别声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽。
 
 打印  发E-mail给: 
    
 
以下评论只代表网友个人观点,不代表科学网观点。 
SSI ļʱ
相关新闻 相关论文

图片新闻
海底泥火山是这样产生的 量子纳米金刚石有助更早检测疾病
火星赤道 曾遇洪水 激光核聚变反应堆里程碑:燃烧等离子体
>>更多
 
一周新闻排行 一周新闻评论排行
 
编辑部推荐博文
 
论坛推荐