面向道路拥塞的拼车服务质量保障算法

Congestion-aware Carpooling Algorithm for Passenger's Quality of Service

拼车可缓解城市道路拥堵,并降低日常出行成本。现有拼车方法往往忽略道路拥堵对于乘客拼车服务质量的影响,从而导致拼车服务成功率降低。为此,以乘客、司机正收益,以及乘客因为道路拥堵导致不耐烦等待时间最小为约束,定义了基于道路拥塞情境的短途拼车优化问题CAC。为解决上述问题,基于Shapley最优值设计贪心策略加以解决。实验结果表明,在满足乘客服务质量约束下,所设计方法相较于已有算法,可显著提升拼车成功率。

Carpooling could not only alleviate traffic congestions,but also reduce people's daily traveling costs.Existing works failed to incorporate the influences of traffic congestion to passenger's quality of service,causing the reduction of carpooling success rate.In this work,considering the constraint of positive utilities of both drivers and passengers,we investigate and formulate the congestion-aware short-range carpooling problem termed as CAC.To solve the above problem,a greedy algorithm had been developed on the basis of the Shapley value.Simulation results demonstrated that the designed algorithm outperform the existing algorithm while meeting the passenger's quality of service constraint.