前沿 | 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 条评论
登录 后参与评论

相关文章

来自专栏腾讯技术工程官方号的专栏

腾讯AI Lab研发「智能显微镜」 抢先布局病理分析领域

腾讯 AI Lab 今日在南京举办的「腾讯全球合作伙伴大会」上宣布,其AI+医疗领域研究已抢先从影像筛查进入病理分析阶段,相关的「智能显微镜」项目已在研发测试阶...

2722
来自专栏量子位

马斯克自曝首辆量产版Model 3,这辆特斯拉买菜车终于要来了

雷刚 发自 凹非寺 量子位报道 | 公众号 QbitAI ? 购买特斯拉汽车本质上是时间问题,无论是Model S,还是Model X,用户平均等待时长是3年。...

3459
来自专栏人人都是极客

自动驾驶汽车硬件系统概述

如果说人工智能技术将是自动驾驶汽车的大脑,那么硬件系统就是它的神经与四肢。从自动驾驶汽车周边环境信息的采集、传导、处理、反应再到各种复杂情景的解析,硬件系统的构...

1241
来自专栏人工智能快报

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

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

2355
来自专栏专知

自动驾驶的“大脑”-控制工程篇(二)

点击上方“专知”关注获取专业AI知识! 自动驾驶的“大脑”——控制工程篇(二) 中国人工智能系列白皮书 -智能驾驶2017 中国人工智能系列白皮书 --智能交通...

4737
来自专栏吉浦迅科技

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

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

3435
来自专栏新智元

【智驾深谈】Tesla再现匝道口致命隐患:谈高精地图和定位的重要性

【新智元导读】估计最近Elon Musk是失眠的。Tesla又爆出月初有一次高速路上的翻车事故,车辆损失惨重,好在驾驶员和乘客只受了小伤。表面上看起来这并不是什...

4508
来自专栏吉浦迅科技

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

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

35914
来自专栏人工智能头条

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

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

1063
来自专栏机器之心

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

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

3367

扫码关注云+社区