Least travel time paths in deterministic and time-varying transportation networks considering the attribute of nodes

The existing study of least travel time paths in deterministic time-varying networks do not really consider the time that vehicles consume at the intersections. However the time a car consumes when it crosses the intersection is not allowed to ignore. The paper studies the least travel time paths problem in deterministic time-varying networks considering the attribute of nodes. Firstly, we set up a mathematical model with the goal of the minimizing time to describe the problem. In order to clearly indicate the characteristic that nodes and edges have different weights in the network in different period of time, we proposed the vector label method. Then we propose an algorithm named Reverse Order Labeling Algorithm to solve the problem by analyzing the properties of the problem. Finally, we prove that the time complexity the algorithm is O (I·(N·|E|+|V|)) and verify the effectiveness of the algorithm by the simulating experiment and case analysis.