Modeling And Optimization Methods For Uncertain Vehicle Routing Problems

Vehicle Routing Problem (VRP) is an important issue in real-word application of logistics and transportation. The diversity of human needs and the existence of uncertainty increase the difficulty in vehicle scheduling management. Although a lot of research has been done in uncertain VRP, there is a lack of dynamic management statigies and the rapid response mechanisms to handle exception information in distribution. This dissertation focuses on the modeling and optimization methods for uncertain VRP. The main contributions and innovative results of our study are as follows.We first study three heruristic algorithms based on the hybrid search strategy for the multi-objective mathematical model of the VRP with time windows. In the discrete differential evolution hybrid algorithm, the linear weighting method is used to solve the multi-objective model. The discrete mutation and crossover operators are improved and the tabu search is introduced to enhance the local search capability of the algorithm. The random vehicle loading method is proposed to construce variety of initial solutions, and the insertion and 2-Opt feasible neighborhoods to search feasible solutions. The memetic algorithm and the multi-objective memetic algorithm use the linear weighting method and the Pareto method to solve the multi-objective model, respectively. In both the algorithms, the population search is genetic algorithm, and the local search uses tabu search. Comparative experiments show the effectiveness of the proposed approaches.Considering the VRP with time windows and fuzzy demands, we propose a dynamic optimization strategy. The initial plan can be dynamically adjusted in the implementation according to the real-time prediction in advance. A hybrid NSGA-â…¡algorithm embedded fuzzy simulation is developed for solving the problem. Computational experiments illustrate the influence of decision-maker's preference on solutions and verify the effectiveness of the dynamic optimization strategy while compared with the traditional vehicle scheduling method. Considering the VRP with fuzzy due-time, the theory of fuzzy event is used to measure the service satisfaction and calculate the best satisfaction. We develop a multi-objective tabu search algorithm based on Pareto optimal. Compared with the multi-objective algorithm NSGA-â…¡, computational experiments show the effectiveness of the proposed algorithm. Considering the influence factors of the customer's subjective preferences, we study the multi-objective optimization method for the VRP with fuzzy time windows. The goals are to minimize the logistics cost and to maximize the service level of the supplier to customers. Moreover, we develop a multi-objective tabu search algorithm embedded the dynamic programming. When fuzzy time windows are in piecewise linear and nonlinear cancave membership function forms, the beginning service times are optimized by the limited enumeration algorithm and subgradient-based dichotomy iterative algorithm, respectively. Further, we consider a stochastic VRP with fuzzy time windows, where the travel and service times are stochastic. To deal with random factors and optimize the customer satisfaction, we propose a pre-planned strategy that priori routes are decided firstly, and then the beginning service time for each customer is adjusted according to the time scheduling rules when the vehicle arrives at a customer node.Finally, we study the dynamic VRP with time windows. A new dynamic scheduling strategy is provided, which is named emergency customer insertion and batch optimization strategy. This strategy only distinguishes the emergency customers and inserts them into real-time routing plan. The simulation experiments compare to the strategies of the repeated reoptimization after inserting any new customers and the batch optimization. Moreover, we discuss the impact of batch scheduling intervals on the scheduling performance.