The Steiner tree problem with hop constraints
The Steiner tree problem with hop constraints
复制标题
DOI：
10.1023/a:1018967121276
复制
发表时间：
1999
影响因子：
4.8
通讯作者：
S. Voß
中科院分区：
文献类型：
--
作者：
S. Voß
图中的斯坦纳树问题是确定给定图的一个最小代价子图，该图跨越一组指定的顶点。在某些电信网络中，附加约束，例如，必须遵守可靠性约束。假设网络的每个弧段都有一定的可靠性，测量各个弧段运行的概率。在必须保证从根顶点发送到指定顶点的每个消息以一定概率到达其目的地的情况下，所谓的跳约束可以用于对相应的泛化进行建模。本文讨论了带跳数约束的Steiner树问题，即，Steiner的问题inggraphs的推广，其中根节点和任何指定的vertexis之间的弧（跳）的数量有限。一个数学规划公式，并扩展到中等规模的问题的实例。由于带跳数约束的Steiner树问题是NP-困难的，本文提出了一种简单的启发式算法，并应用基于禁忌搜索元策略的交换过程来改进已有的解.数值结果进行了讨论，为anumber的问题的情况下，例如，著名的Steiner'sproblem在图中的基准实例
The Steiner tree problem in graphs is to determine a minimum cost subgraph of a givengraph spanning a set of specified vertices. In certain telecommunication networks, additionalconstraints such as, e.g., reliability constraints, have to be observed. Assume that a certainreliability is associated with each arc of the network, measuring the probability that therespective arc is operational. In case there has to be a guarantee that each message sent froma root vertex to a specified vertex reaches its destination with a certain probability, so‐calledhop constraints may be used to model the respective generalization. In this paper, we discussthe Steiner tree problem with hop constraints, i.e., a generalization of Steiner's problem ingraphs where the number of arcs (hops) between a root node and any of the specified verticesis limited. A mathematical programming formulation is provided and extended to handleproblem instances of moderate size. As the Steiner tree problem with hop constraints is NP‐hard,a simple heuristic is developed and an exchange procedure based on the tabu searchmetastrategy is applied to improve given solutions. Numerical results are discussed for anumber of problem instances derived from, e.g., well‐known benchmark instances of Steiner'sproblem in graphs.