A novel model and its algorithms for the shortest path problem of dynamic weight-varying networks in Intelligent Transportation Systems

摘要

Intelligent Transportation Systems (ITS) are defined as those systems utilizing synergistic technologies and systems engineering concepts to develop and improve transportation systems. In this paper, a novel route selection problem based on the envisaged driving mode with dynamic signals in ITS is proposed. It belongs to a kind of the shortest path problem of dynamic weight-varying networks, and the arc-weights of the network vary with the arc-chosen, so it cannot be solved by the existing greedy algorithms. According to the characteristics of the proposed problem, firstly, a dynamic programming model for the driving mode on a single path is established. Secondly, two algorithms for solving the route selection problem based on the former mode are developed. One is a brute-force algorithm based on matrix expansion with the computational complexity of O (Nt x n(2)). The other is an improved adaptive ant colony algorithm with the complexity of O (Nc x m x n(2)). Finally, the computational experiments show the advantages and disadvantages of the two effective algorithms with numerical examples.