前沿 | MIT新论文:这个调度优化算法让纽约出租车数量减少了1/3-阿里云开发者社区

开发者社区> 技术小能手> 正文

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

简介:
+关注继续查看

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


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

6a61e7d714e7b77360ab649938c4a17dd7622486

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

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

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

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

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

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

d703d982f36725daa48705183908f1613b3d54d6

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

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

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


原文发布时间为:2018-06-4

本文作者:文摘菌

本文来自云栖社区合作伙伴“大数据文摘”,了解相关信息可以关注“大数据文摘”。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
图像算法的工程优化技术
图像算法的工程优化技术 当一个很酷的图像算法实现之后,我们希望集成到软件中去,这时将会遇到最大的拦路虎:性能。 可以想像一下,如果美图秀秀做一个美颜效果要转圈圈转个30秒,还会有多少人用呢。 学术界喜欢推出复杂度更低的算法,去解决性能问题,而在实际工程应用中,对代码的优化和硬件的良好运用效果来得更快更显著,这里就对不改动算法,纯工程方面做性能优化的技术作一个简介。
1315 0
神经架构优化(NAO):新的神经架构搜索(NAS)算法
如果你是一名深度学习实践者,你可能发现自己经常会遇到同一个关键问题:我应该为现在的任务选择哪种神经网络架构?
546 0
任务调度:时间轮算法经典案例解析及应用实现
平时大家的工作中应该会遇到较多需要在某个时间点执行某个任务,比如对运维来说,定时数据库的备份,日志和监控信息的抓取;比如业务系统,某个时间点给某个人群用户发放优惠券,甚至从操作系统角度,人机交互进程、视频播放的实时进程、批处理的后台进程等进程间的调度。。。 所以如何将这些任务高效、精准的调度?是任务调度系统中最重要的命题,当然在业务系统中一个完善的任务调度系统是很复杂的,需要具备能调度、可视化管理、过程可追溯、结果可分析、持久化、高可用等特性,这篇文章主要讨论任务调度逻辑,其余的内容我们后面文章探讨。
107 0
通过Android逆向之签名算法分析看apk安全防护
android安全问题日益验证,作为一名移动安全渗透人员,有时需要对移动apk进行全面的渗透测试,而不能仅仅局限于apk本身,此时往往就需要结合静态分析和动态分析进行。
1601 0
凑单算法——基于Graph Embedding的bundle mining
本文描述如何在凑单场景突破找相似、发现惊喜的同时做到成交翻倍,实现体验和数据上的双赢。
13528 0
七大基本排序算法C/C++(已优化及测试)
七大基本排序算法 已通过VS2015环境测试 可能不是最优算法,但是比基本版更好 完整项目GitHub 地址:https://github.com/cugwyman/7-Sorts BubbleSort冒泡排序 //BubbleSort冒泡排序,复杂度O(n^2...
685 0
+关注
技术小能手
云栖运营小编~
7208
文章
9
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载