Research On Optimization Model Of Stochastic Transportation Network And Its Algorithms

The optimization problems of routes and flow rates in the military transportation network would have great influences on the flexibility of the transportation motorcade, the efficiency of logistics as well as the quality of service to the frontline troops. Stochastic transportation network optimization is of great value both theoretically and practically in the military transportation decision-making.Previous researches on the military transportation network optimization focus on static and definite information. However, a large number of indeterminate and stochastic information exists in actual transportation network accompanied by ever increasing scale and structural complexity. Traditional models and algorithms show great limitations in solving the problem, so it is necessary to do further research in order to construct more effective models and algorithms. Based on a military transportation-aided decision-making project, this thesis studies the optimization models and algorithms of stochastic transportation network. The main contents and fruits of this thesis are outlined as follows:Firstly, based on summarizing a great amount of relative references, we review the domestic and foreign research achievement on the transportation network optimization, analyze the components and subsidiaries of the problem, and point out the shortcomings of the traditional models and algorithms in solving optimizations in the stochastic transportation network.Secondly, frequency-domain model of stochastic transportation network and its expected methods are studied. Considering the randomness resulting from occasional accidents and other factors, we treat the travel time of routes, flow rates and reliability as random variables. Then we generate our frequency-domain spanning graph model of the stochastic transportation network from the statistics and probability theory and the classic network models, which not only describe all kinds of stochastic information in the transportation network successfully, but also provide the transformation between time-domain and frequency-domain probability functions. By analyzing the result of the numerical example, we verify the frequency-domain models and algorithms and believe in its fast and highly efficient ability to analyze the expected optimization of the optimal routes, max-flow and min-flow, reliability problems based on generalized cutset algorithm.Thirdly, frequency-domain model of stochastic transportation network optimization and its algorithm with some constrained conditions are studied. Although the expected optimization is easy to implement, it fails to consider some stochastic information and sometimes the analysis differs from what it should be in reality. Thus we prefer to comprehensively optimize the network with probability distribution method. Two scenarios are considered: one sets the success probability as the objective and tries to find out the route with the maximum probability subject to time constraint; the other aims at the travel time and search the least travel time route within fixed creditable probability region. Besides, to find the stochastic max-flow and min-flow, this thesis gives some definitions and theorems in order to convert the problems into finding the sum of the flow rates of all the nodes in the minimum bi-directional cut-set ( S , S )min, i.e. the product of nodes'functions in the frequency domain. In analyzing the reliability of the stochastic transportation network, we propose a frequency-domain reliability model and algorithm. The performance of frequency-domain optimization model and algorithms are verified by analyzing the results of numerical examples.Fourthly, stochastic transportation network optimization model and its algorithm with multiple objectives and multiple constraints are studied. With respect to the stochastic and time-dependent characteristic of military transportation network, we discuss the functional relationship of the travel time, wastage and flow rate. Then we propose the multi-objective multi-constraint frequency-domain weighted utility models and algorithms based on frequency-domain spanning graph model. The performance of the models and algorithms are verified by analyzing the result of a numerical example.Fifthly, optimization model and its algorithm for large-scale stochastic transportation network are studied. Because the network-level attribute values have sub-properties of monotonous, a hierarchical network model based on frequency-domain spanning graph is presented. The hierarchical structure could result in a very effective frequency-domain layering search algorithm to reduce the space complexity. The state space is decreased from exponential to linear search. The computational results of numerical example and algorithm performance experiment verify the feasibility and effectiveness of models and algorithms.Finally, the proposed frequency-domain optimization models and algorithms are applied to a military transportation-aided decision-making project. Other applications of path optimization based on the WebGIS are also studied.