A Research On Distributed Logistics Optimization Algorithm Based On Spark

In the era with highly developed Internet and extremely convenient transportation,the rapid popularization of online shopping has led to the rapid development of the logistics industry and the rapid increase in the amount of data faced by logistics.Before logistics companies dispatch bulk goods,they always need to generate a plan that can meet the needs of all customer and spend the lowest dispatching cost.Therefore,how to quickly generate a high-efficiency logistics dispatching plan with massive data is an urgent problem to be solved.The logistics problem is often modeled as vehicle routing problem(VRP),that is,given the information of packages and warehouses,find a solution that contains several routes that satisfies all the requirements of packages and some physical restrictions with minimize costs.So far,researchers have proposed many optimization algorithms that can be used to solve VRPs and their derivatives,such as Branch and Bound Method,Dynamic Programming(DP),Simulated Anneal(SA),and Tabu Search(TS).Among them,tabu search performs well because it has a mechanism that jumps out of current search space so that can avoid falling into a local optimum.However,these proposed optimization algorithms are difficult to deal with largescale VRPs because of their time complexity and space complexity.Therefore,a large number of parallel optimization algorithms have emerged.Parallel tabu search has received considerable attention in the past years as an approach to accelerate search space exploration for large-scale VRPs.Unfortunately,most of the existing approaches are not friendly for practitioners due to the highly tailored neighborhood search strategy and complicated thread communication mechanism,which may further impair their generality and scalability.Based on the existing technology,this thesis optimizes tabu search in parallel.In this thesis,we propose a divide-and-conquer search strategy with the help of hierarchical space partitioning.We use R-tree to partition the objects in VRP so that a large-scale VRP is converted into several independent small-scale VRPs.However,these small-scale VRPs are not completely independent in the true sense,because the union of the best local dispatching plans obtained by these small-scale VRPs is not always the global optimal dispatching plan of the original large-scale VRP.Therefore,while space-dividing large-scale VRP,bottom-up merge of small-scale VRPs is used to promote the generation of a global optimal dispatching plan.In order to give full use of distributed computing,we implement a distributed tabu search algorithm with hierarchical spatial partitioning based on R-tree on Apache Spark.We conduct extensive experiments on a number of large-scale benchmark datasets.Results show that our algorithm outperforms or achieves comparable performance with the best-known solution in the literature.