Method For Solving Dynamic Vehicle Routing Problem Based On Uncertain Receding Horizon Control Strategy

Dynamic vehicle routing problem(DVRP)is widely used in all aspects of life,such as express delivery,fresh delivery and so on.It also plays an important role in intelligent transportation and intelligent city construction.As an effective method of on-line control,receding horizon control(RHC)strategy can be used to solve DVRP.RHC usually divides the system time into some equal time windows.It cannot divide the time window size reasonably according to the characteristics of the model.RHC can only deal with the customers within the current time window,and it cannot make an overall plan according to the situations of the customers near the window.Thus,this thesis proposes two kinds of uncertain receding horizon control(URHC)strategies: 1.A fuzzy receding horizon control(FRHC)strategy is proposed by introducing the membership function in the fuzzy set.2.By using the property of the definite integral to calculate probability,a dynamic receding horizon control(DRHC)strategy based on definite integral is proposed.In the first step,a FRHC strategy for the DVRP model is studied.According to the rule that RHC can only serve customers within the current time window,the FRHC defines the membership function between the customers and the time windows.By this way,it redefines the relationship between the customers and the time windows,and divides the fuzzy time window by the threshold.According to each time window’s customers,genetic algorithm(GA)is used for planning the traveling route.And 10 instances in international standard test set are simulated.By discussing the result of RHC and other 5 set thresholds,the best threshold value of FRHC is found.Finally,RHC and FRHC are combined with the genetic algorithm(GA),the first come first served algorithm(FCFS),the nearest neighbor search algorithm(NN),the expected service time sorting method(FAST),the objective function nearest neighbor Method,NNF)5 methods respectively,to discuss the solutions of FRHC-GA,RHC-GA,FRHC-FCFS,RHC-FCFS and other 6 methods for DVRP.The experimental results show that FRHC strategy increases the information exchange between time windows,and improves the neighborhood search ability of the time windows.The FRHC-GA method is the most reasonable method for DVRP.In the second step,a dynamic receding horizon control strategy(DRHC)based on definite integral is proposed to solve the dynamic vehicle routing problem model with expected service time obeying normal distribution(DVRP-ESTND).Based on the consideration of people’s lunchtime habits in life,a dynamic vehicle routing problem model with expected service time obeying normal distribution(DVRP-ESTND)is proposed.RHC usually divides the system time into some equal time windows,it is also called the average receding horizon control(ARHC).RHC sometimes divides the system time into some random time windows,it is called the random receding horizon control(RRHC).As for DVRP-ESTND model under this two strategies,the difference of the number of the customers for each time windows is big.It is easy to cause problems such as low vehicle utilization and long customers waiting time.The DRHC strategy based on the definite integral can calculate the probability of normal distribution.The total probability value and the average probability value of each time window can be calculated by using the definite integral,and the size of each time window can be calculated.Through statistical analysis of the number of customers in the time window under the three strategies,the rationality of DRHC strategy is analyzed.Finally,DRHC,ARHC and RHC are combined with GA,FCFS,FAST,NN and NNF algorithms respectively,to simulate 5 groups of different normal distribution instances.The experimental results show that: 1.Under the same conditions,the solution of DRHC strategy is better than that of RHC strategy;2.The DRHC-GA method is the most reasonable and effective way to solve DVRP problem.