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

动态合乘是出行路线相似的出行者共用一辆车的交通方式,能够有效利用现有资源,最大化社会效益。当前合乘研究存在司机-乘客匹配质量不高,算法实时性差等局限。提出了考虑订单匹配数量、司机旅行时间、乘客等待时间与乘客延误时间的司机-乘客合乘匹配模型。针对模型特点,设计了基于分解方法的司机-乘客合乘匹配与路径规划算法。通过选择贪心随机自适应搜索算法、粒子群算法与本文的算法对比,成都市网约车数据验证,结果表明:分解算法下司机与乘客不方便成本低于贪心与粒子群算法;分解算法订单匹配率在90%以上,高于贪心与粒子群算法的80%～90%匹配率。通过对比证明,所提出的模型与算法,能够在保证高匹配率的前提下,降低出行不方便成本,提高算法实时性,在实际工程中有较好的应用效果。

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

Dynamic ride-sharing is a mode of transportation in which travelers with similar travel routes share one car, which can effectively utilize existing resources and maximize social benefits. There are some limitations in current ride-sharing research, such as poor driver-rider matching quality and poor real-time performance of algorithm. This paper proposes a driver-rider ride-matching model considering 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 is designed. By comparing the greedy randomized adaptive search procedures, particle swarm optimization algorithm and the algorithm in this paper, the data of ride-sharing in Chengdu are verified: the results show that the inconvenience cost of drivers and riders under the decomposition algorithm is lower than that under 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 model and algorithm proposed in this paper 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.