...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computers & operations research >Privatized rural postman problems
【24h】

Privatized rural postman problems

机译：私有化农村邮递员问题

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

摘要

In this work we analyze the privatized rural postman problem which is the edge version of the traveling salesman problems with profits. The problem is defined on a undirected graph G( V, E) with a distinguished vertex d, called the Depot. There are two non-negative real functions on the edge set E, which define the value of a cycle in G: one is the profit function, b, and the other one is the cost function, c. They have different meanings when a cycle C traverses an edge e (possibly more than once), because we pay a cost c_e every time e is traversed, but we collect the profit b_e only the first time e is traversed. The privatized rural postman problem is to find a cycle C~*, passing through d and not necessarily simple, which maximizes the sum of the values of the edges traversed in C~*. That is, maxc {∑_(e∈C) (b_e - t_ec_e)} where t_e is the number of times that edge e is traversed in C. We study some properties of the problem: we show that it is NP-hard, its relation with known and new problems, and special cases with good algorithms. We also analyze several integer linear systems of inequalities, which define the polyhedral structure of the problem, and we give dominance and preprocessing conditions. We finish with some remarks and comments about future research.
机译：在这项工作中，我们分析了私有化的农村邮递员问题，这是带有利润的旅行推销员问题的边缘版本。该问题是在无向图G（V，E）上定义的，该无向图具有显着的顶点d，称为Depot。边集E上有两个非负实函数，它们定义G中一个循环的值：一个是利润函数b，另一个是成本函数c。当循环C遍历边缘e（可能不止一次）时，它们具有不同的含义，因为每次遍历e时我们都要付出成本c_e，但是只有在第一次遍历e时才收取利润b_e。私有化的农村邮递员问题是找到一个通过d且不一定简单的循环C〜*，该循环使C〜*中经过的边的值之和最大化。也就是说，maxc {∑_（e∈C）（b_e-t_ec_e）}，其中t_e是在C中遍历边缘e的次数。我们研究了该问题的一些性质：我们证明它是NP难的，它与已知问题和新问题之间的关系，以及具有良好算法的特殊情况。我们还分析了不等式的几个整数线性系统，这些系统定义了问题的多面体结构，并给出了支配性和预处理条件。最后，我们对未来的研究发表一些评论和评论。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号