动态车辆共乘问题的双模式协作匹配算法

摘要

车辆共乘可有效提升运输资源利用率,降低出行成本,缓解交通拥堵并降低环境污染.针对动态车辆共乘问题构建了整数规划模型,并提出了一种基于离线匹配和在线匹配的双模式协作匹配算法.在离线匹配阶段,以共乘比率和绕行距离为标准对匹配价值进行评估,设计了基于带权路径搜索树的通用共乘比率生成算法对共乘参与者进行准确高效的预匹配.在在线匹配阶段,提出了基于首尾距离度的实时订单插入算法,并对离线匹配结果中的行驶路径进行修正.通过双模式协作,可有效兼顾算法的实时性和结果质量.基于真实数据的大量实验结果表明,该算法给出的匹配方案在总匹配价值和求解效率上均优于实验中的对比算法,其平均离线匹配率达93.71%、平均双模式协作匹配率达85.53%,增加运输资源利用率82.86%,减少车辆并发数84.86%.