Time-dependent And Uncertain Routing Optimization Models And Algorithms

Routing optimization is a basic problem in the traffic and transportation field.If the travelers pass on a predetermined optimization path,then they can not only save travel cost,but also play an important role in improving the traffic efficiency of the whole transportation network.However,time-dependent and uncertain nature often occurs in the real-world transportation network due to the influence of various factors.It is necessary to fully consider and deal with the time-dependency and uncertainty of complex networks to get more actual road network information,so as to provide effective path guidance for travelers,which is a subject that is worthy of further study.This dissertation takes the routing optimization as the main line.It investigates the time-dependent and uncertain shortest path generation strategy and coordinated routing optimization methods,which adopts the scenario-based and time-dependent link travel time and capacity to describe the uncertainty and dynamics of transportation networks.Furthermore,we try to apply the proposed models and approaches to evacuation routing optimization when the emergency event occurs.Specifically,the contents of this dissertation mainly include the following five aspects:(1)The evaluation criteria of optimal paths in time-dependent and fuzzy transportation networks.When there is a lack of measured data in the network or even without data,the uncertainty of link travel times can be treated as fuzzy variables by expert estimation.Based on possibility theory,this dissertation proposes three different evaluation criteria for optimal paths in a single time interval and multiple time intervals(i.e.,a time period)respectively,namely deterministic dominance rule,first-order fuzzy dominance rule and fuzzy expected value dominance rule.Finally,a numerical example is illustrated to show the effectiveness of the three dominance criteria.(2)The solution method for finding the least expected time paths in time-dependent and fuzzy networks.Based on the fuzzy expected value dominance rule,a multi-objective 0-1 mathematical programming model is formulated in order to find the least expected time path by considering multiple departure times.In time-dependent and random networks,the path generation follows the addition and multiplication operational rules,but the path generation follows the maximum and minimum operational rules in the time-dependent and fuzzy network due to the fuziness of link travel times.Consequently,this dissertation investigates the solution method for generating optimal paths with least expected travel times and designs the tabu search algorithm to solve the proposed model.In comparion to the backtracking algorithm,the numerical results indicate that the tabu search algorithm can obtain the approximate optimal solution with high accuracy.(3)Stochastic constrained shortest path problem and Lagrangian relaxation-based algorithm.To represent the randomness of transportation networks,the link travel times are assumed to be scenario-based discrete random variables,and then the stochastic constrained shortest path model is mathematically formulated to find the shortest expected travel time paths.Since this model is an NP-hard problem,the Lagrangian relaxation solution approach is provided to relax the hard constraints into the objective function.An algorithmic framework,integrating the sub-gradient algorithm,label-correcting algorithm and K shortest paths algorithm,is designed to minimize the gap between the upper and lower bounds to find near-optimal solutions.Considering the characteristic of joint probability mass functions of link travel times varying with time,the stochastic constrained shortest path problem is further extended a time-dependent case,which can be solved by the modified algorithmic framework.Finally,the proposed algorithm framework is conducted on different scales of transportation networks to its performance,the relative gap between the upper and lower bounds and solution efficiency.Experimental results in a large-scale network indicate that the proposed algorithm can quickly find the high-quality solutions with small relative gaps.(4)Stochastic evacuation routing planning based on disaster emergency response.When the emergency event occurs,for instance,earthquake,flood and hurricane,it is necessary to evacuate the people in dangerous areas to safe areas.To reflect the influence on road networks caused by different levels of disasters,the link travel times and capacities are regarded as discrete random variables.Meanwhile,considering the preference of different decision-makers,three evaluation criteria are introduced to describe the objective function,namely min-max reliability method,percentile reliability method and expected disutility method,and then three corresponding stochastic evacuation programming models are formulated.Finally,a heuristic algorithm combining the Lagrangian relaxation-based approach with K shortest paths techniques is designed to solve the expected disutility model.The real experimental results verify the effectiveness of the proposed algorithm to solve large-scale instances.(5)The two-stage emergency evacuation routing planning model under time-dependent and stochastic environment.As the network information can be obtained after the emergency event,the transportation network is divided into different time stage,i.e.,a priori optimization stage and adaptive routing stage,based on the a priori optimization and adaptive routing selection.In the a priori optimization stage,it is assumed that the traffic information can not be obtained when the disaster will occur or just occurs,and then the a priori evacuation routing plan should be obtained in the first stage based on the historical data.In the adaptive selection stage,assume that the real-time traffic information can be obtained,and therefore we adopt the adaptive routing strategy to find evaluation routing plans in different scenarios.This dissertation formulates a two-stage stochastic routing optimization model based on the minimum cost flow model,for the purpose of minimizing the expected total evacuation time.Further,this model is transformed into an equivalent single stage optimization model.Finally,the Lagrangian relaxation-based heuristic algorithm is designed to solve the proposed model.