...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The Traveling Salesman Problem with flexible coloring
【24h】

The Traveling Salesman Problem with flexible coloring

机译：灵活着色的旅行商问题

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

摘要

This paper introduces a new generalized version of the Traveling Salesman Problem (TSP) in which nodes belong to various color classes and each color class must be visited as an entity. We distinguish the cases of the problem for which the colors are either pre-assigned or can be selected from a given subset of colors. We establish computational complexity and provide concise formulations for the problems that lend themselves to derive tight lower bounds. Exact solutions for special cases and a two-phase heuristic for the general case are provided. Worst case performance and asymptotic performance of the heuristic are analyzed and the effectiveness of the proposed heuristic in solving large industrial size problems is empirically demonstrated.
机译：本文介绍了Traveling Salesman问题（TSP）的新广义版本，其中节点属于各种颜色类别，每个颜色类别都必须作为一个实体进行访问。我们区分了问题的情况，对于这些情况，颜色是预先指定的，或者可以从给定的颜色子集中选择。我们建立了计算复杂性，并为可能导致严格的下界的问题提供了简洁的表述。提供了针对特殊情况的精确解决方案，以及针对一般情况的两阶段启发式方法。分析了启发式方法的最坏情况性能和渐近性能，并通过经验证明了所提出的启发式方法在解决大型工业规模问题中的有效性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号