Study On The Algorithm And Application For Traffic And Transportation Network Path Under Uncertain Environment

The application of the traditional Shortest Path Problem (SP) for the real world is of limitation. But the sub problems derived from SP are applied widely, such as Constraint Path Problem, Multi-objective and Multi-weight path problem, and Stochastic Path Problem and Fuzzy Path Problem under uncertain environment. These derived problems play a very important role in many fields such as traffic, military, communication, computer and management science, etc.Many deep researches have been done since Di jkstra algorithm in 1959. The researches mainly focus on two fields: the study on time effectiveness of algorithms and the study on the variation problems of SP. Though some classical algorithms based on the Bellman Optimization Principle e.g. the Dijkstra algorithm, are regarded as the most effective algorithm, this algorithm is low effectiveness for a big network and repeated calculating SP. Owing to the requirements of real-time control, these algorithms will not be realized in the allowed time. Furthermore, for the derived problems of SP such as constraint path problem and the path problem under uncertain environment, the traditional algorithm is not applicable anymore.From 1970s to the middle of 1980s, the research on SP was going down both abroad and at home. Until the end of 1990s, with the development of computer science, especially the development of communication and traffic and transportation science, the study on SP has become the focus of many researchers both abroad and at home. For network path problem under uncertain environment, many researches have been done in order to obtain the precise solution, and some conspicuous results are obtained in different case studies of SP. However, this paper puts forward a new opinion, that is, because of the native imprecision of these models, such as the confirmation of stochastic function and membership function, even if the optimum solution is obtained under the models, it is difficult to implement the solution in practice.This paper studies and analyzes the genetic algorithms for constraint network SP and chance-constrained programming model and dependent-chance programming model under uncertain environment. Which are still newest and challenging both abroad and at home. According on the priority of vertex and gene weight recoding is given for constraint networks and SP under uncertain environment. By using the models and algorithms presented in this paper, the urban public transfer problem and the fuzzy dissimilar path in urban traffic network under stochastic environment are studied as instance.The derived problems of SP are extremely diverse and their application is very wide. The constraint network path problem is one of the derived problems of SP, and it is always the core sub-problem of other derived problems of SP. Taking the traffic and transportation network as the background, the SP with the constraint of the path via some nodes appointed which is widely used in railway transportation is studied firstly in this paper, and the bound algorithm by bi-directional searching is also proposed. The complexity of this algorithm is time-polynomial. Considering the complexity of general constraint network path problem, a fast genetic algorithm is elaborated on the base of the technology of dynamic coding of the priority of vertex and gene weight. This algorithm is abasis to solve the network path. By using genetic optimization technology to approach the evaluation function value of inner level chromosome, the two-level optimization algorithm for the time dependent path problem that is very important in traffic and transportation network is put forward. In addition, the dissimilar path problem which is widely used in traffic and transportation network is discussed, and the concept of symmetricalα-dissimilar degree and its computable method are also suggested. This problem can be regarded as the constraint path problem or a multi-objective path problem. And the corresponding intelligent algorithm is also presented in this paper. By using this algorithm, the optimum dissimilar path with the constraint of path length or the shortest path with the constraint of dissimilar degree can be obtained. For multi-objective problem, the Pareto solution set can be obtained by using this algorithm.For the network optimum path problem under stochastic environment, the traditional research method is always based on the expected value model and maximum probability model And also,recently,the researches both abroad and at home are all based on the assumptions that the vertexes and arcs have the independent stochastic distributions and the distribution functions are analytical and computable. This paper is done without any assumptions and thus tends to be of greater generality. The stochastic simulation methods for expected value and variance of stochastic distributions are first expounded. The traditional expected value model is then expanded based on the researches of the expected value model and maximum probability model. Furthermore, the optimistic and pessimistic value models and variance constraint model are illustrated. These models are more valuable and general in practice. Likewise, the multi-objective stochastic network model based on the rules of maximizing the probability and minimizing the path length is put forward. Meanwhile, the chance constraint model of network optimum path is also presented. For the SP under stochastic environment, a hybrid intelligent algorithm is given based on vertex priority coding by using stochastic simulation.Compared with the certain and stochastic environment, researches works on network optimum path under fuzzy environment are very few both at home and abroad. And the achieved results are mainly based on the fuzzy set expand sum. On considering those, this paper also studies the network best path by using quality ranking theory and method based on fuzzy set possibility. In fact, this is a different method taken from a different angel to compute the expected value of fuzzy variables. By this method, the fuzzy variables can be changed into certain values and the problem will become a certain problem. Actually, considering the essence of fuzzy problems, its solution should be fuzzy, too. So this paper proposes that the fuzzy paths can be obtained by computing the best and worst paths underα-level cut. Besides, according to the theory of fuzzy possibility measure, the fuzzy chance constraint model and fuzzy chance-dependent model of network optimum path are illustrated. Finally, after giving stochastic simulation methods of characteristic value of fuzzy variables, such as expected value,α-optimistic andα-pessimistic values and possibility, etc, a hybrid intelligent algorithm based on vertex priority coding by using stochastic simulation is put forward.As the main application of the models and algorithms proposed in this paper, the optimum public traffic transfer route problem and fuzzy dissimilar path problem in Lanzhou urban public traffic system are studied as a case. Under the stochastic traveling time and transfer delay environment, the 0-1 programming model of the transfer problem is established. Then, the model is transformed into a hyper graph model so that the hybrid intelligent algorithm based on vertex priority coding by using stochastic simulation can be used to solve this model. The results can provide the optimum public traffic transfer route for passengers.In urban traffic vehicle navigation system, it is necessary to provide the optimum travel route for drivers. When some roads or intersections are congested or jammed, some vehicles will run into the adjacent roads naturally. So the road impedance will become greater and greater in certain area of the traffic network. Undoubtedly, "certain area" is a fuzzy concept. Even if in the same area, the impedance on different road is different. Under such conditions, drivers always expect the vehicle navigation system or other service system to provide one or more dissimilar paths to the congested and jammed area. For this kind of fuzzy optimum dissimilar path problem, the concepts of k-level incident vertex and k-level incident edge are put forward. Then the membership functions of all vertexes and edges to "the certain area" are given. Finally, taking Lanzhou urban traffic network as an example, the fuzzy dissimilar path problem is computed and analyzed.