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

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

1.1. 研究背景 近年来， 随着外来人口的增加以及私家车拥有量的迅猛增长， 国内外各大城市的交通压力陡然剧增， 交通拥挤已经成为城市面临的一大难题。大力发展城市公共交通则是解决道路拥堵的一个重要方法，目前，地铁等公共交通已经成为如纽约、上海等许多城市地区日常通勤者的主要交通方式[1]。但是，过多乘客选择地铁出行造成了地铁线路的拥挤，早晚高峰时段地铁车厢和站台拥挤已成为常态。

与此同时，人们对地铁乘坐舒适度的需求与日俱增，在行程时间允许的情况下，乘客普遍希望尽可能在乘坐地铁时有较为宽松舒适的乘车环境，但是如果增加过多的车次或者增加过多的车厢在乘客人流量较少时又会造成浪费。这就对地铁管理者们提出新的要求，即需要在地铁运输效率和乘客舒适度之间