Solving the K-shortest paths problem in timetable-based public transportation systems
Solving the K-shortest paths problem in timetable-based public transportation systems
复制标题
解决基于时刻表的公共交通系统中的K最短路径问题
DOI：
10.1080/15472450.2015.1082911
复制
发表时间：
2016-09
影响因子：
3.6
通讯作者：
Xu, Bingji
中科院分区：
文献类型：
--
作者：
Yang, Yang;Hu, Xiaolin;Li, Jianmin;Xu, Bingji
摘要 在基于时刻表的公共交通系统中寻找K最短路径是实践中的一个重要问题。它具有三种典型的变体：K-最早到达问题（K-EAP）、K-最短行程时间问题（K-STTP）和K-最小换乘次数问题（K-MNTP）。在本文中，我们表明，通过首先使用时间扩展方法对时刻表信息进行建模，然后应用 Martins 和 Santos (MS) 算法，可以有效地解决这些问题。然后，我们使用时间相关方法对时刻表信息进行建模，并提出用于求解 K-EAP 的 MS 算法的修改版本。真实数据的实验结果表明，当 K 小于 100（对于大多数应用程序来说已经足够）时，MS 算法在具有 1.86 GHz 中央处理器 (CPU) 和 4 GB 内存的服务器上解决时间扩展模型中的问题的执行时间小于 100 ms。为了求解 K-EAP，时间相关模型中的修改 MS 算法比时间扩展模型中的原始算法更加高效（对于 K ≤ 100，大约快三倍）。我们的结果表明 MS 算法在实际交通服务系统中具有巨大潜力。
Abstract Finding the K-shortest paths in timetable-based public transportation systems is an important problem in practice. It has three typical variants: the K-earliest arrival problem (K-EAP), the K-shortest travel time problem (K-STTP), and the K-minimum number of transfers problem (K-MNTP). In this article we show that these problems can be solved efficiently by first modeling the timetable information with the time-expanded approach, then applying the Martins and Santos (MS) algorithm. Then we model the timetable information with the time-dependent approach and propose a modified version of the MS algorithm for solving the K-EAP. Experimental results on real-world data show that for K smaller than 100, which is enough for most applications, the execution times of the MS algorithm for the problems in the time-expanded model are less than 100 ms on a server with a 1.86-GHz central processing unit (CPU) and 4 GB of memory. For solving the K-EAP the modified MS algorithm in the time-dependent model is even more efficient (about three times faster for K ≤ 100) than the original algorithm in the time-expanded model. Our results imply the great potential of the MS algorithms in practical transportation service systems.
登录
查看更多内容
影响因子：
2
作者：
Martins, Ernesto Q. V.;Pascoal, Marta M. B.
通讯作者：
Pascoal, Marta M. B.
DOI：
10.1016/j.ejor.2013.10.022
发表时间：
2014-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
L. Nielsen;K. A. Andersen;D. Pretolani
通讯作者：
L. Nielsen;K. A. Andersen;D. Pretolani
DOI：
--
发表时间：
2001
期刊：
--
影响因子：
--
作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
通讯作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
影响因子：
6.8
作者：
N. V. D. Zijpp;S. Catalano
通讯作者：
N. V. D. Zijpp;S. Catalano
DOI：
10.1142/s0129054199000186
发表时间：
1999-09
期刊：
Int. J. Found. Comput. Sci.
影响因子：
--
作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
通讯作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos