高级地图匹配算法：研究现状和趋势

doi:10.12263/DZXB.20200379

电子学报 ›› 2021, Vol. 49 ›› Issue (9): 1818-1829.DOI: 10.12263/DZXB.20200379

高级地图匹配算法：研究现状和趋势

于娟¹, 杨琼², 鲁剑锋¹, 韩建民¹, 彭浩¹

^1.浙江师范大学数学与计算机科学学院，浙江金华 321004
^2.杭州电子科技大学计算机学院，浙江杭州 310018

收稿日期:2020-04-20 修回日期:2021-05-20 出版日期:2021-10-21
- 作者简介:
- 于　娟　女, 1983年9月出生于湖南省张家界市.现为浙江师范大学数学与计算机科学学院讲师、硕士生导师.主要研究方向为时空数据挖掘、数据隐私保护.E‑mail:yujuan@zjnu.edu.cn
  杨　琼　女, 1982年5月出生于湖南省吉首市.杭州电子科技大学计算机学院博士研究生.主要研究方向为时空数据挖掘、隐私保护.E‑mail:yangqiong525@hdu.edu.cn
  鲁剑锋（通信作者）　男, 1982年10月出生于湖北嘉鱼县.现为浙江师范大学数学与计算机科学学院教授，博士生导师.主要研究方向为群智感知和博弈论.E‑mail:lujianfeng@zjnu.cn
  韩建民　男, 1969年7月出生于辽宁大连.现为浙江师范大学数学与计算机科学学院教授，博士生导师.主要研究方向为数据发布隐私保护.E‑mail:hanjm@zjnu.cn
  彭　浩　男, 1982年12月出生于江苏省泰兴市.现为浙江师范大学校双龙学者特聘教授、硕士生导师，从事网络安全、人工智能安全方面的研究工作.E‑mail:hpeng@zjnu.edu.cn
- 基金资助:
- 国家自然科学基金 (61702148); 浙江省自然科学基金 (LR21F020001); 浙江省教育厅一般项目 (Y201941364)

Advanced Map Matching Algorithms: A Survey and Trends

YU Juan¹, YANG Qiong², LU Jian-feng¹, HAN Jian-min¹, PENG Hao¹

^1.College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
^2.Computer and Software, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018, China

Received:2020-04-20 Revised:2021-05-20 Online:2021-10-21 Published:2021-09-25
- Supported by:
- National Natural Science Foundation of China (61702148); National Natural Science Foundation of Zhejiang Province, China (LR21F020001); General Program of Zhejiang Education Department (Y201941364)

摘要/Abstract

摘要：

地图匹配是许多位置服务与轨迹挖掘应用的基础.随着定位技术和位置服务应用的发展，地图匹配研究不断演进，从早期基于高采样率GPS(Global Position System)的实时匹配，到近期基于低采样率GPS轨迹的离线匹配、再到当前非GPS定位数据或高精度地图匹配。迄今已有许多地图匹配算法相继提出，但鲜有研究对这些算法进行全面总结.为此，对近十年提出的地图匹配算法进行调研，归纳出地图匹配算法的统一框架及常用时空特征.从模型或实现技术角度分类发现：现有算法大都采用HMM(Hidden Markov Model)模型，其次是最大权重模型；深度学习技术近期开始用于地图匹配，将是未来高精度地图匹配研究的趋势.

关键词: 地图匹配, 路网数据, 轨迹数据, HMM, CRF(Conditional Random Fields), 路径推断

Abstract:

Map matching is a necessary procedure for many trajectory data mining and various location-based applications.Map matching algorithms are continuously evolving with the development of positioning techniques and application requirements.Research on map matching has undergone several stages, from real-time GPS data map matching, to low-sampling rate GPS trajectories offline map matching, to recently non-GPS positioning data or high resolution map matching.Various advanced map matching algorithms have been proposed.However, there is a short of a complete review of recent map matching algorithms.To bridge this gap, this paper conducts a comprehensive survey on map matching algorithms proposed in the last decade.A general framework of map matching algorithms is extracted, and spatial or spatial-temporal features commonly used in these algorithms are summarized.From the technical perspective, the HMM is the most commonly-used model in existing algorithms, before the maximum weights model.The deep learning technique has been recently applied into map matching, and is becoming a future trend for high resolution map matching.

Key words: map matching, road network, trajectory data, HMM, CRF, route inference

中图分类号:

TP301.6

于娟, 杨琼, 鲁剑锋, 韩建民, 彭浩. 高级地图匹配算法：研究现状和趋势[J]. 电子学报, 2021, 49(9): 1818-1829.

YU Juan, YANG Qiong, LU Jian-feng, HAN Jian-min, PENG Hao. Advanced Map Matching Algorithms: A Survey and Trends[J]. Acta Electronica Sinica, 2021, 49(9): 1818-1829.

图/表 6

图1 地图匹配的统一框架

图2 地图匹配算法发展历程 (2009~2020)

表1 典型的基于HMM的地图匹配算法

算法	观测概率 $P r p i \| c j i$	转移概率 $P r c j i + 1 \| c k i$
HMM-Newson ^［27］ EnAcq^［5］，OM2^［39］ Eddy^［40］	$f N d k i \| μ, σ 2$ ，其中f_N为正态分布函数， $μ$ ， $σ$ 为参数，下同	$f E Δ c k i, c j i + 1 d, 1 \| β$ ，其中f_E（）为指数分布函数， $β$ 为参数，下同
OHMM^［28］	$1 w ∫ - w / 2 w / 2 f N x \| d k i, σ 2 d x$ ，其中 $w$ 为候选点 $c k i$ 所在路段宽度	$f E ω 1 Δ c k i, c j i + 1 d, 2 + ω 2 P c k i, c j i + 1 v, 2 \| β$ ，其中 $ω 1$ ， $ω 2$ 为权重参数
HMM-IRL^［24］	$f N d k i \| μ, σ 2$	$f E Δ c k i, c j i + 1 d, 1 + ω ⋅ T C R c k i, c j i + 1 \| β$ ，其中 $ω$ 为权重系数
HMM-Jagadeesh ^［41］		$f E Δ c k i, c j i + 1 d, 3 \| β 1 × f E Δ c k i, c j i + 1 t, 1 \| β 2$
Feature-based ^［42］ INC-RB ^［43］		$f E X T i, i + 1 \| T \| d p i, p i + 1 \| β$ ，其中 $X = ∑ l = 1 m - 1 Y ⋅ e l . l e n + ω ⋅ ψ A e l, e l + 1$ ， $ω$ 为权重系数， $Y = m i n d e l, T i, i + 1, δ d$ ， $δ d$ ：给定距离阈值
HMM-DPP ^［33］		$f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2, i f Δ t i ≤ 80 s ω 1 f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2 + ω 2 M, o t h e r w i s e$ 其中M为路径偏好模型^［37］， $ω 1$ 和 $ω 2$ 为权重系数， $ω 1 + ω 2 = 1$
EHMM^［44］	$0, i f A p i, e k i ≥ δ A Z, o t h e r w i s e .$ 其中 $δ A$ 为给定夹角阈值， $Z = f E d k i \| β × c o s A p i, e k i$	$f E x \| β 1 × f E A p i, H c k i, c j i + 1 \| β 2 × f E A H p i, p i + 1, H c k i, c j i + 1 ∣ β 3, i f Δ t i < 60 s f E 1 / S c k i, c j i + 1 d, 1 - 1 \| β 4, o t h e r w i s e$ 其中当 $e k i . e n d = e j i + 1 . s t a r t$ 时，x=1，当 $e k i = e j i + 1$ 时，x=0，否则 $x = ∞$
AOMM^［29］	$f N d k i \| μ, σ 2$	$1 - Δ c k i, c j i + 1 d, 2 × S c k i, c j i + 1 v, 1$
Hybrid HMM^［34］	$f N d k i \| μ, σ 2$	$L R c k i, c j i + 1 × 2 - S c k i, c j i + 1 v, 2$

表1 典型的基于HMM的地图匹配算法

算法	观测概率 $P r p i \| c j i$	转移概率 $P r c j i + 1 \| c k i$
HMM-Newson ^［27］ EnAcq^［5］，OM2^［39］ Eddy^［40］	$f N d k i \| μ, σ 2$ ，其中f_N为正态分布函数， $μ$ ， $σ$ 为参数，下同	$f E Δ c k i, c j i + 1 d, 1 \| β$ ，其中f_E（）为指数分布函数， $β$ 为参数，下同
OHMM^［28］	$1 w ∫ - w / 2 w / 2 f N x \| d k i, σ 2 d x$ ，其中 $w$ 为候选点 $c k i$ 所在路段宽度	$f E ω 1 Δ c k i, c j i + 1 d, 2 + ω 2 P c k i, c j i + 1 v, 2 \| β$ ，其中 $ω 1$ ， $ω 2$ 为权重参数
HMM-IRL^［24］	$f N d k i \| μ, σ 2$	$f E Δ c k i, c j i + 1 d, 1 + ω ⋅ T C R c k i, c j i + 1 \| β$ ，其中 $ω$ 为权重系数
HMM-Jagadeesh ^［41］		$f E Δ c k i, c j i + 1 d, 3 \| β 1 × f E Δ c k i, c j i + 1 t, 1 \| β 2$
Feature-based ^［42］ INC-RB ^［43］		$f E X T i, i + 1 \| T \| d p i, p i + 1 \| β$ ，其中 $X = ∑ l = 1 m - 1 Y ⋅ e l . l e n + ω ⋅ ψ A e l, e l + 1$ ， $ω$ 为权重系数， $Y = m i n d e l, T i, i + 1, δ d$ ， $δ d$ ：给定距离阈值
HMM-DPP ^［33］		$f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2, i f Δ t i ≤ 80 s ω 1 f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2 + ω 2 M, o t h e r w i s e$ 其中M为路径偏好模型^［37］， $ω 1$ 和 $ω 2$ 为权重系数， $ω 1 + ω 2 = 1$
EHMM^［44］	$0, i f A p i, e k i ≥ δ A Z, o t h e r w i s e .$ 其中 $δ A$ 为给定夹角阈值， $Z = f E d k i \| β × c o s A p i, e k i$	$f E x \| β 1 × f E A p i, H c k i, c j i + 1 \| β 2 × f E A H p i, p i + 1, H c k i, c j i + 1 ∣ β 3, i f Δ t i < 60 s f E 1 / S c k i, c j i + 1 d, 1 - 1 \| β 4, o t h e r w i s e$ 其中当 $e k i . e n d = e j i + 1 . s t a r t$ 时，x=1，当 $e k i = e j i + 1$ 时，x=0，否则 $x = ∞$
AOMM^［29］	$f N d k i \| μ, σ 2$	$1 - Δ c k i, c j i + 1 d, 2 × S c k i, c j i + 1 v, 1$
Hybrid HMM^［34］	$f N d k i \| μ, σ 2$	$L R c k i, c j i + 1 × 2 - S c k i, c j i + 1 v, 2$

表2 典型的基于最大权重的地图匹配算法

算法	权重 $W c k i, c j i + 1$ 计算
ST-Matching^［25］ IVMM^［37］， LB-MM^［50］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 1$
WI-Matching^［51］	$ω d f d + ω h f h + ω c f c + ω t f t$ ，其中 $f d = δ e - 0.5 d k i + d j i + 1 / δ e$ ， $δ e = 100$ ； $f h = δ A - 0.5 A (p i, e k i) + A (p i + 1, e j i + 1) / δ A$ ， $δ A = 60$ 度； $f c = I s, k i - 1, i + I k, t i, i + 1 / 2$ ，如果 $c s i - 1$ 到 $c t i$ 在路网上存在可达路径则有 $I s, k i - 1, i = 1$ ，否则 $I s, k i - 1, i = 0$ ； $f t = δ T - 0.5 T C R c s i - 1, c t i + T C R c k i, c j i + 1 / δ T$ ， $δ T$ 为给定阈值； $ω d$ ， $ω h$ ， $ω c$ ， $ω t$ 为实验确定的权重系数.
IF-Matching^［35］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 1 × 1 - a r c c o s A p i + 1, e j i + 1 / 2 π × S c k i, c j i + 1 v, 3$
FMM^［26］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 2$
MSTM^［52］	$f N d k i ∣ μ, σ 2 × Q × f N d j i + 1 ∣ μ, σ 2$ ，当 $R c k i, c j i + 1 ≤ 2$ 时，Q=1，否则 $Q = f E 2 - R c k i, c j i + 1 ∣ β$
STD-Matching^［53］	$f N d j i + 1 ∣ μ 1, σ 12 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 1 × f N A p j i + 1, e j i + 1 ∣ μ 2, σ 22$
AIVMM^［36］	$f N d j i + 1 ∣ μ, σ 12 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 4 × S c k i, c j i + 1 v, 5$
FP-based^［31］	$(1 + ω) f N d k i ∣ μ, σ 2 f N d j i + 1 ∣ μ, σ 2 ω f N d k i ∣ μ, σ 2 + f N d j i + 1 ∣ μ, σ 2 × F r e q R c k i, c j i + 1,$ 其中 $ω$ 为权重系数

表2 典型的基于最大权重的地图匹配算法

算法	权重 $W c k i, c j i + 1$ 计算
ST-Matching^［25］ IVMM^［37］， LB-MM^［50］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 1$
WI-Matching^［51］	$ω d f d + ω h f h + ω c f c + ω t f t$ ，其中 $f d = δ e - 0.5 d k i + d j i + 1 / δ e$ ， $δ e = 100$ ； $f h = δ A - 0.5 A (p i, e k i) + A (p i + 1, e j i + 1) / δ A$ ， $δ A = 60$ 度； $f c = I s, k i - 1, i + I k, t i, i + 1 / 2$ ，如果 $c s i - 1$ 到 $c t i$ 在路网上存在可达路径则有 $I s, k i - 1, i = 1$ ，否则 $I s, k i - 1, i = 0$ ； $f t = δ T - 0.5 T C R c s i - 1, c t i + T C R c k i, c j i + 1 / δ T$ ， $δ T$ 为给定阈值； $ω d$ ， $ω h$ ， $ω c$ ， $ω t$ 为实验确定的权重系数.
IF-Matching^［35］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 1 × 1 - a r c c o s A p i + 1, e j i + 1 / 2 π × S c k i, c j i + 1 v, 3$
FMM^［26］	$f N d j i + 1 ∣ μ, σ 2 × S c k i, c j i + 1 d, 2$
MSTM^［52］	$f N d k i ∣ μ, σ 2 × Q × f N d j i + 1 ∣ μ, σ 2$ ，当 $R c k i, c j i + 1 ≤ 2$ 时，Q=1，否则 $Q = f E 2 - R c k i, c j i + 1 ∣ β$
STD-Matching^［53］	$f N d j i + 1 ∣ μ 1, σ 12 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 1 × f N A p j i + 1, e j i + 1 ∣ μ 2, σ 22$
AIVMM^［36］	$f N d j i + 1 ∣ μ, σ 12 × S c k i, c j i + 1 d, 1 × S c k i, c j i + 1 v, 4 × S c k i, c j i + 1 v, 5$
FP-based^［31］	$(1 + ω) f N d k i ∣ μ, σ 2 f N d j i + 1 ∣ μ, σ 2 ω f N d k i ∣ μ, σ 2 + f N d j i + 1 ∣ μ, σ 2 × F r e q R c k i, c j i + 1,$ 其中 $ω$ 为权重系数

表3 典型地图匹配算法应用场景角度的对比

应用场景	算法	采样间隔	改进方法和目标
实时GPS导航	EnAcq^［5］	5~30s	利用自适应采样，降低采样率
	OHMM^［28］	1~300s	利用变长滑动窗，降低时延
	Eddy^［40］	1~120s	利用自适应滑动窗，降低时延
	OLMM^［70］	/	利用变长滑动窗，降低时延
	HMM-RCM^［30］	1~5min	利用路径选择模型，提高准确率、降低时延
	AOMM^［29］	30~210s	优化转移概率、利用自适应滑动窗，降低时延
	HMM+PRP^［71］	1~20s	利用概率路径预测，降低时延
	INC-RB^［43］	60~180s	利用回滚机制，降低时延
离线WiFi轨迹挖掘	HTrack^［2］	/	优化转移概率，提高准确率
离线WiFi轨迹挖掘	PDMatching^［4］	1~6m	优化转移概率，提高准确率
离线GPS轨迹挖掘	SIMP^［21］	1~60s	简化轨迹，提高效率
	OBR-HMM^［72］	1~64s	逐段匹配，提高效率
	FMM^［26］	/	利用预计算，提高效率
	Truncating^［73］	30~300s	优化最短路径计算，提高效率
	Feature-based^［42］	1~5min	优化转移概率，提高效率
	EHMM^［44］	5~150s	优化观测、转移概率，提高准确率
	OM2^［39］	/	利用轨迹分割、后处理，提高准确率
	HMM-IRL^［24］	30~360s	优化转移概率，提高准确率
	HMM-DPP^［33］	20~180s	优化转移概率，提高准确率
	PIF^［47］	1~120s	利用模型改进，提高准确率
	CRF-Xu^［32］	180~420s	优化转移概率，提高准确率
	ST-CRF^［46］	5~120s	优化转移概率，提高准确率
	CRF-Yang^［48］	/	利用 $l 1$ 正则化，提高准确率
	ST-Matching^［25］	30~300s	优化权重度量，提高准确率
	LB-MM^［50］	2~6min
	IF-Matching^［35］	/
离线GPS轨迹挖掘	IF-Matching^［35］	/
	MSTM^［52］	5~30min
	STD-Matching^［53］	1~120s
	AIVMM^［36］	/
	FP-based^［31］	1~5min
	IVMM^［37］	2.5~10.5min	考虑采样点间影响，提高准确率
	WI-Matching^［51］	/	优化权重度量、插值，提高准确率
	HRIS^［38］	3~15min	利用参考轨迹，提高准确率
	InferTra^［56］	5~15min	网络移动性建模，提高准确率
	SF-Matching^［57］	2~8min	利用路径选择模型，提高准确率
	STRS^［58］	15~90s	利用概率局部路径推断，提高准确率
	TAMM^［59］	20~260s	利用重力模型，提高准确率
	FP-Matching^［31］	30~300s	利用频繁路径，提高准确率
	DPMM^［74］	30~300s	引入个性化路径选择偏好，提高准确率
	Genetic^［54］	/	考虑全局特征，提高准确率
	AntMapper^［55］	10~300s	考虑全局特征，提高准确率

表3 典型地图匹配算法应用场景角度的对比

应用场景	算法	采样间隔	改进方法和目标
实时GPS导航	EnAcq^［5］	5~30s	利用自适应采样，降低采样率
	OHMM^［28］	1~300s	利用变长滑动窗，降低时延
	Eddy^［40］	1~120s	利用自适应滑动窗，降低时延
	OLMM^［70］	/	利用变长滑动窗，降低时延
	HMM-RCM^［30］	1~5min	利用路径选择模型，提高准确率、降低时延
	AOMM^［29］	30~210s	优化转移概率、利用自适应滑动窗，降低时延
	HMM+PRP^［71］	1~20s	利用概率路径预测，降低时延
	INC-RB^［43］	60~180s	利用回滚机制，降低时延
离线WiFi轨迹挖掘	HTrack^［2］	/	优化转移概率，提高准确率
离线WiFi轨迹挖掘	PDMatching^［4］	1~6m	优化转移概率，提高准确率
离线GPS轨迹挖掘	SIMP^［21］	1~60s	简化轨迹，提高效率
	OBR-HMM^［72］	1~64s	逐段匹配，提高效率
	FMM^［26］	/	利用预计算，提高效率
	Truncating^［73］	30~300s	优化最短路径计算，提高效率
	Feature-based^［42］	1~5min	优化转移概率，提高效率
	EHMM^［44］	5~150s	优化观测、转移概率，提高准确率
	OM2^［39］	/	利用轨迹分割、后处理，提高准确率
	HMM-IRL^［24］	30~360s	优化转移概率，提高准确率
	HMM-DPP^［33］	20~180s	优化转移概率，提高准确率
	PIF^［47］	1~120s	利用模型改进，提高准确率
	CRF-Xu^［32］	180~420s	优化转移概率，提高准确率
	ST-CRF^［46］	5~120s	优化转移概率，提高准确率
	CRF-Yang^［48］	/	利用 $l 1$ 正则化，提高准确率
	ST-Matching^［25］	30~300s	优化权重度量，提高准确率
	LB-MM^［50］	2~6min
	IF-Matching^［35］	/
离线GPS轨迹挖掘	IF-Matching^［35］	/
	MSTM^［52］	5~30min
	STD-Matching^［53］	1~120s
	AIVMM^［36］	/
	FP-based^［31］	1~5min
	IVMM^［37］	2.5~10.5min	考虑采样点间影响，提高准确率
	WI-Matching^［51］	/	优化权重度量、插值，提高准确率
	HRIS^［38］	3~15min	利用参考轨迹，提高准确率
	InferTra^［56］	5~15min	网络移动性建模，提高准确率
	SF-Matching^［57］	2~8min	利用路径选择模型，提高准确率
	STRS^［58］	15~90s	利用概率局部路径推断，提高准确率
	TAMM^［59］	20~260s	利用重力模型，提高准确率
	FP-Matching^［31］	30~300s	利用频繁路径，提高准确率
	DPMM^［74］	30~300s	引入个性化路径选择偏好，提高准确率
	Genetic^［54］	/	考虑全局特征，提高准确率
	AntMapper^［55］	10~300s	考虑全局特征，提高准确率

表4 典型地图匹配算法的数据需求对比

算法	轨迹数据包含：				路网数据包含：
算法	时间+经纬度	瞬时速度	瞬时方向	历史轨迹	路网拓扑	路宽	限速	历史平均速度	自由流速
CRF-Liao^［45］， HMM-Newson^［27］， HMM-IRL^［24］， Eddy^［40］， OBR-HMM^［72］， MSTM^［52］， OM2^［39］， Feature-based^［42］， Genetic^［54］， FMM^［26］，INC-RB^［43］	$√$				$√$
WI-Matching^［51］， AntMapper^［55］，EHMM^［44］， STD-Matching^［53］	$√$		$√$		$√$
OHMM^［28］	$√$				$√$	$√$
ST-Matching^［25］， IVMM^［37］， EnAcq^［5］，LB-MM^［50］， ST-CRF^［46］， AIVMM^［36］	$√$				$√$		$√$
CRF-Xu^［32］， HMM+RCM^［30］， Hybrid HMM^［34］	$√$				$√$			$√$
HMM-Jagadeesh^［41］	$√$				$√$		$√$		$√$
AOMM^［29］	$√$	$√$			$√$			$√$
STD-Matching^［53］	$√$		$√$		$√$			$√$
HRIS^［38］， SF-Matching^［57］， STRS^［58］， InferTra^［56］， FP-based^［31］， DPMM^［74］	$√$			$√$	$√$
Hybrid HMM^［34］	$√$			$√$	$√$	$√$
HMM-DPP^［33］	$√$	$√$		$√$	$√$
IF-Matching^［35］， TAMM^［59］	$√$	$√$	$√$	$√$	$√$

表4 典型地图匹配算法的数据需求对比

算法	轨迹数据包含：				路网数据包含：
算法	时间+经纬度	瞬时速度	瞬时方向	历史轨迹	路网拓扑	路宽	限速	历史平均速度	自由流速
CRF-Liao^［45］， HMM-Newson^［27］， HMM-IRL^［24］， Eddy^［40］， OBR-HMM^［72］， MSTM^［52］， OM2^［39］， Feature-based^［42］， Genetic^［54］， FMM^［26］，INC-RB^［43］	$√$				$√$
WI-Matching^［51］， AntMapper^［55］，EHMM^［44］， STD-Matching^［53］	$√$		$√$		$√$
OHMM^［28］	$√$				$√$	$√$
ST-Matching^［25］， IVMM^［37］， EnAcq^［5］，LB-MM^［50］， ST-CRF^［46］， AIVMM^［36］	$√$				$√$		$√$
CRF-Xu^［32］， HMM+RCM^［30］， Hybrid HMM^［34］	$√$				$√$			$√$
HMM-Jagadeesh^［41］	$√$				$√$		$√$		$√$
AOMM^［29］	$√$	$√$			$√$			$√$
STD-Matching^［53］	$√$		$√$		$√$			$√$
HRIS^［38］， SF-Matching^［57］， STRS^［58］， InferTra^［56］， FP-based^［31］， DPMM^［74］	$√$			$√$	$√$
Hybrid HMM^［34］	$√$			$√$	$√$	$√$
HMM-DPP^［33］	$√$	$√$		$√$	$√$
IF-Matching^［35］， TAMM^［59］	$√$	$√$	$√$	$√$	$√$

参考文献 75

1	GUF Q, HUX K, et al.Indoor localization improved by spatial context⁃a survey[J].ACM Comput.Surv, 2019, 52(3): 1 - 35.
2	WUY, CHENP, et al.HTrack: An efficient heading-aided map matching for indoor localization and tracking[J].IEEE Sensors Journal, 2019, 19(8): 3100 - 3110.
3	ZHOUR, TANGM, et al.FreeTrack: device-free human tracking with deep neural networks and particle filtering[J].IEEE Systems Journal, 2020, 14(2): 2990 - 3000.
4	CHENP, ZHENGX P, et al.Path distance-based map matching for Wi-Fi fingerprinting positioning[J].Future Generation Computer Systems, 2020, 107: 82 - 94.
5	FANGS K, ZIMMERMANNR.EnAcq: energy-efficient GPS trajectory data acquisition based on improved map matching[A].ACM SIGSPATIAL GIS'11[C].New York: ACM, 2011. 221 - 230.
6	DONGJ X, HICKSC, LID J.A heuristics based global navigation satellite system data reduction algorithm integrated with map-matching[J].Annals of Operations Research, 2020, 290(1): 731 - 746.
7	GONGX R, HUANGZ, et al.High-performance spatiotemporal trajectory matching across heterogeneous data sources[J].Future Generation Computer Systems, 2020, 105: 148 - 161.
8	CHAOP F, HUAW, et al.A survey and quantitative study on map inference algorithms from GPS trajectories[J/OL].IEEE Transactions on Knowledge and Data Engineering (Early Access), ,2020.
9	ZONGF, WUT, JIAH.Taxi drivers' cruising patterns—insights from taxi GPS traces[J].IEEE Transactions on Intelligent Transportation Systems, 2019, 20(2): 571 - 582.
10	LIL, JIANGR, et al.Trajectory data-based traffic flow studies: A revisit[J].Transportation Research Part C: Emerging Technologies, 2020, 114: 225 - 240.
11	CHEND, DRIEMELA, et al.Approximate map matching with respect to the Fréchet distance[A].ALENEX 2011 [C].San Francisco: SIAM, 2011. 75 - 83.
12	VELAGAN R, QUDDUSM A, BRISTOWA L.Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems[J].Transportation Research Part C: Emerging Technologies, 2009, 17(6): 672 - 683.
13	QUDDUSM A, OCHIENGW Y, NOLANDR B.Current map-matching algorithms for transport applications: State-of-the art and future research directions[J].Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312 - 328.
14	WEIH, WANGY, et al.Map matching: Comparison of approaches using sparse and noisy data[A].ACM SIGSPATIAL GIS'13[C].New York: ACM, 2013. 444 - 447.
15	HASHEMIM, KARIMIH A.A critical review of real-time map-matching algorithms: Current issues and future directions[J].Computers, Environment and Urban Systems, 2014, 48: 153 - 165.
16	SINGHJ, SINGHS, et al.Evaluating the performance of map matching algorithms for navigation systems: an empirical study[J].Spatial Information Research, 2018, 27: 63 - 74.
17	KUBICKAM, CELAA, et al.Comparative study and application-oriented classification of vehicular map-matching methods[J].IEEE Intelligent Transportation Systems Magazine, 2018, 10(2): 150 - 166.
18	高文超, 李国良, 塔娜.轨迹路网匹配算法综述[J].软件学报, 2018, 29(2): 225 - 250.
	GAOW C, LIG L, TA N.Survey of map matching algorithms[J].Journal of Software, 2018, 29(2): 225 - 250.(in Chinese)
19	KUMARP, GANTIR K, RAINAG.A new technique to find candidate links for map matching for transportation applications[A].The 8th International Conference on Communication Systems and Networks [C].New Jersey, USA: IEEE, 2016. 1 - 6.
20	KOLLERH, WIDHALMP, et al.Fast hidden Markov model map-matching for sparse and noisy trajectories[A].ITSC 2015[C].New Jersey, USA: IEEE, 2015. 2557 - 2561.
21	LIH F, KULIKL, RAMAMOHANARAOK.Spatio-temporal trajectory simplification for inferring travel paths[A].ACM SIGSPATIALGIS'14[C].New York: ACM, 2014. 63 - 72.
22	LIUX L, YUL, et al.ST-PF: Spatio-temporal particle filter for floating-car data pre-processing[A].(IF&IGIS'17[C].Switzerland: Springer, 2018. 197 - 211.
23	RAPPOSE, ROBERTS, CUDRÉ-MAUROUXP.A force-directed approach for offline GPS trajectory map matching[A].ACM SIGSPATIAL GIS'18[C].New York: ACM, 2018. 319 - 328.
24	OSOGAMIT, RAYMONDR.Map matching with inverse reinforcement learning[A].IJCAI'13[C].Palo Alto, California: AAAI, 2013. 2547 - 2553.
25	LOUY, ZHANGC Y, et al.Map-matching for low-sampling-rate GPS trajectories[A].ACM SIGSPATIAL GIS'09 [C].New York: ACM, 2009. 352 - 361.
26	YANGC, GIDÓFALVIG.Fast map matching, an algorithm integrating hidden Markov model with precomputation[J].International Journal of Geographical Information Science, 2018, 32(3): 547 - 570.
27	NEWSONP, KRUMMJ.Hidden Markov map matching through noise and sparseness[A].ACM SIGSPATIAL GIS'09[C].New York: ACM, 2009. 336 - 343.
28	GOH C Y, DAUWELSJ, et al.Online map-matching based on Hidden Markov model for real-time traffic sensing applications[A].ITSC'12[C].New Jersey, USA: IEEE, 2012. 776 - 781.
29	ANQ, FENGZ, et al.A green self-adaptive approach for online map matching[J].IEEE Access, 2018, 6: 51456 - 51469.
30	JAGADEESHG R, SRIKANTHANT.Online map-matching of noisy and sparse location data with hidden Markov and route choice models[J].IEEE Transactions on Intelligent Transportation Systems, 2017, 18(9): 2423 - 2434.
31	HUANGY, RAOW, et al.Frequent pattern-based map-matching on low sampling rate trajectories[A].IEEE MDM'18[C].New Jersey, USA: IEEE, 2018. 266 - 273.
32	XUM, DUY M, et al.Map matching based on conditional random fields and route preference mining for uncertain trajectories[J].Mathematical Problems in Engineering, 2015, 717095: 1 - 13.
33	SONGC, YANX, et al.Hidden Markov model and driver path preference for floating car trajectory map matching[J].IET Intelligent Transport Systems, 2018, 12(10): 1433 - 1441.
34	OZDEMIRE, TOPCUA E, OZDEMIRM K.A hybrid HMM model for travel path inference with sparse GPS samples[J].Transportation, 2018, 45(1): 233 - 246.
35	HUG, ShaoJ, et al.IF-Matching: towards accurate map-matching with information fusion[J].IEEE Transactions on Knowledge and Data Engineering, 2017, 29(1): 114 - 127.
36	ZHANGY, HEY.An advanced interactive-voting based map matching algorithm for low-sampling-rate GPS data[A].IEEE ICNSC 2018 [C].New Jersey, USA: IEEE, 2018. 1 - 7.
37	YUANJ, ZHENGY, et al.An interactive-voting based map matching algorithm[A].IEEE MDM'10[C].New Jersey, USA: IEEE, 2010. 43 - 52.
38	ZHENGK, ZHENGY, et al.Reducing uncertainty of low-sampling-rate trajectories[A].IEEE ICDE'12[C].New Jersey, USA: IEEE, 2012. 1144 - 1155.
39	XIEY, ZHOUK, et al.High-accuracy off-line map-matching of trajectory network division based on weight adaptation HMM[J].IEEE Access, 2020, 8: 7256 - 7266.
40	WANGG F, ZIMMERMANNR.Eddy: An error-bounded delay-bounded real-time map matching algorithm using HMM and online viterbi decoder[A].ACM SIGSPATIAL GIS'14[C].New York: ACM, 2014. 33 - 42.
41	JAGADEESHG R, SRIKANTHANT.Probabilistic map matching of sparse and noisy smartphone location data[A].IEEE ITSC'15 [C].New Jersey, USA: IEEE, 2015. 812 - 817.
42	YINY F, SHAHR R, ZIMMERMANNR.A general feature-based map matching framework with trajectory simplification[A].ACM SIGSPATIAL IWGS'16[C].Burlingame, California, USA: ACM, 2016. 7:1 - 7:10.
43	LUOL B, HOUX T, et al.Incremental route inference from low-sampling GPS data: An opportunistic approach to online map matching[J].Information Sciences, 2020, 512: 1407 - 1423.
44	CHEM L, WANGY L, et al.An enhanced hidden Markov map matching model for floating car data[J].Sensors, 2018, 18(6): 1758.
45	LIAOL, FOX D, KAUTZH.Extracting places and activities from GPS traces using hierarchical conditional random fields[J].The International Journal of Robotics Research, 2007, 26(1): 119 - 134.
46	LIUX L, LIUK, et al.A ST-CRF map-matching method for low-frequency floating car data[J].IEEE Transactions on Intelligent Transportation Systems, 2017, 18(5): 1241 - 1254.
47	HUNTERT, ABBEELP, BAYENA.The path inference filter: model-based low-latency map matching of probe vehicle data[J].IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2): 507 - 529.
48	YANGJ, MENGL Q.Feature selection in conditional random fields for map matching of GPS trajectories[A].Progress in Location-Based Services 2014[C].Switzerland: Springer, 2015. 121 - 135.
49	CHENB Y, YUANH, et al.Map-matching algorithm for large-scale low-frequency floating car data[J].International Journal of Geographical Information Science, 2014, 28(1): 22 - 38.
50	CHANDIOA A, TZIRITASN, et al.An approach for map-matching strategy of GPS-Trajectories based on the locality of road networks[A].Internet of Vehicles - Safe and Intelligent Mobility[C].Switzerland: Springer, 2015. 234 - 246.
51	LIUS Y, LIUC, et al.Calibrating large scale vehicle trajectory data[A].IEEE MDM 2012[C].New Jersey, USA: IEEE, 2012. 222 - 231.
52	TUO Y, YUNX, ZHANGY.MSTM: A novel map matching approach for low-sampling-rate trajectories[A].IEEE PIMRC 2017 [C].Montreal, QC, Canada: IEEE, 2017. 1 - 7.
53	HSUEHY L, CHENH C.Map matching for low-sampling-rate GPS trajectories by exploring real-time moving directions[J].Information Sciences, 2018, 433-434: 55 - 69.
54	NIKOLIĆM, JOVIĆJ.Implementation of generic algorithm in map-matching model[J].Expert Systems with Applications, 2017, 72: 283 - 292.
55	GONGY J, CHENE, et al.AntMapper: an ant colony-based map matching approach for trajectory-based applications[J].IEEE Transactions on Intelligent Transportation Systems, 2018, 19(2): 390 - 401.
56	BANERJEEP, RANUS, RAGHAVANS.Inferring uncertain trajectories from partial observations[A].IEEE ICDM 2014[C].New Jersey, USA: IEEE, 2014. 30 - 39.
57	CHENC, ZHANGX D, et al.Map-matching based on driver behavior model and massive trajectories[A].IEEE ITSC2014[C].New Jersey, USA: IEEE, 2014. 2817 - 2822.
58	WUH, MAOJ Y, et al.Probabilistic robust route recovery with spatio-temporal dynamics[A].ACM SIGKDD'16[C].New York: ACM, 2016, 1915 - 1924.
59	CINTIAP, NANNIM.An effective Time-Aware map matching process for low sampling GPS data[DB/OL].arXiv:, 2016.
60	WUH, SUNW W, ZhengB H.Is only one GPS position sufficient to locate you to the road network accurately[A].ACM UbiComp'16[C].New York: ACM, 2016. 740 - 751.
61	ZHAOK, FENGJ, et al.DeepMM: deep learning based map matching with data augmentation[A].ACM SIGSPATIAL GIS'19[C].Chicago: ACM, 2019. 452 - 455.
62	卢家品, 罗月童, 等.基于排名学习和多源信息的地图匹配方法[J].浙江大学学报(理学版), 2020, 47(1): 27 - 35, 66.
	LUJ P, LUOY T, et al.An information fusion map matching methond based on ranking learning[J].Journal of Zhejiang University(Science Edition), 2020, 47(1): 27 - 35, 66.(in Chinese)
63	SHENZ H, DUW, et al.DMM: fast map matching for cellular data[A].MobiCom'20[C].New York: ACM, 2020. 1 - 14.
64	SRIVATSAM, GANTIR, et al.Map matching: facts and myths[A].ACM SIGSPATIALGIS'13[C].New York: ACM, 2013. 484 - 487.
65	RAHMANIM, KOUTSOPOULOSH N.Path inference from sparse floating car data for urban networks[J].Transportation Research Part C: Emerging Technologies, 2013, 30: 41 - 54.
66	LIY, HUANGQ X, et al.Large-scale joint map matching of GPS traces[A].ACM SIGSPATIAL GIS'13[C].New York: ACM, 2013. 214 - 223.
67	KONGX F, YANGJ W.A scenario-based map-matching algorithm for complex urban road network[J].Journal of Intelligent Transportation Systems,2019, 23(6): 617 - 631.
68	孙文彬, 熊婷.历史数据和强化学习相结合的低频轨迹数据匹配算法[J].测绘学报, 2016, 45(11): 1328 - 1334.
	SUM W B, XIONGT.A low-sampling-rate trajectory matching algorithm in combination of history trajectory and reinforcement learning[J].Acta Geodaetica et Cartographica Sinica, 2016, 45(11): 1328 - 1334.(in Chinese)
69	KRUGERR, SIMEONOVG, et al.Visual interactive map matching[J].IEEE Transactions on Visualization and Computer Graphics, 2018, 24(6): 1881 - 1892.
70	LIANGB W, WANGT J, et al.Online learning for accurate real-time map matching[A].PAKDD 2016[C].Switzerland: Springer, 2016. 67 - 78.
71	TAGUCHIS, KOIDES, YOSHIMURAT.Online map matching with route prediction[J].IEEE Transactions on Intelligent Transportation Systems, 2019, 20(1): 338 - 347.
72	LIH F, KULIKL, RAMAMOHANARAOK.Robust inferences of travel paths from GPS trajectories[J].International Journal of Geographical Information Science, 2015, 29(12): 2194 - 2222.
73	IMAMICHIT, OSOGAMIT, RAYMOND, R.Truncating shortest path search for efficient map matching[A].IJCAI 2016[C].Palo Alto, California: AAAI, 2016. 589 - 595.
74	高需, 武延军, 等.基于偏好的个性化路网匹配算法[J].软件学报, 2018, 29(11): 3500 - 3516.
	GAOX, WUY J, et al.Personalized map-matching algorithm based on driving preference[J].Journal of Software, 2018, 29(11): 3500 - 3516.(in Chinese)
75	MAAREFM, KASSASZ M.Ground vehicle navigation in GNSS-Challenged environments using signals of opportunity and a closed-loop map-matching approach[J].IEEE Transactions on Intelligent Transportation Systems, 2020, 21(7): 2723 - 2738.

算法	观测概率 $P r p i \| c j i$	转移概率 $P r c j i + 1 \| c k i$
HMM-Newson ^［27］ EnAcq^［5］，OM2^［39］ Eddy^［40］	$f N d k i \| μ, σ 2$ ，其中f_N为正态分布函数， $μ$ ， $σ$ 为参数，下同	$f E Δ c k i, c j i + 1 d, 1 \| β$ ，其中f_E（）为指数分布函数， $β$ 为参数，下同
OHMM^［28］	$1 w ∫ - w / 2 w / 2 f N x \| d k i, σ 2 d x$ ，其中 $w$ 为候选点 $c k i$ 所在路段宽度	$f E ω 1 Δ c k i, c j i + 1 d, 2 + ω 2 P c k i, c j i + 1 v, 2 \| β$ ，其中 $ω 1$ ， $ω 2$ 为权重参数
HMM-IRL^［24］	$f N d k i \| μ, σ 2$	$f E Δ c k i, c j i + 1 d, 1 + ω ⋅ T C R c k i, c j i + 1 \| β$ ，其中 $ω$ 为权重系数
HMM-Jagadeesh ^［41］		$f E Δ c k i, c j i + 1 d, 3 \| β 1 × f E Δ c k i, c j i + 1 t, 1 \| β 2$
Feature-based ^［42］ INC-RB ^［43］		$f E X T i, i + 1 \| T \| d p i, p i + 1 \| β$ ，其中 $X = ∑ l = 1 m - 1 Y ⋅ e l . l e n + ω ⋅ ψ A e l, e l + 1$ ， $ω$ 为权重系数， $Y = m i n d e l, T i, i + 1, δ d$ ， $δ d$ ：给定距离阈值
HMM-DPP ^［33］		$f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2, i f Δ t i ≤ 80 s ω 1 f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2 + ω 2 M, o t h e r w i s e$ 其中M为路径偏好模型^［37］， $ω 1$ 和 $ω 2$ 为权重系数， $ω 1 + ω 2 = 1$
EHMM^［44］	$0, i f A p i, e k i ≥ δ A Z, o t h e r w i s e .$ 其中 $δ A$ 为给定夹角阈值， $Z = f E d k i \| β × c o s A p i, e k i$	$f E x \| β 1 × f E A p i, H c k i, c j i + 1 \| β 2 × f E A H p i, p i + 1, H c k i, c j i + 1 ∣ β 3, i f Δ t i < 60 s f E 1 / S c k i, c j i + 1 d, 1 - 1 \| β 4, o t h e r w i s e$ 其中当 $e k i . e n d = e j i + 1 . s t a r t$ 时，x=1，当 $e k i = e j i + 1$ 时，x=0，否则 $x = ∞$
AOMM^［29］	$f N d k i \| μ, σ 2$	$1 - Δ c k i, c j i + 1 d, 2 × S c k i, c j i + 1 v, 1$
Hybrid HMM^［34］	$f N d k i \| μ, σ 2$	$L R c k i, c j i + 1 × 2 - S c k i, c j i + 1 v, 2$

算法	观测概率 $P r p i \| c j i$	转移概率 $P r c j i + 1 \| c k i$
HMM-Newson ^［27］ EnAcq^［5］，OM2^［39］ Eddy^［40］	$f N d k i \| μ, σ 2$ ，其中f_N为正态分布函数， $μ$ ， $σ$ 为参数，下同	$f E Δ c k i, c j i + 1 d, 1 \| β$ ，其中f_E（）为指数分布函数， $β$ 为参数，下同
OHMM^［28］	$1 w ∫ - w / 2 w / 2 f N x \| d k i, σ 2 d x$ ，其中 $w$ 为候选点 $c k i$ 所在路段宽度	$f E ω 1 Δ c k i, c j i + 1 d, 2 + ω 2 P c k i, c j i + 1 v, 2 \| β$ ，其中 $ω 1$ ， $ω 2$ 为权重参数
HMM-IRL^［24］	$f N d k i \| μ, σ 2$	$f E Δ c k i, c j i + 1 d, 1 + ω ⋅ T C R c k i, c j i + 1 \| β$ ，其中 $ω$ 为权重系数
HMM-Jagadeesh ^［41］		$f E Δ c k i, c j i + 1 d, 3 \| β 1 × f E Δ c k i, c j i + 1 t, 1 \| β 2$
Feature-based ^［42］ INC-RB ^［43］		$f E X T i, i + 1 \| T \| d p i, p i + 1 \| β$ ，其中 $X = ∑ l = 1 m - 1 Y ⋅ e l . l e n + ω ⋅ ψ A e l, e l + 1$ ， $ω$ 为权重系数， $Y = m i n d e l, T i, i + 1, δ d$ ， $δ d$ ：给定距离阈值
HMM-DPP ^［33］		$f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2, i f Δ t i ≤ 80 s ω 1 f E Δ c k i, c j i + 1 d, 1 ∣ β 1 × f E Δ c k i, c j i + 1 v ∣ β 2 + ω 2 M, o t h e r w i s e$ 其中M为路径偏好模型^［37］， $ω 1$ 和 $ω 2$ 为权重系数， $ω 1 + ω 2 = 1$
EHMM^［44］	$0, i f A p i, e k i ≥ δ A Z, o t h e r w i s e .$ 其中 $δ A$ 为给定夹角阈值， $Z = f E d k i \| β × c o s A p i, e k i$	$f E x \| β 1 × f E A p i, H c k i, c j i + 1 \| β 2 × f E A H p i, p i + 1, H c k i, c j i + 1 ∣ β 3, i f Δ t i < 60 s f E 1 / S c k i, c j i + 1 d, 1 - 1 \| β 4, o t h e r w i s e$ 其中当 $e k i . e n d = e j i + 1 . s t a r t$ 时，x=1，当 $e k i = e j i + 1$ 时，x=0，否则 $x = ∞$
AOMM^［29］	$f N d k i \| μ, σ 2$	$1 - Δ c k i, c j i + 1 d, 2 × S c k i, c j i + 1 v, 1$
Hybrid HMM^［34］	$f N d k i \| μ, σ 2$	$L R c k i, c j i + 1 × 2 - S c k i, c j i + 1 v, 2$

[1]	袁水莲, 皮德常, 胥萌. 基于差分隐私的轨迹隐私保护方法[J]. 电子学报, 2021, 49(7): 1266-1273.
[2]	任明荣, 孟娟, 王普. MEMS-INS室内行人定位三维地图匹配算法[J]. 电子学报, 2021, 49(1): 111-116.
[3]	覃鸿, 王守觉. 多权值神经元网络仿生模式识别方法在低训练样本数量非特定人语音识别中与HMM及DTW的比较研究[J]. 电子学报, 2005, 33(5): 957-960.
[4]	王作英;肖熙. 基于段长分布的HMM语音识别模型[J]. 电子学报, 2004, 32(1): 46-49.
[5]	赵力;邹采荣;吴镇扬. 基于FVQ/HMM的无教师说话人自适应[J]. 电子学报, 2002, 30(7): 967-969.
[6]	姚鸿勋;吕雅娟;高文;. 基于色度分析的唇动特征提取与识别[J]. 电子学报, 2002, 30(2): 168-172.
[7]	谢贤亚;王家鼎;李焕润. EM-HMM多频率线跟踪算法[J]. 电子学报, 2002, 30(1): 22-26.
[8]	贺前华;陆以勤;韦岗. 一种新的HMM训练方法[J]. 电子学报, 2000, 28(9): 56-58.
[9]	赵力;邹采荣;吴镇扬. 基于3维空间Viterbi算法的汉语连续语音识别方法[J]. 电子学报, 2000, 28(7): 84-87.

高级地图匹配算法：研究现状和趋势

Advanced Map Matching Algorithms: A Survey and Trends

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 75

相关文章 9

编辑推荐

Metrics