考虑用户偏好的启发式动态共乘匹配算法

Heuristic dynamic ridesharing matching algorithm considering user preferences

针对现有算法很少考虑用户之间的共乘偏好需求,提出了一种考虑用户偏好的启发式动态共乘匹配算法。构建一个满足用户偏好需求的动态共乘匹配模型,旨在最大化系统匹配率和最小化车辆的绕行距离。算法首先根据出行请求的时间约束、车辆与用户的出行轨迹以及用户的兴趣偏好,过滤不满足用户偏好需求的车辆;其次,构建一个临时匹配图,设置边的权值为出行请求插入到车辆的当前行驶路线中的最小绕行距离;最后采用贪婪方式实现用户与车辆之间的匹配,并采用节点插入方式,将出行请求的出发地点和到达地点插入到车辆的当前行驶路线中。仿真结果表明,提出的启发式动态共乘匹配算法使车辆增加的平均绕行距离和运行时间低于现有算法,系统匹配率高于现有算法;用户的出行时间需求、兴趣偏好、信誉度等共乘需求对系统匹配率有显著影响。

This paper designed a heuristic dynamic ridesharing matching algorithm considering user preference to overcome defects that the existing algorithms seldom considered the demand of ridesharing preference among users in dynamic ridesharing system.It established a dynamic ridesharing matching model to satisfy the user’s preference demands,which was to address the problem of maximize the system matching rate and minimize the vehicle detour distance.At first,the proposed algorithm filtered the vehicles that did not meet the user’s preferences according to the time constraints of travel requests,the travel trajectories of vehicles and users,and the user’s interests and preferences.And then,it constructed a temporary matching graph,and set the weight of the edge as the minimum vehicle detour distance when inserted a travel request into the current driving route of a vehicle.Finally,the proposed algorithm used a greedy method to realize the matching between users and vehicles,and adopted the nodes insertion method to insert the origin and destination of a travel request into the current driving route of a vehicle.The simulation results show that the average vehicle detour distance and runtime of proposed algorithm are lower than the existing algorithms,and the system matching rate is higher than the existing algorithms.The user’s ridesharing preference requirements such as user’s travel time demand,interest preference,reputation,and so on,have a significant impact on the system matching rate.