Optimal Path Finding Algorithm With Applications Under Uncertainty In Transportation Networks

In recent years,the optimal reliable path finding problem under uncertainty is a hot topic in the research field of algorithm.Such problem has been widely used among transportation,communication and geographic information.This thesis mainly investigates the optimal reliable path finding algorithm under uncertainty with special consideration of travel time correlations,delays at signalized intersection,energy consumption of electric vehicles,traffic assignment problem and estimation of mean and covariance of OD demand based on license plate recognition technique.Chapter 1 introduces the background and the importance of the reliable path finding problem with respect to the network uncertainty,the energy consumption,the traffic assignment and the estimation of mean and covariance of OD demand.Meanwhile,a literature review including the recent research progress as well as the classic algorithms on path finding problem and the traditional traffic assignment models are provided.In chapter 2,the stochastic link travel time,travel time correlations between different links and delays at signalized intersections are taken into consideration in reliable path finding problem.Best to our knowledge,few existing studies simultaneously consider all three factors in the literature.The traditional path finding algorithm cannot be applied to solve the proposed model due to the non-additive property of effective travel time.Thus,we proposed a new algorithm to tackle the proposed path finding problem.The proposed algorithm deduces the upper and lower bounds of the effective travel time using the inequality techniques.It utilizes the path with minimum upper bound of the effective travel time as temporal reliable path.Then,calculating the effective travel time of temporal reliable path as threshold to search the feasible reliable paths.The candidate path set can be obtained based on the K-shortest algorithm.This algorithm avoids searching the impossible optimal path and saving the amount of calculation.Our numerical results show that ignoring travel time correlations between different links or stochastic delays at signalized intersections can lead to biased results for finding the reliable shortest path.Finally,we show that the resultant reliable shortest path can provide travelers with better trip-planning support by avoiding unexpected delays due to network uncertainty and delays at signalized intersections.Chapter 3 investigates optimal path finding algorithm with consideration of energy consumption of electric vehicles on the basis of the proposed algorithm inchapter 2.We first propose a bi-objective optimization model to maximize(1)the on-time arrival reliability and(2)energy-efficiency for battery electric vehicles(BEVs)in a path finding problem.Then,the non-dominated solutions can be obtained based on the heuristic algorithm proposed in chapter 2 and the existing K-shortest algorithm.We numerically demonstrate the potential applications of the proposed algorithm in real-life road traffic networks.Chapter 4 further incorporates the path finding algorithm proposed in chapter 2into traditional traffic assignment problem.We propose a new traffic assignment problem with simultaneous consideration of travel time correlations and delays at intersections under network uncertainty.It is assumed that the travelers are able to learn the variation of the path travel time based on past experiences.This chapter proposes a travel time reliability-based user equilibrium with consideration of correlations and delays(TRUE-CD)principle to characterize travelers’ path choice behavior under uncertainty.This principle can be formulated as an equivalent path-based variational inequality(VI)problem.It is rigorously proved that there is at least one solution for the VI problem.The method of successive averages algorithm(MSA)and the solution algorithm proposed in chapter 2 are employed for solving the VI problem.Moreover,we demonstrate the effectiveness and efficiency of the proposed algorithm using numerical examples.Chapter 5 investigates the estimation of mean and covariance of OD demand based on license plate recognition technique.To this end,we propose a least square model to estimate the mean and covariance of OD demand on the basis of the results of chapter 4.In order to solve the proposed estimation model,the path flows are reconstructed with the obtained information according to the technology of license plate recognition.Once the path flows have been reconstructed,the OD demand and all link flows become immediately available.In addition,an algorithm for selecting optimal sets of links to be scanned for predicting path flows is provided.Moreover,we adopt the root mean square error(RMSE)to illustrate the accuracy of the estimation.Finally,the numerical example shows that the proposed method,which utilize the license plate recognition technique,is capable of providing more precise results than traditional methods.