• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International journal of mobile network design and innovation >Using GRASP to solve the generalised graph colouring problem with application to cell site assignment
【24h】

Using GRASP to solve the generalised graph colouring problem with application to cell site assignment

机译：使用GRASP解决广义图形着色问题，并将其应用于细胞位置分配

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

摘要

Consider a graph with nodes, weighted links and a set of colours. In the generalised graph coloring problem (GGCP), one must colour each node while minimising the total weight of monochromatic links. GGCP can model a cell site assignment problem in which nodes represent cell sites and colours represent multi-service nodes (MSN). The links indicate pairs of cell sites whose geographic service areas overlap; the link weight indicates the degree of overlap. The objective is, as much as possible, to assign cell sites with overlap to different MSNs. We describe a greedy randomised adaptive search procedure (GRASP) for GGCP. At each replication, it builds an initial solution by randomly choosing nodes, one at a time, from a candidate list and myopically assigning a colour to each chosen node. Exchange heuristics can then improve upon the initial solution. Computational experiments indicate that the heuristic provides excellent solutions in little CPU time.
机译：考虑具有节点，加权链接和一组颜色的图。在广义图着色问题（GGCP）中，必须在最小化单色链接总权的同时为每个节点着色。 GGCP可以对小区站点分配问题建模，其中节点代表小区站点，颜色代表多服务节点（MSN）。链接指示其地理服务区域重叠的小区站点对；链接权重指示重叠程度。目的是尽可能将重叠的小区位置分配给不同的MSN。我们描述了GGCP的贪婪随机自适应搜索过程（GRASP）。在每次复制时，它都通过从候选列表中一次随机选择一个节点并为每个所选节点近视地分配颜色来构建初始解决方案。交换启发法可以改善初始解决方案。计算实验表明，启发式算法可在很少的CPU时间内提供出色的解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号