Uncertain Information Vehicle Routing Problem And Its Algorithms Analysis

Along with the further division of labor in global market, trade frequency and quantity in the worldwide scale have grown remarkably, and the logistics efficiency has become one of important indicators in judging economy operating efficiency for an enterprise and even a state. Vehicle routing problem is the main problem in the field of logistics transportation system, for its research methodology and the achievement can apply directly to the combination optimization domain, thus it has obtained the widespread attention and made a great achievement in theoretical and the practical realm since it was born. However, restrained by the time economical background and the information processing technology, these researches are mostly confined in certainty models, namely supposing all related information has known and determined before planning vehicles routing. Nowadays, the environment of social economy operating has changed greatly comparing with the past. On the one hand, economic activity frequency increases considerably, and also following the massive indefinite information; on the other hand, the rapid development of correspondence and computer technology not only causes the social economy order to avoid the confusion resulting from the flood of indefinite information, but also further urges the people to use these indefinite information to create more wealth. It can be said that the processing strategy and the technical method to indefinite information directly decides efficiency and profit level of a economic entity. In view of this new situation, this article studies the uncertain information vehicle routing problem, and the work are as follows:First, this article gives the general outline to uncertain information vehicle routing problem, including the definition, the constitution, the classification, the model as well as the classical algorithms to solve the vehicle routing problem. On this basis, this article puts the uncertain information vehicle routing problem into two parts----the problems of the non-real-time information processing and the real-time information processing according to the advancement of time development. And this article also analyzes the connotation, the characteristic, the research present situation of uncertain information vehicle routing problem and the corresponding mathematical model and the optimized method, and then points out the problems in the process of research.Second, this article makes a throughout overview and summary of the present situation of all kinds of heuristic algorithms to solve vehicle routing problem, elaborates the source thinking and the operation flow of these algorithms and then gives a detailed analysis of application progress into vehicle routing problem. On this basis, this article has proposed new algorithms----maximum entropy distribution algorithm, self-telepathy ant colony algorithm and hybrid particle swarm optimization, and carried on the corresponding theoretical analysis and the proofs, which provide the essential mathematics solution tool to deal with the complex indefinite information vehicle routing problem. Third, this article gradually researches on tow kinds of stochastic vehicle routing problems. The work studies from vehicle routing problem with only supplying or carrying assignment. To this, combining with the long-term customer record in the real life, this article constructs the new statistics model, designs hybrid particle swarm optimization to solve this model, and comparatively analyzes advantage and weakness between the new algorithm and other algorithms. Then, this article further studies on the vehicle routing problem with simultaneous selivery and pick-up.By application the statistics method in previous section, this article constructs integer programming model for this kind of question, proposes concepts of the expectation degree factor, the distance compares factor and so on, designs self- telepathy ant colony algorithm to solve this question, compares dates with other optimized algorithms which finally validates this algorithm.Forth, this article analyzes the fuzzy vehicle routing problem. Taking vehicle's fuzzy travel time and customer's fuzzy due time as fuzzy information parameter, using the method of subdivides the customer class to absorb the allocation knowledge system and using the method of subdividing the customer's class to absorb the carriers'knowledge system, this article converts two deciding-making goals of logistic enterprises'utility maximization and customers's utility maximization to two kinds of fuzzy information vehicle scheduling model and gives maximum entropy distribution algorithm to solve this kind of problem, analyzes the influence of the computed results of these two kinds of models with the change of policy-making parameters and suggests the frame basis of correlation parameters of the formulation.Fifth, this article gradually lucubrates two kinds of dynamic vehicle routing problem. The research starts from dynamic vehicle routing problem of non-full loads, namely dynamic traveling repairman problem, elaborates technical support for the realization of dynamic vehicle routing problem as well as the production method of dynamic information datas, and inspects the performance of various one-off optimization strategies in various scenes of real-time uncertain information vehicle routing problem by the simulation experiment.Then, this article makes study on dynamic vehicle routing problem of full loads with time windows, which is a more practical significance problem. This article also proposes new notions about the mechanism of deal with new information and the strategy of the dynamic programming of travel routing of the traveling vehicles, which expounds the methods of logistic enterprise to deal with new information, proposes separated-gang strategy to optimize dynamic vehicle routing problem,designs modified ant colony optimization to improve this problem and the corresponding using regulation of replicate computation, and compares the performance of various one-off optimization strategies and ant colony algorithm based on artificial test which confirms the validity of the new strategy and the new algorithm.At last, on the basis of the above theory, taking VB as the development language, this article develops dynamic vehicle routing plan system that has Windows graphical interface. And this system can dynamically demonstrate the vehicles'traveling routing and the current position on the electronic map, choose the optimal routing according to the dynamic information change, and then demonstrate the output.