融合用户相似度与时间期望的长期车辆共乘匹配算法

Long-term ride-sharing matching algorithm based on user similarity and time expectation

长期车辆共乘可显著提升出行便利性和稳定性,对缓解城市交通拥堵、减少环境污染具有重要作用,但由于需同步进行分组规划和路径规划,其全局最优匹配方案难以获取且匹配结果的可行性无法保障。针对上述问题,基于行驶距离、行驶时间、出发抵达期望和整合熵权相似度,构建了带有时间窗和车容量约束的多目标混合整数规划模型,采用复合熵权法对独立相似度进行融合,并提出一种质心寻优小簇分割算法对共乘用户进行匹配划分。在用户分割过程中迭代优化共乘组质心,并采用减枝枚举法计算用户的最佳行驶路径,生成符合多元约束的共乘组划分方案。实验结果表明,所提算法与一般K-Means聚类算法相比,平均近似解提高了9.66%。平均时间减少了49.29%,且在处理大规模实例上效果明显,能够高效求解长期车辆共乘匹配问题。

Long-term ride-sharing significantly improves travel convenience and stability,and plays an important role in alleviating traffic congestion and reducing environmental pollution.However,due to the simultaneous group planning and route planning,it is difficult to obtain the global optimal matching scheme and the feasibility of the matching results cannot be guaranteed.In view of the above problems,a multi-objective mixed integer programming model with time window and vehicle capacity constraints was constructed based on travel distance,travel time,departure and arrival expectation and integrated entropy weight similarity.The independent similarities were fused by the compound entropy weight method,and a centroid optimization based mini-cluster segmentation algorithm was proposed to match and divide ride-sharing users.In the process of user segmentation,the center of the ride-sharing group was iteratively optimized,and the best travel route of each user was calculated by the pruning enumeration method to generate a ride-sharing group division scheme that met multiple constraints.The experimental results shows that the average approximate solution of this proposed algorithm is improved by 9.66%compared with the general K-Means clustering algorithm,and the average time is reduced by 49.29%.The algorithm has obvious effects in dealing with large-scale instances and can efficiently solve the long-term ride-sharing matching problem.