Abstract: The Multi Depot Vehicle Routing Problem with Time Windows(MDVRPTW)is an important variant of the Vehicle Routing Problem(VRP),which is extremely complex and still not resolvedr well.To solve the problem,mathematical model of the MDVRPTW is constructed and a modified variable neighborhood search algorithm is proposed.In the algorithm,a clustering algorithm is utilized to allocate customers in the initial solution construction phase,a hybrid operator is applied in the local search phase to come up with a local optimal solution,apost optimization procedure is incorporated to further improve the best found solutions,the idea of simulated annealing is introduced to take control of the acceptance of new solutions.The performance of the proposed algorithm is tested on the benchmark instances proposed by Cordeau and compared with other algorithms in the literature.The results indicate that the proposed algorithm is effective in solving the MDVRPTW and showes some advantage both in stability and runtime.And finally most of the old optimal solutions are updated.

Key words: multi depot vehicle routing problem with time windows, variable neighborhood search, post optimization, simulated anneali