Study On Large Scale Logistics Vehicle Routing Optimization Based On Voronoi Diagram

Logisitcs plays an important place in the social-econimic activities and directs to the modern times logitistics. The transportation routing optimization is a key component for logistics, which pursues to provide a high quality solution in a short time. Usually, it is modeled as a vehicle routing problem (VRP). As it is NP-hard, the computation time increases factorially as the customer number. Current research has diversified the optimization directions and dealt with small and medium-size VRPs. Nowadays, the growing urbanization in China has motivated the explosion of customer demand. The size of vehicle routing problem becomes bigger and bigger. Solving the lagre-scale vehicle routing problem is an emerging challenge for modern times logistics.From a spatial view, components in the vehicle routing problem are spatial objects, such as depots, customers and routes. The optimization of VRP must deal with spatial-temporal sub-problems including route optimization, customers assignment between depots and time confilict. Based on the Voronoi diagram, this study proposes efficient heuristic algorithms for three typical largs-scale vehicle routing problems. The main dissertation consists of four parts as follows.1. The study proposes a heuristic algorithm for the large scale capitated vehicle routing problem (CVRP). The key optimization issue is to make use of the infinite computation efforts to search the promising solution space. This disseratation derives the k-ring Voronoi neighbors from the Voronoi diagram. The proposed algorithm employes the local search with the k-ring Voronoi neighbors reduction strategy. The long edge defined by Voronoi distance is used to guide the local search. An experiment on the large scale CVRP benchmark and real-life logistics cases in Guangzhou, China were implemented to test its performance. The result indicated the proposed algorithm outperforms current metaheuristics.2. The study proposes a heuristic algorithm based on bi-level Voronoi diagram for the muti-depot vehicle routing problem (MDVRP). The challenge is to keep a balance between customer assignment and routing optimization. Based on the Voronoi partition and Voronoi neighborhood, a bi-level Voronoi diagram model is derived from the MDVRP. The upper Voronoi diagram is generated using depots, to assign customer between depots. The lower Voronoi diagram is generated using customers, to reduce local search space. The combination of them promotes a customer reassignment at the k-ring Voronoi neighbours of the upper Voronoi edges. An experiment with the MDVRP bencnmark and simulated logistics cased in Beijing. China were conducted. Their results showed the proposed heuristic could provides high quality solution in a reasonable time.3. The study proposes a heuristic algorithm based on bi-level spatial-temporal Voronoi diagram for the multi-depot vehicle routing problem with time windows (MDVRPTW). The time windows of depots and customer are represented at a spatial-temproal coordination system. A bi-level spatial-temproal Voronoi diagram is built to deal with customer assignment and route optimization. Combining with spatial-temporal accessibility, the spatial-temporal Voronoi neighbors is used to reduce local search space. An experiment with the popular MDVRPTW and the simulated logistics cases in Yangtze River Delta, China were done to validate the performance. The result showed the effectiveness and efficiency of the proposed algorithm.4. The study validates the effectiveness of the vehicle routing optization based on voronoi diagram. The k-ring Voronoi neighors in the many VRPs was summrized. The time complexity of the local search was analysed and validated by experiment. By using of many hiqh quality solutions for the VRPs, the hidden Voronoi neighborhood is revealed as the short Voronoi segments are their main parts. Therefore, the optimization for the VRP based on the Voronoi diagram is propoer and effective.