Research On Modeling And Optimization Methods For Vehicle Routing Problems

Intelligent transportation system acts as a timely, accurate and high efficient transportation management system which is based on modern science and technology and has great influence on a large scale in many fields. The global economic integration is promoting the development of modern logistic which is called the third profit source of enterprises. Vehicle routing problems as the important content of intelligent transportation system play an important role in modern logistic. Though it has acquired a lot of research achievements for decades, due to its complexity, there are now many problems needed to be investigated. With the development of compute technology and optimization algorithm, as well as information and communication technology, the problems that were imperfect or unsolved in the past can be improved or be solved by means of the power of modern science and technology. Considering the status of vehicle routing problems now and using the systems engineering theory and newly optimization algorithm, this dissertation buildes the models and investigates the optimizing methods for the imperfect or unsolved problems, and has theoretical significance and practical value. The most distinctive parts of this dissertation can be listed in the following aspects:1, For the vehicle routing problems with windows and a limited number of vehicles, a hybrid genetic and tabu search algorithm is proposed. On the basis of the problem description and model establishment, firstly, as only parts of genes in a chromosome are used, in order to make full use of the chromosome, the Bellman-Ford shortest path algorithm is adopted to find the best solution that the chromosome string can represent. Secondly, tabu search is utilized to improve the capability of local search of genetic algorithm, which is caused due to smaller mutation probabilities. Moreover, tabu search is designed by adding punishing items in the objective function, and searches dynamically between feasible and infeasible region, thus not only makes the search not far from the optimal solution but enriches the search area, so that the probabilities of obtaining much better solution are improved. Finally, the solutions are compared with the best known solution and the impacts are analyzed with different parameters. 2,For the large scale and homogeneous fleet vehicle routing problem with soft time windows, a new method for solving it is proposed based on decomposition and coordination technology. After the problem is described and its model is established, firstly, by using fuzzy k-means cluster, the vehicles are classified and the center coordinates of the classified vehicles are obtained based on the position of each vehicle; then the tasks are classified based on the distances between the tasks and the center coordinates of the classified vehicles. Secondly, regarding the bad convergence while using traditional decomposition and coordination technology to solve the problem, the coordination values are designed elaborately and different adaptive genetic algorithms are proposed for the main system and subsystems. The simulation results show the efficiency of the proposed algorithm.For the large scale and heterogeneous fleet vehicle routing problem with soft time windows, an effective tabu search for application to the problem is proposed. After the description of the problem is given and its mathematic model is presented, Firstly, the candidate list strategy is proposed, which is used to abandon a large number of hopeless movements, and the size of candidate list related to the search neighborhood is adjusted dynamically with the progress of search, which provides a simple method for implementing intensification and diversification search. Secondly, the dynamic oscillation strategy is developed to control the search in the boundary area between feasible and infeasible space. The validity of the proposed method is proved by the simulation results.3,For the multi-depot vehicle routing problem with time windows, after several classic multi-depot location models are analyzed, the problem is described and its mathematical model is built. Considering the problems of lower efficiency and of easily falling into local optimal solutions for solving multi-depot vehicle routing problem presently, a new method based on decomposition and coordination technology is proposed. Firstly, the customers are decomposed into coupling and non-coupling customers by a heuristic method. Secondly, the coordination values are designed elaborately by means of an adaptive genetic algorithm and a tabu search method is developed to solve the vehicle routing problem for each depot. Finally, the simulation results are given.For multi-depot vehicle routing problcm with stochastic demands (VRPSD), on the basis of the description of the problem and the analysis of models related to the problem, its mathematical model is developed. Based on decomposition and coordination technology, in the coordination layer the coupling customers are decomposed in the optimal way by using an adaptive genetic algorithm. In the executive layer, an adaptive cross-entropy method is designed for solving VRPSD with the preventive recourse action for each subsystem. Finally, the comparison of results obtained by using different method proves the validity of the proposed method.4,After several typical algorithms are analyzed for solving the vehicle routing problems with stochastic demands, based on Cross-Entropy as well as integrating Important Sample, Monte-Carlo and Markov Chain, a new method is proposed for solving the vehicle routing problem with stochastic customers and demands. On the basis of the description of problem and the establishment of its mathematical model, firstly, due to the complexity of its objective function, an effective algorithm is designed to obtain the expected cost of routes by using Monte-Carlo sampling. Secondly, in order to improve the performance of basic cross-entropy method, an adaptive adjustment scheme is developed for the crucial routes used to update Markov transition matrix in terms of the improvement level of quintiles. Finally, simulation results show both the robustness and the effectiveness of the proposed approach for solving the problems.5,On the basis of the analysis of the stochastic shortest path problem, the dynamic vehicle routing problem with stochastic demands is described and its optimal policy model is established. For the "dimension disaster" problem of its state space, a radical basis function is utilized to approximate the optimal cost-to-go function based on the principle of reinforcement learning. Firstly, a basis function is analyzed and designed. Secondly, for a fixed policy, the bellman error as an optimization criterion is minimized by on-line tuning both least squares temporal difference algorithm for determining approximation function weight coefficients and cross entropy method for solving basis function parameters, so as to approximate the optimal cost-to-go function. Finally, simulation results show the effectiveness of the proposed method.