前沿 | 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 计算平台

在本篇中,将走进工业界,看一看半导体厂商和互联网巨头在 AI 计算中的不同选择。

6463
来自专栏ATYUN订阅号

自动驾驶:摆脱3D地图,MapLite系统只需GPS和传感器即可导航

在导航缺失的路段行驶自动驾驶汽车是一项艰巨的任务。实际上可供自动驾驶汽车行驶的路段也不多。像谷歌这样的公司只会在大城市测试车队,他们花了大量时间,精心制作了城市...

1013
来自专栏企鹅号快讯

城市堵车的根本原因并不全是车太多,已有解决办法

日前,美国麻工理工学院计算机和人工智能的研究表明,汽车行驶中在不频繁变道的前提下,保持好与前车和后车的距离,将有效地改善路面交通堵车的情况发生。 ? 研究人员称...

2319
来自专栏量子位

对冲基金第三次浪潮:硅谷和华尔街从未如此接近

量子位 | 李林 编译整理自 Wired ? 来自华尔街的Jeffrey Tarrant,过去三十年里一直投资新的对冲基金。他总是用YC来类比自己的工作,YC在...

35110
来自专栏PPV课数据科学社区

量化投资:深入浅出量化对冲Alpha基金的操作

1.量化 对于一般投资者,甚至是部分金融从业者来说,量化投资都是一门高大上的技术,充斥着模型代码和算法假设,门槛非常高。其实,生活中的量化思想无处不在。 例如,...

3013
来自专栏新智元

【智驾深谈】羡慕Tesla全自动系统?不能错过这五篇经典(全文下载)

【新智元导读】Tesla发布了新版AutoPilot系统,还发布了一段从家到公司的全自动驾驶视频,伴随着Musk一句“我们能五级全自动了”,业界开始争论不休。这...

3348
来自专栏新智元

滴滴研究院副院长叶杰平:深度学习在交通领域应用潜力巨大【北大AI公开课第9讲】

【新智元导读】 在北大 AI 公开课第9讲上,滴滴出行副总裁、滴滴出行研究院院长叶杰平老师,和北大人工智能创新中心主任、曾经的“百度七剑客”之一雷鸣老师一道,为...

3666
来自专栏企鹅号快讯

人工智能的回报率:对冲基金嵌入机器学习?

ARTIFICIAL intelligence (AI) has already changed some activities, including part...

1779
来自专栏人称T客

研究:2016年知名SaaS市场估值大盘点

T客汇官网:tikehui.com 撰文| 李哲 ? 近期,咨询机构Centaur Partners发布了《2016 SaaS市场概述介绍》的研究报告,对Saa...

2798
来自专栏新智元

谷歌 TPU 的强大与局限:TPU/GPU/CPU性能功耗全面对比

【新智元导读】谷歌公布 TPU 论文(被ISCA-17 接收)引发新一轮讨论,连英伟达CEO黄仁勋都亲自撰文回应。使用 TPU 代表了谷歌为其人工智能服务设计专...

4739

扫码关注云+社区