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

作     者：郭羽含 刘永武 Guo Yuhan;Liu Yongwu

作者机构：辽宁工程技术大学软件学院辽宁葫芦岛125105 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2022年第59卷第7期

页      面：1533-1552页

核心收录：

学科分类：08[工学] 0903[农学-农业资源与环境] 0901[农学-作物学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金项目(61404069) 辽宁省自然科学基金项目(2019-ZD-0048) 辽宁省教育厅基础研究项目(LJ2019JL012)。 

主　　题：车辆共乘 动态匹配 双模式 搜索树 距离矩阵 

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