同时配送和回收需求的容量约束弧路径问题

发布时间：2018-04-18 15:58

本文选题：容量约束弧路径问题 + 同时配送和回收　；参考：《天津大学》2014年硕士论文

【摘要】：标准的容量约束弧路径问题(Capacitated Arc Routing Problem, CARP)是单纯的配送或回收的路径规划问题，其典型应用有邮件投递、街道清扫等问题。随着逆向物流在现代快递公司的服务模式中的普及，本文将逆向物流加入到CARP问题的模型中，提出了一种同时配送和回收需求的容量约束的弧路径问题(Capacitated Arc Routing Problem with Simultaneous Pickups andDeliveries, CARPSPD)并进行了研究，主要内容如下：首先，对具有配送和回收需求的车辆路径问题(VRPB、VRPMB、VRPSPD)的研究现状进行了综述，分析了存在的问题及现有的求解方法，以此作为进一步研究的基础。其次，通过对问题的分析，本文建立了CARPSPD问题的基本模型，将具有两种不同需求的条件加入到模型中去，增加了模型的实用性，并定义了强弱可行解的概念及转化方法。再次，针对CARPSPD问题，设计了两种求解算法：构造启发式算法与变邻域搜索算法。前者利用基于椭圆规则的路径扫描的启发式算法产生初始弱可行解，再将其转换成强可行解；后者采用4种邻域结构混合进行局部搜索，并采用了一种分层的局部搜索策略，扩大了算法的搜索空间。最后，将CARP的基准数据集转化为CARPSPD问题的数据集，，并用本文提出的路径扫描启发式算法与变邻域搜索算法进行求解。结果表明，本文提出的变邻域搜索算法在寻优能力、稳定性与解的质量等方面都优于构造启发式算法，能更有效地求解CARPSPD问题。
[Abstract]:The standard capacity-constrained arc routing problem (CARPs) is a simple routing problem of distribution or recovery. Its typical applications include mail delivery, street cleaning and so on.With the popularization of reverse logistics in the service mode of modern express company, this paper adds reverse logistics to the model of CARP problem.In this paper, a capacity-constrained arc path problem for both distribution and recovery requirements is proposed and studied. The main contents are as follows:Firstly, the research status of VRPMBPSPD, a vehicle routing problem with the demand of distribution and recovery, is summarized, and the existing problems and existing solutions are analyzed as the basis of further research.Secondly, through the analysis of the problem, this paper establishes the basic model of the CARPSPD problem, adds two conditions with different requirements to the model, increases the practicability of the model, and defines the concept and transformation method of the strong and weak feasible solution.Thirdly, for the CARPSPD problem, two algorithms are designed: construct heuristic algorithm and variable neighborhood search algorithm.The former uses the heuristic algorithm of path scanning based on elliptic rules to generate the initial weak feasible solution, and then converts it into a strong feasible solution, while the latter uses four kinds of neighborhood structures to carry out local search, and adopts a hierarchical local search strategy.The search space of the algorithm is expanded.Finally, the benchmark data set of CARP is transformed into the data set of CARPSPD problem, and the path scanning heuristic algorithm and variable neighborhood search algorithm proposed in this paper are used to solve the problem.The results show that the proposed variable neighborhood search algorithm is superior to the heuristic algorithm in terms of its searching ability, stability and solution quality, and can solve the CARPSPD problem more effectively.
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F252;U116.2

【相似文献】