Uroad:一种高效的大规模多对多拼车匹配算法

Uroad:An Efficient Method for Large-Scale Many to Many Ride Sharing Matching

由于日益拥堵的交通环境和不断增加的私家车出行成本,越来越多的人关注并接受拼车的出行方式.虽然现在已经有很多针对拼车研究的算法,但是目前还没有从全局的角度出发考虑拼车匹配问题的算法.从全局的角度合理规划所有拼车匹配路线,使所有司机因为拼车而产生的绕路距离最小,这不但能减少空气污染还能缓解交通压力等.因此,提出了一种高效的大规模多对多拼车匹配算法Uroad来弥补这一不足.Uroad允许乘客在提出的拼车请求中包含出发时间段和最大拼车费用来表明自己要求的出发时间范围和对拼车服务最多愿意支付的费用;也允许司机提出出发时间和最晚达到时间约束来表明自己开始行程的时间点和最晚达到自身目的地的时间点.和其他拼车算法一样,Uroad根据乘客自身的行程距离和拼车后对司机造成的绕路距离来计算车费.根据乘客和司机的要求,Uroad支持多乘客与多司机全局最优匹配,并同时尽可能为每一名乘客匹配一名符合双方拼车条件的司机,最终使得所有司机产生的绕路距离总和最小.Uroad通过前期一系列的基于时间、欧氏距离、路网距离的3种空间剪枝策略来减少最短路径的计算量,从而提高算法的整体效率.实验结果显示,Uroad算法能在2 min内,实现1 000名乘客在100 000名司机中找出最优的拼车匹配组合方案,与直接计算最短路径的基本方法相比,整体耗时缩短了40%.和现有算法中乘客随机选择司机的策略相比,加入了全局优化策略之后,Uroad算法中所有司机的绕路距离总和可减少60%左右.

Due to the congested road and the increasing cost of private car,more and more people are willing to choose carpooling for travel.Although there are a lot of algorithms for ride sharing research,there is no algorithm to consider this problem from a global view.Plan all the matching routes from the global view and make all drivers'detour distances minimize,which not only can reduce air pollution,but also can ease the traffic pressure.This paper presents an efficient large-scale matching method for many to many ride sharing algorithm,called Uroad,to make up for the shortcomings of existing algorithms.Uroad allows the rider to request a ride service which includes the periods of departure time when he gets ready to start off and the maximum cost of the ride-sharing he is willing to pay for this service.At the same time,Uroad allows the driver to set the departure time to indicate when he will set out and the arrival time that he must reach to his destination before.The same to the other Carpooling algorithms,Uroad calculates the fare based on the distance of rider s trip and the detour caused by the rider.According to the requirements of riders and drivers,Uroad supports the global optimal matching among multiple riders and drivers,matches a driver who can meet the requirements to each rider as far as possible,and minimizes the total detour of all the drivers to reach the goal of environmental protection and reducing the traffic pressure.Uroad uses a series of time pruning techniques and Euclidean distance pruning techniques to reduce the calculation of the shortest path which can make the overall algorithm more quick and efficient.The experiments show that it is less than 2 minutes for Uroad to find the optimal combination of ride-sharing for 1 000 riders in 100000 drivers,which is 40% shorter than the direct calculation of the shortest path.Compared with the random selection of drivers,the total detours of all drivers can be reduced by about 60% with the global optimization strategy.