带容量约束的弧路径问题的综述分析.docx

带容量约束的弧路径问题的综述分析 弧路径问题（Arc Routing Problem）是指在一给定的连通图中，其中若干边需要某种服务，有一个车队以网络中的某个特殊点作为车场，车队中的所有车辆假定是同一车型的，由该车队中的每辆车提供相关服务。每条边均必须由一辆车提供服务，且服务需要一次完成，所有边均允许被经过任意多次，每辆车从车场出发并且在服务完成后再回到车场。弧路径问题最早可以追溯到1936年欧拉的七孔桥问题，而国内经典的弧路径问题是管梅谷教授（1962）提出的中国邮路问题，其要求邮递员至少对无向图的各边遍历一次，求其最小成本。弧路径问题大致可以分为三类：中国邮路问题，乡村邮路问题，带容量约束的弧路径问题。 中国邮路问题（Chinese Postman Problem）最早是由管梅谷教授提出，该问题可以表示如下：在一无向连通图中，车辆从某一点出发，至少遍历图中所有边一次，并且最后回到出发点。乡村邮路问题（Rural Postman Problem）是在中国邮路问题的基础上衍化出来的，其不要求车辆对所有边进行遍历，只需车辆对路径中某些需要服务的边进行服务并求得最小成本。 带容量约束条件的弧路径问题（CARP）是指在一无向连通图中，给定一组有着固定容量限制的车辆，对图中非负需求边遍历，确定一条路径，在该路径上所有需求边的需求量不能超过装载车的容量，并且每辆车从车场出发再回到车场。带容量约束条件的弧路径问题应用领域有城市垃圾回收、冬季道路除雪、道路洒水、街道清扫、输电线路检测等方面。CARP是个NP-hard问题，它最早由Golden（1981）提出，并且目前大量文献是基于该问题的研究。孙锡梅，林丹研究的是同时配送和回收需求的带容量约束的弧路径问题，它不同于传统的只负责配送的CARP问题，每条需求边都有配送需求和回收需求，在配送过程中同时还要从顾客处回收需求，典型示例是快递员在派发邮件时也可以从客户那搜集邮件。 弧路径问题的三种分类的主要区别是中国邮路问题和乡村邮路问题都不是NP-hard问题，运用最多的解决方法是构造型算法和精确算法，而带容量约束条件的弧路径问题则三种算法都可以运用，并且越来越多的研究集中在对标准ARP问题的扩展，增加多种约束条件，使研究更有价值。 1 CARP的分类 由于带容量约束条件的弧路径问题有着广泛的应用领域，为了使其更加与实际状况接轨，很多研究者在该问题的基础上加上限制条件，如周期性的CARP，来进行相关研究，现可以将带容量约束条件的弧路径问题分为以下几类。 1.1 基于服务时间成本的CARP。该问题描述的是车辆在进行服务时，其服务成本与每个需求弧相关，并且服务成本是随时间变化的分段线性函数，即车辆路径成本随着时间而呈现动态变化，该问题的研究目标是根据具体情况选择合适的时间段进行服务来使总的服务成本最小。Tagmouti， Gendreau将弧路径问题转化为点路径问题，并且结合分支定界算法来解决基于时间约束的弧路径问题。Tagmouti， Gendreau在2007年的基础上，未将弧路径问题转化为点路径，直接用变领域搜索下降算法VND（Variable Neighborhood Descent Heuristic）来求解弧路径问题，并且他们在2011年的研究中，考虑了信息的变化性来更新路径选择，将以往的静态研究转化为更加贴近实际的动态研究。 根据以上文献可知，对于基于服务时间成本的CARP，其研究价值主要在于可以对车辆的出行时间进行规定，如果司机只根据自己的经验而不遵守科学的行车路线以及行车时间，他将会遭受很大损失。 1.2 周期性的CARP。周期性的CARP是指在某一段时间区域内，将一些服务区域根据不同的服务需求进行分层划分，对于这些层次结构确定一个服务时间段，隔几天服务一次，主要适用于那些需求不规律的街道，该问题的研究目标是确定路径来满足边需求并且不超过车容量限制。Monroy， Amaya将该问题划分为两种情况，一种是每次的服务时间和服务量都是固定的，另一种是服务时间和服务量由上一次服务决定，而作者研究的是后者，即服务需求是不规则不固定的。对于服务需求不规则的周期性CARP而言，其主要应用于村镇垃圾回收、电路检查以及冬季扫雪等不需每天进行服务的事件。 1.3 多车场的CARP。多车场的CARP是指服务区域内有多个车场，车辆可以从这些车场出发，该问题可以分为两类：一类是封闭式车场，即从某个车场出发的车辆要回到该车场；一类是开放式车场，车辆从某个车场出发后可以回到任意一个车场。Fung， Liu研究的是开放式车场的CARP，它不要求路径形成回路，并且限定了车辆的容量与行驶距离，在不超过这些限制的前提下使得研究成本最小。目前在该问题研究上，有一部分研究是将OCARP转化成OVRP问题来解决，但作者认为该种做法忽视了车辆行驶过程中的固定成本而只考虑了其变动成本，并且这种转换将会使问题变得更加复杂。 1.4 有补给点的CARP。有补给点的CARP是指在整个服务过程中，一辆车对道路进行服务，另一辆车则对该服务车进行原料补充，使得服务车不用再回到车场添加原料。Amaya， Langevin有两种车型，一种车对街道进行喷漆，另一辆车对该服务车进行补给。作者认为有补给点的CARP可以转化为LARP（Location-ARP）来求解，原因是在求解过程中要确定再补给点的位置，所以涉及到选址问题。Salazar-Aguliar， Langevin， Laporte在前文研究的基础上增添了服务车是异质车的限制条件，并且相比前文增加了三种再补充策略，使用路径平衡标准来使服务车和补给车的路径同步。 1.5 以利润为目标的CARP。以利润为目标的CARP是指将利润最大化作为目标函数，在大多数的带容量约束限制的弧路径中，其目标函数都是成本最小化，而本段讨论的以利润最大化为目标的CARP考虑的是在车辆为满载时如何选择服务边来使利润最大化。Archetti， Feillet， Speranza研究的是在一系列有利润的边集中，每条边都有特定的需求和利润单位，一条边上的利润最多由一辆车收集，车辆可以对几条边进行服务，但达到了最大时间限制后要回到车场，研究的目标是找寻一组满足车容量限制并且使利润最大化的路径。Zachariadis， Kiranoudis是一个多目标决策问题，一个是解决利润最大化问题，另一个是使旅行时间最短，车辆只对途中某些边进行遍历，该研究相比于前一个来 说，增加了一个使旅行时间变短的约束条件，考虑到了当两条路径的利润相当时，可以选择旅行时间短的作为最优路径，因此该限制条件有着很好的实际价值。 1.6 带时间窗的CARP。带时间窗的CARP是指对于某些路径只能在规定的某个时间段进行服务，早于时间段的开始时间或者晚于时间段的开始时间将会有惩罚成本，并且只能在该时间段内服务。这个问题可以分为两大块，一个是硬时间窗问题，另一个是软时间窗问题。它与基于服务时间成本的CARP的不同之处在于后者的服务成本是一个分段函数。Vansteen wegen， Souffriau将街道拍照工作转化为具有软时间窗的车辆路径问题，同时将弧路径问题转化为点路径问题来求解，并且用ILS（Interated Local Search）来弱化时间窗的波动，在整体上先用两阶段算法进行求解，再用局部搜索算法使拍照时间缩短。 总结可以得出，对于纯粹的CARP问题并不能够很好地与现实社会接轨，因此大部分研究就集中在它的扩展问题上，这样可以从不同角度来研究弧路径问题。而且通过分类对比发现，目前研究的热点是有服务时间限制的CARP，并且国外研究对于各个角度的扩展问题都有涉猎，但国内研究少有对CARP扩展问题的研究，大部分集中在对研究方法的改进上。 2 CARP的计算方法 CARP的计算方法有很多，有些算法可以得出确定的值，但有些算法只是对解的逼近，具有更强的适应性，大致可以分为三类：构造型算法，精确算法，元启发式算法。 2.1 构造型启发式算法。路径扫描算法。路径扫描算法（path-scanning）基本思想是首先构建一条空回路，然后依据给定的规则将所有任务逐个插入到回路末尾。Fabio， Paulo， Luiz一文中先建立整数规划模型，再利用路径扫描算法来求解，并且作者在该算法的基础上加入了椭圆规则和响应性参数β来根据实际情况选择最近的路减少行驶费用。 先分区域，再排路径。Monroy， Amaya运用Benavent提供的方法对种子弧进行区域划分，当弧V满足路径要求时，将其从弧集中调入区域集V中，并使从弧到种子弧的路径最短化；在进行第二步路径的划分时作者用混合整数规划来解决路径的移动，在整数规划过程中，对重要路径赋予更大的权重。 先排路径，后分区域。首先在所有服务边中求出单一的最佳路径，再根据车容量限制分割成若干个单独的区域。刘天堂、江志斌运用RFCS思想先构建一个大巡回，然后分割成车辆路线。在构建大的巡回时运用改进的路径扫描算法（MPS），MPS按照5个规则形成5个巡回，他们被路线分割程序分成5个不同的HFF-CARP解，成本最小的解被留下。 分支定价算法。该种方法大部分运用于解决基于服务时间成本的CARP问题，是指在运用列生成技术时，将路径拟化成列进行划分，随后对该部分列定价，直到再也找不到任何有效的列并且最好的定价为止。Christiansen，Lysgaard， Wohlk解决的是40辆车69条路径的问题，在定价过程中，不考虑两条边是连续的问题，而是研究两条边非连续情况。文中加入了失误成本概念，即当边的需求量大于车的装载量时要考虑失误成本，该文考虑弧的方向问题就是为了更好地计算失误成本，并将定价问题转化为最短路径问题。在分支过程中，设定方向相反的弧具有不同的需求量，赋一个初值来将这两条弧分成两枝，这个过程类似于分支定界法。 定下限算法。以前的定下限主要是通过割平面算法来规范其下限，而当今学术界则将研究重点转向从组合优化中寻找组合下限，大多数下限的构建是基于多种匹配方式。Wohlk主要是运用一种新的定下界方法多切割点复制性低下界算法MCNDLB（Multiple Cuts Node Duplication Lower Bound）与NDLB， LB2进行对比，证明其计算效果更优，但该算法比较复杂，适合解决大规模路径问题。 从上述文献我们可以总结得出同一种算法可以用在不同的问题中，但它在不同的问题中会根据相应的进行变形来更好地解决该问题。而且通过阅读文献发现，最近3年内构造型算法的研究热潮回归，很多国外学者对该种算法的改进进行了相关研究。 2.2 精确算法。割平面算法。Belenguer， Benavent运用割平面算法来求解CARP问题，其数据样本来源于Benavent，Golden和Kiuchi，将计算结果与这些论文中的相比，具有一定的优越性。Amaya， Langevin先建立了整数规划模型，再利用整数规划割平面算法来测试模型的有效性，并且能够有效地缩短计算时间。 分支定界算法。Tagmouti， Gendreau先将弧路径问题转化为点路径问题，建立了一个数学模型，并用列生成方案来解决点路径问题。在进行计算机仿真的时候使用的数据也是从点路径问题中获取的，但将弧路径问题转化为点路径问题面临的缺陷是当弧数目较多时，转化为点路径后其计算量明显增大。通过上述文献的综述，可以得出结论：精确型算法对于小规模问题的求解具有较好的效果，并且它不是目前学术界的研究热点。 2.3 现代启发式算法。局部搜索算法。局部搜索算法可以分为变领域搜索算法（VNS），变领域下降搜索算法（VND）和自适应大邻域搜索算法。刘天堂，江志斌运用居于搜索算法和加强的局域搜索算法来改善两阶段算法，并且证明了后者优化解的效果更明显。Zachariadis， Kiranoudis将局部搜索算法于拓扑搜索算法相结合来选择邻域结构。Black， Eglese， Wohlk先用VNS求解模型，再用LANTIME求解，将两者结果对比得知后者更优。Tagmouti， Gendreau在研究过程中利用VND将邻域进行弧移动，弧交叉和弧切除变换。王立斌，林丹通过自适应局部搜索算法，并创新性地配以改进型和条件性局域搜索机制，使自适应局部搜索更有效。金倩倩，林丹通过六种邻域结构变动，扩大了变领域搜索算法的解的范围，使计算免于陷入局部最优。 遗传算法。徐凯，朱征宇先具体描述了混合遗传算法的特征及计算方法，再引出该文要具体展示的分层遗传算法，进行对比得知分层遗传算法能更好地解决单行道、爬坡问题。刘天堂，刘志斌在遗传算法中嵌入加强的局域搜索算子来强化搜索，充分发挥遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力。 蚁群算法。Santos， Rodrigues先用构造型算法产生初始种群，再使每只 蚂蚁都会产生一条路径，该路径要遍历图中所有的弧。由于不是每条路径都是可行的，文章中就利用Ulusoy算法来寻求可行路径，随后通过局域搜索算法对可达路径进行改进，只保留最优解，最后得出的就是最短路径。 在对现代启发式算法相关文献的分析中，可以发现大多数解的求取并不只是依靠某一种算法就能够实现的，大多数的研究中总是会将几种算法混合在一起进行求解。在最近的研究中，在对解进行优化的时候多数用到的是局域搜索算法，而国内对于算法的研究主要集中在遗传算法的设计上以及一些改进，国外的相关研究重心是在局域搜索算法上。但目前国内研究中也在相关方面有了相关研究，有些研究成果也运用了局域搜索算法来优化解的质量。 3 CARP的应用领域 道路洒水。洒水车在对道路进行洒水时，在单行道上可以对道路两边洒水，而在双行道上只能对特定的一边进行服务，并且洒水车的容量有限，这就可以转化为带容量约束的弧路径问题，在大多数的实际工作中，对于道路洒水问题，还要考虑上下坡问题。朱征宇，刘建辉解决的是多车场洒水车路径问题，描述的是在现实社会中洒水车车内水量用光之后可以到多个加水点进行补水，可以转化为多车场的弧路径问题。 冬季道路除雪。在冬季，道路结冰以及积雪会给交通带来极大的不便，这时就会用融雪剂或者道路撒盐方式对道路进行除冰除雪工作。刘敏研究的是融雪剂撒布车辆的路径规划问题，他从路网特性、路段特性、作业区划分以及车辆路径特性等方面分析了融雪剂撒布车辆路径规划的影响因素，并且将道路除雪过程中的车辆分类。 城市垃圾回收。城市垃圾回收是指在回收城市小区内的垃圾时，车辆从车场出发，对街道边上的垃圾进行收集并且只能对该街道服务一次。Afsar在对城市垃圾回收的过程中加入了时间窗的限制，并说明若垃圾回收车在时间窗的结束时间点后进行服务，则服务时间和服务费用都将会增加，而且在垃圾回收过程中只能在时间窗的开始时间后进行服务。 路标喷漆。路标喷漆是指车辆对街道中的某些路标进行重新喷漆和粉刷。Amaya， Langevin解决的是两种车型的问题，服务车有着固定的容量并且对路段中的某些路径进行服务，而补给车辆能够在任何时候任何地点对服务车进行原料再补给使得服务车能够再服务而不用回到车场，从上述描述可知，作者对于补给车辆的限制有些理想化，实际情况比这要复杂。Salazar-Aguliar， Langevin， Laporte相比较前文来说，并没有限制补给车能够随时给服务车进行补给，而是要同时考虑两种车的最短路径问题来使总成本最小。 工厂应用。工厂应用是指某些研究人员将带容量约束的弧路径问题运用到工厂或者企业，比如厂房内机器人的路线设计等一些应用。Sipahioglu， Kirlik文中工厂机器人要对工作场所中某些位置至少遍历一次，作者用GVD（Generalized Voronoi Diagram）来模拟机器人工作的环境，并在前人的基础上加入了机器人的能源限制条件，将题转化为CARP问题来求解。 道路监管。道路监管是指在一些特殊时间段，如周末或者道路维修时，如何合理地安排车辆来使总成本最小。Shan-Huen Huang， Pei-Chun Lin考虑的是在实际生活中经常面临的问题，即在对道路进行整修时，该工程的持续会一定程度上影响居民生活。作者为了很好地解决该问题，将需要整修的路段划成几个区域，装载砂石和泥土的车辆等同于CARP中的车辆，并在问题的描述中加入了时间窗的限制，可以保证在特殊时间段车辆以及其他设备不会对居民生活造成困恼。 4 总 结 本文通过阅读国内外关于带容量约束的弧路径问题的文献，对文献进行梳理，对CARP问题进行分类，并且对使用的计算方法也进行了总结。 对比国内外研究成果，我们发现目前中国的带容量约束的弧路径问题研究目标比较单一，主要是对不同车场、不同车型的研究；而对于计算方法而言，主要是遗传算法以及在遗传算法上的改进。而国外的研究方向非常广泛，上述研究方向都有涉及，并且这些研究方向有着很重要的实际意义。而计算方法近几年也是集中在元启发式算法上。但这些研究也存在着一些问题，就是虽然对研究方向做了一些限定，但现实世界比建立的模型更复杂，弧路径问题的研究相比于车辆路径来说还很不成熟。综合来说，现在的研究趋势是将弧路径问题丰富化加入一些限制条件使其与实际更贴切，在算法上会将几种算法交叉起来运用来优化解，以后的研究会更加侧重在