一种新的算法让分析一亿五千万纽约计程车的GPS数据成为可能。 图片来源:Thinkstock 时下打车手机应用越来越流行,在美国提供打车服务的公司优博Uber市值已经达到18亿美元。即使面临法律纠纷,仍然有一些利用有合格执照的计程车提供相似服务的公司涌现出来。 试想一下,如果你可以通过手机应用上的一个按键来告诉别人你愿意跟其他乘客共搭一辆计程车会怎样?如此拼车是不是会大大减少交通压力,乘车费用以及二氧化碳排放? 要想给出一个权威的答案需要分析大量的数据/海量数据,这对传统计算方法来说是不可行的。不过在今天的美国科学院院报刊登了一篇论文,来自麻省,康奈尔,和意大利国家研究学会情报和信息技术研究所的研究者们提出了一种新技术。这种新技术可以帮助人们详尽分析纽约市13000辆计程车一年内的一亿五千万条乘车记录。 他们的结论是:如果乘客能够每次忍耐不超过五分钟的延迟,那么95%的出行都可以实现拼车。最优的“混搭”乘车方案可以使人们的出行总时长减少40%,同时出行费用和二氧化碳排放也会相应减少。 “当然,没人会强迫你去拼车”,论文作者之一,麻省城市研究和规划部教授卡洛•拉提说道:“不过,我们的研究结果说明了如果人们把拼车作为一种选择的话,会有什么样的效果。” 研究过程 要想寻找这样一个最优的拼车方案,需要预先知道出行的时间。比如横穿曼哈顿的一辆30分钟车可以在开车10分钟后接上另一名客人,然后共乘15分钟。但如果乘客是使用手机应用的话,这种预先计划就不太可能实现/但这种预先计划不太可能通过手机应用实现。所以研究者在分析数据的时候假定,只有出行时间相差一分钟以内的乘客才可以拼车。即便如此,仍然可以缩减32%的出行时间。 “我们认为这项举措有可能节省30%的经营开支,如此一来就有了利润空间使各方受益:给顾客提供更低的价格;提供优惠吸引司机们加入这个体系;公司提高收益;当然对社会也是益举”,麻省城市研究和规划部的访问学者,论文第一作者保罗•桑提(Paolo Santi)如是说。 实际上,桑提还说道,由于这项成果如此引人注目,他们还特地请了来自康奈尔的数学家,论文的合作者斯蒂文•史楚盖兹来核查他们的研究方法。同为论文作者的还有来自麻省智能城市实验室的拉提(Ratti),博士后斯坦尼斯拉夫•苏波拉温斯基(Stanislav Sobolevsky),西北大学的迈克尔•赛尔Michael Szell(当时是智能城市实验室的博士后)以及与桑提一样来自情报和信息技术研究所的乔瓦尼•瑞斯塔Giovanni Resta。 在分析这些打车数据来寻找可以实现拼车的机会时,“通常我们采用的方法就是解决所谓‘推销员出差’问题的变体,”桑提解释道:“就是在最基本的算法框架的基础上增加了与人合乘的概念。 推销员出差问题要解决的是:给定推销员要去的一系列城市和出差时间,可以找到一条路线使他可以再规定时间内走遍这些城市。不过,推销员出差问题同时也是一个——也许是最著名的——没有最优解问题。也就是说即使是最精简的数据库设定,也不能在理想时间内解决。 研究结论 有鉴于此,桑提和他的同事们采用了另一种算法。首先,他们把每条乘车记录按特征归为四类:上下车的时间及GPS坐标。然后标定出与每条路线有重叠的线路(起点位于上一条终点之前),继而决定出在规定的延误时间内可以拼合在一起的线路。每条给定的路线平均能有100条可选路线拼合。 下一步,这套算法把所有1亿5千万的乘车记录是否适于合乘的信息制成图表。图表可以通过点和点与点之间的连线这些抽象的数学符号来传达信息。这里用一个点代表一次乘车,用线表示是否适于拼车。这张图表是研究者做进一步分析的关键。有了它,我们就可以通过一些既有的算法有效找出一个最优解,无论是要求有最多的合乘人还是最短的出行时间。 研究者们同时还通过实验中保证他们的这套算法切实可行,能够在手机软件内应用。实验的结果是即使是一台Linux台式机,也能在0.1秒内算出10万条路径之中的最优搭配,而GPS数据显示纽约的打车记录只有平均每分钟300条。 最后,MIT的泽尔开发了一款以纽约市地图为界面的在线应用,帮助人们建立自己的乘车数据 大卫•玛法达是一家汽车和出租车公司Bandwagon的CEO。这家公司的经营理念就是建立在这种拼车出行模式之上。大卫说,桑提和他的同事们所分析的这些数据,在他们的公司则是雇人来分析。 “我们分析了从拉瓜迪亚机场出发的乘车数据,也能绘制出那些人们出发频率高的起点的详细地图。不过我们确实进行了一些简化,从而能着力解决一些更贴近实际的问题。让整个数据库可查询,并且具有切实的可行性是一个更大的跨越” 玛法达说Bandwagon的创立,就是基于有“相当数量”的打车出行是可以实现拼车的。“现在MIT的研究证实了这一点。能够有这样的外部证明,对我们的商业运营也是有好处的。” 他还补充道,在拉斯维加斯举行的2014消费者时尚电子产品展上,Bandwagon为与会者运行了他们这项应用的一个展示版本。在四天的时间里,拼车出行节省了18000美元的各种花费和1000磅以上的二氧化碳排放。不过最重要的是节省了乘客的时间。 “研究中最重要的成果是拼车到底能给人们节省多少时间”,玛法达说“很多时候人们都认为要想与人拼车一定要花费更多的等待时间。但是在堵车的时候,拼车显然就是一种更快的选择了。”
原文链接: http://newsoffice.mit.edu/2014/rideshare-data-cut-taxi-time-0901 本文版权属于研发埠所有,如需转载请注明出处!
|