...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Fractional routing using pairs of failure-disjoint paths
【24h】

Fractional routing using pairs of failure-disjoint paths

机译：使用成对的故障-不相交路径进行部分路由

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given a set of commodities and a network where some arcs can fail while others are reliable, we consider a routing problem with respect to a survivability requirement that each commodity can be split among pairs of failure-disjoint paths. Two paths p and p′ form a pair of failure-disjoint paths if they share only reliable arcs. The same flow is sent over p and p′, but the flow sent on a common reliable arc is not doubled. We present a compact linear formulation of the problem. Also three non-compact formulations solvable by column generation are introduced. In the first formulation, the generated columns correspond to pairs of failure-disjoint paths, while in the second formulation the generated columns correspond to simple paths. The third formulation is solved by generating pairs of arc-disjoint paths. All formulations are compared numerically. On top of that we study some generalizations and some special cases of the problem of computing a shortest pair of failure-disjoint paths. One of these generalizations is equivalent to a single-commodity capacitated network design problem.
机译：给定一套商品和一个网络，其中某些电弧可能会失效而另一些电弧则是可靠的，因此，我们考虑了关于生存能力要求的路由问题，即每个商品都可以在成对的故障不相交路径之间划分。如果两个路径p和p'仅共享可靠的弧，则它们将形成一对故障断开路径。在p和p'上发送相同的流，但是在公共可靠弧上发送的流不会加倍。我们提出问题的一个紧凑的线性表述。还介绍了三种可通过色谱柱产生的非紧凑型制剂。在第一个公式中，生成的列对应于失效-不相交路径对，而在第二个公式中，生成的列对应于简单路径。第三种公式是通过生成成对的弧形不相交路径来解决的。将所有配方进行数值比较。最重要的是，我们研究了计算一条最短的故障-不相交路径对的问题的一些概括和一些特殊情况。这些概括之一等效于单商品容量网络设计问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号