基于Frechet距离的地图匹配算法研究

 2022-06-25 10:06

论文总字数:36061字

摘 要

移动通信的快速发展和信息时代的极速到来促进了很多技术和应用的产生,手机信令数据由于其获取成本小,数据规模大,覆盖范围广等优点,逐渐成为多个领域十分有价值的数据。本文针对手机信令原始数据冗余误差大,出行数据不能很好匹配真实路网等缺点,设计了一套手机信令地图匹配的算法。具体来说,论文工作主要包含以下几方面内容:

首先,对原始信令数据进行了数据预处理,采用相应技术处理了重复冗余数据和乒乓数据、漂移数据等噪声数据。其次,设计了基于时空分析的聚类算法,将出行定位数据分类为出行点群和停留点群,获取了用户的出行信息,将用户的空间位置划分为出行和停留,进而对每次出行进行地图匹配。其三,设计了基于Fréchet距离的地图匹配算法,其主要思路是根据Fréchet距离来衡量曲线相似度,计算聚类后获得的每次出行中的原始信令数据,通过将其连接成线与在真实路网抽象成的无向图中遍历获取的候选路径做Fréchet距离计算,得到相似度最大的真实路径,作为匹配所得的出行路径。第四,采用中国移动提供的真实出行数据进行仿真实验,并比对Hausdorff距离和Fréchet距离的匹配结果,获取平均路段匹配率,在一定程度上验证了算法的有效性。

总的来说,本次研究综合信令数据在时空上群的特征,设计了一种在信令数据时空分类基础上,基于Fréchet距离的针对单次出行全局匹配地图匹配算法。

关键词:Fréchet距离;地图匹配;手机信令

Abstract

The rapid development of mobile communications and the rapid arrival of the information age have prompted the development of many technologies and applications. Cell detail record data has become a valuable data in many fields because of its advantages such as low acquisition cost, large data size, and wide coverage. In this paper, a set of mobile phone cell detail record map matching algorithm is designed aiming at the shortcomings of the original data redundancy of mobile phone detail record and the shortcomings that the travel data cannot match the real road network well. Specifically, the thesis work mainly includes the following aspects:

First, the original detail record is preprocessed by using the corresponding technology to process the redundant data, ping-pong data, drift data, and other noise data. Secondly, a clustering algorithm based on spatio-temporal analysis is designed. The travel location data is classified into travel point group and stay point group, user travel information is obtained, the user's space location is divided into travel and stay, and then perform map matching for each trip. Thirdly, a map matching algorithm based on Fréchet distance is designed. The main idea is to measure the curve similarity according to the Fréchet distance, calculate the original detail record obtained after clustering, and traverse it with the undirected graph. The obtained real road network candidate path is calculated by Fréchet distance, and the real path with the largest similarity is obtained as the match of the travel. Fourth, using the actual travel data provided by CMCC to conduct simulation experiments, and comparing the matching results of Hausdorff distance and Fréchet distance, the matching rate of the average road segment is obtained, and the effectiveness of the algorithm is verified to some extent.

In general, this study studies the characteristics of cell detail record data over time and space, and designs a detour map matching algorithm based on the Fréchet distance based on spatio-temporal classification of signaling data.

KEY WORDS: Fréchet Distance; Cell Detail Record; Map Matching

目 录

摘要 I

Abstract II

1 绪论 3

1.1 研究背景 3

1.2 国内外研究现状 3

1.3 主要研究内容 5

1.3.1 研究内容 5

1.3.2 技术路线 5

2 手机定位原理和数据预处理分析 7

2.1 移动通信技术原理 7

2.1.1 GSM通信原理 7

2.1.2 GSM蜂窝基站定位技术 9

2.2 数据预处理 11

2.2.1 无效数据过滤 11

2.2.2 噪音数据识别预处理 11

2. 2. 3 噪音数据处理算法 13

2.3 本章小结 15

3 基于Fréchet距离地图匹配算法设计 16

3.1 常用地图匹配算法 17

3.1.1 基于几何分析的地图匹配算法。 17

3.1.2 基于拓扑分析的地图匹配 19

3.1.3 基于概率统计的地图匹配算法 19

3.1.4 其他高级地图匹配算法 20

3.2 时空聚类算法 20

3.3 Fréchet距离计算算法 20

3.4 图的遍历算法 21

3.5 地图匹配算法 21

3.6 本章小结 22

4 基于Fréchet距离地图匹配算法实现及实例分析 23

4.1 实验环境和参数标定 23

4.2 数据预处理 23

4.2.1 原始数据存储 23

4. 2. 2 原始数据处理 24

4.3 聚类算法实现 25

4.4 图的遍历 27

4.5 实例验证与对比分析 27

4.6 本章小结 29

5 总结与展望 30

5.1 总结 30

5.2 不足点与展望 30

参考文献 32

附录 34

绪论

研究背景

近年来,随着城市化进程的不断推进,交通规划问题和城市道路问题越来越严重,而因之引起的交通过分拥堵、通勤距离过长等问题,使得城市的交通成本不断增长,减弱了由城市的聚集性带来的经济优势,削弱了城市的竞争力,是当前主要的城市问题之一。客观上来说,道路基建相对落后,路网规划不尽合理是一部分原因所在,但是主观上的交通管理、调度规划存在问题也不容忽视。而从本质上来说,城市交通是聚居地居民的活动衍生物,宏观的城市交通形成于居民的出行在空间和时间上的分布。因此,针对上述的城市交通问题,应当尽量准确地掌握居民的出行行为规律和特征。进而通过对大数据的居民出行特征进行研究从而进行智能城市和智能交通的研究和发展,以解决城市交通中存在的交通拥堵、规划不合理等问题的思路越来越受到人们的关注。通过对大量级的居民出行数据进行研究,分析就业、常住人口分布,分析通勤出行、特定区域出行特征等,进而应用于动态分析居民时空分布、分析客流特征、分析出行和交通强度,交管和城建部门就能有的放矢,合理安排规划交通。而大样本的出行数据在获取时往往存在一定的时空定位误差,因此如何对各种方式获取的出行轨迹数据进行误差修正,成了研究中需要关注和解决的一个问题。

随着个人手机终端的普及,在居民出行信息的研究中,出行行为数据调查有了更好的技术选择,即将手机作为一种交通探测器进行交通数据获取。当处于蜂窝网络中的手机进行通信或移动时,会产生与附近的蜂窝基站产生不同类型的通信(事件响应),基站则记录该用户的时间、时空位置信息等。相比于传统的交通调查方法,手机信令数据在数据采样的开销、覆盖率、实时性等方面具有显著的优势。

剩余内容已隐藏,请支付后下载全文,论文总字数:36061字

您需要先支付 80元 才能查看全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;