Multi-depot Vehicle Routing Problem With Vehicles Time Windows

With the rapid development of social economy, many logistics companies often have multiple distribution centers(depots). In order to achieve lower costs and higher quality of service, how to carry out reasonable task allocation and arrange appropriate vehicle route between distribution center is a question the companies are extremely concerned. Multi-depot vehicle routing problem has become a hot issue in the field of vehicle routing problems.At present, multi-depot vehicle routing problem studies the time window mainly from the customer perspective, aimed at improving the quality of services at the same time ensuring the lowest cost. This paper puts forward the concept of vehicle time window based on enterprise cost control and resource allocation optimized. Thus the vehicle time window is introduced into vehicle routing problem, when considering the running vehicle resources in the deployment of the vehicle. Finally we establish the model of multi-depot vehicle routing problem with the customer time window and vehicle time window, combined with the actual situation and characteristics of practical operation. This paper mainly includes the following aspects:1. An overview of the research background, significance and innovation, summarize the current research status of the domestic and foreign related issues, etc.2. Research about multi-depot vehicle routing problem with customer time window. On the basis of the introduction about components, classification, model and algorithm of VRP, the paper presents two kinds of constraints including multi-depot and customer time window, and thus describes the multi-depot vehicle routing problem with customer time window. Finally the mathematical model is built and its algorithms are summarized.3. Build a mathematical model of multi-depot vehicle routing problem with vehicle time window. On the basis of a detailed description of the vehicle time window, multi-depot vehicle routing problem with vehicle time window is described and defined. Eventually the paper constructs a mathematical model of multi-depot vehicle routing problem with vehicle time window.4. Algorithm for multi-depot vehicle routing problem with vehicle time window. Firstly the paper introduces clustering algorithm and simulated annealing algorithm in detail. Secondly based on the method of “Cluster First- Route Second”, the distribution area is divided by k-means clustering analysis, at this point multi-depot vehicle routing problem will be converted to vehicle routing problem. Then the paper uses simulated annealing algorithm to solve the vehicle routing problem, and gives a experimental analysis.