环树型设施选址问题的分支-价格算法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）3-14www.elsevier.com/locate/entcs环树型设施选址问题的分支-价格算法法比奥·H N. Abea，1，Edna A.星野b，2，5，亚历山德罗山c，3和罗伯托巴尔达奇d，4a巴西，南马托格罗索州联邦研究所b南马托格罗索联邦大学计算机学院大坎普，巴西加州州立理工大学工业与制造工程系圣路易斯奥比斯波，美国d博洛尼亚大学“古列尔莫·马可尼”电气、电子和信息工程系意大利博洛尼亚摘要环树设施选址问题是能力约束环树问题的推广，其中考虑了与设施相关的额外费用和能力。这个问题的应用出现在双层电信网络的战略设计。我们研究了一个扩展的整数规划公式的问题和不同的方法来处理的NP-困难的定价问题，出现在一个分支和价格算法来解决它。计算实验表明，算法和松弛如何提高性能的分支和价格算法。关键词：能力限制环树问题、网路设计、整数规划、列产生、q-路线。1介绍环树设施定位问题（RTFLP）与容量限制环树问题（CRTP）有关，该问题首先在[13]中描述。这两个问题的目标在于设计一个最小成本的集中式两级网络，1电子邮件：fabio. ifms.edu.br2电子邮件：eah@facom.ufms.br3电子邮件：ahill29@calpoly.edu4电子邮件：r. unibo.it5由巴西Fundect提供部分支助https://doi.org/10.1016/j.entcs.2019.08.0021571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。4F.H.N. Abe等/理论计算机科学电子笔记346（2019）3将客户连接到中央仓库。在内层，客户通过环形（或循环）连接到中央仓库，在外层，客户通过与仓库或环形的一个节点相交的树连接到中央仓库。内层的结构提供了冗余，而且通常更昂贵。根据所需的连接级别，客户也可分为两类。 类型1的客户可以通过环或树连接，而类型2的客户必须通过环连接。此外，Steiner节点可以用作可选的中间连接，以降低整体网络成本，并且可以在环或树中使用。一个环树是一个截取仓库的树或一个绕过仓库的环加上所有截取它的环节点的树。受实际应用的启发，RTFLP和CRTP考虑了每个环树中的客户总数的容量，以及用于将所有客户连接到仓库的环树的数量。 在[1]中，RTFLP被引入以处理更广泛的应用类别。它通过考虑每个连接的两个不同成本（环和树连接成本），当树连接到环节点时必须支付的额外设施安装成本，以及定义每个设施可以服务的客户数量上限的树容量来在文献中有一些作品与CRTP和RTFLP直接相关。在[10，14]中描述了CRTP的多交换局部搜索启发式和基于通用局部分支的数学。在[13，16]中提出了CRTP的精确方法。在[12]中，讨论了CRTP的不同双目标函数，以最小化由于单边故障而导致的服务丢失风险。最近在[11]中引入了CRTP的面向利润的版本，其中提出了模型，启发式，有效不等式和精确算法。RTFLP也与能力限制的环星问题（CRSP）有关。基本上，环星指的是环树，其树的深度为1。在CRSP中，对客户、采油树容量和设施安装成本没有要求。请注意，CRSP解决方案不适用于RTFLP，反之亦然。因此，RTFLP和CRSP是相似的，但每一个都不推广另一个。CRSP的精确算法在[3，15]中提出。CRSP有许多应用，它与校车路线问题有关，其评论可以在[18]中找到。多车辆旅行购买者问题（MV-TPP）是一个与CRSP非常接近的校车路径在MV-TPP中，公交车站的选择与路线的生成同时在[19]和[20]中分别提出了MV-TPP的分支和切割算法和分支和切割和价格算法。[17]中给出了对其他集成两级网络设计问题的综述。受[17]中枢纽选址问题应用的启发，第一级称为骨干网络，第二级称为支路网络。考虑2-边连通网络和环作为两层结构，[21]提出了一种分支切割算法来设计两层生存网络。文[1]给出了两个整数线性规划（ILP）公式和RTFLP的分支价格（B P）算法的初步结果。这些初步结果表明，集合覆盖公式提供了非常严格的下限，但在非常膨胀的处理时间。在这项工作中，我们研究了一个扩展的ILP制定的RTFLP和dif-F.H.N. Abe等/理论计算机科学电子笔记346（2019）35e∈Ri=1ee∈Tev∈V[R]<$V[T]v不同的方法来处理NP困难的定价问题，出现在一个分支和价格算法来解决它。为了加速定价问题的精确方法这种放松类似于ng-routes和q-arbs的想法，它们成功地用于车辆路径问题的变体[4，5，22]。我们还提出了一个原始的启发式填充的初始基础和启发式的定价问题。本文的其余部分组织如下。在第2节中，我们提供了问题的正式描述，额外的定义和符号。第3节是专门为我们的算法方法，包括一个原始的启发式，算法和放松的定价问题。这些方法进行了分析，从文献中的实例和计算结果报告在第4节。最后，我们讨论了一些结论，并在第5节中讨论了未来的工作。2问题定义设G=（V，E）是一个 简单无向图，V=U1<$U2<$W<${d}，其中d表示中心仓库，U2是2型顾客集，U1是1型顾客集，W是Steiner节点集.我们用U表示所有顾客U1<$U2的集合，用下式表示由边集X<$E诱导的顶点的集合：V[X].我们将环树定义为一对（R，T），其中RE在G中诱导一个循环，TE在G中诱导一个森林，使得R=，T是一棵树，其中d是一个叶，或;R/=d是一个圈，包括d和每个最大连通分量在V[R]中有一个顶点v d 在后一种情况下，我们假设某些设备必须安装在每个顶点V中，以向相应连接部件的所有用户提供服务。在这种情况下，我们说顶点v有一个与之相关联的设施，连通分支中的那些客户由这个设施提供服务最后，我们说一个客户u被一棵环树（R，T）覆盖，如果u∈V[R]<$V[T]。考虑一个环边代价函数cr：E<$→N，一个树边代价函数ct：E<$→N和一个设施安装代价函数cf：V<$→N。 设m、Q和Qt为整数，分别表示最大环树数、环树容量和树容量。则环树p=（R，T）是（Q，Qt）-可容的，如果|V [RT] |≤Q且每个设施服务的客户数小于或等于Q t。p的环树成本由下 式给 出 ：cr+环树设施定位问题在于找到至多m（Q，Q t）个容量受限的环树p1，...，pk，使得（i）类型1的每个客户被一个环树覆盖;（ii）类型2的每个客户属于一个环树的循环，环树;以及（iii）最小化总网络成本我RTFLP是NP难的，因为它推广了旅行商问题，当m =1，Q=|V|，且U2=Vd. 它也与其他已知的优化问题如车辆路径问题、Steiner树问题、星环问题等相关6F.H.N. Abe等/理论计算机科学电子笔记346（2019）3Σλ（a）λ=1pP我我∈∈ PΣ\| ||×|×（a）λ=ypiΣee我我我我我p∈P问题关于环树拓扑的更多关系，我们参考[13]。3算法方法在[1]中提出了两种RTFLP的ILP公式。第一个是基于多商品树（MCF）的紧凑公式，第二个将（Q，Qt）-容量限制的环树视为集合划分模型（SPF）中的列。由（SPF）的线性松弛（LR）提供的下限比由紧凑公式[1]获得的下限紧51%。由于（SPF）具有指数数量的变量，通常使用列生成（CG）方法来求解其LR。在这种方法中，必须解决两个子问题：限制主问题（RMP）和定价问题。RMP是限制于列的小子集的线性松弛，并且定价问题包括识别具有要添加到RMP的负降低成本的列，其被重新优化。重复此过程，直到找不到具有负降低成本的列。CG求解（SPF）的LR时出现的定价问题包括找到一棵具有最小降低成本的环树 在[1]中，（MCF）和（SPF）考虑一个辅助定向图GJ=（V，A），其中A ={（i，j），（j，i）：ij∈E}建立有向环树模型。注意，有向环树唯一地导出无向对应物。此后，GJ将用作G。因此，边和树也可以被称为弧和树形。为了便于标记，弧（i，j）将由ij表示。设是RTFLP实例的所有（Q，Qt）-容量限制环树的集合。一棵环树p=（R，T）可以用两个维数为（V+A）的特征向量r和t表示1. r的分量使得rp等于一个当且仅当顶点i属于V [R]，并且r ij是一个当且仅当弧ij在R中。类似地，t的分量使得tp等于1当且仅当顶点i属于V[T]V [R]和t ij是1当且仅当弧ij在T中。我们联想变量λp到每个环树p以决定p是否是解的一部分我们也对于每个顶点i W和每个弧e使用二进制变量y i和x e，当且仅当它们属于解时，它们假定值为1。接下来描述RTFLP的集合划分公式（SPF） 最小cpλpp∈Pλp≤mp∈Ppip∈Ppip∈P（rp+tp）λp=xey∈ {0，1} |W|，x ∈ {0，1}|一|，0 ≤ λp ≤ 1其中ap=rp，如果i∈U2，否则ap=rp+tp.约束（1）限制了环树的数量，而不等式（2）确保类型1的每个客户被包含在恰好一个环树中，并且每个客户（一）i∈U（二）i∈W（三）e∈A（四）p∈P（五）F.H.N. Abe等/理论计算机科学电子笔记346（2019）37IJ=cIJ=cij∈Ai=r+1IJIJij∈A 伊季v∈VvIJIJ类型2属于一个环。约束（3）、（4）和（5）禁止Steiner节点和弧出现在两个或更多个环树中。 设π、α、γ和β为分别与约束（1）、（2）、（3）和（4）相关联的对偶变量。的环arc的约化成本是c<$rr−βij−kj，树arc的约化成本是是c<$t−βij−kj，其中kj是0，αj，或rγj，取决于j是否是d，或rj分别为U或W因此，环树p=（R，T）的降低的成本为：givenbyc<$p=c<$rrp+c<$tp+cfθv−π，其中θv是equa ltoo 1 ifv∈V[R]<$V[T]且0，否则。（SPF）的定价问题在于找到一个环树p∈ P，使c′p最小化，这是NP-难的，因为它推广了可盈利的旅游问题[8]，当U1=W=N且Q=|V|.接下来我们讨论我们的方法来应付这个子问题的硬度。3.1放松定价问题而不是找到最小的减少成本的环树，我们考虑放松的定价问题，允许一些顶点重复。 我们的想法包括结合两个成功的松弛：ng-route和qarb松弛，分别在[5]和[22]这种方法也成功地应用于CRSP[4]。ng-route由考虑一组禁止顶点的不必要的基本路由（或环）组成。这个集合是动态构建的，并且基于与每个顶点相关联的称为ngsets的集合。基本上，由NG（i）表示的顶点i的ngset包含i和选定顶点的有限大小子集，例如顶点i的Δ最近邻。参数Δ越高，路线就越基本。通常，路线被构建为从仓库d开始，在顶点i结束，并且包括弧（i，d）的路径。因此，所有的路线可以通过动态规划（DP）得到，只是在所有的顶点，不禁止的延伸路径考虑路径P =（v0= d，v1，...，v k）从仓库开始并在顶点v k处结束。扩展路径P的禁止顶点的集合表示为由π（P）给出，由π（P）={v r：v r∈kNG（v i），1 ≤r≤k− 1}<${v k}给出。现在，根在顶点i的qarb，i i = d，是顶点i单独的或者顶点i连接到根在不同顶点v1，.，v k由弧（i，v j），j = 1，...，K.我们结合ng-route和qarb来获得定价问题的松弛。为了解释这个概念，我们再考虑几个定义。松弛qarb是以顶点i加上弧（d，i）为根的qarb。ng-path是不必要的ele-pathP=（v0=d，v1，.，v k）从仓库开始，其中v k/∈π（PJ），其中PJ=（v0，v1，.，v k−1）也是一条ng-路。换句话说，P不是禁止的顶点来延伸路径（v0，.，v i−1）。一个ng-pathtree是一个ng-path P=（v0=d，v1，...，v k），k≥ 2，加上以P中除仓库以外的顶点为根的qarbs. 一个ng-ringtree是一个ng-pathtree结束于顶点i加上弧（i，d）。我们称之为松弛qarb和ng-ringtree，作为松弛环树。注意到环树也是松弛环树。放松定价问题包括找到最小降低成本的放松环树8F.H.N. Abe等/理论计算机科学电子笔记346（2019）3IJIJ我1ID不di纪求解放松定价问题的算法由两个DP过程组成。 考虑一个命令v1v2<<. 1，否则b=0。我们初始化f（{0}，0，0，0）=0和f（{0}，0，q，0）=∞，<$1≤q≤ Q。 因此，最小成本松弛ng-ringtree的成本可以计算为：mini∈Vd，0≤q≤Q，0≤s≤|W|f（π，i，q，s） +c<$r.考虑两个ng-环树Ri，i∈ {1， 2}，其相应的ng-路Pi终止于在同一个顶点。 设qi和si分别为Ri中的客户数和Steiner节点数。Ng-ringtreeR1支配R2（R2被R1支配），如果它的代价小于R2由于支配ng-ring树对于构造最小代价的松弛环树是不必要的，所以我们将它们全部丢弃。3.2部分定价部分定价包括使用启发式算法快速确定定价问题的近似解。如果启发式算法不能找到一个具有负缩减成本的列，则必须使用精确算法我们的启发式算法由两层组成。在外层，使用贪婪随机自适应搜索过程（GRASP）[9]来构建通过仓库和一些客户的环R。在内层，构造了连接U1<$W−V[R]中顾客的树形结构，并进一步将其附着到环R上，得到一棵环树.在外层构造阶段的每次迭代中，我们增加环R={（v0，v1），（v1，v2），.，（vk，vk+1=v0）}，通过随机选择限制候选列表（RCL），并且包括V[R]中的一个顶点。RCL中的每个元素由一对（u，i）组成，其中u是V-V[R]中的顶点，i∈[0，k]是R中的一个位置贪婪自适应函数f提供以下贡献：c¯F.H.N. Abe等/理论计算机科学电子笔记346（2019）39viu−c<$dkVKviVKkV-c'Kviueachcandidate（u，i），用于降低R的成本，并且它是givenbyf（v，i）=c<$r+Ruvi+1Rvivi+1.该函数用于构造具有最有希望基于贪婪参数α的候选人。在外层的R每次变化之后，调用内层的过程来构造树形结构，并将具有负减少成本的树形结构连接到当前R。请注意，每个树形图T都有一个减少的成本，我们将用yc′（T）表示，如果需要，它是由它们的arcs减少的成本和额外的设施安装成本之和给出的为了构造树形图的集合，我们使用Edmond的算法[ 7 ]，通过连续地选择弧（i，j），以降低成本的非递减顺序，具有dumping条件|V[TiTj]U1|≤min{Qt，Q−|V[R]U|其中Ti（T j）是包含顶点i（j）的树形图。 我们考虑三种方式 将以节点k为根的树状图连接到R：（1）直接连接根k在仓库节点处，（2）将其连接到V[R]的环节点;或（3）包括k作为R中的环节点。考虑到所有已建的树，我们构造了另一个RCL来选择要连接到R的树. 这个RCL的每个元素都由一个三元组（T，i，l）组成，其中T是一个树状图，i是指T在R中应该连接的位置，l定义了将T连接到R的方式之一，1，2或3。 我们计算贡献- 每个候选者（T，i，l）对于给定的环树的降低的成本的作用byc<$（T）+g，其中g=c<$t，g=c<$t我 +cf，如果在vi或r中未安装任何设备g=c<$r我 +c<$r一期+1Rvivi+1 +cf，de p以l=1、2或3结尾。为了减少候选者，我们只考虑使c′（T）+g最小化且其系数为是非负的。内层交互式地随机选择RCL中的一个三元组，并在没有更多的树状图可以连接到R时完成。另一方面，当V[R]中的客户数量达到极限Q时，外层结束。在局部搜索阶段，我们应用众所周知的2opt[6]来提高环树的降低成本。发现的所有具有负降低成本的环树作为列包括在RMP中。3.3一个原始的启发式我们提出了一个原始的启发式构造一组RTFLP的解决方案这些解决方案用于填充RMP的初始基础，最好的一个用于定义第一个原始边界。我们的启发式是基于GRASP没有本地搜索阶段。首先，我们构造一个集合S={（R1，T1），（R2，T2），.，（Rs，Ts）}的空环树来覆盖所有客户。然后，我们迭代地将每个客户U2包含在S中的某个环树的环中。之后，每个客户U1都包含在某个环树中，最后，我们尝试将W的Steiner节点包含在某个环树中，只有当总成本降低时。为了选择一个顶点被包含在一个环树中，我们构造了一个RCL在相同的方式使用的启发式定价。对于第一步，RCL中的每个元素由三元组（u，i，l）组成，其中u是U2−V[Rl]中的顶点，l是S的一个环树（Rl，Tl）的索引，i∈[0，k]是Rl中的位置。在这种情况下，提供（u，i，l）对S的成本的贡献的函数f是由f（v，i，l）=cr给出Ruvi+1Rvivi+1. 我们考虑四种方法来包含一个顶点c¯+C- -10F.H.N. Abe等/理论计算机科学电子笔记346（2019）3eek插入到环树中：（1）通过去除环弧（i，j）并添加（i，k）和（k，j）插入到环中，（2）附加到环节点j上，（3）通过去除树弧（i，j）并添加（i，k）和（k，j）插入到树中，或（4）附加到现有树的顶点j在后一种情况下，必须检查树的容量，在第二种情况下，必须考虑设施安装成本4计算实验所有实验都在具有Intel i7-4790 3.6GHz处理器、32 GB RAM的台式计算机上在Linux下进行。算法用C语言实现，并使用gcc 4.9.2编译。我们使用SCIP（v3.1.0）框架[2]和Cplex（v12.6.1.0）作为线性规划求解器。[6]对于3.3节中描述的原始启发式，我们将α = 0。6.在所有实验中，我们将时间限制固定为1800秒，并考虑以下配置：分支定界（B B）过程中的最佳节点选择，变量上的分支，以及SCIP和Cplex的所有预处理，启发式，切割和多线程都被禁用。我们从[13]中提出的基于TSPlib的CRTP实例中派生出四个实例类A、B、C和D。 所有CRTP实例（称为Q-1、Q-2、. . ，Q-45）和在{0，0. 25，0。五，零。75， 1}被认为是。 每级差压在树边成本、设施安装成本和树容量方面。设w e是CRTP实例中的边e∈E的成本。对于边缘e，我们设置cr=we和ct=[we/2]。 在实例类A和B中 ， cf=0，而在类C和D中，cf=[（mine∈Ewe+maxe∈Ewe）/2|. 在A类和C类中，Qt=1，而在其他类中，Q t=2 [Q/3]。容量m和Q以及集合U1、U2和W与CRTP中的相同。我们考虑具有26个顶点的小实例和具有51、76和101个顶点的大实例。我们分析了不同的B P实现的性能。考虑（SPFr）一个类似于（SPF）的模型，其列是松弛环树。SPF-、SPF+和SPF* 是&使用B B求解确切定价的B P实 现 求 解 （ SPF ） & ， 而 SPFr+ 和 SPFr* 使 用 第 3.1 节 中 描 述 的 DP 求 解（SPFr）。我们还考虑了（MCF）的B B的实现（MCF-和MCF+）信号首先，我们分析了原始启发式算法在小实例中找到的原始解的质量。在表1中，列BestUB呈现等于通过B P和B B实现找到的最佳上限的启发式解决方案的百分比。“最佳”列显示这些解也是最佳的百分比，“差距”列提供原始解与最佳已知解相比的相对目标函数差距。我们还分析了哪个过程生成了SPF*代码找到的最佳解决方案中的列原始列，[6]作者感谢IBM和SCIP提供的学术许可。7测试实例集可根据相应作者的要求提供F.H.N. Abe等/理论计算机科学电子笔记346（2019）311ExactPric和HeurPric分别显示由原始启发式、精确定价过程和定价启发式生成的最佳解决方案中列的百分比。如表1所示，原始启发式在许多情况下提供了最佳上限，并且还负责最佳解决方案中86%的列。表1原始启发式（Primal Heuristics）类最佳UB（%）最佳（%）差距（%）原始（%）准确价格（%）HeurPric（%）一42.215.84.589.75.25.2B31.135.78.782.08.49.6C48.922.73.893.30.06.7D44.450.011.082.67.99.6总41.731.17.086.95.47.8接 下 来 ， 我 们 分 析 了 所 有 实 现 的 性 能 。 表 2 总 结 了 |V|= 26 ， |V|= 51 。Lineoptimal给出了解决到最优性的实例的百分比，time表示达到最优性所花费的平均时间。Linesolved表示未解决到最优性的实例的百分比，但其原始和对偶界限可以计算，gap表示最终对偶差距，平均而言，仅限于这些实例。最后，线根lb表示在根节点达到的平均对偶间隙，定义为（ub−lb0）/ub，其中ub表示找到的最佳上界，lb0表示根下界（LB）。符号“”用于表示达到了时间限制类SPF-SPF+SPF*|= 26|=26MCF-MCF+SPFr+SPFr*MCF+|= 51|=51SPFr+SPFr*一最佳（%）4.48.96.70013.311.1000时间（秒）859.8550.6476.1**61.387.7***差距（%）1.16.15.751.447.810.910.647.715.915.3已解决（%）2.226.742.271.110086.788.978.393.371.7根磅（%）3.53.53.533.733.77.37.329.313.413.4B最佳（%）11.117.817.802.233.337.8055时间（秒）1029.6366.5389.9*1167.22.825.6*123.1431.7差距（%）*63.250.137.810.911.339.815.314.3已解决（%）02022.297.897.866.762.298.38570根磅（%）1.81.81.828.328.35.25.225.712.512.5C最佳（%）4.48.911.10022.224.4055时间（秒）855.8903.7825.9**13.4215.9*81.5302.1差距（%）2.54.15.8108.963.77.87.964.49.410.3已解决（%）6.728.942.26010077.875.673.39578.3根磅（%）3.43.43.438.738.75.85.834.18.58.5D最佳（%）15.615.624.42.24.444.435.603.31.7时间（秒）1200.9559.3719.81721.11428.494133.9*373324.5差距（%）1.42.83.282.859.511.710.66215.415.3已解决（%）2.215.62082.295.655.664.493.393.383.3根磅（%）1.41.41.433.833.85.35.333.112.612.6表2实例的B& P和B& B性能，|V| = 26，|V|= 51如表2所示，SPFr+和SPFr*呈现出比其他实现更好的性能。例如，在小实例上，SPFr+以最优方式解决了28%的实例，平均达到了约10%的最终对偶差距此外，这两个代码所花费的处理时间比其他的小。相对12F.H.N. Abe等/理论计算机科学电子笔记346（2019）3对于根LB，放松定价问题的使用仅使初始LB质量降低3%，而（MCF）提供的LB差约32%。基于这些结果，我们决定分析解决大型实例的性能（|V|= 51）仅用于三种实现（MCF+、SPFr+和SPFr*）。在大型实例中，MCF+无法以最优方式解决任何实例，而SPFr+解决了3。百分之三 这两种代码都可以计算几乎所有情况下的最终对偶性差距，但MCF+达到的最终对偶性差距平均约为45%，而SPFr+达到约14%。我们只对解决的实例进行了成对比较以分析结果两个代码。我们比较SPF+×SPF*（表3），以分析使用部分定价时的B P性能。表4报告了SPF+和SPFr+之间的比较，以分析放松定价问题的使用。最后，表5比较了B B和B P性能。在这些表中，已求解列和最优性列以XX/YY（ZZ）的形式显示值，其中XX表示实例的数量由第一个代码解决（或在第二种情况下解决最优性），而YY对第二个代码也是如此，ZZ给出了由两个代码解决的实例数量（或等效地，由两个代码解决最优性）。列间隙和时间给出了最终对偶间隙和处理时间，平均而言，对于每个代码，仅限于由两个代码解决的实例表3对比SPF+ ×SPF*求解间隙最优时间类SPF+/ SPF*（=）SPF+SPF*SPF+/ SPF*（=）SPF+SPF*一16/ 22（16）4.64.24/ 3（3）488.3476.1B17/ 18（14）2.31.58/ 8（7）395.7298.0C17/ 24（17）3.13.24/ 5（4）903.7620.5D14/ 20（14）1.41.47/ 11（6）405.5325.1总64/ 84（61）23/ 27（20）Avg2.92.6548.3429.9关于部分定价，在3.2节中提出的定价启发式不能像预期的那样改善B P性能。虽然在（SPFr）上使用部分定价没有任何改进，但SPFr+和SPFr*以最优方式解决了不同的情况。另一方面，如表3所示，定价的启发式改进了（SPF）的BP性能考虑到定价问题的松弛性，表4表明3.1节中提出的松弛定价对于处理NP-困难定价问题是有效的。虽然SPF+提供了比SPFr+更好的对偶间隙，但宽松的定价程序可以为所有实例提供对偶间隙。SPFr+比SPF+具有更大的对偶间隙，可能是由于放松模型提供的下界F.H.N. Abe等/理论计算机科学电子笔记346（2019）313表4比较SPF+×SPFr+求解间隙最优时间类SPF+/ SPFr+（=）SPF+SPFr+SPF+/ SPFr+（=）SPF+SPFr+一16/ 45（16）4.68.54/ 6（2）192.21.2B17/ 45（17）3.26.5第15章（五）292.00.7C17/ 45（17）3.15.14/ 10（4）903.70.7D14/ 45（14）1.45.57/ 20（3）370.60.9总64/ 180（64）23/ 51（14）Avg3.16.4439.60.9表5比较MCF+×SPFr+解决间隙优性时间类MCF+/SPFr+（=）MCF+SPFr+MCF+/SPFr+（=）MCF+ SPFr+一45/ 45（45）47.89.40/ 6（0）- -B45/ 45（45）36.97.31/ 15（0）- -C45/ 45（45）63.76.10/ 10（0）- -D45/ 45（45）56.96.52/ 20（0）- -总180/ 180（180）3/ 51（0）Avg51.37.3- -最后，对B-P码和B-B码进行了比较.如表5所示，SPFr+可以比MCF+解决更多的最优实例。由于两个代码都没有然而，二元性差距平均减少了7倍。这些结果是由于（SPFr）提供的紧LB5结论我们分析了不同的方法，以提高性能的分支和价格算法，以解决一个集划分制定的环树设施定位问题。计算实验表明，改进是由于原始启发式和放松的定价问题。原始启发式算法提供了良好的上界和列来填充初始基，这对最佳解决方案中的几乎所有列负责在我们的实验中，只有小的实例（最多51个顶点）可以被当前的实现处理。作为进一步的工作，我们打算从相关问题中调整有效的不等式，14F.H.N. Abe等/理论计算机科学电子笔记346（2019）3用分支-切割-价格算法分析它们的效率。引用[1] 阿贝，F. H. N.，E. A. Hoshino和A. Hill，The ring tree facility location problem，Electron NotesDiscret Math50（2015），pp. 331 -[2] Achterberg，T.，SCIP：Solving constraint integer programs，Math Progr Comput1（2009），pp.1-41[3] 巴尔 达奇河， M. DellSalazar ，The capacitated m-ring star problem， Oper Res55（ 2007 ） ，pp.1147-1162.[4] 巴尔达奇河，A.希尔，E. A. Hoshino和A. Lim，基于动态规划算法的容量限制环星问题的定价策略，Eur J OperRes262（2017），pp.879[5] 巴尔达奇河，A. Mingozzi和R. Roberti，New route relaxation and pricing strategies for the vehiclerouting problem，Oper Res59（2011），pp.1269-1283年。[6] Croes，G.一、A method for solving traveling-salesman problems，Oper Res6（1958），pp. 791-812[7] Edmonds，J.，最佳分支，J Res国家标准局71B（1967），pp.233-240。[8] Feillet ， D. ， P. Deadly 和 M.Gendreau ， Travelling Salesman Problems with Profits ， Transp Sci39（2005），pp.188-205[9] Feo，T.A. 和M.G. Resistance，Greedy randomized adaptive search procedures，J Global Optim6（1995），pp.109-133[10] Hill，A.，多交换邻域的能力限制环树问题，在：I。Dimov，S.我和菲达诺娃。Lirkov，编辑，数值方法和应用，计算机科学讲义，施普林格国际出版社，2015年，pp。85比94[11] Hill，A.，R. Baldacci和E. A. Hoshino，Capacitated ring arborescence problems with profits，ORSpectrum（2018）。[12] 希尔A.和S. Schwarze，具有可靠性度量的双目标环树问题的精确算法，Comput Oper Res94（2018），pp.38[13] 希尔A.和S.Vocabulary，Optimal capacitated ring trees，EURO J COMPUT OPTIM4（2016），pp.137-166。[14] 希尔A.和S. Vocabulary，广义局部分支算法和有能力的环树问题，离散应用数学242（2018），pp。34[15] Hoshino，E. A.和C. C. De Souza，A branch-and-cut-and-price approach for the capacitated m-ring2728-2741[16] Hoshino，E. A. 和A. Hill，能力约束环树问题的列生成方法（2014），ALIO/EURO 2014。[17] Klincewicz，J. G.， 主干/支路网络设计中的集线器位置：综述，Locat Sci6（1998），pp. 307[18] Park，J.B. -I. Kim，The school bus routing problem：A review，Eur J Oper Res202（2010），pp.311–[19] Riera-Ledesma，J. 和J。- J. Salazar-Gonza'lez，Solvingschooloolbusroutingusingthemultiplevehicletravelling purchaser problem：A branch-and-cut approach，Comput Oper Res39（2012），pp.391[20] Riera-Ledesma，J. 和j. J. Salazar-Gonz'alez，Accolumngenerationapproachforaschooloolbusroutingproblem with resource constraints，Comput OperRes40（2013），pp.566[21] 我是R od r'ıguez-Mart'ın，J. - J. Salazar-Gonz'alez和H. Yaman，Abranch-and-cutalgorithmfortwo-levelsurvivablenetwork design problems，Comput Oper Res 67（2016），pp. 102[22] U choa ， E. ， R.去他妈 的 ， J 。 Lysgaard ， A.Pessoa ， M.P.deAragZhao 和 D. Andrade ，Robustbranch-cut-and-price for the capacitated minimum spanning tree problem over a largeextended formulation，Math Progr 112（2008），pp. 443-472.