基于离线关键站点和路径阻抗的地铁路线推荐方法

Offline Key Station and Path Impedance Based Subway Route Recommendation Method

摘要: 目前主流的路线推荐方法先通过寻径算法在满足各种约数条件下寻找K条可行路线，然后根据乘客的出行偏好从K条可行路线中选择一条路线推荐给乘客。然而，由于寻径算法的约束条件只能通过实时计算得到K条可行路线，当同时进行大量乘客的路线推荐时，由于无法快速获得推荐路线从而影响乘客的用户体验。因此本文提出基于离线关键站点的K最短时间算法，通过构造关键站点图和哈希表离线辅助查找K条最短路径，从而降低算法的时间复杂度。此外，通过分析发现，乘客对出行的负面感受与地铁换乘次数及拥挤度间并不是简单的线性关系，随着换乘次数和拥挤度的增加，乘客对出行的满意度会迅速衰减，所以，目前通过最大最小值方法计算出的乘客偏好路线并不一定是最佳路线。因此，本文设计了基于路径阻抗的地铁路线推荐方法，其中路径阻抗由不同权重的地铁时间成本和拥挤成本组成，通过计算K条最短时间路径的路径阻抗，从中选出符合乘客偏好的出行线路推荐给乘客。通过理论分析，随着查询次数的增多，本文提出的基于离线关键站点的K最短时间算法时间复杂度要远小于其他约数条件下的寻径算法。最后通过具体的实验示例验证本方法完全可以满足不同乘客的路线推荐需求。

Abstract: The current mainstream route recommendation method first finds K feasible routes by path finding algorithm under various approximate conditions, and then selects a route from K feasible routes to recommend to passengers according to their travel preferences. When a large number of passengers’ routes are recommended at the same time, the recommended routes are not available quickly and thus affect the passengers’ user experience. Therefore, this paper proposes the K shortest time algorithm based on offline key sites, which can reduce the time complexity of the algorithm by constructing a key site graph and hash table to assist in finding K shortest routes offline. In addition, it is found through analysis that there is not a simple linear relationship between passengers’ negative feelings about the trip and the number of interchanges and crowding, and passengers’ satisfaction with the trip will decay rapidly as the number of interchanges and crowding increase. There-fore, the current passenger preference route calculated by the maximum-minimum method is not necessarily the best route. Therefore, this paper designs a subway route recommendation method based on path impedance, where the path impedance consists of different weights of subway time cost and congestion cost, and by calculating the path impedance of the K shortest routes, the travel routes that meet passenger preferences are selected from them and recommended to passengers. Through theoretical analysis, with the increase of the number of queries, the time complexity of the K shortest time algorithm based on offline key stations proposed in this paper is much smaller than that of the path finding algorithm under other approximate conditions. Finally, it is verified through specific experimental examples that this method can fully meet the route recommendation needs of different passengers.