本文關(guān)鍵詞： 開放式 弧路徑問題 禁忌搜索 變鄰域搜索 劣解　出處：《天津大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：具有容量約束弧路徑問題（Capacitated Arc Routing Problem, CARP）產(chǎn)生于交通運輸服務(wù)系統(tǒng)，因其廣泛應(yīng)用于城市街道清掃、垃圾回收、輸電線路檢查、物流配送等現(xiàn)實生活中，而得到了廣泛的研究。本文主要研究CARP的一種新的擴展類型 具有容量約束的開放式弧路徑問題（OpenCARP, OCARP），該類問題與CARP的主要區(qū)別在于車輛在服務(wù)完所有客戶后無需返回車場。該類問題主要產(chǎn)生于第三方物流配送服務(wù)業(yè)，而且隨著電子商務(wù)的日漸繁榮，第三方物流配送企業(yè)間的競爭也更加激烈，提升物流配送服務(wù)效率，，較好地滿足大城市及超大城市的密集型配送需求，降低物流配送成本，對第三方物流企業(yè)的存亡至關(guān)重要。 本文詳細描述了OCARP的圖論模型及數(shù)學(xué)模型，分析了其現(xiàn)有的求解算法及求解效果，設(shè)計了兩種算法用于求解OCARP，即禁忌搜索算法與改進的變鄰域搜索算法。 禁忌搜索算法基于局部搜索算法，通過接受劣解來避免算法陷入局部最優(yōu)，同時使用禁忌表來避免循環(huán)搜索，最后配合破特赦則來允許算法向更好的區(qū)域搜索，該策略使得算法同時具有廣度搜索與深度搜索的良好性能。變鄰域搜索其基本思想是在局部搜索的過程中系統(tǒng)地改變當(dāng)前解的鄰域結(jié)構(gòu)，以降低陷入局部最優(yōu)的風(fēng)險，經(jīng)過多次迭代，最終達到收斂的目的。 兩種算法在81個基準(zhǔn)數(shù)據(jù)集上的測試結(jié)果表明了它的有效性，TS算法在23個算例上達到了最優(yōu)下界，并優(yōu)化了51個算例的最優(yōu)上界；IVNS算法在28個算例上達到了最優(yōu)下界，并優(yōu)化了55個算例的最優(yōu)上界。
[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.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：U116.2

【相似文獻】

相關(guān)期刊論文 前10條

1 田W

本文編號：1475215