车载算法有望快速解决堵车问题

标签: 算法 堵车 问题 | 发表时间:2011-09-19 22:02 | 作者:猪的米 人精
出处:http://www.yeeyan.org

译者 猪的米

In recent years, various mathematical models and experimental measurements of traffic patterns have led to a consensus about the general kinds of traffic flows that can occur. There are three types.

近年来,多种关于交通模式的数学模型和实验测量都得出了一个相同的结论:一般来说发生拥堵都经历三个过程。

First is free flow in which the density of traffic is low enough to allow vehicles to travel at the maximum speed allowed. Then there is synchronised flow when a higher traffic density forces cars to travel at similar slow speeds but without stop-start motion. Finally, there is the jam in which the speed drops to zero when the traffic density rises above some threshold.

首先是畅通无阻,交通密度足够低,使得车辆能以最高时速行驶。不久之后由于交通密度的提高,车辆被迫以相对较低但仍相同的速度行驶,但不至于走走停停。最终,某一区域的汽车速度跌至零,造成交通密度骤然上升从而引起交通拥堵。

The way the flow transitions from one regime to another is hugely complex but a number of models, in particular those using cellular automaton, have become useful in studying how it occurs.

车辆流量的变化从一个区域传导到另一个区域的方式极其复杂,但一些模型如元胞自动机算法,对研究这个过程如何发生十分有用。

One interesting question is how best to dissolve jams once they form. Most traffic experts agree that the basic idea is to ensure that cars leave the jam more quickly than they arrive, so that the jam dissolves.

一个有趣的问题是,你如何在拥堵刚形成时就解决它。大多数交通专家都认为如果能够保证车辆逃离拥堵的速度比车辆聚集的速度更快,那么拥堵就能自行消失。

Now Hyun Keun Lee and Beom Jun Kim at the University of Seoul in South Korea have a come up with a simple idea to automate and improve this dissolving process. They define two types of drivers: optimistic and defensive. Defensive drivers leave more room to the vehicle ahead than required by safety. Optimistic drivers leave too little.

现在来自韩国首尔大学的Hyun Keun Lee和Jun Kim提出了一个简单的想法,能够自动并改善缓解过程。他们把司机分为两类:乐观型和防御型。防御型司机与前车留的距离会比安全距离大很多,而乐观型司机空的太少。

They then use a cellular automaton to model traffic flow in a way that reproduces most of the usual driving behaviours such as exceeding the speed limit, overreacting to road conditions by accelerating and braking to hard and so on.

接着他们用元胞自动机算法来模拟交通车流,这种算法能够重现普通驾驶员的行为诸如超速、对道路情况过度反应,比如加速或刹车过猛等等。

But they also add an extra ingredient. All the vehicles in this model share their speed and position with their neighbours and this information filters downstream. That means downstream vehicles immediately become aware that the traffic ahead has come to a standstill.

不过他们在这种情况中附加了一个条件,那就是所有的车辆都与附近的车辆共享它的速度和位置,并且这个信息会向“下游”传播。这意味着“下游”的车辆立即就能知道前面的车子停住了。

When that happens, Lee and Kim's algorithm immediately switches all the downstream driving behaviour to defensive, so that vehicles exceed the safe distance between them. This slows the rate at which vehicles join the jam.

当这种情况发生时,Lee和Kim的算法就能立即将“下游”车辆的驾驶模式调为“防御型”,因而车辆会将与增大与前车的安全间距,这样就能减缓后续车辆聚积的速度。

At the same time, vehicles leaving the jams are made to accelerate away quickly using automated cruise control. This increases the rate at which vehicles leave the jam.

与此同时,逃离拥堵的车辆将自动提高巡航速度,这样就加快了车辆离开拥堵的速度。

The result is that the jam quickly dissolves.

这种情况下拥堵将得到快速缓解。

That's an interesting and simple approach that could be implemented relatively easily in the next generation of cars. It's greatest value is that it requires no central control, only an on-board algorithm on most cars. It also requires a little more automated on-board control than cars currently have but not an unrealistic amount.

这是一个有趣而又简单的解决方案,能够相对轻松地应用于下一代的车辆上。它最大的价值在于它无需中央控制,只需在大多数车辆上加载一套算法。这只需要在现有的车辆控制上再装一个自动算法就行了,并不是一个不切实际的幻想。

But it will require a little more modelling to ensure that this kind of group control doesn't lead to other emergent behaviour that could be detrimental. Neither is it clear what percentage of cars must be fitted with this ability for the effect to work. But it certainly looks worthy of further investigation.

然而这套系统还需要一点建模来保证这种群体控制不会导致其他我们不想看到的情况。我们不太清楚需要多少车辆装备这个系统才能让整个系统有效运作,但这值得我们去进一步研究。

It's a little premature to say the traffic jams could be banished from the roads of the future but we may bot have to spend as long sitting in them.

现在说我们从此解决了拥堵问题还为时过早,但至少我们不用花费如此多的时间坐在车里干等。

相关 [算法 堵车 问题] 推荐:

车载算法有望快速解决堵车问题

- 人精 - 译言-每日精品译文推荐
In recent years, various mathematical models and experimental measurements of traffic patterns have led to a consensus about the general kinds of traffic flows that can occur.

算法系列总结:回溯算法(解火力网问题)

- 团子小囧 - 博客园-首页原创精华区
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法. 回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试. 用回溯算法解决问题的一般步骤为:. 1、定义一个解空间,它包含问题的解. 2、利用适于搜索的方法组织解空间. 3、利用深度优先法搜索解空间. 4、利用限界函数避免移动到不可能产生解的子空间.

顾森:稳定婚姻问题和Gale-Shapley算法

- - 博客 - 伯乐在线
每当有人问作者这样的问题时,他总会引用这个例子:假如你是一个媒人,有若干个单身男子登门求助,还有同样多的单身女子也前来征婚. 如果你已经知道这些女孩儿在每个男孩儿心目中的排名,以及男孩儿们在每个女孩儿心中的排名,你应该怎样为他们牵线配对呢. 最好的配对方案当然是,每个人的另一半正好都是自己的“第一选择”.

海量用户的积分排序问题算法的分析

- - SegmentFault 最新的文章
某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更新. 现在要为该网站设计一种算法,在每次用户登录时显示其当前积分排名. 用户最大规模为2亿;积分为非负整数,且小于100万. 表(user_score)的结构可以如下设计:. 通过使用一个简单的SQL语句查询出积分大于该用户积分的用户数量:.

分布式的一致性问题的算法

- - 行业应用 - ITeye博客
在分布式系统中,一致性(consensus)问题,是指对于系统中的多个服务节点,给定一系列操作,在一致性协议保障下,试图使得它们对处理结果达成一致. 在实际的计算机系统中,存在如下问题:. 节点间的网络通讯是不可靠的,包括任意延迟和内容故障;. 节点的处理可能是错误的,甚至节点自身随时可能宕机;. 同步调用会绕过系统变得不具备可扩展性;.

模拟退火算法应用于最优排列问题和最优组合问题 之 排列篇

- 团子小囧 - 博客园-首页原创精华区
一般学习模拟退火算法的时候,都是用全排列问题作为例子讲解,所谓全排列问题,就是说解的长度(或者步骤)是确定的,只不过排列顺序不同罢了,其中任何一种排列顺序都是问题的一个解,我们通过不断尝试不同的排列顺序,找到其中最优的一个. 象TSP旅行商问题就是典型的全排列问题,所有的城市都是两两互联的,每个城市都要去一次(且只能去一次),先去那个后去那个,顺序不同只不过花费的代价不一样,但都是问题的一个解决方案.

东京为何不堵车?

- - 徐静波 品味日本
  交通拥堵,是世界各国现代大都市面临的一个共同难题. 但是在东京,在这一座已经实现了城乡一体化的国际大都市,虽然做不到路路畅通、时时畅通,但是在上下班高峰期,东京不仅不会出现堵车,相反地是道路最为畅通的时间. 即使平时出现一些堵车,也是缓慢前行,不会出现堵死不动的问题,除非在高速公路上遇到了交通事故.

_00013 一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

- - CSDN博客云计算推荐文章
一般通常会想到的就是哈希取余了吧. 也就是 Hash(userid)% N (N=12),这样的话也能适当的减小很多压力了,但是这样的话又会产生一些新的问题,增加节点跟减少节点 :. 假如有一台Redis服务器挂掉了,那么是否这样 Hash(userid)% N (N=12) 哈希取余到该Redis的数据会全部丢失呢.

IJCAI 2019 丨利用半参表示算法缓解推荐系统中的冷启动问题

- - 雷锋网
由于常见电商、视频等推荐系统 (淘宝首猜、优酷推荐等) 用户量巨大, 而且用户个性化兴趣差异明显, Item-CF 较于 User-CF 有着天然的巨大优势,它因此被广泛运用于推荐系统中. 常见的 Item-CF 推荐系统中, 服务器收到用户访问请求, 经解析、查询得到用户 profile(包括用户长期画像、历史足迹等) 后,通过 Item2Item、tag 等方式进行候选召回,参与后续排序和后处理.

京藏高速堵车进入第11天

- 顾 - Solidot
备受关注的京藏高速公路大堵车已经超过了10天,《华尔街日报》称这次事件已经成为揭示中国汽车热阴暗面的一个符号. 自京藏高速从8月13日开始大修(原因主要是110国道北京延庆路况破损严重,110国道新线2007年底建成通车才开通2年)以来,北京远郊的交通就已经陷入混乱,并且正在向内蒙古省界蔓延. 紧接着的一个星期,一条环绕北京的主干道关闭部分路段,让道路更加不堪重负.