近年来，随着地球观测和导航技术、互联网技术的发展，人们获取的各式各样的道路网数据海量增长，数据获取周期不断缩短，因此，空间数据的有效管理、集成与更新技术也得到快速发展。同名要素匹配是数据集成与更新的重要前提，是进行一系列地图要素的差异性分析和空间相似度评价之后，匹配出不同来源地图数据库中描述地球上同一地物(或地理现象)的地图要素，并建立逻辑关系的过程^[1]。志愿者地理信息(volunteered geographic information，VGI)^[2]，如维基地图、OpenStreetMap等，充分发挥了技术和用户参与相结合的优势，为数据更新提供了新的数据来源。然而由于志愿者地理信息数据质量差异大，为多源数据的匹配带来了新的难题。

Saalfeld在1988年提出了一套蜘蛛编码规则，这是基于八字节结点拓扑结构二进制编码途径用于对道路结点进行匹配^[3]，然而该方法只考虑了1:1的匹配情况。Walter和Fritsch在1999年采用缓冲区增长和信息论中的优势函数方法对欧洲地理数据文件GDF和德国地形制图数据库ATKIS中的道路实体进行匹配^[4]，虽然得到了较好的匹配效果，但匹配效率低下。此外，其他很多学者通过道路间的几何特征关系来对道路进行匹配，如Hausdorff距离、Fréchet距离、L₂距离、转向角函数、路段外包矩形等^[5-12]。上述匹配方法主要存在以下问题：① 很多匹配方法中均涉及到了阈值的选取，阈值过大就会产生更多的误匹配的情况，过小则会出现很多没有匹配出来的路段，因此减小阈值对匹配结果的影响非常重要; ② 针对复杂道路网(如含有双线路等)道路数据的匹配研究较少; ③ 现有道路匹配研究对多种情况进行了研究，但在匹配准确度和匹配效率上很少两者都能顾及。为解决上述不足，本文提出采用模拟退火优化技术对道路进行匹配，顾及双线路等复杂道路，既减小了阈值对匹配结果的影响，也提高了匹配的准确度和效率。

1 基于模拟退火的道路匹配算法

1953年Metropolis提出模拟退火算法这一设想，1983年Kirkpatrickl团队成功将其引入优化组合问题，如今已广泛应用于工业生产当中^[13]。模拟退火算法实质上是一个全局寻优的过程，同时对局部搜寻算法进行扩充。而道路匹配也是一个全局优化的过程，因此，模拟退火可以运用到道路匹配这一问题当中。

1.1 VGI道路数据特点

VGI数据根据其获取方法具有以下特征：

1) 内容细致丰富。不同的用户有不同的文化背景、教育水平和对地理空间的认知，对于相同的地理现象或物体的认知也就存在一定的不同，以此通过合作建立起来的志愿者地理信息数据便拥有了极其丰富的几何和属性信息，这对用传统方式很难获得的属性信息来说是一个巨大的优势。

2) 实时更新准确。传统的更新方式是通过已定好的计划来更新，这一方式周期长，时间固定，从而导致其更新速度无法跟上实际变化速度。而志愿者地理信息的数据更新则是通过用户对地理现象的随时感受，通过互联网和移动终端上传并共享，实现了地理数据准确的实时更新。

3) 较低的更新成本。传统的地理数据更新方式需要投入巨大的人力物力成本，而志愿者地理信息则是用户利用全球卫星定位系统(globle positioning system, GPS)获取的GPS轨迹和兴趣点(point of interest, POI)无偿地分享地理数据，这样降低了数据维护和更新成本。

4) 数据分布不均。信息化水平高低和VGI用户数量多少导致VGI数据的分布不平均，此外，数据的传送也受限于手机等移动设施的使用范围。在人类活动频繁和通信发达的地区，数据就比较密集，在人烟稀少的地区，数据就显得很稀少，造成了数据分布不均的现象。

5) 数据质量差异大。普通用户由于缺乏专业的测绘知识，所使用的GPS装置也存在精度不够等问题，在遥感图像上得到的数据也缺乏一定的代表性，全凭个人对地理空间的认知来添加信息，具有很大的人为主观性，因此，数据质量得不到保证。在遥感图像上矢量化得到的数据，在制图地图学中的各类型地物均要符合制图标准，有详有略，不同类型地物的特征要素的获取和综合也要符合相关要求，相比之下，在VGI应用环境下，缺乏专业知识训练的用户所绘制的地物可能不完全满足制图的标准。专业测绘数据关注于属性数据的规范性，字段长度和数据类型都有一定的标准，而在VGI的操作环境下，由于用户在不同角度上认知的局限性，即使也规定了一些规范用户的输入和编辑行为，地物属性数据的获取还存在很多困难。与此同时，传统测绘得到的数据有完备的元数据信息，而VGI则不多，采集到的数据也比较杂乱无章。VGI还存在数据可能包含恶意信息，数据冗余量大，用户隐私泄露等。

基于以上特点，本文用VGI道路数据与专业测绘道路数据匹配，然后更新，从而使两者的优点得以结合。

1.2 专业道路数据预处理

本文将专业测绘道路数据作为匹配数据，志愿者地理信息道路数据作为参考数据。在通常情况下，道路匹配包括1:1、1:M、N:1、N:M、1:0、0:1等多种情形，而出现多对多或多对1的匹配情况除了双线路与单线路匹配之外，还存在因为数据中一条道路被分成了若干路段的情形。因此，为减少匹配情况，对专业测绘道路数据进行实体识别与连接操作，经过对专业测绘道路数据进行断线连接之后，便消除了1:M、N:M的匹配情况，为匹配对的选取提供了方便。

1.3 模拟退火算法相关设置

1) 解空间和初始解。在解空间的选取上，对专业测绘道路数据和志愿者地理信息道路数据添加缓冲区，通过形成缓冲区的重叠度来获取每条道路的匹配候选集。在形成缓冲区的过程中要注意两点：① 由于通过志愿者道路数据来选取专业测绘道路数据的匹配候选道路，因此，当遇到双线路时，选取其中一条生成缓冲区；② 根据我国对公路的划分规则，把道路缓冲区距离设置为20 m，但当碰到志愿者道路数据某个路段较短时，过大的缓冲距离对之后的匹配产生不利影响，故选取该路段长度的1/3作为缓冲区距离，对应的专业测绘道路数据无论长短，缓冲距离与志愿者道路数据相同。此外，为了提高算法效率，建立了匹配禁忌表，即丢弃重叠度过低的道路，比如，待匹配道路与候选道路垂直等。

对于候选集中只有一条候选道路时，若重叠度较高，直接将它们视为1:1匹配。因此，在确定下来的解空间Ω = {v₁，…，v_n}中，每个元素都拥有两个以上的候选匹配道路。在初始解的选取上，选取解空间中每个元素的候选匹配集中的第一条候选匹配道路作为初始解。

2) 目标函数。确定了解空间和初始解之后，对于每一条志愿者地理信息道路，计算它与它的候选匹配道路集合中每条道路的匹配重叠度，设某志愿者地理信息道路缓冲区面积为S，与候选匹配道路生成的缓冲区重叠部分的面积为S₂，则它们的重叠度为S₂/S，将这个结果视为它们的匹配概率P，依次得到各个路段之间的匹配概率：P₁、P₂、…、P_N，由此得出目标函数为：

$ P = \frac{1}{N}\sum\limits_{i = 1}^N {{P_i}} $

(1)

3) 邻域形成机制。模拟退火算法中邻域的形成机制是极其关键的一步。在形成初始解后，使用怎么样的机制用于形成一个新的解，直接导致算法整体是不是能很好地执行，同时得到结果，解决问题。在道路匹配问题上，采用随机的方法，先在解空间中随机选择一条道路，在这条道路的匹配候选集中，也随机地选取一条与当前候选道路不同的道路，对应的，其所产生的目标函数差ΔP即为两者的重叠度的差。

4) 接受规则。根据模拟退火算法的思想，新的匹配对被接受的准则为：

$ \Delta P > 0{\rm{或}}{{\rm{e}}^{\Delta P/T}}{\rm{ > random}}\left( {0,1} \right) $

(2)

如果符合要求，则接纳新解，然后把目标函数值修改成P+ΔP。

5) 停止机制。在每一个温度值下，若满足迭代循环次数，则进行指数降温，直到温度衰减到遇到值为止，或者在某一温度下，新解连续不被接受的次数到达了预定值，算法也停止。

1.4 算法步骤

1) 对道路生成缓冲区，计算重叠度，获得候选匹配集。

2) 对于匹配集个数为1时，若重叠度高，则视为1:1匹配，然后获得解空间和初始解。

3) 计算匹配概率，获得目标函数。

4) 确定初始温度T_S，停止温度T_E，各个温度下的循环次数N。

5) 随机选取解空间中的一条线，在对应的匹配候选集中随机选取与当前不同的候选道路，相应的目标函数差为ΔP。

6) 判断新解是否被接受，如果接受，则更新目标函数；若不被接受，则统计连续不被接受的次数。

7) 如果连续不被接受的次数达到预定值，则程序结束；若没有达到，则判断迭代次数是否达到N，若是，则转到步骤8)，反之转到步骤5)。

8) 降低温度，判断是否逼近终止温度，若是，则程序结束，反之则转到步骤5)。

1.5 匹配对选取

在经过上述过程之后，将得到一个最终解，在匹配对的选取上，由于之前对专业测绘数据的预处理操作，1:1匹配的工作已经完成，因此只需找出N:1、0:1、1:0等情况。于是，先遍历最终解，将候选道路相同的归类为一组，同时顾及到双线路，若带匹配道路属于双线路，则找出对应的道路划入该组，直至遍历结束。

2 实验分析

实验利用C#和ArcEngine 10.0编写，参考数据来源于VGI地理信息道路数据，如图 1(a)所示，拥有852条路段；匹配数据为专业测绘部门道路数据，如图 1(b)所示，拥有632条路段。对其进行stroke连接操作后，剩下548条路段，如图 1(c)所示，粗实线为stroke后的道路。

通过模拟退火技术匹配结果如图 2所示，总耗时20 s，其中粗实线代表N:1匹配道路，细实线代表 1:1匹配道路，虚线表示未匹配道路，即1:0和0:1的匹配关系，结果中共319对道路判别为匹配道路，对交叉口环形道路以及双线路对单线路多对1匹配的效果也很好。

3 结束语

利用模拟退火技术能很好地对道路进行有效的匹配。该方法的优势是通过全局寻优能以一定概率跳出局部最优的陷阱，从而减少道路误匹配的情况，此外，也降低了阈值的选取对匹配结果的影响。此外，如何快速发现并纠正误匹配的情况，面对更为复杂的情况以及通过匹配结果进行更新同时保持属性信息一致性是今后研究的工作。