Algorithm Design And System Implementation For Dynamic Vehicle Routing Problem With Time Constraints

With the rapid development of logistics enterprises in recent years,enterprises' expectations reduce the cost are more and more intensely,there is a strong need for research on vehicle allocation issues.Vehicle routing problem researches on such issues,most of the earlier research focus on CVRP,but the limitation of CVRP restrains its practicability.Based on CVRP,DVRP eliminates the constraints of predicting all customer requirements,it is more realistic,but more difficult to solve the optimal solution than CVRP,furthermore it is also more complex than constrained vehicle routing problem,and harder to find the optimal solution.At present,there are few researches on dynamic vehicle routing problem,and there are fewer researches on time-constrained dynamic vehicle routing problem which is more realistic.It is very necessary to build the model and design efficient algorithms for these problems.This thesis proposes the model of the dynamic vehicle routing problem with time constraints,and gives a hybrid algorithm(simulated annealing al gorithm and genetic algorithm)for solving it.Based on the theoretical results,the thesis designs and develops a dynamic vehicle scheduling system with time constraints.The hybrid algorithm proposed in this thesis sets up the solution in two stages: The first stage is to play the rapidity of simulated annealing algorithm and obtain the pre-optimal solution set;The second stage plays the high efficiency of genetic algorithm,and uses the preliminary optimal solution set of the first stage as the population,and in the processing of genetic algorithm for the selection of operations,crossover operation,mutation operation provid es a flexible solution,and finally obtain the optimal solution.The experiment is compared with general genetic algorithm and simulated annealing algorithm.The experiment results prove the competition of the algorithm.In addition,dynamic vehicle scheduling system with time constrained based on the hybrid algorithm which this paper proposed,contains three stages: foreground data input,background data operations and show the results of the operation by combining Baidu map API.