...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Pesquisa Operacional >Lagrangean relaxation bounds for point-feature cartographic label placement problem
【24h】

Lagrangean relaxation bounds for point-feature cartographic label placement problem

机译：点特征制图标签放置问题的拉格朗日松弛边界

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The objective of the point-feature cartographic label placement problem (PFCLP) is to give more legibility to an automatic map creation, placing point labels in clear positions. Many researchers consider distinct approaches for PFCLP, such as to obtain the maximum number of labeled points that can be placed without overlapping or to obtain the maximum number of labeled points without overlaps considering that all points must be labeled. This paper considers another variant of the problem in which one has to minimize the number of overlaps while all points are labeled in the map. A conflict graph is initially defined and a mathematical formulation of binary integer linear programming is presented. Commercial optimization packages could not solve large instances exactly using this formulation over instances proposed in the literature. A heuristic is then examined considering a Lagrangean relaxation performed after an initial partition of the conflict graph into clusters. This decomposition allowed us to introduce tight lower and upper bounds for PFCLP.
机译：点特征制图标签放置问题（PFCLP）的目的是使自动地图创建更具可读性，将点标签放置在清晰的位置。许多研究人员考虑了PFCLP的不同方法，例如考虑到必须标记所有点，从而获得可以放置而不重叠的最大标记点数量或获得不重叠的最大标记点数量。本文考虑了该问题的另一种变体，其中必须在地图上标记所有点的同时最小化重叠的数量。最初定义了一个冲突图，并给出了二进制整数线性规划的数学公式。商业优化软件包无法使用这种公式完全解决大型实例，而不是文献中提出的实例。然后考虑在将冲突图初始划分为簇之后执行的拉格朗日松弛来检查启发式算法。这种分解使我们能够为PFCLP引入严格的上下限。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号