The Shortest Path Problems On Complex Dynamic And Stochastic Networks

The classical shortest path problem is one of the most important research contents in the field of graph theory and network optimization. The study of the shortest path problem not only helps to solve many practical problems directly, but also can be used to solve other optimization problems as a basic tool. However, many networks in the real world are dynamic (or time-dependent) and stochastic. The definitions and the searching methods of the shortest path in such networks are different from those of the classical one. Furthermore, the study of the shortest path problem in dynamic and stochastic networks (DSNs) not only has important practical value, but also has high theoretical significance. Thus, we are devoted to the study of the shortest path problems in DSNs in this dissertation. The main contents contain the following six parts:(1). Based on the ant colony optimization (ACO), the temporal ACO (TACO) is proposed in this dissertation, which is used to solve the a priori shortest path problem in DSNs. Firstly, the significance of the study for the a priori shortest path is clarified. Then the methods for complex networks searching are introduced. It shows that these methods can be used to solve the shortest path problems in DSNs, but there are some inevitable limitations if these methods are used directly. In this dissertation, we propose the TACO which is combined with the ACO and the searching methods in complex networks. It shows that the TACO is improved by such combination. However, the TACO proposed in our dissertation focus mainly on scale-free networks which exist ubiquitously, and is not adapted for the other network model. The authors expect that the algorithm solving the shortest path problems is improved by the purposeful algorithm design.(2). Not only the departure and arrival times, but also the states of networks should be considered when solving the shortest path problems in DSNs. Thus, the scales of problems are increased significantly. As the scales increase, the path searching becomes computationally challenging and this will decrease the effectiveness of searching algorithms. While in fact, for a given DSNs, an origin-destination (OD) pair and a departure time at the origin node, information about the whole network may be not required for a given path searching process. That is, a large amount of information in the network is redundant. Based on this fact, the reduction method for shortest path problems in DSNs is studied in this dissertation. The ideas and the methods of the reduction processes are introduced. We also make some analyses of the factors affecting reduction results and the complexity of the algorithms.(3). Travel costs through a link in a DSN are uncertain values, so, in some cases, such as travel costs are non-periodic variables, the paths obtained en-route are always better than those obtained a priori. Furthermore, the definition of the real-time shortest path in DSNs based on disutility function is given. Then the convolution-propagation approach (CPA) is introduced into the shortest path searching in DSNs with real-time information, and the corresponding algorithm GASPSP (GA for Shortest Path Searching Policy) based on the improved genetic algorithm (GA) is proposed. (4). The extensive simulations is implemented under Matlab environment in this dissertation. Simulation results show that the TACO algorithm, the reduction algorithm, and the GASPSP algorithm are effective and efficient.