基于分解算法的动态大规模合乘匹配-路径规划  

Dynamic Large-scale Ride-matching and Route Planning Based on Decomposition Algorithm

作　　者：孙芮 吴文祥[1] SUN Rui;WU Wen-xiang(School of Electrical and Control Engineering, North China University of Technology, Beijing 100144, China)

机构地区：[1]北方工业大学电气与控制工程学院,北京100144

出　　处：《科学技术与工程》2022年第4期1662-1668,共7页Science Technology and Engineering

基　　金：国家自然科学基金(72071003)。

摘　　要：动态合乘是出行路线相似的出行者共用一辆车的交通方式,能够有效利用现有资源,最大化社会效益。当前合乘研究存在司机-乘客匹配质量不高,算法实时性差等局限。提出了考虑订单匹配数量、司机旅行时间、乘客等待时间与乘客延误时间的司机-乘客合乘匹配模型。针对模型特点,设计了基于分解方法的司机-乘客合乘匹配与路径规划算法。通过选择贪心随机自适应搜索算法、粒子群算法与本文的算法对比,成都市网约车数据验证,结果表明:分解算法下司机与乘客不方便成本低于贪心与粒子群算法;分解算法订单匹配率在90%以上,高于贪心与粒子群算法的80%~90%匹配率。通过对比证明,所提出的模型与算法,能够在保证高匹配率的前提下,降低出行不方便成本,提高算法实时性,在实际工程中有较好的应用效果。Dynamic ride-sharing is a mode of transportation in which travelers with similar travel routes share the same vehicle,which can effectively utilize existing resources and maximize social benefits.There are some limitations ride-sharing research,such as poor driver-rider matching quality and poor real-time performance of algorithm.A driver-rider ride-sharing matching model was proposed,which took account of order matching quantity,driver travel time,rider waiting time and rider delay time.According to the characteristics of the model,a driver-rider ride-matching and route planning algorithm based on decomposition method was designed.By comparing the greedy randomized adaptive search procedures,particle swarm optimization algorithm and the algorithm,the data of ride-sharing in Chengdu was verified.The results show that the inconvenience cost of driver and rider under the decomposition algorithm is lower than that of the greedy and particle swarm optimization algorithm,the order matching rate of decomposition algorithm is more than 90%,which is higher than the 80%~90%matching rate of greedy algorithm and particle swarm optimization algorithm.Through comparison,it is proved that the proposed model and algorithm can reduce the cost of travel inconvenience and improve the real-time performance of the algorithm under the premise of ensuring a high matching rate,and have a good application effect in practical engineering.

关 键 词：交通工程 动态合乘 合乘匹配模型 路径规划 分解算法 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]