@ 2018.05.28 , 11:00

MIT新调度算法可以减少3成的出租车

MIT新调度算法可以减少3成的出租车

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

他们在几天前出版的一篇论文中介绍了他们的工作。

“如果优化我们对出租车的管理,甚至只需要指挥司机,纽约的出租车车辆就可以减少30%。”麻省理工学院可感知城市实验室主任Carlo Ratti告诉IEEE Spectrum。无论对出租车还是对城市街道的利用率来说,这都是效率巨大的提升。纽约有一万四千多辆出租车,每天搭载乘客总共要跑50万趟左右。

这项技术似乎可以帮助陷入困境的出租车公司避开私人乘车服务的打击,如优步和Lyft。他们有自己的算法,有的算法优化匹配司机和乘客,有的算法分享乘客。

触动Ratti和他的同事们进行研究的起因是,2014年,他们发现如果曼哈顿的出租车乘客愿意多花五分钟的时间,他们中就有近95%的行程可以共享。这将减少乘客花费在租车上达40%的总时间。

这次,研究人员分析了一个更好的调度模型需要如何更好地利用现有的出租车队列,也就是说,不再假设同路的乘客共享里程。他们称之为最小舰队问题,并且他们以旗舰玩家的身份来调度所有船只/车辆。通过适当地估计某趟运营中出租车的目的地与下一次潜在出行起点之间的最小化距离,该模型保证了在给定的时间段内每辆车可以运送最多的乘客。

一个通用的完美算法可以解决著名的旅行推销员问题,该问题试图找到推销员路过所有城市的最短路径。然而,随着城市数量的增加,这个问题很快变得异常的棘手。你可以在新加坡实现最优路径,但无法为美国找到那个解。

相反,麻省理工学院的研究人员创建了他们所谓的车辆共享网络,类似于他们在2014年用于优化乘客共享历程的网络。它看起来像一个图表,其中每个节点代表一次发车,每条连接两个节点的线代表一辆车可以连续接送的两趟路程。调整图的布局尽可能让最多的点被线连接在一起。这样就保证,所有的出租车司机,每次送走一个客人的时候,在几乎相同的位置和时间点上就能接到另一位客人。节约了在路上寻找客人的时间。

如果曼哈顿全部28万辆左右的汽车都采用自动驾驶,在麻省理工学院总体规划的控制下,效率能提升多少呢? “如果我们有一座完全智能的城市,”Rotti说,“汽车减少量将接近50%。”

本文译自 IEEE,由 majer 编辑发布。

支付宝打赏 [x]
您的大名: 打赏金额:
赞一个 (4)