当前访客身份:游客 [ 登录  | 注册加入尚学堂]
启用新域名sxt.cn
新闻资讯

现实中的排队算法问题:为什么排队时你似乎总会选择最慢的队伍

helloworld 发表于 2年前  | 评论(0 )| 阅读次数(585 )|   0 人收藏此文章,   我要收藏

为了赶紧买到个东西,你跑进了百货商店。你匆匆忙忙地选好你要的商品,朝商店前方走去。在迅速瞄了一眼收银处排的队伍之后,你选择了看上去最快的那列队伍。

你的选择大错特错。那些在你选择了队伍之后才在其他队伍排队的人已经付完帐去停车场了。为什么遇到这种事情的总是你?为什么这个残酷的世界会允许这种事情发生?这不公平!

呃,其实,这只是数学在碍着你的事罢了。

当你在百货商店里的不同队伍中踌躇时,机会并非对你有利。很有可能,别的队伍实际上更快一些。研究排队现象的数学家被称为排队论学家,他们有大量的 数据来证明这一点。他们的模型也是研究一系列多样化的现代问题的基础,这些问题包括交通工程、厂房设计、以及互联网基础设施。与此同时,排队理论为商店的 收银提供了一个更为公平合理的模式。唯一的问题就是其不为许多顾客所喜。

在探究这一问题之前,我们需要先去了解一个有些出乎大家意料的地方:哥本哈根电话局。20世纪早期,年轻的工程师Agner Krarup Erlang就试图计算出哥本哈根接线总机的电话线路的最优数量。这要追溯到运营商还处于人工接线,并将拨片连到线路中才能接通电话的年代。

为了节约人力成本和基础设施,Erlang想要搞清楚能够确保每个人的电话都被接通的必要线路的数量。一个成本很低的总机可能就只有一条线路。但这 样的话打电话这件事就会让用户备受折磨,其他人想要打电话的同时你也想打电话,你就只能乖乖跟在后面等。 而要是给这个城市的几千部电话机每部都配上一条线路,也是没有实际意义的。

让我们看一个简化版的例子。如果哥本哈根接线总机每小时平均接通两个电话的话,你也许觉得两条线路就够了。但是这没把实际情况考虑进去,实际情况是 可能有些时间段电话多一些,有些时间段少一些。繁忙时段时,总机可能会收到5个接线要求,但两条线路也就只能为两个用户接通电话,其他用户则会占线。如果 丹麦人都特别话唠的话,电话可能要讲一个小时,这就意味着会有更多的电话在同一时间处于等待状态,然后整个电话系统就都堵了。

Erlang构建了一个关于特定的某一小时内电话的平均数量以及每一通电话平均花费的时间的方程。将他的方程代入上述的例子中,哥本哈根电话局会发 现他们需要7条线路以保证99%的电话能够即时接通。1909年,Erlang针对他的研究发表了一篇论文,开创了一门新的数学分支学科——排队论。

现在,排队论的研究在诸多不同的领域都有所应用。比如,拥有客服中心的公司经常运用排队论来处理客户反馈的问题。一些基本的、普遍的问题,由相对来 说技能要求较低但人数众多的业务代表来处理。稍复杂些的问题则由一些受了较多培训的员工解决。客服中心可以使用Erlang的研究成果来确定每种类型的业 务代表的最优数量,而并不是如大众所想的那样,是个由撒旦定下的随机数字。

让我们回过头看看那些超市里在你之前结账的人。排队论解释了为什么你总是没法处于那条最快的队伍中。一个百货商店设法在收银台配备足够的收银员让所 有顾客以最快速度完成付款。但有时,比如说周日下午,收银员就会超级忙。因为大多数百货商店没有足够的物理空间来再增加一个收银队伍,他们的收银系统不堪 重负。一些小杂事——一次价格速查、一个特别能侃的顾客——都会引起下游效应——让其身后的队伍停滞不前。

如果一家店里排了三条队伍,这种延迟可能会随机地发生在不同的收银台前。想一想发生的几率。你所在的队伍成为最快的队伍的机会只有三分之一,这也意味着你有三分之二的几率不处于那条最快的队伍中。所以说这可不仅仅由你决定:可能另一条队伍比你的队更快。

现在,排队论学家已经想出了一个解决这一问题的好办法:让所有顾客排成一条长长的蛇形队伍,也被成为蛇形队,每个处在队伍最前端的顾客去下一个空闲 的收银台前。如果有三个收银台,这种方法比传统方法平均快三倍。这种方法在大多数银行、Trader Joe’s连锁商店以及一些快餐店中已经开始使用。在蛇形队中,一个收银台前的拖延不会影响后面排着队的无辜者,相反,这会耽误所有人的时间。

那么为什么许多地方却不鼓励排蛇形队呢?此时,我们就要从消费心理学入手了。我们人类倾向于认为,如果有机会,我们能控制我们的生活,钻规章制度的 空子。研究人员指出一些消费者拒绝接受蛇形队,因为蛇形队比普通队伍排得更长,他们更喜欢那种在多条队伍中走好运排到较快队伍中的机会。

排队论不仅仅在数学方面得到发展,它也结合了心理学层面。电梯大堂里通常都装有落地镜,这有助于缓和人们在等待下班电梯时的厌烦心理。诸如在迪士尼 等游乐场里的排队的队伍也与各种各样的娱乐活动相结合——比如排队时的背景变换、队伍要穿过不同的房间、经过不同的大屏幕——在让游客等待两小时只为玩五 分钟的同时,也让游客全神贯注,感觉好像在为了一个目标奋进一样。智能手机可能是赐予现代的排队者们的最好的奖赏,几乎每个人在等待的同时都能靠玩游戏、 刷社交网络或者浏览网页来杀时间。

最后,为了证明最理性的选择并非总是最优选择,还有一个关于麻省理工学院的杰出的排队论学家Richard Larson的搞笑轶闻。在一次关于排队论的研讨会上,Larson说有一次一个宾馆大厅因为人多,阻塞了排队论学家们的登记入住。这群数学家们决定自力 更生,自发形成了一个蛇形队以控制速度。

但是,正如Larson2012年对《Slate》杂志所说的那样:“大厅的设计并不适宜蛇形队,蛇形队看上去乱哄哄的,宾馆经理的脸色也很不好看。如果我们在前台分散排成六个平行队伍,那么等待的时间会更短些,混乱程度也少一些。但是,公平性也就会少一些。”

英文原文标题是:What’s Up With That: Why You Always Seem to Choose the Slowest Line

分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183