首页> 外文期刊>Mathematical Programming >Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
【24h】

Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

机译:容量最小生成树问题的多交换邻域结构

获取原文
获取原文并翻译 | 示例

摘要

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The CMST problem is an NP-complete problem, and existing exact algorithms can solve only small size problems. Currently, the best available heuristic procedures for the CMST problem are tabu search algorithms due to Amberg et al. and Sharaiha et al. These algorithms use two-exchange neighborhood structures that are based on exchanging a single node or a set of nodes between two subtrees. In this paper, we generalize their neighborhood structures to allow exchanges of nodes among multiple subtrees simultaneously; we refer to such neighborhood structures as multi-exchange neighborhood structures. Our first multi-exchange neighborhood structure allows exchanges of single nodes among several subtrees. Our second multi-exchange neighborhood structure allows exchanges that involve multiple subtrees. The size of each of these neighborhood structures grows exponentially with the problem size without any substantial increase in the computational times needed to find improved neighbors. Our approach, which is based on the cyclic transfer neighborhood structure due to Thompson and Psaraftis and Thompson and Orlin transforms a profitable exchange into a negative cost subset-disjoint cycle in a graph, called an improvement graph, and identifies these cycles using variants of shortest path label-correcting algorithms. Our computational results with GRASP and tabu search algorithms based on these neighborhood structures reveal that (i) for the unit demand case our algorithms obtained the best available solutions for all benchmark instances and improved some; and (ii) for the heterogeneous demand case our algorithms improved the best available solutions for most of the benchmark instances with improvements by as much as 18%. The running times our multi-exchange neighborhood search algorithms are comparable to those taken by two-exchange neighborhood search algorithms.
机译:容量最小生成树(CMST)问题是找到最小成本生成树,该树在入射到给定根节点的子树的大小上具有附加的基数约束。 CMST问题是一个NP完全问题,并且现有的精确算法只能解决小尺寸问题。目前,由于Amberg等人,针对CMST问题的最佳可用启发式程序是禁忌搜索算法。和Sharaiha等。这些算法使用基于两个子树之间交换单个节点或一组节点的两次交换邻域结构。在本文中,我们对它们的邻域结构进行了概括,以允许多个子树之间同时交换节点。我们将这种邻里结构称为多交换邻里结构。我们的第一个多交换邻域结构允许几个子树之间交换单个节点。我们的第二个多交换邻域结构允许涉及多个子树的交换。这些邻域结构中的每一个的大小都随问题的大小呈指数增长,而寻找改进的邻居所需的计算时间却没有任何实质性增加。我们的方法基于Thompson和Psaraftis以及Thompson和Orlin产生的循环转移邻域结构,在图表(称为改进图)中将有利润的交换转换为负成本子集-不相交的周期,并使用最短变体识别这些周期路径标签校正算法。我们使用基于这些邻域结构的GRASP和禁忌搜索算法进行的计算结果表明:(i)对于单位需求情况,我们的算法为所有基准实例获得了最佳的可用解决方案,并进行了一些改进; (ii)对于异构需求情况,我们的算法针对大多数基准实例改进了最佳可用解决方案,改进幅度高达18%。我们的多交换邻域搜索算法的运行时间与两次交换邻域搜索算法的运行时间相当。

著录项

  • 来源
    《Mathematical Programming》 |2001年第1期|71-97|共27页
  • 作者单位

    Department of Industrial and Systems Engineering University of Florida Gainesville FL 32611 USA e-mail: ahuja@ufl.edu;

    Sloan School of Management Massachusetts Institute of Technology Cambridge MA 02139 USA e-mail: jorlin@mit.edu;

    Operations Research Center Massachusetts Institute of Technology Cambridge MA 02139 USA e-mail: dushyant@mit.edu;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号