Models And Algorithms Of The Multi Depot Vehicle Routing Problem With Time Windows

Vehicle routing problem is a class of optimizaion problems, whose objective is to construct a set of feasible routes with minimal transportation cost. The correlative theories and methods have great application values for reducing the logistic cost, thus they are always the research hotspot of operations research and combinatorial optimization domains. For decades, a lot of variants of the vehicle routing problem have been derived, such as multi depot vehicle routing problem, vehicle routing problem with time windows, open vehicle routing problem, periodic vehicle routing problem, vehicle routing problem with pickup and delievery and so on, a great deal of research results have been achieved.In real life, there exists such a class of vehicle routing problem:A big logistic company has more than one depot located in different area, and each depot uses several vehicles to do the distribution tasks. Meanwhile, the customers have strict limit to their service time and hope to be served in appointed time intervals (time windows). Therefore, the decision-makers need to assign the customers to appropriate depots and vehicles according to their locations and time windows. The problem above can be abstracted as multi depot vehicle routing problem with time windows. For the introduction of dual constraints of multi depot and time windows, it becomes much more difficult to solve this type of vehicle routing problem.The models and algorithms of multi depot vehicle routing problem with time windows are studied in this paper. The main research works are as follows:A mathematical model of multi depot vehicle routing problem with time windows was constructed, and the heuristic algorithms commonly used to solve the multi depot vehicle routing problem with time windows were introduced.A modified variable neighborhood search was designed and implemented, integrating a hybrid local search opeartor, a post optimization procedure and the idea of simulaed annealing into the basic framework of the variable neighborhood search.Computational experiments were carried out on Cordeau benchmark instances, and serveal new best solutions were found. The computational results show that the proposed algorithm is effective in solving the multi depot vehicle routing problem with time windows.