时间依赖网络中非FIFO弧的转化研究

Study on the Conversion of Non-FIFO Arc in Time-dependent Networks

经典最短路算法不能有效地解决时间依赖网络的最短路问题.时间依赖网络中的非FIFO弧的存在是导致经典的最短路算法失效的原因.本文对非FIFO弧的权函数为非连续(存在有限个非连续点)或者离散情况下转化为FIFO弧进行了研究,在允许等待的前提条件下,提出了解决此类问题的方法.建立在经典Dijkstra算法基础上,本文提出了时间依赖网络最短路算法.

Traditional algorithm can not effectively find out the shortest paths in time-dependent networks. The reason is that there are non-FIFO arcs in time-dependent networks. This paper studies on the method of converting the non-FIFO arcs into FIFO arcs in the condition of the function of this arcs is non-continuous （exist only limited non-continuous points） or discrete, then proposes the algorithm to solve this problem in the prerequisite of allowing wait. Based on the traditional Dijkstra algorithm, this paper develops the improved shortest-path in time-dependent network.