王一丁、元元、Aileen编译

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

文章来源于微信公众号大数据文摘(ID:BigDataDigest):普及数据思维,传播数据文化。

麻省理工学院的研究人员表示,他们发明了一种高效的调度算法,可以将城市的出租车数量减少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.

产业
1
相关数据
参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

自动驾驶技术
self-driving

从 20 世纪 80 年代首次成功演示以来(Dickmanns & Mysliwetz (1992); Dickmanns & Graefe (1988); Thorpe et al. (1988)),自动驾驶汽车领域已经取得了巨大进展。尽管有了这些进展,但在任意复杂环境中实现完全自动驾驶导航仍被认为还需要数十年的发展。原因有两个:首先,在复杂的动态环境中运行的自动驾驶系统需要人工智能归纳不可预测的情境,从而进行实时推论。第二,信息性决策需要准确的感知,目前大部分已有的计算机视觉系统有一定的错误率,这是自动驾驶导航所无法接受的。

调度技术
Scheduling

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。 进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态,允许多位用户有效地同时共享系统资源,或达到指定的服务质量。 see planning for more details

旅行推销员问题技术
travelling salesperson problem

旅行推销员问题是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是旅行购买者问题与车辆路径问题的一种特殊情况。 在计算复杂性理论中,TSP的做决定版本属于NP完全问题。

权重技术
Weight

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

推荐文章
AI 赋能百度地图 全量数据采集索引真实世界
藤子
【日报】发明「@」符号的人走了、比利时大学生制作蝎子机器人…
机器之心
BCG报告:自动驾驶时代来临前的万字忠告
PSI内容合伙人
返回顶部