最小时间路径算法的改进及在路径优化中的应用

Improvement of shortest path algorithm and its application to route optimization

由于城市交通网络中路径行程时间是随着时间的变化而变化的,求解最小时间路径比较困难,为此提出把交通网络抽象为时间依赖的网络模型的解决方法。对时间依赖网络模型和理论基础进行分析,指出文献[1]描述的最小时间路径算法存在的不足,即不能正确记录路径;通过引入一个记录路径的数组来对此算法进行改进,改进后的算法不仅解决了原算法存在的问题,而且可以满足n∶1的最短路径搜索,扩展了原算法的应用范围。最后用实验验证了改进算法的正确性和有效性。

As the time is changing,the travel time is also changing in traffic network.So shortest path search becomes consi-derably more difficult.For solve the problems,many transportation systems could be represented by networks with travel times that were time-dependent.This paper presented time-dependent networks and its theoretical foundations and analyzed the problems of reference [1].It proposed an array to note the results to improved the algorithm.The shortest path algorithm in time-dependent networks had a broad application fields.The improved algorithm is proved to be correct and efficient by experiments and practical application.