前沿 | 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.