带容量约束的开放式弧路径问题的算法研究

发布时间：2018-01-30 03:52

本文关键词： 开放式弧路径问题禁忌搜索变邻域搜索劣解　出处：《天津大学》2014年硕士论文　论文类型：学位论文

【摘要】：具有容量约束弧路径问题（Capacitated Arc Routing Problem, CARP）产生于交通运输服务系统，因其广泛应用于城市街道清扫、垃圾回收、输电线路检查、物流配送等现实生活中，而得到了广泛的研究。本文主要研究CARP的一种新的扩展类型具有容量约束的开放式弧路径问题（OpenCARP, OCARP），该类问题与CARP的主要区别在于车辆在服务完所有客户后无需返回车场。该类问题主要产生于第三方物流配送服务业，而且随着电子商务的日渐繁荣，第三方物流配送企业间的竞争也更加激烈，提升物流配送服务效率，，较好地满足大城市及超大城市的密集型配送需求，降低物流配送成本，对第三方物流企业的存亡至关重要。本文详细描述了OCARP的图论模型及数学模型，分析了其现有的求解算法及求解效果，设计了两种算法用于求解OCARP，即禁忌搜索算法与改进的变邻域搜索算法。禁忌搜索算法基于局部搜索算法，通过接受劣解来避免算法陷入局部最优，同时使用禁忌表来避免循环搜索，最后配合破特赦则来允许算法向更好的区域搜索，该策略使得算法同时具有广度搜索与深度搜索的良好性能。变邻域搜索其基本思想是在局部搜索的过程中系统地改变当前解的邻域结构，以降低陷入局部最优的风险，经过多次迭代，最终达到收敛的目的。两种算法在81个基准数据集上的测试结果表明了它的有效性，TS算法在23个算例上达到了最优下界，并优化了51个算例的最优上界；IVNS算法在28个算例上达到了最优下界，并优化了55个算例的最优上界。
[Abstract]:The capacity-constrained arc path problem (CARP) is derived from the transportation service system. It is widely used in urban street cleaning, garbage collection, transmission line inspection, logistics distribution and other real life. In this paper, a new extended type of CARP with capacity constraints open arc path problem (OCARP) is studied. The main difference between this kind of problem and CARP is that vehicles do not need to return to the yard after serving all customers. This kind of problem mainly arises from the third party logistics service industry, and with the increasing prosperity of electronic commerce. The competition between the third party logistics distribution enterprises is also more fierce, improve the efficiency of logistics distribution services, better meet the needs of large cities and megacities, reduce the cost of logistics distribution. It is very important to the survival of the third party logistics enterprises. In this paper, the graph theory model and mathematical model of OCARP are described in detail, and its existing algorithms and results are analyzed. Two algorithms are designed to solve OCARP. Tabu search algorithm and improved variable neighborhood search algorithm. Tabu search algorithm is based on local search algorithm, by accepting inferior solution to avoid the algorithm falling into local optimum, and Tabu table is used to avoid circular search. Finally, it allows the algorithm to search for better areas. The strategy makes the algorithm have good performance of both breadth search and depth search. The basic idea of variable neighborhood search is to systematically change the neighborhood structure of the current solution in the process of local search. In order to reduce the risk of falling into the local optimum, after many iterations, the goal of convergence is finally achieved. The test results of the two algorithms on 81 datum data sets show that the TS algorithm achieves the optimal lower bound in 23 examples, and optimizes the optimal upper bound of 51 examples. The IVNS algorithm achieves the optimal lower bound for 28 examples and optimizes the optimal upper bound for 55 examples.
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U116.2

【相似文献】