Optimal Path Finding Algorithm With Applications Under The Consideration Of Travel Time Correlation

The reliable path finding algorithm under uncertainty is a significant topic in the field of computational mathematics. Such algorithm has been widely used among transportation, communication and geographic information. This paper mainly investigates the reliable path finding algorithm under uncertainty with special consideration of travel time correlations and energy saving.Chapter 1 introduces the background and the importance of the reliable path finding problem under uncertainty. Also, a literature review including the recent research progress as well as the classic algorithms on path finding problem are provided.In chapter 2, the travel time correlation between different links is taken into consideration in reliable path finding problem. Such issue seldom addressed in the literature. The proposed algorithm deduces the upper and lower bounds of the effective travel time using the inequalities techniques. It uses the minimum upper bound of the effective travel time as threshold to search the feasible reliable paths. This algorithm avoids searching the impossible optimal path and saving the amount of calculation. Numerical examples are presented to demonstrate the efficiency of the proposed algorithm.Chapter 3 investigates the critical link identification problem on the basis of the proposed algorithm in chapter 2. The corresponding mathematical model is given in which the minimum system total travel time is set as the objective function. Then, the critical link is defined as the link which has the biggest influence on the system total time. The whole network congestion will be alleviated by improving the service of critical link.Chapter 4 further extends the path finding algorithm proposed in chapter 2 to simultaneously account for energy saving and reliability enhancement under network uncertainty. This is bi-objective path finding problem. To solve it, the K-shortest algorithm is incorporated into the algorithm proposed in chapter 2 so as to find the Pareto efficient solutions. Then, the applications of the proposed algorithm are demonstrated by the medium-size and large-size transportation networks.