前沿 | MIT新论文:这个调度优化算法让纽约出租车数量减少了1/3

大数据文摘出品

编译:王一丁、元元、Aileen

麻省理工学院的研究人员表示,他们发明了一种高效的调度算法,可以将城市的出租车数量减少30%。

他们的研究成果近日发表于《自然》杂志。

大数据文摘公众号后台对话框回复“调度”下载本论文~

麻省理工学院 Senseable City Lab 主任Carlo Ratti告诉《IEEE Spectrum》杂志,“如果对出租车或驾驶人员进行更好的管理,纽约的车辆可以减少30%。”纽约的一万四千多辆出租车每天大约出车50万趟。无论是从出租车的角度还是从占据城市街道空间的角度来看,精简车辆可以大大节约资源。

目前顺风车服务异常火爆,他们开发自己的算法优化匹配司机和乘客,或者匹配拼车的乘客。像优步和Lyft这样的公司一度让出租车生意陷入困境。麻省理工学院开发的调度算法给传统的出租车行业带来了曙光。

时间回溯到2014年,Ratti和他的同事们就开始研究共享出行。他们的研究表明,如果曼哈顿的出租车乘客能够多等5分钟,近95%的情况下,他们有机会和别人拼车。而拼车会使所有乘客在出租车上花费的总时间减少高达40%。

现在,研究人员基于现有出租车模式(即抛开拼车的假设)来优化调度模型。他们称之为最少车辆调度问题。解决问题的思路与台球高手击球的思路相似,即每次击打都要考虑下一杆。模型通过给出恰当的权重使出租车的目的地与下一可能的行程起点之间的距离最小化,从而达到在一定时间内每辆车运送更多乘客的结果。

对著名的旅行推销员问题的研究可以为此问题提供一个完美的解决方案。旅行推销员问题(Traveling Salesman Problem)是为一个推销员找到能经过每个推销点的最短路径。然而,随着地点数量的增加,这个问题的复杂度迅速提升。如果范围是一个小镇,我们还有希望;如果是曼哈顿,那问题就复杂得多。

麻省理工学院的研究人员采取了另一种方案。他们创建了一个“车辆共享网络”,类似于2014年他们用于优化共享出行的网络。这个网络看起来像一个图表,其中每个节点代表一个行程,每条连接两个节点的线代表同一辆车可以完成的两个行程。研究人员不断变换图表,虽然不能得到完美的答案,但是可以不断改进解决方案。

构建车辆可分享性网络,使最低车队数量问题能以参数δ最优解决。

车辆数最小化分析,显示了使用这个算法解决纽约市整个出租车需求所需的每日车辆数量

车队效率比较,与纽约市目前的出租车运营相比,循环出租车的数量可以减少40%,并且在当天保持相当稳定

基于网络的在线车辆调度模型的性能 - 在减少30%的出租车数量并使用该算法的在线版本的情况下,超过90%的出行请求可以成功地接受到服务;当每日需求可以被提前预知的话,其性能非常接近可减少40%的所需车辆

通过引入“车辆共享网络”的概念,MIT提出了一个最佳的计算有效的解决方案,以及一个适合实时实现的近乎最佳的解决方案,用两年内在纽约市进行的1.5亿次计程车数据集测试了这个解决方案。

与目前的出租车运营状况相比,实时实施该算法可把所需出租车数量规模减少30%。尽管司机档期的限制以及特殊的出行需求可能会导致实际车辆数量会超过最优价值,但车辆数量对于历史出行需求的各种变化仍然十分可靠。随着网络化自动驾驶汽车的普及,这个研究结果可能在未来几年变得更加有意义。

如果曼哈顿岛上大概28万辆汽车全部换成自动驾驶的车辆,在麻省理工学院的网络调度下行进,会有什么样的结果呢?Rotti告诉我们,“如果我们城市的交通完全达到自动驾驶,车辆数量将减少约50%。”

大数据文摘公众号后台对话框回复“调度”下载本论文~

相关报道:

https://spectrum.ieee.org/cars-that-think/transportation/mass-transit/mit-finds-mathy-way-to-minimize-taxi-fleet

https://www.nature.com/articles/s41586-018-0095-1

http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml.

原文发布于微信公众号 - 大数据文摘(BigDataDigest)

原文发表时间:2018-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏BestSDK

腾讯优图:开放天眼SDK,提供车辆识别、检测、追踪等服务

腾讯优图面向交通行业推出智能化解决方案,可以检测并追踪车辆和行人、结构化存储车辆和行人信息、自动识别车辆违章行为、自动识别拥堵等路面情况,并提供以图搜车等功能,...

78014
来自专栏人工智能头条

AI 3分钟:一张图看懂AI;谷歌3位 AI 女高管离职;全自驾驶药丸;吴恩达新课让领导学AI;索尼训练ImageNet创纪录

禅师很小的时候看过一部叫做《霹雳游侠》的美国电视剧,讲述的是一部拥有智慧的汽车,可以自己操控自己,协助主角完成很多危险任务。

753
来自专栏人工智能快报

麦肯锡专家指出自动驾驶主要挑战与发展方向

麦肯锡专家Kersten Heineke、Philipp Kampshoff、Armen Mkrtchyan和Emily Shao等人撰文讨论了自动驾驶面临的主...

2205
来自专栏大数据文摘

Neurons字幕组 | 2分钟告诉你飞秒成像的秘密

1353
来自专栏吉浦迅科技

解放手指:将 VR 最困难的挑战交给 GPUs(含论文)

在实体环境里,双手就是带领我们认识这个世界的工具,我们用手来感觉、来操作、来探索,还用双手来吃饭喝水、穿衣打扮、赚钱谋生,以及跟他人建立关系。 而要是能在虚拟世...

3264
来自专栏吉浦迅科技

NVIDIA 为未来无人自动驾驶交通工具推出人工智能超级计算机“Xavier”

NVIDIA 执行长黄仁勋在首届 GPU GTC Europe 大会上,介绍 NVIDIA 为自动驾驶车所设计的全新人工智能超级计算机“Xavier”。 “这是...

3405
来自专栏吉浦迅科技

读取人工智能车辆的心思:NVIDIA 的神经网络如何做出决定

在变化条件无穷无尽的情况下,想要开发出一部在各种情况下都能自动驾驶的车辆,一点都不切实际。 然而拜人工智能之赐,我们能够教它怎么开车,而车跟你家中正处于青春期的...

35414
来自专栏机器之心

专栏 | 为什么只用摄像头和光学雷达是不够的:我们能从Uber的自动驾驶车致死事件中学到什么

机器之心专栏 作者:陈熙 (Nuance)、刘学(麦吉尔大学) 1. 事件回顾 3 月 18 日星期天晚十点左右,Uber 的一辆自动驾驶 SUV 在美国亚利...

3287
来自专栏量子位

高精地图对自动驾驶有多重要?和一般导航地图有何区别?

作者:陈光 上汽集团 | 高精度地图&环境建模工程师 量子位 已获授权编辑发布 转载请联系原作者 在社交媒体上红极一时的Tesla AutoPilot功能,并还...

3985
来自专栏专知

给自动驾驶一双通天眼——环境感知器篇

? 视频是Tesla自动驾驶简述 给自动驾驶一双”通天眼” ...

1K5

扫码关注云+社区