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

Bimodal Cooperative Matching Algorithm for the Dynamic Ride-Sharing Problem

作　　者：郭羽含 刘永武 Guo Yuhan;Liu Yongwu(College of Sofware,Liaoning Technical University,Huludao,Liaoning 125105)

机构地区：[1]辽宁工程技术大学软件学院,辽宁葫芦岛125105

出　　处：《计算机研究与发展》2022年第7期1533-1552,共20页Journal of Computer Research and Development

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

摘　　要：车辆共乘可有效提升运输资源利用率,降低出行成本,缓解交通拥堵并降低环境污染.针对动态车辆共乘问题构建了整数规划模型,并提出了一种基于离线匹配和在线匹配的双模式协作匹配算法.在离线匹配阶段,以共乘比率和绕行距离为标准对匹配价值进行评估,设计了基于带权路径搜索树的通用共乘比率生成算法对共乘参与者进行准确高效的预匹配.在在线匹配阶段,提出了基于首尾距离度的实时订单插入算法,并对离线匹配结果中的行驶路径进行修正.通过双模式协作,可有效兼顾算法的实时性和结果质量.基于真实数据的大量实验结果表明,该算法给出的匹配方案在总匹配价值和求解效率上均优于实验中的对比算法,其平均离线匹配率达93.71%、平均双模式协作匹配率达85.53%,增加运输资源利用率82.86%,减少车辆并发数84.86%.Ride-sharing can effectively improve the utilization of transportation resources, decrease travel costs, alleviate traffic congestion, and reduce environmental pollution. Aiming at the dynamic ride-sharing problem, an integer linear programming model is constructed, and a bimodal cooperative matching algorithm based on offline and online matching is proposed. In the offline stage, the sharing route percentage and the detour length are adopted to evaluate the matching value, and a general sharing route percentage algorithm based on the weighted path search tree is designed to perform accurate pre-matching of the participants. In the online stage, a real-time order insertion algorithm based on the complex location to destination is proposed, and the routes obtained in the offline matching stage are further improved. Through the bimodal cooperation, the real-time performance and solution quality of the proposed algorithm can be significantly augmented. Finally, a large number of experiments based on real-world data are performed. The results show that the overall sharing value and efficiency of the proposed algorithm surpass those of the comparative algorithm. The average offline matching rate and the average bimodal cooperative matching rate reach 93.71% and 85.53%, respectively, while the transportation efficiency is improved by 82.86% and the vehicle concurrency is reduced by 84.86%.

关 键 词：车辆共乘 动态匹配 双模式 搜索树 距离矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]