基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法，能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度，从而求得精确解。进一步地，算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明，基于优先队列的时变网络最短路径算法与经典方法相比，不仅能够求得精确解，运算速度也有所提高。

Time varying network shortest path algorithm based on priority queue

This paper presented a time-varying network shortest path algorithm based on priority queue to solve the time-varying network shortest path problem which was difficult for traditional shortest path algorithm. Proposed algorithm could address optimal solution by using proposed time-window selection strategy which could select appropriate time window for the node to reduce the path length. Also, the algorithm used the priority queue to organize node set, which could improves the computational efficiency. Experiments on randomly generated network data and united state road data show that compared with classical algorithm, the proposed algorithm is not only able to obtain global optimal solutions, but also improve the speed of the algorithm.