导读:本文包含了弧路径问题论文开题报告文献综述及选题提纲参考文献，主要关键词:多次需求,弧路径问题,路径优化
弧路径问题论文文献综述
李坤阳[1]（2019）在《多次需求的特殊路段限容量弧路径问题研究》一文中研究指出限容量弧路径问题在城市生活当中具有一定的普遍性,引起广泛的关注。本文所关注的焦点是针对CARP问题的一种拓展问题:考虑了特殊路段的多次需求情况下的路径优化问题。首先提出了此类问题的背景和意义,然后针对该问题中的容量约束和需求次数两个方面进行了分析,最后建立模型,并用模拟退火算法进行求解,然后对结果进行分析。(本文来源于《山东工业技术》期刊2019年02期）
李金萍,杨信丰,赵平平,卢军莉[2]（2018）在《周期性带容量限制的弧路径问题模型研究》一文中研究指出周期性带容量限制的弧路径问题已成为现实生活中路径优化方面很普遍的问题,因此,研究该问题具有很重要的意义。文章研究的主要内容是多周期带容量限制的弧路径优化模型,以洒水车服务道路为例,将车场和路线的组成看作无向网络,在相关假设前提下,考虑道路需求次数,车辆容量,车辆最长服务时间,周期时长等约束条件,建立了以所有周期所有车辆的服务总时间最短为目标的优化模型。最后运用LINGO软件对实例进行了计算,验证了模型的正确性和有效性,并对计算结果进行了分析。(本文来源于《物流科技》期刊2018年03期）
要婷婷[3]（2016）在《基于模因演化算法的有限容量弧路径问题研究》一文中研究指出有限容量弧路径问题(Capacitated Arc Routing Problem, CARP)是一个经典的带有约束条件的组合优化问题,在现实生活中有非常广泛的应用,如城市道路撒盐与洒水路径规划,垃圾回收线路规划,物流配送网络优化,输气、输电线路检修规划等等,因此也得到了许多研究者的关注。由于该问题是NP-hard问题,对于精确算法,要在可接受的时间内得到问题的最优解是非常困难的,并且计算成本非常之大。因此,本文旨在利用元启发式方法在给定时间内取得性能更优的次优解,为有限容量弧路径问题提供更加有效实用的解决方案。首先,本文以目前求解CARP较为领先的算法—基于扩展邻域搜索的模因演化算法(MAENS)为基础算法,提出了叁种改进方法,即(1)使用锦标赛选择算子筛选父代(MAENS-T);(2)基于个体适应度的自适应搜索概率(MAENS-Pls);(3)基于动态参数的随机排序算法(MAENS-Pf)，结合叁种改进方法,形成了本文所提出的基于自适应扩展邻域搜索的模因演化算法(MAENS-C)，然后利用C语言编程实现算法,并采用研究领域内的通用测试集—Egl数据集中的叁个实例对叁种改进算法分别进行测试,证明了本文所设计算法的有效性。其次,针对设计的各版本算法中包含的参数,利用统计赛车技术(Racing Algorithm)与统计检验中的非参数检验方法对所有算法在全部的实验用例上(Egl数据集的八个实验用例)进行了参数优化,大大节省了参数优化的计算成本,最终得到了各算法的优化参数组合,为算法评价、应用奠定了基础。再次,基于改进算法与其相应的优化参数组合,利用平均总成本,收敛可靠性,全局寻优能力,鲁棒稳定性,以及时间复杂度五个评价指标,在Egl数据集的八个实例上进行了定量与定性的算法评价。本文主要从相同演化代数和相同时间复杂度水平两个角度进行了比较总结,得出了MAENS-Pls以及叁种改进方法的结合算法MAENS-C显着的优于基础算法MAENS,并且发现了13个针对CARP问题的新型最优解,进一步验证了本文提出的算法能有效地对局部搜索频率与深度进行双重优化,证明了算法的优异性能。最后,将本文的理论研究成果应用于路径规划实例中,利用英国兰开夏郡Egl数据集的路径服务需求与地理信息,对兰开夏郡的路网进行了实例验证,为路径规划与车辆分配提供了优化的规划方案,并进行了优化解的可视化呈现,为交通领域内的路径规划提供了有效的解决方案。(本文来源于《北京交通大学》期刊2016-03-01）
王娟[4]（2016）在《针对非确定和大规模限容量弧路径问题的近似算法》一文中研究指出限容量弧路径问题是一个经典的组合优化问题。它可以归结为在一个给定的连通图上寻找经过图中某些边并满足特定约束条件的最优回路集。限容量弧路径问题在现实生活中有着极为广泛的应用,如冬季路面撒盐、城市垃圾清理及物流运输等实际应用均可被抽象为限容量弧路径问题。此类问题在现代工业和民生中有着重要的地位。因此,近年来,限容量弧路径问题获得了越来越多的研究关注,发展出各式各样的问题模型与求解方法。然而,研究工作与实际应用间尚存在一定的差距。大部分研究工作均局限于确定性问题模型,且所能求解的问题规模较小,而实际应用中往往存在许多不确定因素,问题规模也往往超出已有方法的能力范围,因而导致这些研究工作无法直接应用于大部分的实际问题。基于此,本文主要研究上述有着广泛应用需求却在一定程度上被研究者们忽视的问题模型—非确定限容量弧路径问题与大规模限容量弧路径问题。本文研究的第一个问题——非确定限容量弧路径问题是近年来提出的新的问题变种。该问题考虑了实际应用中的四个不确定因素：任务的需求量,边的消耗,任务的存在性以及边的存在性,问题目标为求解所有可能的环境下鲁棒性最优的解。相比以往的确定性问题模型,非确定限容量弧路径问题更贴近实际应用,然而,由于其提出时间较晚且求解难度较大,现有的研究中尚不存在针对该问题模型的有效解法。考虑到在许多实际问题中,我们往往无法得知问题所包含随机变量的底层分布,从而无法建立对应的概率模型对其进行求解。因此,本文采用样本近似的方法来对非确定问题进行建模,将原问题表达为一组确定的样本问题,并求解针对样本问题集的鲁棒解。我们首先选择期望性能作为鲁棒性评价标准,提出基于多种群的模因算法(Memetic Algorithm with Multiple Population, MAMP)。MAMP的核心思想在于：对每个样本维护一个种群,在算法运行过程中通过种群选择机制从样本实例层面调控算法的搜索偏好,避免算法陷入较易求解的样本而忽略了较难求解的样本；在局部搜索过程中,使用合并-拆分算子从问题解的层面调控算法的搜索方向,避免算法在单个样本实例解空间中陷入局部最优。实验表明,通过上述两个层面对算法搜索方向的引导,MAMP相比现有算法具有更好的寻求全局最优解的能力。但由于使用了较为耗时的局部搜索算子以及对中间解的适应度评估较为耗时,MAMP算法需要更多的运行时间。随后,我们采用最坏情况下的性能作为鲁棒性评价标准。针对搜索过程中解的适应度评估较为耗时的问题,设计了一个可以避免无效适应度计算的随机局部搜索方法,并将其与分布估计算法结合,得到一个兼顾性能与效率的算法Estimation of Distribution Algorithm with Stochastic Local Search (EDASLS)。该算法通过学习种群中优质个体所蕴含的任务之间紧密度的信息,建立分布模型。然后利用此模型生成新的解并在随机局部搜索中避免无效的适应度计算。实验表明,EDASLS可获得比其他算法鲁棒性更优的解。在算法的运行时间上,EDASLS也表现出较强的优势,在适应度评估次数相同的情况下,EDASLS需要的运行时间更短。更进一步的实验表明,EDASLS的优越性主要归功于随机局部搜索,该方法可以在不影响算法性能的前提下,大大提升算法运行速度。本文研究的另一个问题——大规模限容量弧路径问题本质上是一个基本限容量弧路径问题,但是由于其问题规模较大,现有的研究方法均无法在可接受的时间内给出问题的一个质量上可被接受的解。基于上述原因,本文提出一个基于层次分解的对问题规模具有可扩展性的算法Scalable Approach based on Hierarchical Decomposition (SAHiD),该算法的可扩展性表现在当问题规模(任务数)急速增长时,算法仍能在给定的较短时间(例如30分钟)内给出一个质量较优的解。通过对任务集以层次分解的方式进行组合排序,SAHiD可以快速生成具有较高质量的初始解。上述层次分解操作耗时极短,因而可被嵌入迭代搜索过程中以不断提升解的质量。为了验证SAHiD算法的可扩展性,我们根据合肥市和北京市的真实交通路网生成了两个问题规模逐渐增大的测试集Hefei与Beijing,并在上述问题集上将SAHiD与现有的求解传统限容量弧路径问题的优秀算法和专为大规模问题设计的算法进行了比较。实验结果表明,无论是从(得到质量相当的解需要的)运算时间还是从(给定时间内能求得的)解的质量来看,SAHiD表现出优异的性能,而现有的算法性能则不尽如人意。尤其是在规模较大(任务数超过400)的问题实例上,现有优秀算法均无法在给定时间内给出该问题的一个质量上可被接受的次优解。在现有的规模最大的问题集egl-large上,SAHiD虽然不能得到最优的最终解,但在计算时间相当少的情况下,SAHiD可以得到比其他算法更优秀的解。因此,在需要较快得到问题的解(分钟级甚至是秒级)的情况下,SAHiD是一个更好的选择。(本文来源于《中国科学技术大学》期刊2016-01-16）
林丹,梁桉洋[5]（2015）在《多起始点进化算法在容量约束弧路径问题上的应用》一文中研究指出容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.(本文来源于《天津理工大学学报》期刊2015年03期）
梁桉洋[6]（2015）在《需求可分割的容量限制弧路径问题的启发式算法研究》一文中研究指出弧路径问题是一类运筹学邻域的组合优化问题,由于其在运输业,物流配送上的广泛应用而备受研究者的关注.在本文中,我们主要研究容量约束弧路径问题和需求可分割的容量约束弧路径问题,它们在邮递送货,城市垃圾回收,城市冬季供暖等方面有着非常广泛的现实应用.在容量约束弧路径问题的研究中,文中主要在现有的求解算法基础上进行构造与优化,并将并行计算应用在竞争模因算法的求解过程中,得到了并行的进化算法,在测试集上的测试表明,算法可行有效且能够节省大量时间.在需求可分割问题的研究中,文中通过需求可分割的容量约束弧路径问题与容量约束弧路径问题间的关系,提出了一种过渡模型,通过这种过渡模型对问题进行求解,从而得出了用于求解需求可分割的容量约束弧路径问题的交叉迭代算法,在CARP问题的63个基准数据集上的求解表明,算法可在有效时间内得出所有的最好解,并且,与CARP相比,算法在3个问题上得到了更好解.(本文来源于《天津大学》期刊2015-05-27）
彭锦环,马慧民[7]（2015）在《带容量约束的弧路径问题:文献综述》一文中研究指出参考关于弧路径问题(ARP)的文献,可以将弧路径问题分为叁类,中国邮路问题、乡村邮路问题和带容量约束的弧路径问题,文章对带容量约束的弧路径问题(CARP)作出综述,通过对CARP问题的了解来阐述目前带容量约束的弧路径问题的研究热点,以及目前CARP的主要应用领域。对CARP问题的综述重点是CARP问题的分类以及CARP问题的计算方法,通过对前人成果的总结能更加明确地理解带容量约束的弧路径问题。(本文来源于《物流科技》期刊2015年01期）
黄庆伟[8]（2014）在《带容量约束的开放式弧路径问题的算法研究》一文中研究指出具有容量约束弧路径问题（Capacitated Arc Routing Problem, CARP）产生于交通运输服务系统，因其广泛应用于城市街道清扫、垃圾回收、输电线路检查、物流配送等现实生活中，而得到了广泛的研究。本文主要研究CARP的一种新的扩展类型―具有容量约束的开放式弧路径问题（OpenCARP, OCARP），该类问题与CARP的主要区别在于车辆在服务完所有客户后无需返回车场。该类问题主要产生于第叁方物流配送服务业，而且随着电子商务的日渐繁荣，第叁方物流配送企业间的竞争也更加激烈，提升物流配送服务效率，较好地满足大城市及超大城市的密集型配送需求，降低物流配送成本，对第叁方物流企业的存亡至关重要。本文详细描述了OCARP的图论模型及数学模型，分析了其现有的求解算法及求解效果，设计了两种算法用于求解OCARP，即禁忌搜索算法与改进的变邻域搜索算法。禁忌搜索算法基于局部搜索算法，通过接受劣解来避免算法陷入局部最优，同时使用禁忌表来避免循环搜索，最后配合破特赦则来允许算法向更好的区域搜索，该策略使得算法同时具有广度搜索与深度搜索的良好性能。变邻域搜索其基本思想是在局部搜索的过程中系统地改变当前解的邻域结构，以降低陷入局部最优的风险，经过多次迭代，最终达到收敛的目的。两种算法在81个基准数据集上的测试结果表明了它的有效性，TS算法在23个算例上达到了最优下界，并优化了51个算例的最优上界；IVNS算法在28个算例上达到了最优下界，并优化了55个算例的最优上界。(本文来源于《天津大学》期刊2014-05-01）
孙锡梅[9]（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问题。(本文来源于《天津大学》期刊2014-05-01）
刘洁,何彦锋[10]（2013）在《城市垃圾收集车辆弧路径问题研究》一文中研究指出考虑部分街道单行及转向限制等状况,采用带有转向禁忌条件的垃圾收集车辆弧路径问题模型对城市垃圾收运路线进行优化.通过建立将其转换为对应的点路径问题的求解模型以减少问题规模,并利用一种聚类蚁群算法对该问题进行求解.实例优化结果表明,有、无转向约束的路线优化后,总路程分别减少了89 984.96 m和92 330.04 m,分别节约了31.1%和31.9%.优化效果明显.此外,优化后减少了需求车辆数,减少了车辆使用成本和人员雇佣成本.(本文来源于《成都大学学报(自然科学版)》期刊2013年04期）
弧路径问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
周期性带容量限制的弧路径问题已成为现实生活中路径优化方面很普遍的问题,因此,研究该问题具有很重要的意义。文章研究的主要内容是多周期带容量限制的弧路径优化模型,以洒水车服务道路为例,将车场和路线的组成看作无向网络,在相关假设前提下,考虑道路需求次数,车辆容量,车辆最长服务时间,周期时长等约束条件,建立了以所有周期所有车辆的服务总时间最短为目标的优化模型。最后运用LINGO软件对实例进行了计算,验证了模型的正确性和有效性,并对计算结果进行了分析。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
弧路径问题论文参考文献
[1].李坤阳.多次需求的特殊路段限容量弧路径问题研究[J].山东工业技术.2019
[2].李金萍,杨信丰,赵平平,卢军莉.周期性带容量限制的弧路径问题模型研究[J].物流科技.2018
[3].要婷婷.基于模因演化算法的有限容量弧路径问题研究[D].北京交通大学.2016
[4].王娟.针对非确定和大规模限容量弧路径问题的近似算法[D].中国科学技术大学.2016
[5].林丹,梁桉洋.多起始点进化算法在容量约束弧路径问题上的应用[J].天津理工大学学报.2015
[6].梁桉洋.需求可分割的容量限制弧路径问题的启发式算法研究[D].天津大学.2015
[7].彭锦环,马慧民.带容量约束的弧路径问题:文献综述[J].物流科技.2015
[8].黄庆伟.带容量约束的开放式弧路径问题的算法研究[D].天津大学.2014
[9].孙锡梅.同时配送和回收需求的容量约束弧路径问题[D].天津大学.2014
[10].刘洁,何彦锋.城市垃圾收集车辆弧路径问题研究[J].成都大学学报(自然科学版).2013