Local search alogrithm of dynamic vehicle routing problem with time window

In order to effectively solve dynamic vehicle routing problem with time windows, the mathematical model was established, the planning period was cut into slices, and the dynamic problem was partitioned into a series of static sub-problems, the initial solutions were constructed by intertion method.Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and Or-opt were introduced, different approaches were combined to improve initial solutions.The influences of arrival time, distribution of geographical location and time window range on route selection were analyzed, and the solving results of standard example were compared.Result shows that relocation method is the best, 2-opt* is the second and exchange is the worst for inter-route local search, 2-opt is better than Or-opt for intra-route local search, and the vehicle number, traveling distance and delay of all routes decrease with early requests, concentrated customers and wide time windows.