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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社