Research On Stochastic Vehicle Routing Problems

With increasing intensification of marketing competition, step out of global integration, and speedy development of science and technology, many enterprises have been conscious that logistic is an important measure to improve the ability of market competition and exalt the ability of coral competition, and introduced advanced logistical theory and logistical technique to manufacture and operation management of enterprise. Being an important approach to realize logistic rationalization, research on vehicle routing problems will help enterprise to reduce logistical cost, improve operation efficiency, and enhance customer satisfaction roundly. Because vehicle routing problems bridge theory of Operations Research and practice of production, they are named as one of the most successful areas in Operations Research in the past decades. In the classical vehicle routing problems, all kinds of information are assumed to be determinate, but in practice, planner of routes must meet with stochastic information according with statistical law frequently. Consequently, because effective methods to solve determinate vehicle routing problems are not always solving stochastic vehicle routing problems effectively, it is indispensable to summarize characteristics of stochastic vehicle routing problems and design effective models and algorithms. Until now, research on stochastic vehicle routing problems is scant, and many dissatisfactory items await amelioration and modification. The dissertation, in which a series of vehicle routing problems under stochastic information are analyzed thoroughly, takes on important theoretical significance and practical value.The main contents of this dissertation are listed below:In chapter 1, based on summarize relative reference, we retrospect domestic and foreign research on vehicle routing problem, analyze all constitutes of the problem, and point out shortcomings of research on stochastic vehicle routing problem and some potential areas of research.In chapter 2, we introduce simply some concepts of combinatorial optimization, summary characteristics of meta-heuristic which are applied comprehensively, and expound emphatically source, development, mechanism and characteristics of genetic algorithm and simulated annealing. In addition, owing to lack oftheoretical research, we analyze schema theory of genetic algorithm with ordinal number code: short, low-order, above average schemata receive exponentially increasing trials in subsequent generations.In chapter 3, we analyze models and algorithms of a vehicle routing problem with stochastic customer and stochastic demand. The specialties of the problem lie in which the information that a customer needs commodity or not can be received before vehicle visit him (or her), but exact requirement of the customer is obtained only after vehicle visit him (or her), and supposes that his (or her) demand can not be divided. In the dissertation, we put forward tour policy and multi-tour policy, analyze upper bound, lower bound and asymptotic property of the policies, and based on evaluating prior tour as objective function, devise genetic algorithms and simulated annealing algorithms to solve the problem.In chapter 4, we research models and algorithms of vehicle routing problems with stochastic time. Considering capacity of vehicle, we provide chance-constraint model and recourse model, and reconstruct them to be solvable with genetic algorithm; Based on two crossover operators MX3 and MX4, we design genetic algorithms to solve the two models. The experiment indicates that the operators are more excellent than operators MX1 and MX2.Utilizing knowledge of combinatorial optimization, queue theory and geometry probability, in chapter 4 we research lower bound of capacited dynamic vehicle?routing problem with stochastic demand, put forward TSP policy and modified TSP policy, and analyze asymptotic property of the policies.Because inventory control problem and routing problem are two important and interrelated closely items in logistic...