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

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