基于概率路由的出租车共乘调度算法

针对现有的拼车方案大多服务在线乘客请求，而忽略了离线乘客请求，导致出租车资源无法得到充分利用这一问题，提出了一种基于挖掘历史出行轨迹数据的概率路由拼车优化算法。该算法根据乘客请求的历史时空数据计算出区域概率转移矩阵，并使用该矩阵优化平台为出租车推荐拼车路径，提供了历史数据和拼车问题相融合的一种解决方案，可以有效提高出租车的载客量。在保障离线乘客接载率、在线乘客忍耐度的同时，使用松弛时间的度量指标，可以在O（n）内对整条路径的乘客忍耐时间进行评估预测，并用迪杰斯特拉算法对绕行区域进行路径规划，让出租车的绕行距离最短。使用滴滴GAIA真实数据集对算法有效性进行验证，结果显示，该算法在服务请求数量上高于基准算法12%。

Algorithm for taxi ride-sharing scheduling based on probabilistic routing

Aiming to address the issue that current ridesharing solutions mostly focus on serving online passenger requests and overlook offline ones, leading to underutilization of taxi resources, the paper proposed a probability-based routing ridesharing optimization algorithm that relied on mining historical travel trajectory data. This algorithm calculated a regional probability transition matrix from historical spatiotemporal data of passenger requests and utilized this matrix to optimize the recommended ridesharing routes for taxis. It presented a solution that integrated historical data with the ridesharing problem, effectively increasing the taxi''s passenger capacity. By ensuring the offline passenger acceptance rate and online passenger tolerance, the algorithm employed a relaxed-time metric to predict and evaluate the passenger tolerance time for the entire path in O(n) time, and used the Dijkstra algorithm to plan routes through detour areas, minimizing the detour distance for taxis. This paper validated the effectiveness of the algorithm by using the real-world DiDi GAIA dataset, and the results demonstrate that the proposed algorithm outperforms the baseline algorithm by 12% in terms of the number of service requests served.