农村有奖邮递员问题的禁忌搜索算法助力

可在www.sciencedirect.com在线获取理论计算机科学电子笔记281（2011）85-100www.elsevier.com/locate/entcs基于禁忌搜索的农村邮递员有奖问题求解Guillermo Palma1DepartamentodeComputaci'onyTecnolog'ıadelaInformaci'onUniversidadSimonBol'ıvar委内瑞拉加拉加斯摘要提出了一种基于禁忌搜索的启发式算法，用于求解农村有奖邮递员问题。这个问题是最近定义的，是其他弧路由问题的推广。一系列不同类型实例的数值实验结果表明，与以往的工作相比，所提出的算法具有良好的性能关键词：圆弧布线，超启发式，禁忌搜索，组合优化。1引言由Ar'aoz，Férna'ndez和Zolt'an[6]提出的获奖路由问题（PARP ）是Arc 路由问题（ARP）的推广弧路由问题的目的是找到从图的一些边或弧遍历的最大收益，受到一定的限制。主要弧路径问题是中国邮递员问题（CPP）和农村邮递员问题（RPP）。[ 14 ]这本书由Dror编辑[14]是关于ARP的主要参考。PARP是关于一个图定义的，其中有一个顶点d称为存款。每个边都有一个利润函数和一个成本函数。只有当第一次遍历边时，才考虑利润函数。P ARP的目标是找到一个通过d的最大利润周期。Ar'aoz等[6]表明PARP是NP-难的，是许多弧路由问题和旅行商问题的推广最基本的PARP是农村有奖邮递员问题。其他PARP通过添加约束来定义PRPP是在无向图中找到通过矿床的最大利润周期。在PRPP处，需求服务在图的边缘上1电子邮件：gpalma@ldc.usb.ve1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.02786G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85当向边缘提供服务时，不仅会产生成本，还会获得利润。代价是穿越边缘。利润来自于为边缘提供的服务。 在一个循环中，考虑到遍历相同的所有边缘的成本。 一条边可能被遍历多次。只有在第一次穿越某条路线的边缘时，才能获得奖励。PRPP的目标是找到一条从矿床开始并结束的路线。PRPP的目标是找到一条以矿床为起点和终点的路线，从而最大限度地提高服务边缘的总利润，减少穿越边缘的成本图1显示了一个图的例子，它是PRPP的一个实例。的 图2示出了作为图1的问题的最优解的循环。图1. PRPP实例。 顶点d是存款，ce/be是边e图2.图1的最优解。循环是d-1 - 4 -3-2-1-d，利润等于14Ar'aoz、Fern'andez和Meza[5]提出了PRPP的第一个租赁解决方案他们的算法有两个阶段，在每个阶段使用不同的求解器。第一阶段通过线性不等式系统以及启发式算法给出PRPP的近似解。 启发式是RPP的启发式3T的改编[16]。第二阶段使用第一个解决方案来获得问题的最佳解决方案。除了PRPP，还有四个问题属于PARP家族。第一个是加权PARP（WPARP）[9]，其中每个边的服务都有一个权重，并且总权重有一个限制 当它被服务时，它可以有一个路由。一个解决方案可以有多个路由。第二个问题是有奖励的弧路由问题（CPARP）[3]。CPARP的目标是找到一个通过d的循环，使得满足边缘集群的子集的需求。Franquesa [17]对C PARP及其求解算法进行了全面的研究。最近，Ar′aoz，Fern′andez和Franquesa [3]提出了一种基于线性规划的精确算法G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）8587并提出了求解CPARP的启发式算法。PARP家族的第三个问题是有风的奖励收集弧路由问题（WCPARP）。这个问题具有CARP的所有特征。不同之处在于，遍历一条弧的代价取决于遍历它的方向，Franquesa [17]研究了这一问题的特点，提出了一种精确的算法来求解。Ar'aoz等人[4]提出了一种基于分支切割的精确算法来求解WCPARP，并提出了一种简单的启发式算法来获得可行解。第四个也是最后一个问题，PARP家族的成员是有能力的农村邮递员（PCRPP）。PCRPP于2009年为Stefan Irnich引入[24]对于PCRPP，应用与PRPP相同的定义。此外，当第一次遍历边缘时消耗时间qe，并且其他时间消耗时间Re。PCRPP的目标是找到一个利润最大的周期，使得周期的时间小于或等于Q。除了对PRPP及其相关问题的研究外，我还了解了六个带利润的弧路由问题的Deitch和Ladany [13]有兴趣为旅游地区确定一条有吸引力的运输路线。Feillet，Deborah和Gendreau [15]引入了一个新的问题，称为盈利弧巡回问题（PATP）。PATP的目标是找到一组周期在图中，最大化利润减去路线成本，限制利润在边缘的次数和循环的最大长度。Malandraki和Daskin [25]介绍了最大利益中国邮递员问题（MBCPP）和最大利益旅行推销员问题（MBTSP）。MBCPP类似于PRPP，一个区别是MBCPP是用有向图定义的，每个弧都有一个利润函数ben。这个函数返回一个profit，当一个弧e被遍历了n次。MBTSP的定义是类似的，主要区别是通过通过节点获得收益。最后，Hertz等人介绍了带利润的无向电容约束弧路由问题[8] [7]（UCARPP）。UCARPP定义在一个无向图上，其中每条边都有一个与之相关的奖励，一个需求和旅行时间。一列服务于边缘的车辆。目标是找到一组满足所有约束条件的最大收益PRPP有潜在的实际应用。应用弧布线问题试图使成本最小化。它决定了服务需求恰恰是在某些地方。因为目标不是决定哪些边将被服务，而是确定遍历它们的最小成本。用农村邮递员问题可以模拟更为复杂的实际问题。一家想要实现利润最大化的公司可以决定不满足优势的需求，除非这为公司带来了利益应用这一原则的一个例子另一个例子是由私营公司管理的邮件服务。公司可以选择他们将服务的地区。由于将禁忌搜索应用于几个ARP [23，12，11，2，19，1，10，8，7]所获得的成功，因此选择该元启发式作为PRPP算法解决方案的基础本文的组织结构如下。第2节正式描述了PRPP88G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85以及它的一些特性第3节介绍了为求解PRPP而开发的算法实验结果和讨论在第4节中完成。第5节介绍了工作的结论第二章农村有奖邮递员问题在本节中，我正式定义了PRPP，并提出了一些在这项工作中使用的符号和定义定义2.1设G（V，E）是一个无向图，具有一个可分辨的d，称为deposit，在R +中的边集E上有两个函数，利润函数b和成本函数c。问题的目标是找到一个循环C，使e∈E（C）（be−tece）（1）其中C是G中通过d的圈，d不一定是简单的，e是边e在C中遍历的次数，E（C）是循环C的边集。使用以下符号和其他定义。V（H）：子图H的顶点集。 如果H=G，则V（G）=V。E（H）：子图H的边顶点。如果H=G，则E（G）=E。γ（S）：设S是一个集合，使得S ∈S∈V 我们记为γ（S）={e∈E|e ={u，v}，u，v∈S}是两个顶点都在S中的边集。δ（S）：设S是一个集合，使得S ∈S∈V 我们记δ（S）={e∈E|e ={u，v}，u∈S，v∈V\S}=δ（V\S）S和V\S之间的割中的边。对于单例集，我不使用方括号。 例如，以下表达式是有效的δ（v）<$δ（{v}）和γ（v）<$γ（{v}）。在图G的边e上定义下列函数：•e=be−ce。当你第一次穿越一条边时，你得到的利润就是•e=be− 2ce。 当一条边被遍历两次时，你得到的利润就是利润。边集分为三个集P ={e∈E|，则γR（Vk）的所有边都在C <$。注2.3优势2意味着对于每个连通分支Ck，我们有γR（Vk）中的边，或者所有边都在最优解Ck中，或者没有其中，C？优势2还意味着，如果存在一条不在集合R中的边，在圈C中，并且与任何顶点Vk关联，则所有的边都在C中。预处理1设Ck是GR的连通分支，对k，e ∈ γ（Vk）\R. 然后我们有边e在最优解C中至多被遍历一次，注2.4优势2和预处理1意味着如果边e∈γ（Vk）\R在C中，则所有的边γR（Vk）都在C中3PRPP的求解算法我开发了一个基于禁忌搜索的算法来解决PRPP。该算法分为两个阶段。在第一阶段中，通过两个构造性算法生成两个可行的PRPP解。这些算法被称为连通分量的联合和连通分量的连续消除。第二阶段是禁忌搜索算法的应用，试图改善初始解。算法1连接组件的并集基于两个算法。这些是Pearn和Wang提出的最大收益中国邮递员问题的算法[26]和Frederickson提出的RPP的近似算法[18]。该算法为PRPP构造一个可行解，该可行解具有除输入列表的边之外的图的所有边。 这个想法 禁忌搜索的一个重要特点是创建一个初始可行解，其中包含第一次遍历时产生利润的边 。 禁 忌 搜 索 的 思 想 是 创 建 一 个 初 始 可 行 的 解 决 方 案 ， 其 中 包 含 第 一 次transaversed时提供利润的边，这些边是 需要设置RQ的边。Ar'aoz等[6]证明了边e∈R∈Q不一定是PRPP最优解的一部分然而，它被认为是最好的策略，因为在解决方案中包括这些边缘而失去利润，而不是因为不包括它们而失去利润的一个原因90G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85使用该技术是因为利用禁忌搜索算法可以确定是否消除了循环的边缘，即可行的解决方案，获得了具有更大益处的循环。使用这种技术的一个原因是因为禁忌搜索算法可以确定是否消除了循环的边缘，即可行的解决方案，获得了更大收益的循环在禁忌搜索中，算法1连接组件的并集为PRPP提供了一个可行的解决方案，该解决方案包含提供收益的所有边，这是R和Q类型的边。算法3连续消除连通分量有一个策略，可以排除R和Q类型的边缘，这些边缘不会为PRPP的解决方案提供好处。设Gt=（Vt，Et）是算法1连通分支并的步骤2。然后在算法1的步骤3中得到图Gt的最小生成树，其中边集为Est。 与这一套 图Gmst=（Vt，Est）对应于树。每个顶点vi∈Vt对应于一个连通分支Ci。Est的每条边对应于连接的组件之间的最小成本路径。C0是包含沉积物的连通分支从连通分支C0中的顶点v0∈Vt开始，用搜索算法遍历图Gmst.当访问每个顶点viinVt时，可以获得到达顶点vi的成本cvi和连通分量Ci.也可以计算从连通分量Ci获得的最大收益，这是<$（γ（Ci））。如果连通分量的最大收益小于成本，则该分量则该分量不应是解的一部分。这是因为包含这组边可能会给PRPP的解提供损失。这是算法3连续连通消元法的基本思想。连接的组件按升序排序基于总利润减去到达分量的成本的值，使得对于解决方案来说，不强制具有连通分量Ci的边。从所有的解决方案中，我们选择最大的利润。Tabu Search由Fred Glover [20]引入，是解决组合优化问题的元算法之一Glover和Laguna[21]以及Meli'an和Glover[22]对禁忌搜索的概念和应用进行了很好的描述。TabuSearch是一种基于自适应记忆和采用智能一般原理求解问题的元启发式禁忌搜索用于引导slocal搜索，试图使用有助于避免陷入局部最优并访问先前达到的状态的内存结构来找到全局最优值。最好的想法是开始与一个可行的解决方案的PRPP在解释如何工作之前，算法将描述它们的一些结构和基本程序。首先，我们将解释它如何从PRPP的可行解生成一组相邻解。它将使用一个交换方案的边缘的路径的启发由本公司提出的Cober'an等人。混合RPP[12]。 在G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）8591算法1：连通分量的并集输入：图G=（V，E）和边集Le输出：循环C，PRPP的可行解步骤1：创建一个图Gs=（Vs，Es），其中Es=E\Le。若存款d∈/Vs，则将存款d添加到图Gs中，并将存款d视为连通分支C0.做GJ←Gs。如果GJ是欧拉（连通且偶），则转到步骤6。IfGj仅连接，执行EsJt←和go到步骤4步骤2：设C0，C1，.，Ct是G j的两个连通分支。构造一个完全图Gt=（Vt，Et），其中Vt以每个连通分支Ci为元素.每条边et∈Et的成本由函数cet给出：Et→R该函数定义为cet（et）=min{dcc（vi，vj）|vi∈Ci<$vj∈Cj<$i=/j}其中dcc是返回图G中顶点vi和vj之间的最小成本路径的值的函数。 我们调用最小成本路径，MCvivj.设MCP是一个集合，其中MCvivj。 我们使用以下函数来获得最小成本路径MCP←find-minimum-cost-path（G，GJ）第三步：计算图G t的最小生成树，得到对应于树的边集的边E st。 设ESt是通过确定图G中对应于E s t的每条边的路而得到的一个边集e ∈ E。将EsJt添加到图GJ以获得GJ=（Vs，ES<$EsJt）第四步：我们得到图GJ的奇度顶点集，称为Vo。我们构造了一个完全图Gm=（Vo，Eo），其中每条边eo=（i，j）|eo∈ Eo的成本为最小成本路径的值，叫MCij 我们有MCij是图G中顶点i，j∈Vo之间的最小费用路。设MCP是MCij的集合，我们有最小费用路是用函数MCP←寻找最小代价路径（G，GJ）步骤5：求图Gm中的最小代价完美匹配。 让Em是Gm中对应于最优匹配的边的集合让E·M·J是通过确定路径的边e∈E的集合，图G对应于E m的每一条边。E·M·J是把gGJ得到GJ=（Vs，Es<$Est<$Em）。我们有GJ是一个欧拉图（偶数和因此，它具有PRPP的可行解步骤6：欧拉循环C用算法在Dror书中提出的Eulerian循环[14]。我们有C是一个循环，它是G中PRPP的可行解步骤7：返回C92G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85功能2：寻找最小成本路径输入：图G=（V，E）和Gs=（Vs，Es）输出：最小成本路径集MCP1开始2MCP←路径//最小代价路径集3EdgeSet←//Set of edges4设MCvivj是图G中顶点vi，vj∈Vs之间的最小费用路。每条边e∈E，具有由函数cst：E→R给出的成本，该成本将取决于先前找到的路径MCvivj5对于vi，vj∈Vsdo6确定MCvivj关于CST（e）=。ce，如果e∈Es∈EdgeSet-e，否则7MCP←MCP {MCvivj}8EdgeSet←EdgeSet将MC的边定义为vivj9返回MCP函数4获得器VECINOS，我们给出了生成集合的算法，相邻的解决方案。设C是PRPP的一个可行解的一个圈，该可行解由对应于图的边被遍历的顺序的一系列边表示。 循环C 具有以下形式 C =（（d，a）（a，b），.，（i，j），.，（l，m），.，（p，q），.，（s，t），（t，d）），其中d是偏差。给定属于解C的任何边e=（l，m），从该边开始，从边e的左边和右边遍历解C。当我们遍历到解C的左边时，我们想找到一条边h，在第一次遍历时提供了好处，这是h∈RQ。如果我们没有找到边h∈R<$Q，我们取与水库相连的边，在这种情况下，在解C中，我们有h=（d，a）。假设我们在C中找到一条边h∈R<$Q，这条边记为h=（i，j）∈C。我们从边开始做同样的过程，我们从右边遍历解，直到找到一条边，或者默认情况下，找到最右边有存款的边，这是k=（t，d）∈C。一旦我们确定了解C中的这三条边h=（i，j），e=（l，m）和k=（p，q），我们找到图G中顶点j和p之间的最小成本路径，我们称之为MCPjp。 然后，我们将循环的路径替换为最小成本路径，J和P，这是MCPJP。 这将为PRPP提供新的可行解决方案V，其具有形式V =（（d，a）（a，b），.，（i，j），CCMjp，（p，q），.，（s，t），（t，d））。该过程应用于解C的所有边，从而生成PRPP的一组可行解相邻解的集合将由以下组成：元组（V，e），其中V是可行解，e=（l，m）∈C是在算法开始时选择，并且允许生成解决方案V。 函数4OBTENERVECINOS显示了获取集合的算法作为一组元组。设C是PRPP的可行解，用它可以得到相邻解集。设G=（V，E）是表示要解析的实例PRPP在获得最小成本路径G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85930，e∈R<$Q的边占优2⎪算法3：连续消除连通分量输入：图G=（V，E）输出：PRPP的循环C可行解1开始2禁忌边←P型图G的所有边3应用算法的步骤1和步骤21连接组件图G和禁忌边。 得到一个图Gt=（Vt，Et）.4ncc ←|Vt|//连接的组件数5最佳解←具有输入G和禁忌边缘如果ncc= 1，则返回最佳解。7计算图Gt的最小生成树，得到一组边Est。创建图Gmst=（Vt，Est）。8用深度优先搜索算法从顶点遍历图Gmst，该顶点对应于分量C0（包含存款d）并计算到达每个连通分量的成本cCi∈Vt。9对于每个连通分支Ci∈Vtdo[10]计算可以获得的最大利润<$（γ（Ci））。11利润Ci←（γ（Ci））−cCi12profit-connec-component<$profit-connec-component<${（Ci，prof itCi）}图13它是按照连通分量利润连接组件。14foreachtuple（Ci，prof itCi）∈profit-connec-componentdo15edges-connec-component←获取图G中的边，连通分量Ci.16tabu-edges←tabu-edges=edges-connec-component.17解←具有输入G和禁忌边缘18.如果profit（solution）>profit（best-solution），那么best-solution←solution。19返回最佳解MCPjp每个边缘具有由函数c（2）给出的成本预处理1<$TabuListc（e）=<$ce，ife∈C⎪⎩−ϕe,o t herwise(t heedgeistypeP).（二）一旦生成了相邻解的集合，我们希望得到一个将是当前最佳解的解，换句话说，是正在运行的迭代的最佳解。函数4获得者S解决方案选择一个解决方案，概率，94G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85∈算法4：PRPP的禁忌搜索所使用的函数funcobtaininNeighbors（G：A graph，CurrentSol：Sol. PRPP，BestSolution：Sol. PRPP，TabuList：边缘集）−→邻居：溶胶集。PRPP开始foreachedgeeCurrentSoldo设e=（l，m）是边缘，并且循环CurrentSol被表示为以以下形式遍历的边缘CurrentSol=（（d，a）（a，b），.，（i，j），.，（l，m），.，（p，q），.，（s，t），（t，d））;从边e=（l，m）向左遍历解CurrentSol以找到边（i，j）∈RQ。如果没有这样的边，那么我们取解的更极端的边，这是一个有存款的边（d，a）;从边e=（l，m）向右遍历解CurrentSol以找到边（p，q）∈R<$Q。如果没有这样的边，那么我们取解的更极端的边，这是一个具有沉积物的边（t，d）;找到顶点j和p之间的最小成本路径MCPjp;通过用CurrentSol中的最小成本路径MCPjp替换CurrentSol的路径[j，l]（l，m）[m，p]来获得PRPP的新的可行解。我们得到一个具有以下形式的解：NewSolution←（（d，a）（a，b），.，（i，j），MCPjp，（p，q），.，（s，t），（t，d））;如果e∈TabuList，则//吸引准则如果Bio（NewSolution）>profit（BestSolution），则Neighbors=Neighbors<${（NewSolution，e）};其他Neighbors=Neighbors<${（NewSolution，e）};return邻居;funcobtainSolution（Neighbors：Set of soluc. TabuList：边缘集，最佳解决方案：溶胶。 PRPP）−→C：溶液。PRPP开始（ChosenSol，e）←在Neighbors中找到具有最大利润的可行解的元组;ChosenSol←获取元组（ChosenSol，e）PRPP的解如果利润（ChosenSol）≤利润（BestSolution），则（ChosenSol，e）←选择概率方式的元组，使用轮盘赌技术，其中被认为是PRPP的解决方案的利润;ChosenSol←获取元组（ChosenSol，e）的解决方案PRPP;e←获取元组（ChosenSol，e）与PRPP解相关联的边e，e是构建解ChosenSolenobtaininNeighbors的边;TabuList←TabuList<${e};returnChosenSol;G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）8595相邻解的集合。在算法5中示出了PRPP的禁忌搜索 首先，该算法用算法1和3生成两个可行解。 由算法3连续消除连通分量生成的解是将在禁忌搜索中搜索的初始解。算法1连接组件的并集的解决方案可以稍后在禁忌搜索中使用，以防我们需要多样化搜索。在第6行中，开始算法的迭代。允许的最大迭代次数MaxIter为120。 一旦得到了相邻解的集合，就通过解的改进算法。这是三种算法。第一种方法消除了解决方案的负效益循环第二种方法消除了解的重复边第三种方法是取解的每一对边，并检查两条边上的顶点极值之间是否存在最低成本路径如果两个解具有相同的利润，则有一个称为BeneficiioMultiConjunto的多解集，它具有搜索过程中解 在第12-19行中，我们可以看到，如果一个解出现了三次，那么搜索就试图改变搜索空间，从目前为止找到的最佳解开始进行搜索，或者从算法1连通分量的并集开始进行发散。我们记得，算法1的解在第一次遍历它们时具有所有有益的边。在行20和21中，获得与PRPP的属性相关联的边缘，其被称为优势2和预处理1。关于边DOMINANCE 2的边的想法是试图促进它们包含在可行解中，因为如果一个边R属于最优解，则可能一些相邻边也属于最优解。因此，我们看到函数2中这些边的成本为0。使边P的边重新处理1的目的是试图避免必须将这些边包括在可行解中，如函数2所示。在第26-33行中，观察到如果你有多次迭代而没有找到更好的全局解，那么算法是什么第一次将在完全不同的状态空间中进行搜索，这是通过继续使用随机生成的禁忌搜索可行解来获得的 如果回到这种情况，将通过选择当前解决方案来加强搜索，解决方案算法3连续消除连接组件。4实验结果与讨论这些算法是用C实现的，可以在http：//www.ldc.usb.ve/~ gpalma.所有实验测试都在计算机SUN ULTRA 10 modelo 440上进行，该计算机具有处理器UltraSPARC-IIi de 440 MHz，1.0 GB DRAM。到目前为止，PRPP唯一可用的实例是由Ar'aoz，Ferna'ndez和Meza模拟 的实 例[5]。它们是一组118个实例，这些实例是从一组广泛使用的农村邮递员问题（RPP）的实例中生成的我们将使用96G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85算法5：PRPP的禁忌搜索输入：图G输出：PRPP的循环C可行解1开始2iterWithoutImprovement←10， MultisetProfit← 103SECCSol←使用输入G应用算法34CurrentSol← SECCSol，BestSolution← CurrentSol5UCCSol←使用输入G和类型P的边应用算法1以G6而iterMaxIter做<7Neighbors←getNeighbors（G，CurrentSol，BestSolution，TabuList）8将改进算法应用于邻域9CurrentSol←getSolution（Neighbors，TabuList，BestSolution）10PCS←利润（CurrentSol）11MultisetProfit← MultisetProfit{ PCS}12如果MultisetProfit中PCS的出现次数= 3，则13如果使用BestSolution，则14useBestSolution15CurrentSol←最佳解决方案其他16个17useBestSolution ←TRUE18CurrentSol ←UCCSol19删除MultisetProfit中出现的所有PCS20edgesDominance2←获取与CurrentSol的R类型的边相邻且不属于它的所有Q和P类型的边21条边预处理1←获取属于以下部分的所有边γ（Vk）<$δ（VkCurrentSol（预处理1）如果利润（CurrentSol）>利润（BestSolution），则23最佳解决方案←CurrentSol24iter←iter−10，iterWithoutImprovement←iterWithoutImprovement-925删除一个单位的迭代次数，应该是边缘e∈TabuListinTabuList26iter←iter+1，iterWithoutImprovement ←iterWithoutImprovement+127如果iter=iterWithoutImprovement，则28.如果RandomSol=TRUE，则29CurrentSol←得到一个随机生成的可行解30秒RandomSol ←TRUE其他31个32CurrentSol ←SECCSol33RandomSol←34MultisetProfit<$，TabuList< $35iterWithoutImprovement←iterWithoutImprovement+936return最佳解决方案G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）8597||||这些相同的实例来测试实现的算法。118个实例根据其类型和顶点数分为15类问题。表1显示了需要解决的问题的特点用禁忌搜索算法求解PRPP得到的结果与由Ar′aoz、Fern′andez和Meza[5]提出的割平面启发式算法的结果一致。两种算法的所有结果都是在同一台SUNULTRA10计算机上得到的表1总结要解决的问题的特点 R和P是R型边的个数每种类型的问题都是P型的问题实例数|V||E||R||P|AA1102515116010AB190400514411P247-5021-122513-1842-8D1691612031-322-5D36936630724-11D6496420161285-15D100910049502009-22G16916120243-5G36936630605-9G6496420161124-14G100910049501804-20R2052019037-753-4R3053043570-1114-6R4054078082-2035-9R505501225130-203 7-12由于禁忌搜索的概率元素，在求解实例时可以获得不同的解为了测试算法的鲁棒性和可靠性，对118个实例中的每一个进行了30次禁忌搜索，在表4中报告了获得的平均值和找到的最佳解的结果。当将获得的结果与启发式进行比较时，可以看到启发式的总偏差百分比（10.98）大于平均值的总偏差百分比（10.22），并且大于禁忌搜索的最佳值（2.85）。这表明，在一般情况下，禁忌搜索得到更好的解决方案比启发式[5]。如果我们观察禁忌搜索算法找到的最佳解决方案，我们必须在15种类型98G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）85的问题他过得文[5]的启发式算法在G64和G100问题中找到了比禁忌搜索更好的解。禁忌搜索算法在15类问题中的12类问题中得到了最优解，取得了令人满意的结果。禁忌搜索的计算时间在小的情况下更高，在大的问题中要低得多这是因为在Tabu搜索中生成两个初始解，这在时间上是昂贵的。然而，我们认为，禁忌搜索的计算效率是好的，如果我们看到两个算法所花费的时间总和表2在PRPP的实例中，禁忌搜索和[5]的启发式的结果其中Vo：最优值，%dHeur：启发式的百分比偏差，%dMeanTS：禁忌搜索的平均值的百分比偏差，%dBestTS：禁忌搜索找到的最佳值的百分比偏差，tHeur：tTS：禁忌搜索的平均时间ProblemaVo%dHeur% d平均值%dBestTStHeur（分段）TTS（分段）AA62660.300.080.00471.65124.60AB43720.000.030.00102.59109.40P25671.250.080.0097.13240.31D1620760.000.010.003.717.09D3651622.230.010.00210.1266.47D6488430.440.070.00509.85310.94D100116462.000.360.056714.301385.33G16200.000.000.002.742.77G361160.000.690.00249.6520.61G642800.363.920.711094.7075.80G1004781.053.932.099876.65182.19R20474020.840.000.001.552.71R30545510.000.540.0010.0314.32R40892082.230.370.0010.1834.58R50979350.280.130.0081.8363.66托塔莱斯-10.9810.222.8519436.682640.785结论在所研究的大多数问题中，PRPP的禁忌搜索算法得到了优于[5]的禁忌搜索算法中的策略这项工作的主要贡献之一是邻近的生成机制G. Palma/Electronic Notes in Theoretical Computer Science 281（2011）8599禁忌搜索中的PRPP解决方案。这是禁忌搜索性能的一个关键过程，并且非常通用，可以应用于其他具有利润和成本的弧路由问题。禁忌搜索算法的计算量适中。未来的工作之一是将禁忌搜索算法应用于其他有利润的弧路由问题，如有向有奖弧路由问题（CPARP）和无向有利润的有能力弧路由问题（UCARPP）。引用[1] Ahr，D.和G. Reinelt，A tabu search algorithm for the3403-3422.[2] Amberg，A.，W. Domschke和S. 多中心电容约束弧路由问题：一个禁忌搜索算法使用电容约束树，欧洲运筹学杂志124（2000），页。360-376[3] Ar'aoz，J.，E. Fern’andez和C. Franquesa，《运输科学》第47期（2009年），第100页。287-300[4] Ar'aoz，J.，E. Ferna'ndez和C. 风之团的一个奖项- 系统建模与优化会议，IFIP TC7，2009。[5] Ar'aoz ， J. ， E.Ferna'ndez 和 O. Meza ， Solvingtheprize-col l ectingruralalpostmanproblem ， EuropeanJournal of Operational Research 196（2009），pp. 886-896.[6] Ar'aoz ，J.，E. Fernandez和C. Zoltan，Privatiz edru ralpostmanp roblems， Computers&O perationsResearch 33（2006），pp. 3432-3449[7] 阿尔凯蒂角，D. Feillet，A.Hertz和M.Speranza，带利润的有容量限制的弧路由问题C. Archetti，D. Feillet，Technical report，GERAD（2009）.[8] 阿尔凯蒂角，D. Feillet，A. Hertz和M. Speranza，无向能力约束弧路由问题与利润，计算机和运筹学（2009）。[9] 我们走吧J E.弗恩南德斯角 Franquesa和O. Meza，Prize-collectinga rcroutingproblemsandextensions，in：OdysseusConfe r en ce，Valencia，Esp anEscherichia，2006.[10] BrandJ.和 R. Eglese ， Adeterministictabus ea rchalgorithmfortheca pacitat eda rroutingproblem ，Computers &Operations Research 35（2008），pp. 1112-1126。[11]Cor ber'an，A.，R. 我来了，E。 Mar t'ınez和D. Soler，TheRuralPostmanProblemonmix ed graphs withturnpenalties，Computers& Operations Research 29（2002），pp. 887-903.[12] Cor ber'an ，A.，R. Mar t't和A. Romero，Heuristicsforthemix edruralpostmanprob