【作者】 刘艺；

【导师】 徐行；

【作者基本信息】 电子科技大学 ， 计算机科学与技术， 2020， 硕士

【摘要】 在当前这个互联网高度发展,交通极度便利的时代,网络购物迅速普及,从而带动了物流行业的迅猛发展,也使得物流配送面临的数据量急剧增长。物流公司在对批量货物进行配送之前,往往都需要制定一个能够满足所有客户需求且配送成本最低的方案。因此如何为海量物流数据快速生成一个高效益的物流配送方案是一个亟待解决的问题。物流配送问题往往被模型化为车辆路径问题(vehicle routing problem,VRP),即在给定包裹信息以及仓库信息的情况下,找到一个在满足所有包裹配送需求以及一些物理限制的同时,使得配送路径成本最小化的路径规划方案。截至目前为止,研究人员们已经提出了许多可以用于解决车辆路径问题及其衍生问题的优化算法,例如分支界限法、动态规划法、模拟退火算法以及禁忌搜索算法等等。其中禁忌搜索算法因为其具有跳出当前搜索空间的机制,能够避免陷入局部最优而表现卓越。然而目前提出的这些优化算法都因为其自身的时间复杂度或空间复杂度而难以用于应对具有大规模数据的车辆路径问题。为此,大量的并行优化算法孕育而生。因为并行禁忌搜索是一种可以加速搜索空间探索的有效策略,近年来受到了广泛关注。然而,由于高度定制的邻域搜索策略和复杂的线程通讯机制,大部分现有方法对物流从业人员并不友好,这大大损害了这些算法的通用性和伸缩性。本论文在现有技术的基础上,对禁忌搜索算法进行了并行化优化。论文提出了一种基于分层空间划分的新的分而治之的分布式禁忌搜索算法。论文采用R树对车辆路径问题中的对象进行空间划分,将一个大规模数据的车辆路径问题转换为若干个独立的小规模的车辆路径问题。然而这些小规模的车辆路径问题并非真正意义上的完全独立,因为这些小规模的车辆路径问题得到的最佳配送方案的并集并不一定就是原本大规模车辆路径问题的最佳配送方案。因此,在对问题进行空间划分的同时,论文采用自底向上的问题合并来促进全局最佳配送方案的生成。为了充分发挥分布式计算的优势,论文在Apache Spark平台上实现了基于R树的空间划分的分布式禁忌搜索算法。并且论文对多个大规模基准数据集进行了广泛的实验。实验结果表明,论文提出方法的性能达到甚至优于文献中提出方法的性能。更多还原

【Abstract】 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.更多还原