本文選題：容量約束弧路徑問題 + 同時配送和回收��； 參考：《天津大學(xué)》2014年碩士論文

【摘要】：標(biāo)準(zhǔn)的容量約束弧路徑問題(Capacitated Arc Routing Problem, CARP)是單純的配送或回收的路徑規(guī)劃問題，其典型應(yīng)用有郵件投遞、街道清掃等問題。隨著逆向物流在現(xiàn)代快遞公司的服務(wù)模式中的普及，本文將逆向物流加入到CARP問題的模型中，提出了一種同時配送和回收需求的容量約束的弧路徑問題(Capacitated Arc Routing Problem with Simultaneous Pickups andDeliveries, CARPSPD)并進(jìn)行了研究，主要內(nèi)容如下： 首先，對具有配送和回收需求的車輛路徑問題(VRPB、VRPMB、VRPSPD)的研究現(xiàn)狀進(jìn)行了綜述，分析了存在的問題及現(xiàn)有的求解方法，以此作為進(jìn)一步研究的基礎(chǔ)。 其次，通過對問題的分析，本文建立了CARPSPD問題的基本模型，將具有兩種不同需求的條件加入到模型中去，增加了模型的實(shí)用性，并定義了強(qiáng)弱可行解的概念及轉(zhuǎn)化方法。 再次，針對CARPSPD問題，設(shè)計(jì)了兩種求解算法：構(gòu)造啟發(fā)式算法與變鄰域搜索算法。前者利用基于橢圓規(guī)則的路徑掃描的啟發(fā)式算法產(chǎn)生初始弱可行解，再將其轉(zhuǎn)換成強(qiáng)可行解；后者采用4種鄰域結(jié)構(gòu)混合進(jìn)行局部搜索，并采用了一種分層的局部搜索策略，擴(kuò)大了算法的搜索空間。 最后，將CARP的基準(zhǔn)數(shù)據(jù)集轉(zhuǎn)化為CARPSPD問題的數(shù)據(jù)集，，并用本文提出的路徑掃描啟發(fā)式算法與變鄰域搜索算法進(jìn)行求解。結(jié)果表明，本文提出的變鄰域搜索算法在尋優(yōu)能力、穩(wěn)定性與解的質(zhì)量等方面都優(yōu)于構(gòu)造啟發(fā)式算法，能更有效地求解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.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：F252;U116.2

【相似文獻(xiàn)】

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

1 田W

本文編號：1769054