多目的地地图作为一种导航地图,能够指引某个区域内的用户到达多个目的地。多目的地地图常见于旅游景区,为游客游览多个景点提供导航。它也常被印刷在商家的宣传材料中,以告知周围的顾客如何快速达到商家的地址。使用现有的在线地图服务(谷歌地图、百度地图等)来自动生成多目的地地图往往存在许多缺陷,如存在冗余数据和无法静态显示不同层次的细节信息。当前多目的地地图的制作主要由专业的制图人员手工去绘制完成,他们需要依靠自身丰富的经验对地图数据进行简化,然后运用大量的制图设计规则包括变形、简化和抽象等布局技术来增强地图的可读性,这是一个非常费时费工的过程。因此,自动地简化地图数据和实现多目的地地图布局优化是一项具有挑战性的工作。本文提出了一种基于设计规则的地图数据简化算法。首先,通过分析认知心理学家的有关研究成果和手绘制图专家的设计经验,我们从中归纳总结出简化和设计多目的地地图的规则。这些规则指导系统根据用户的个性化需求,从大量的原始地图数据中抽取与当前用户最相关的信息,忽略无关信息。然后,结合设计规则构建出分层次的地图数据简化算法,依次识别路网中类型为高速公路、主干道和街道的“可见环”,环上的关键点与目的地之间使用A*算法寻找最佳线路进行连接,构建简化的稀疏地图网络。其中,最佳线路被定义为距离最短、转弯最少和冗余最少的线路。最后,在维持路网正确拓扑结构的前提下,使用Douglas-Peucker算法去除道路上冗余的数据点。在地图数据简化的基础上,本文提出了一种多目的地地图布局优化模型,它使用包含目的地的矩形关注区域(ROI)的空间位置关系,以及连接它们的连接边来描述多目的地地图的布局。首先,本文使用改进的Min-Cut算法将地图切割为多个ROI,确保每个ROI仅包含一个目的地,拥有完整的可达线路,最少的重叠面积等。然后,依据地图设计规划将地图布局优化问题形式化为一个约束系统,约束条件包括充分利用显示空间、限制道路的长度、角度和维持道路网络的拓扑结构等。最后,我们使用基于扰动的模拟退火算法从复杂的布局空间中求解出满足该约束系统的地图布局。本文从地图的全局和局部两个层次来考虑多目的地地图的布局优化,确保在有限面积的显示空间内,与用户最相关的道路信息都能清晰可见。本文提供了大量实验结果和算法的测评,并和相关工作进行了对比。通过用户的问卷和使用调查,借助客观的实验结果分析和比较,验证了本文算法的有效性。最后,我们对本文的工作进行了总结,指了出本文方法的局限,并提出了未来研究工作的方向。