论文带容量约束弧路径问题文献综述是关于本文可作为文献综述方面的大学硕士与本科毕业论文文献综述范文模板论文开题报告范文和职称论文论文写作参考文献下载。
摘 要：参考关于弧路径问题（ARP）的文献,可以将弧路径问题分为三类,中国邮路问题、乡村邮路问题和带容量约束的弧路径问题,文章对带容量约束的弧路径问题（CARP）作出综述,通过对CARP问题的了解来阐述目前带容量约束的弧路径问题的研究热点,以及目前CARP的主要应用领域.对CARP问题的综述重点是CARP问题的分类以及CARP问题的计算方法,通过对前人成果的总结能更加明确地理解带容量约束的弧路径问题.
关键词：弧路径；CARP；算法；应用领域
中图分类号：F506 文献标识码：A
0 引 言
弧路径问题（Arc Routing Problem）是指在一给定的连通图中,其中若干边需要某种服务,有一个车队以网络中的某个特殊点作为车场,车队中的所有车辆假定是同一车型的,由该车队中的每辆车提供相关服务.每条边均必须由一辆车提供服务,且服务需要一次完成,所有边均允许被经过任意多次,每辆车从车场出发并且在服务完成后再回到车场[1].弧路径问题最早可以追溯到1936年欧拉的七孔桥问题,而国内经典的弧路径问题是管梅谷教授（1962）提出的中国邮路问题,其要求邮递员至少对无向图的各边遍历一次,求其最小成本.弧路径问题大致可以分为三类：中国邮路问题,乡村邮路问题,带容量约束的弧路径问题.
中国邮路问题（Chinese Postman Problem）最早是由管梅谷教授提出,该问题可以表示如下：在一无向连通图中,车辆从某一点出发,至少遍历图中所有边一次,并且最后回到出发点.乡村邮路问题（Rural Postman Problem）是在中国邮路问题的基础上衍化出来的,其不要求车辆对所有边进行遍历,只需车辆对路径中某些需要服务的边进行服务并求得最小成本.
带容量约束条件的弧路径问题（CARP）是指在一无向连通图中,给定一组有着固定容量限制的车辆,对图中非负需求边遍历,确定一条路径,在该路径上所有需求边的需求量不能超过装载车的容量,并且每辆车从车场出发再回到车场.带容量约束条件的弧路径问题应用领域有城市垃圾回收、冬季道路除雪、道路洒水、街道清扫、输电线路检测等方面.CARP是个NP-hard问题,它最早由Golden（1981）提出,并且目前大量文献是基于该问题的研究.孙锡梅,林丹[2]研究的是同时配送和回收需求的带容量约束的弧路径问题,它不同于传统的只负责配送的CARP问题,每条需求边都有配送需求和回收需求,在配送过程中同时还要从顾客处回收需求,典型示例是快递员在派发邮件时也可以从客户那搜集邮件.
弧路径问题的三种分类的主要区别是中国邮路问题和乡村邮路问题都不是NP-hard问题,运用最多的解决方法是构造型算法和精确算法,而带容量约束条件的弧路径问题则三种算法都可以运用,并且越来越多的研究集中在对标准ARP问题的扩展,增加多种约束条件,使研究更有价值.
1 CARP的分类
由于带容量约束条件的弧路径问题有着广泛的应用领域,为了使其更加和实际状况接轨,很多研究者在该问题的基础上加上限制条件,如周期性的CARP,来进行相关研究,现可以将带容量约束条件的弧路径问题分为以下几类.
1.1 基于服务时间成本的CARP.该问题描述的是车辆在进行服务时,其服务成本和每个需求弧相关,并且服务成本是随时间变化的分段线性函数,即车辆路径成本随着时间而呈现动态变化,该问题的研究目标是根据具体情况选择合适的时间段进行服务来使总的服务成本最小.Tagmouti, Gendreau[3]将弧路径问题转化为点路径问题,并且结合分支定界算法来解决基于时间约束的弧路径问题.Tagmouti, Gendreau[4]在2007年的基础上,未将弧路径问题转化为点路径,直接用变领域搜索下降算法VND（Variable Neighborhood Descent Heuristic）来求解弧路径问题,并且他们在2011年的研究中,考虑了信息的变化性来更新路径选择,将以往的静态研究转化为更加贴近实际的动态研究.
根据以上文献可知,对于基于服务时间成本的CARP,其研究价值主要在于可以对车辆的出行时间进行规定,如果司机只根据自己的经验而不遵守科学的行车路线以及行车时间,他将会遭受很大损失.
1.2 周期性的CARP.周期性的CARP是指在某一段时间区域内,将一些服务区域根据不同的服务需求进行分层划分,对于这些层次结构确定一个服务时间段,隔几天服务一次,主要适用于那些需求不规律的街道,该问题的研究目标是确定路径来满足边需求并且不超过车容量限制.Monroy, Amaya[5]将该问题划分为两种情况,一种是每次的服务时间和服务量都是固定的,另一种是服务时间和服务量由上一次服务决定,而作者研究的是后者,即服务需求是不规则不固定的.对于服务需求不规则的周期性CARP而言,其主要应用于村镇垃圾回收、电路检查以及冬季扫雪等不需每天进行服务的事件.
1.3 多车场的CARP.多车场的CARP是指服务区域内有多个车场,车辆可以从这些车场出发,该问题可以分为两类：一类是封闭式车场,即从某个车场出发的车辆要回到该车场；一类是开放式车场,车辆从某个车场出发后可以回到任意一个车场.Fung, Liu[6]研究的是开放式车场的CARP,它不要求路径形成回路,并且限定了车辆的容量和行驶距离,在不超过这些限制的前提下使得研究成本最小.目前在该问题研究上,有一部分研究是将OCARP转化成OVRP问题来解决,但作者认为该种做法忽视了车辆行驶过程中的固定成本而只考虑了其变动成本,并且这种转换将会使问题变得更加复杂.
1.4 有补给点的CARP.有补给点的CARP是指在整个服务过程中,一辆车对道路进行服务,另一辆车则对该服务车进行原料补充,使得服务车不用再回到车场添加原料.Amaya, Langevin[7]有两种车型,一种车对街道进行喷漆,另一辆车对该服务车进行补给.作者认为有补给点的CARP可以转化为LARP（Location-ARP）来求解,原因是在求解过程中要确定再补给点的位置,所以涉及到选址问题.Salazar-Aguliar, Langevin, & Laporte[8]在前文研究的基础上增添了服务车是异质车的限制条件,并且相比前文增加了三种再补充策略,使用路径平衡标准来使服务车和补给车的路径同步.
总结:这篇文献综述论文范文为免费优秀学术论文范文,可用于相关写作参考。
参考文献：
1、 国内公民网络参和文献综述 摘 要：本文在梳理国内有关公民网络参与文献的基础上，从概念界定、理论研究领域、实证研究领域三方面对公民网络参与进行总结与探讨。从现有研究成果中发。
2、 股票市场操纵国内外文献综述 【摘 要】 股票市场操纵行为主要有：利用虚假信息的操纵；进行真实交易的操纵，如连续或联合买卖类型的操縱等；通过交易影响特定时段证券价格的操纵；通。
3、 全球治理文献综述 摘 要 20世纪90年代至今国内外学者围绕全球治理进行了深入的研究，从全球治理的源起，治理主体延伸到全球治理途径。目前学界对于全球治理理念的来源。
4、 政府采购绩效评估文献综述 摘 要：随着我国政府采购规模的不断扩大，政府采购绩效的评估逐渐成为研究热点。完善的政府采购制度能够有效节省政府财政支出、强化预算约束力、提高财政。
5、 战略柔性文献综述 一、引言现代企业所处的环境与以前相比有很大的不同，环境的不确定性更大，要求企业的应变能力也越强。当今科技、经济迅速发展的现状下，企业之间的竞争。