Research Of Large-Scale Multiple Depot Vehicle Routing Problem

Distribution is an important element in modern logisties system. It includes picking up goods from distribution center and delivering goods to the customers on time.Among distribution business there are many optimizing strategies. The vehicle routing problem has great effect on improving distribution speed, quality of service and economy benefit. According to the number of distribution center, the vehicle scheduling problem can be divided into single-depot vehicle routing problem and multi-depot vehicle routing problem. The modern city logistics system usually has more than one depot. So this paper has both theoretical and practical value.Current research on MDVRP is still not deep enough. Moreover, due to the large scalability in current problem, algorithms with less running time and relative acceptable problem-solving ability are needed in practice. With the aim of the difficulties in solving them, a customer pre-merge, two-solve, three-optimize merge optimization algorithm (MOA) is developed. At the first stage, merging the clients according to the distance between the client and the depot, which transform the multi-depot vehicle routing problem to the single-depot vehicle routing problem; at the second stage, dividing the clients to the certain depot through solving the SDVRP with the Clarke-Wright algorithm with adaptive neighborhood selection strategy. At the third stage, with the disadvantage of current routing, processing two optimizing steps. One is merging the routing which has less cargo to increase using ratio of the vehicle. The other is adjusting the marginal-point using genetic algorithm, this step can lower the mileage effectively. At the same time, this paper develops the single vehicle routing deeply using the improved Lin-Kernighan algorithm. Aim at the specific status of the problem, the part of improved Lin-Kernighan algorithm is a selectivity module dueing to the complexity of this algorithm.In order to verify the effectiveness and efficiency of the proposed algorithm, a large number of simulation experiments have been carried out. In Chapter3and4, experriments on Clarke-Wright and Lin-Kernighan algorithm proves the effictive of improvement. In the last Chapter of this paper,there are a lot of experiments on the MOA, they can bu divided into three parts:experiments on the standard MDVRP examples, experiment on a small-scale MDVRP example on other paper, and experiment on some large-scale MDVRP examples. The experimental results prove the feasibility and the validity of MOA, in the second part of experiments, MOA give a better result of the small-scale MDVRP example, in the third part, MOA can obtain the efficient solution within short time, and the solution get better using the improved Lin-Kernighan algorithm.