后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载导读本文是 Valhalla面向 OpenStreetMap 的开源路由引擎中地图匹配子库Meili的实现细节技术指南。Meili 基于隐马尔可夫模型HMM将一段带有噪声的 GPS 轨迹序列匹配到真实道路网络上其核心链路包括候选查询 → 状态构建 → Viterbi 搜索 → 道路网络路由 → 结果组装。读完本文你将掌握 Meili 的模块划分、候选查询的空间索引原理、Viterbi 搜索的两种实现差异、路由模块与 Thor 路由的异同、插值策略以及全部核心配置参数并能在源码层面定位每个组件的具体实现文件。整体架构一条从测量点到匹配结果的流水线implementation-details.md给出了 Meili 的顶层数据流图。一条 GPS 轨迹以一连串Measurements测量点进入系统经过候选查询、地图匹配、Viterbi 搜索与路由四步最终输出Match Results匹配结果Measurements / | \ | | | V V V ------------------------------------------------------- | | | [ Candidate Query ] | | | | / | \ | | Candidate | | | Candidate | -- Map Matcher | cluster V V V cluster | | | | [ Map Matching ] --- [ Viterbi Search ] | | \__ [ Routing ] | | / | \ | -------------|------|-------|-------------------------- V V V Match Results这条流水线可以拆成四个核心组件本文后续按序深入候选查询Candidate Query、地图匹配Map Matching含 Viterbi 搜索与路由、门面组件 Map Matcher含插值与匹配结果以及 Map Matcher Factory。Meili 的完整模块文档位于 docs/docs/contributing/architecture/meili算法与概率建模细节见 algorithms.md配置说明见 configuration.md。Candidate Query基于网格空间索引的候选点检索候选查询组件对应文档中的valhalla/meili/candidate_query.h在当前代码库中其实现位于 src/meili/candidate_search.cc接口定义于 valhalla/meili/candidate_search.hCandidateQuery类。职责给定一个位置GPS 测量点和一个半径search_radius找出该半径范围内所有可能被匹配的道路路段。对每一个进入系统的测量点都要执行一次这样的查询得到该点附近的一簇候选点candidate cluster作为后续地图匹配组件的输入。算法原理Meili 采用的空间查询算法简单而高效。查询发生前先将道路网络即一个图块 graph tile按grid.size默认 500×500的方格划分成规则网格随后预计算每条道路路段与哪些方格相交并将路段登记进对应方格。真正的查询则退化为取出半径范围覆盖到的所有方格中的路段集合。这本质上是一种经典的基于网格的静态空间索引grid-based spatial indexing一次测量点查询的代价与扫描的方格数成正比与全网络路段数无关。性能定位与 Loki 子库提供的Loki::Search相比CandidateQuery在内存中维护了一份高分辨率的道路网络几何空间索引/缓存一旦缓存热起来对大批量点的吞吐量显著更高。这正是地图匹配与普通路由场景的关键差异路由请求通常不会带数千个途经点而 GPS 轨迹常以 1Hz 频率上报——一条 15 分钟的轨迹就近 1000 个点。index.md明确指出未来希望用Loki::Search的能力取代CandidateQuery但现阶段性能考量使其保留独立实现。Map Matching基于 HMM 的核心匹配组件地图匹配组件是 HMM 匹配算法的核心实现原文档指向valhalla/meili/map_matching.h。它接收一串候选点簇candidate clusters从每个簇中挑选一个候选点组合成最可能的状态序列即 Viterbi path。匹配组件本身不执行图搜索而是把搜索任务委托给 Viterbi Search 模块自己只负责定义似然度的量化方式——具体来说它继承自ViterbiSearch类并实现其两个虚费用函数ViterbiSearch::TransitionCost转移代价与ViterbiSearch::EmissionCost发射代价。从当前源码结构看valhalla/meili/map_matcher.h这一层职责在MapMatcher门面类中被进一步组合化MapMatcher聚合了ViterbiSearch、TopKSearch、StateContainer、EmissionCostModel与TransitionCostModel见 map_matcher.h发射与转移代价模型成为独立类分别实现在 src/meili/transition_cost_model.cc 与 valhalla/meili/map_matcher.h 引用的 emission/transition cost model 头文件中——模块职责与原文档完全对应只是组织方式随演进有所调整。State候选点的包装将一簇候选点送入匹配组件时每个候选点会被附加两个属性一个唯一的 ID和一份相同的时刻戳time。ID 用于标识一个状态state时刻戳则说明该候选点来自哪一个簇对应轨迹中的第几个测量点。代码内部把这种包装后的候选点称为state其类型定义见 valhalla/meili/stateid.hStateId同时编码列索引 0..n 与列内候选索引 0..m对应index.md中对StateId的说明。Viterbi Search两种实现、统一接口Viterbi Search 模块专注于在 HMM 语境下的 trellis 图网格图即 DAG中寻找最可能的序列Viterbi path。它在 valhalla/meili/viterbi_search.h 中定义提供统一接口IViterbiSearchviterbi_search.h通过IEmissionCostModel与ITransitionCostModel两个std::function类型的代价模型注入发射/转移代价并提供AddStateId、RemoveStateId、SearchWinner、Predecessor、AccumulatedCost等操作实现一NaiveViterbiSearchMaximizeviterbi_search.h实现朴素的 Viterbi 算法通过模板参数支持最大化与最小化两种目标实现二ViterbiSearchviterbi_search.h实现基于Dijkstra 的惰性 Viterbi 算法内部使用SPQueueStateLabel优先队列逐层扫描仅支持最小化目标因为 Dijkstra 本质是求解最短路径。两种实现都能找到最优路径。Meili 之所以让匹配组件继承基于 Dijkstra 的ViterbiSearch是因为它在理论上性能更好见下文算法原理部分。如果你要针对其他道路网络数据源如 pgRouting开发自己的地图匹配算法完全可以照MapMatching的做法根据你的优化目标继承上述两个实现之一并实现IViterbiSearch::TransitionCost与IViterbiSearch::EmissionCost即可——这正是该接口设计为可扩展模型的原因。Routing基于 AStar 的单源多目标最短路路由模块文档指向valhalla/meili/routing.h当前实现见 src/meili/routing.cc负责在道路网络中求解两个候选点之间的最短路径SP。路径距离是转移代价计算MapMatching::TransitionCost所必需的输入并且若两个候选点都被选入最终的最可能序列这条路径就是它们各自测量点之间被推断出来的实际行驶路径。几个关键实现特征AStar 单源多目标SP 算法基于 A*从单一源点向多个目标路由。A* 在此很合适因为目标集合正是测量点周围的那一簇候选点由候选查询提供——于是启发式代价可以直接瞄准测量点的位置来计算。返回搜索树而非路径SP 算法不直接为你构造路径而是返回搜索树即LabelSet。搜索树随后被保存在源状态中供后续路径重建使用。对应地routing.h 中的Label类继承自sif::EdgeLabel额外携带nodeid_、dest_目标索引、source_/target_边内起止比例与turn_cost_等信息。转弯代价聚合寻路过程中会聚合路段之间的转弯代价turn cost该代价作为转移代价MapMatching::TransitionCost中独立的一部分用于惩罚多转弯的路径。按节点而非按边扫描与 Thor 中的路径算法不同Meili 的 SP 算法扫描节点而非边因此此处不考虑转弯限制turn restriction。Viterbi Search vs. Routing相似与差异文档特别强调这两个模块的异同维度Viterbi SearchRouting目标最可能的候选序列最大似然最短距离路径最小代价底层算法均基于 Dijkstra 思想均基于 Dijkstra 思想此处为 A*图模型trellis 图HMM 网格图道路网络图两者都在寻找最优路径但优化目标与作用在图模型上截然不同。底层算法原理从概率模型到对数代价变换要真正理解 TransitionCost / EmissionCost 的含义需要补充 algorithms.md 中的建模过程。Meili 采用 2009 年 Paul Newson 与 John Krumm 提出的 HMM 地图匹配方法给定一串 GPS 测量点HMM 中的观测值每个测量点必须匹配到它附近若干潜在候选道路路段之一HMM 中的隐状态问题归结为求最可能的隐状态序列。上图展示了一段含噪声的 4 个测量点的 GPS 序列图中由绿到红每个测量点周围散布着若干青色小标记表示的候选点而最终被选中的最可能序列是0, 4, 9, 11它们连成了红色的匹配路径。图模型DAG 与两级概率上述问题可建模为一张有向无环图DAG每个测量点对应一列节点节点即候选点——元组(road segment, offset)表示道路路段上的某个位置边(u, v)表示节点 u 的取舍会影响 v。文档中的例子节点 9 到节点 12 虽然看起来很近实际绕行很远因此节点 12 不太可能是最后一个测量点的匹配。图中一个测量点只受其前一测量点影响。两个概率模型联合量化测量点匹配到某节点的可能性发射概率emission probability节点离其测量点越近匹配的可能性越大高斯分布转移概率transition probability节点 u 到 v 的路网步行距离越接近测量点间距v 的测量点匹配到它的可能性越大经验分布。路径概率定义为路径上所有边含首节点发射项的联合概率乘积。为了便于求解图中加入虚拟源点 s 与汇点 t并将相关发射/转移概率设为 1.0任务变为求 s 到 t 概率最大的路径。为什么用 Dijkstra 而不是朴素 Viterbi朴素 Viterbi 算法按层 BFS 展开并记录每节点最优解与拓扑排序都能求最优路径但二者都必须探索全部边。在地图匹配模型中探索一条边是昂贵的计算边(u,v)的转移概率需要在道路网络中先求 u、v 之间的最短路径。若轨迹有 S 个测量点、每个测量点平均 T 个状态则朴素 Viterbi/拓扑排序要做S * T * T次最短路计算在 T 较大的城市密集区域不可接受。Dijkstra 算法的优势在于贪心按最可能顺序出队节点一旦目标被出队最优解即已确定其余节点可以安全丢弃从而大量减少转移概率计算次数。但 Dijkstra 求解的是最小化问题而我们需要最大化路径概率因此要做对数变换由于log(a*b) log(a) log(b)最大化∏(E(u)·T(u,v))等价于最小化Σ(-lg E(u) -lg T(u,v))。变换后发射概率变为节点代价转移概率变为边代价且代价均为非负——问题就变成了标准的 Dijkstra 可求解形式。文档 algorithms.md 中给出了完整的伪代码与数学推导值得精读。Map Matcher连接一切的 Facade门面组件MapMatchervalhalla/meili/map_matcher.h把候选查询组件与地图匹配组件连接起来对外提供简单接口——正如架构图中所示它像一个黑盒输入测量点序列输出匹配结果。除此之外它还会在测量点进入匹配组件前做内部过滤工作。主入口是OfflineMatch(const std::vectorMeasurement measurements, uint32_t k 1)map_matcher.hk参数支持返回 top-k 备选路径测量点批量组织工作由AppendMeasurements完成map_matcher.h。插值Interpolation并非每个点都要参与匹配架构图中未画出的一点并非所有进入的测量点都会被送入匹配组件。若连续的几个测量点空间上过于接近则只发送第一个点其余点将被插值进最终匹配路线。文档用直路示例说明下面的数字代表沿一条直路按顺序排列的测量点每个空格为 1 米。若interpolation_distance设为 10 米则只发送1*、4*、7*彼此相距超过 10 米测量点 2、3 被插值进1*→4*的路线测量点 5 插值进4*→7*的路线依此类推1* 2 3 4* 5 8 7* 9 10这样设计有两个理由性能对高密度轨迹可以大幅减少参与匹配计算的测量点数量抗噪声若两个连续测量点过近后者很可能因噪声误差而被定位到前者的上游。这种误差在auto、bicycle等禁止 U 形转弯的模式下会造成错误路径推断。例如上图中 8 的真实位置应在7*下游右侧但噪声可能把它挪到上游左侧在auto模式下这种轻微偏移会导致7*→8 无路可走或路径错误。改为插值 8 而非参与匹配即可规避此问题。index.md补充了插值的另一层细节匹配完成后会再次遍历状态对把被跳过插值的输入点逐个投影到两状态间的路线几何上生成它们的MatchResult从而保证输出序列顺序不变p4 先于 p5 先于 p6 先于 p7。注意轨迹的首尾点不能插值如 p9 靠近末点 p8 的示例中p9 因靠近不可插值的末点而被插值而末点本身必须参与匹配。Match Result测量点对应的匹配结果每个测量点对应一个匹配结果MatchResult定义于 valhalla/meili/match_result.h。它告诉你测量点被匹配或插值到了哪条道路路段上、匹配位置坐标、到该位置的距离等。若测量点是被匹配的结果还会附带对应的状态 ID。由于路由搜索树已保存在状态上你可以凭该 ID 找到状态再利用 valhalla/meili/match_route.h实现见 src/meili/match_route.cc其中MergeRoute等辅助函数声明于 map_matcher.h中的辅助函数重建整条路线。路径重建与 EdgeSegmentindex.md对路由重建做了更细的说明ConstructRoute利用状态拿到保存在LabelSet中的一串EdgeLabel每个状态知道自己到达目标状态时最后看到的EdgeLabel因此沿EdgeLabel前驱链回溯到源状态即可还原路径类似链表但用LabelSet索引而非指针。这些EdgeLabel随后被组装成EdgeSegment对象——它记录所属图边、使用了边的多少、首尾落在该段上的MatchResult以及该段之后是否存在不连续discontinuity两列之间所有候选对都找不到路径时发生。遇到标记为break/break_through的位置EdgeSegment会被切分以对应最终输出中的路线分段route legs。OfflineMatch的k参数还支撑**备选路径alternatives**能力对应 API 中的 best_paths可返回 top-k 条最可能路径但有两个限制——其一若某条结果中出现不连续其后不再返回更多结果其二冗余路径被剔除若某条结果的EdgeSegment序列与先前结果完全一致则不再返回常见于交叉口两个候选点不同但路径边序列相同。Map Matcher Factory低成本创建与数据共享MapMatcherFactoryvalhalla/meili/map_matcher_factory.h用于便捷地创建地图匹配器。传入 Valhalla 配置和出行模式它会读取参数并为该模式创建一个MapMatcher。工厂同时维护一份GraphReader 实例与一份 CandidateQuery 实例并在其所有匹配器之间共享——正是由于这种数据共享从工厂创建匹配器非常廉价。注意工厂和匹配器都不是线程安全的需要调用方自行保证互斥。库 API 层面的用法详见 library-api.md构造工厂meili::MapMatcherFactory(const boost::property_tree::ptree config)传入合法的配置对象否则抛出std::invalid_argument创建匹配器meili::MapMatcherFactory::Create(const std::string mode_name)模式参数无效时同样可能抛std::invalid_argument离线匹配std::vectorMatchResult meili::MapMatcher::OfflineMatch(const std::vectorMeasurement sequence)返回与输入测量点序列一一对应的匹配结果序列MatchResult的关键访问器lnglat()匹配后的坐标、distance()测量点到匹配坐标的距离、edgeid()Valhalla 瓦片数据中标识边与节点的GraphId。工厂实例化一次即可但必须存活到其创建的所有匹配器被销毁之后。配置参数详解要启动 Meili 服务或实例化MapMatcherFactory都需要传入 Valhalla 配置文件Meili 的全部配置都位于配置的meili节点下。所有出行模式节点auto、pedestrian、bicycle、multimodal都可以持有自己的参数设置否则使用default节点中的设置。地图匹配参数以下参数控制匹配过程的精度与性能完整表格见 configuration.md参数说明默认值sigma_z非负值指定输入 GPS 序列的精度正态分布的方差同时用于加权测量点的发射代价4.07beta非负经验值用于加权两个连续候选点之间的转移代价3max_route_distance_factor非负值限制路由搜索范围到下一测量点的距离 × 该因子5max_route_time_factor非负值限制路由搜索范围到下一测量点的时间 × 该因子5breakage_distance非负值米。若两个连续测量点相距超过该值则二者之间的连通性不予考虑2000米interpolation_distance若两个连续测量点距离小于该值则后一个点被插值进匹配路线10米search_radius非负值米指定为每个测量点搜索道路候选点的半径50米max_search_radius指定search_radius的上界100米turn_penalty_factor非负值惩罚从一个路段转向下一个路段0米参数间的协同关系search_radius直接决定候选查询的扫描范围过小会漏掉可能的候选点过大则显著拖慢匹配sigma_z与beta分别决定发射与转移代价的权重形状直接影响 HMM 的似然量化interpolation_distance决定跳过多少近邻点max_route_distance_factor/max_route_time_factor是路由搜索的剪枝边界breakage_distance用于处理轨迹中的长间隙信号丢失turn_penalty_factor让匹配结果倾向于少转弯的路径。服务参数以下参数仅用于 Meili 服务HTTP API参数说明默认值mode指定默认出行模式multimodalcustomizable允许通过 URL 查询参数定制的参数列表[mode, search_radius]verbose控制用于调试的详细输出false服务 API 用法Meili 服务接受 POST 请求请求体为 GeoJSON 特征或几何对象类型为MultiPoint或LineString。URL 参数方面mode可选auto、bicycle、pedestrian、multimodal默认multimodalsearch_radius为[0, 100]内的数值服务默认 40。指定出行模式可以限制可匹配的道路类型如auto只考虑可行驶道路从而提升精度与速度模式未知时用默认multimodal考虑所有道路类型。当 GPS 精度未知时过大的search_radius会拖慢匹配过小又可能漏掉候选点。响应为 GeoJSONMultiLineStringfeature匹配坐标存放在属性matched_coordinates中未匹配到任何道路的测量点对应null。一个完整请求示例详见 service-api.mdcurl -X POST https://localhost:8002?search_radius35modeauto{ coordinates: [ [ 13.288925, 52.438512 ], [ 13.288938, 52.438938 ], [ 13.288904, 52.439169 ], [ 13.288821, 52.439398 ], [ 13.288824, 52.439491 ], [ 13.288824, 52.439563 ] ] }响应中每条输入坐标都会对应一个匹配后的坐标如matched_coordinates数组所示若匹配失败则为null。Thor 合约与工程边界index.md明确了 Meili 的定位边界Meili 本身没有对外 API曾经的独立 API 已被重构它通过 Valhalla 其余路由 API 被访问因此必须履行与 Thor 相同的合约——即一系列Location每个位置填入选中的候选点由MatchResult转换而来加上一条由PathInfo组成的路径表示路径上的边及其代价/时长。Meili 主入口OfflineMatch返回的MatchResults与EdgeSegments需要经过FormPath把EdgeSegment组装成PathInfo向量与TripLegBuilder::Build每段路线一次转换为 Thor 合约要求的输出格式。此外工程上最棘手的特殊情形是节点吸附候选node snapped candidates当测量点在图上最近的点恰是连接多条边的节点时既要避免为每条边都生成候选点会成倍放大 Viterbi 的路径组合数量因此路由器中用特殊逻辑将节点候选当作单一候选处理又要处理节点不指向边而MatchResult/EdgeSegment又必须引用边的歧义问题——例如轨迹切分点落在节点上时前一段结束在一条边、后一段开始于另一条边而同一个只存一条边引用的MatchResult会与其中一段冲突。结语源码阅读路线图将本文内容与源码对照阅读可沿此路径深入候选检索看 src/meili/candidate_search.ccHMM 代价模型看 src/meili/transition_cost_model.ccViterbi 搜索看 valhalla/meili/viterbi_search.h 与 src/meili/viterbi_search.cc路网最短路径看 src/meili/routing.cc门面与结果组装看 valhalla/meili/map_matcher.h、src/meili/map_matcher.cc、src/meili/match_route.cctop-k 备选路径见 src/meili/topk_search.cc。配套的测试用例可在 test/mapmatch.cc、test/map_matcher_factory.cc 与 test/viterbi_search.cc 中找到它们展示了上述各模块在实际数据上的行为验证。赞分享后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载相关推荐Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解 本文以 Valhalla 仓库中 Meili 架后端Valhalla地图匹配技术详解Meili库如何实现GPS轨迹智能修正Valhalla地图匹配技术详解Meili库如何实现GPS轨迹智能修正 地图匹配技术是现代导航系统的核心功能之一它能将原始的GPS轨迹点智能地修正到实际的道后端Valhalla Loki 源码级解析从坐标到路由图的候选边关联引擎Valhalla Loki 源码级解析从坐标到路由图的候选边关联引擎 导读 本文以 Valhalla 官方架构文档 docs/docs/contributin后端上一篇Anaconda-mode源码解析Python后端脚本关键函数详解下一篇Frontend Masters Bootcamp 计算器项目HTML/CSS/JS综合实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/10 1:55:50 · 阅读 1.2k Valhalla Meili 地图匹配引擎实现细节深度解析：从候选查询到 Viterbi 搜索
后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载导读本文是 Valhalla面向 OpenStreetMap 的开源路由引擎中地图匹配子库Meili的实现细节技术指南。Meili 基于隐马尔可夫模型HMM将一段带有噪声的 GPS 轨迹序列匹配到真实道路网络上其核心链路包括候选查询 → 状态构建 → Viterbi 搜索 → 道路网络路由 → 结果组装。读完本文你将掌握 Meili 的模块划分、候选查询的空间索引原理、Viterbi 搜索的两种实现差异、路由模块与 Thor 路由的异同、插值策略以及全部核心配置参数并能在源码层面定位每个组件的具体实现文件。整体架构一条从测量点到匹配结果的流水线implementation-details.md给出了 Meili 的顶层数据流图。一条 GPS 轨迹以一连串Measurements测量点进入系统经过候选查询、地图匹配、Viterbi 搜索与路由四步最终输出Match Results匹配结果Measurements / | \ | | | V V V ------------------------------------------------------- | | | [ Candidate Query ] | | | | / | \ | | Candidate | | | Candidate | -- Map Matcher | cluster V V V cluster | | | | [ Map Matching ] --- [ Viterbi Search ] | | \__ [ Routing ] | | / | \ | -------------|------|-------|-------------------------- V V V Match Results这条流水线可以拆成四个核心组件本文后续按序深入候选查询Candidate Query、地图匹配Map Matching含 Viterbi 搜索与路由、门面组件 Map Matcher含插值与匹配结果以及 Map Matcher Factory。Meili 的完整模块文档位于 docs/docs/contributing/architecture/meili算法与概率建模细节见 algorithms.md配置说明见 configuration.md。Candidate Query基于网格空间索引的候选点检索候选查询组件对应文档中的valhalla/meili/candidate_query.h在当前代码库中其实现位于 src/meili/candidate_search.cc接口定义于 valhalla/meili/candidate_search.hCandidateQuery类。职责给定一个位置GPS 测量点和一个半径search_radius找出该半径范围内所有可能被匹配的道路路段。对每一个进入系统的测量点都要执行一次这样的查询得到该点附近的一簇候选点candidate cluster作为后续地图匹配组件的输入。算法原理Meili 采用的空间查询算法简单而高效。查询发生前先将道路网络即一个图块 graph tile按grid.size默认 500×500的方格划分成规则网格随后预计算每条道路路段与哪些方格相交并将路段登记进对应方格。真正的查询则退化为取出半径范围覆盖到的所有方格中的路段集合。这本质上是一种经典的基于网格的静态空间索引grid-based spatial indexing一次测量点查询的代价与扫描的方格数成正比与全网络路段数无关。性能定位与 Loki 子库提供的Loki::Search相比CandidateQuery在内存中维护了一份高分辨率的道路网络几何空间索引/缓存一旦缓存热起来对大批量点的吞吐量显著更高。这正是地图匹配与普通路由场景的关键差异路由请求通常不会带数千个途经点而 GPS 轨迹常以 1Hz 频率上报——一条 15 分钟的轨迹就近 1000 个点。index.md明确指出未来希望用Loki::Search的能力取代CandidateQuery但现阶段性能考量使其保留独立实现。Map Matching基于 HMM 的核心匹配组件地图匹配组件是 HMM 匹配算法的核心实现原文档指向valhalla/meili/map_matching.h。它接收一串候选点簇candidate clusters从每个簇中挑选一个候选点组合成最可能的状态序列即 Viterbi path。匹配组件本身不执行图搜索而是把搜索任务委托给 Viterbi Search 模块自己只负责定义似然度的量化方式——具体来说它继承自ViterbiSearch类并实现其两个虚费用函数ViterbiSearch::TransitionCost转移代价与ViterbiSearch::EmissionCost发射代价。从当前源码结构看valhalla/meili/map_matcher.h这一层职责在MapMatcher门面类中被进一步组合化MapMatcher聚合了ViterbiSearch、TopKSearch、StateContainer、EmissionCostModel与TransitionCostModel见 map_matcher.h发射与转移代价模型成为独立类分别实现在 src/meili/transition_cost_model.cc 与 valhalla/meili/map_matcher.h 引用的 emission/transition cost model 头文件中——模块职责与原文档完全对应只是组织方式随演进有所调整。State候选点的包装将一簇候选点送入匹配组件时每个候选点会被附加两个属性一个唯一的 ID和一份相同的时刻戳time。ID 用于标识一个状态state时刻戳则说明该候选点来自哪一个簇对应轨迹中的第几个测量点。代码内部把这种包装后的候选点称为state其类型定义见 valhalla/meili/stateid.hStateId同时编码列索引 0..n 与列内候选索引 0..m对应index.md中对StateId的说明。Viterbi Search两种实现、统一接口Viterbi Search 模块专注于在 HMM 语境下的 trellis 图网格图即 DAG中寻找最可能的序列Viterbi path。它在 valhalla/meili/viterbi_search.h 中定义提供统一接口IViterbiSearchviterbi_search.h通过IEmissionCostModel与ITransitionCostModel两个std::function类型的代价模型注入发射/转移代价并提供AddStateId、RemoveStateId、SearchWinner、Predecessor、AccumulatedCost等操作实现一NaiveViterbiSearchMaximizeviterbi_search.h实现朴素的 Viterbi 算法通过模板参数支持最大化与最小化两种目标实现二ViterbiSearchviterbi_search.h实现基于Dijkstra 的惰性 Viterbi 算法内部使用SPQueueStateLabel优先队列逐层扫描仅支持最小化目标因为 Dijkstra 本质是求解最短路径。两种实现都能找到最优路径。Meili 之所以让匹配组件继承基于 Dijkstra 的ViterbiSearch是因为它在理论上性能更好见下文算法原理部分。如果你要针对其他道路网络数据源如 pgRouting开发自己的地图匹配算法完全可以照MapMatching的做法根据你的优化目标继承上述两个实现之一并实现IViterbiSearch::TransitionCost与IViterbiSearch::EmissionCost即可——这正是该接口设计为可扩展模型的原因。Routing基于 AStar 的单源多目标最短路路由模块文档指向valhalla/meili/routing.h当前实现见 src/meili/routing.cc负责在道路网络中求解两个候选点之间的最短路径SP。路径距离是转移代价计算MapMatching::TransitionCost所必需的输入并且若两个候选点都被选入最终的最可能序列这条路径就是它们各自测量点之间被推断出来的实际行驶路径。几个关键实现特征AStar 单源多目标SP 算法基于 A*从单一源点向多个目标路由。A* 在此很合适因为目标集合正是测量点周围的那一簇候选点由候选查询提供——于是启发式代价可以直接瞄准测量点的位置来计算。返回搜索树而非路径SP 算法不直接为你构造路径而是返回搜索树即LabelSet。搜索树随后被保存在源状态中供后续路径重建使用。对应地routing.h 中的Label类继承自sif::EdgeLabel额外携带nodeid_、dest_目标索引、source_/target_边内起止比例与turn_cost_等信息。转弯代价聚合寻路过程中会聚合路段之间的转弯代价turn cost该代价作为转移代价MapMatching::TransitionCost中独立的一部分用于惩罚多转弯的路径。按节点而非按边扫描与 Thor 中的路径算法不同Meili 的 SP 算法扫描节点而非边因此此处不考虑转弯限制turn restriction。Viterbi Search vs. Routing相似与差异文档特别强调这两个模块的异同维度Viterbi SearchRouting目标最可能的候选序列最大似然最短距离路径最小代价底层算法均基于 Dijkstra 思想均基于 Dijkstra 思想此处为 A*图模型trellis 图HMM 网格图道路网络图两者都在寻找最优路径但优化目标与作用在图模型上截然不同。底层算法原理从概率模型到对数代价变换要真正理解 TransitionCost / EmissionCost 的含义需要补充 algorithms.md 中的建模过程。Meili 采用 2009 年 Paul Newson 与 John Krumm 提出的 HMM 地图匹配方法给定一串 GPS 测量点HMM 中的观测值每个测量点必须匹配到它附近若干潜在候选道路路段之一HMM 中的隐状态问题归结为求最可能的隐状态序列。上图展示了一段含噪声的 4 个测量点的 GPS 序列图中由绿到红每个测量点周围散布着若干青色小标记表示的候选点而最终被选中的最可能序列是0, 4, 9, 11它们连成了红色的匹配路径。图模型DAG 与两级概率上述问题可建模为一张有向无环图DAG每个测量点对应一列节点节点即候选点——元组(road segment, offset)表示道路路段上的某个位置边(u, v)表示节点 u 的取舍会影响 v。文档中的例子节点 9 到节点 12 虽然看起来很近实际绕行很远因此节点 12 不太可能是最后一个测量点的匹配。图中一个测量点只受其前一测量点影响。两个概率模型联合量化测量点匹配到某节点的可能性发射概率emission probability节点离其测量点越近匹配的可能性越大高斯分布转移概率transition probability节点 u 到 v 的路网步行距离越接近测量点间距v 的测量点匹配到它的可能性越大经验分布。路径概率定义为路径上所有边含首节点发射项的联合概率乘积。为了便于求解图中加入虚拟源点 s 与汇点 t并将相关发射/转移概率设为 1.0任务变为求 s 到 t 概率最大的路径。为什么用 Dijkstra 而不是朴素 Viterbi朴素 Viterbi 算法按层 BFS 展开并记录每节点最优解与拓扑排序都能求最优路径但二者都必须探索全部边。在地图匹配模型中探索一条边是昂贵的计算边(u,v)的转移概率需要在道路网络中先求 u、v 之间的最短路径。若轨迹有 S 个测量点、每个测量点平均 T 个状态则朴素 Viterbi/拓扑排序要做S * T * T次最短路计算在 T 较大的城市密集区域不可接受。Dijkstra 算法的优势在于贪心按最可能顺序出队节点一旦目标被出队最优解即已确定其余节点可以安全丢弃从而大量减少转移概率计算次数。但 Dijkstra 求解的是最小化问题而我们需要最大化路径概率因此要做对数变换由于log(a*b) log(a) log(b)最大化∏(E(u)·T(u,v))等价于最小化Σ(-lg E(u) -lg T(u,v))。变换后发射概率变为节点代价转移概率变为边代价且代价均为非负——问题就变成了标准的 Dijkstra 可求解形式。文档 algorithms.md 中给出了完整的伪代码与数学推导值得精读。Map Matcher连接一切的 Facade门面组件MapMatchervalhalla/meili/map_matcher.h把候选查询组件与地图匹配组件连接起来对外提供简单接口——正如架构图中所示它像一个黑盒输入测量点序列输出匹配结果。除此之外它还会在测量点进入匹配组件前做内部过滤工作。主入口是OfflineMatch(const std::vectorMeasurement measurements, uint32_t k 1)map_matcher.hk参数支持返回 top-k 备选路径测量点批量组织工作由AppendMeasurements完成map_matcher.h。插值Interpolation并非每个点都要参与匹配架构图中未画出的一点并非所有进入的测量点都会被送入匹配组件。若连续的几个测量点空间上过于接近则只发送第一个点其余点将被插值进最终匹配路线。文档用直路示例说明下面的数字代表沿一条直路按顺序排列的测量点每个空格为 1 米。若interpolation_distance设为 10 米则只发送1*、4*、7*彼此相距超过 10 米测量点 2、3 被插值进1*→4*的路线测量点 5 插值进4*→7*的路线依此类推1* 2 3 4* 5 8 7* 9 10这样设计有两个理由性能对高密度轨迹可以大幅减少参与匹配计算的测量点数量抗噪声若两个连续测量点过近后者很可能因噪声误差而被定位到前者的上游。这种误差在auto、bicycle等禁止 U 形转弯的模式下会造成错误路径推断。例如上图中 8 的真实位置应在7*下游右侧但噪声可能把它挪到上游左侧在auto模式下这种轻微偏移会导致7*→8 无路可走或路径错误。改为插值 8 而非参与匹配即可规避此问题。index.md补充了插值的另一层细节匹配完成后会再次遍历状态对把被跳过插值的输入点逐个投影到两状态间的路线几何上生成它们的MatchResult从而保证输出序列顺序不变p4 先于 p5 先于 p6 先于 p7。注意轨迹的首尾点不能插值如 p9 靠近末点 p8 的示例中p9 因靠近不可插值的末点而被插值而末点本身必须参与匹配。Match Result测量点对应的匹配结果每个测量点对应一个匹配结果MatchResult定义于 valhalla/meili/match_result.h。它告诉你测量点被匹配或插值到了哪条道路路段上、匹配位置坐标、到该位置的距离等。若测量点是被匹配的结果还会附带对应的状态 ID。由于路由搜索树已保存在状态上你可以凭该 ID 找到状态再利用 valhalla/meili/match_route.h实现见 src/meili/match_route.cc其中MergeRoute等辅助函数声明于 map_matcher.h中的辅助函数重建整条路线。路径重建与 EdgeSegmentindex.md对路由重建做了更细的说明ConstructRoute利用状态拿到保存在LabelSet中的一串EdgeLabel每个状态知道自己到达目标状态时最后看到的EdgeLabel因此沿EdgeLabel前驱链回溯到源状态即可还原路径类似链表但用LabelSet索引而非指针。这些EdgeLabel随后被组装成EdgeSegment对象——它记录所属图边、使用了边的多少、首尾落在该段上的MatchResult以及该段之后是否存在不连续discontinuity两列之间所有候选对都找不到路径时发生。遇到标记为break/break_through的位置EdgeSegment会被切分以对应最终输出中的路线分段route legs。OfflineMatch的k参数还支撑**备选路径alternatives**能力对应 API 中的 best_paths可返回 top-k 条最可能路径但有两个限制——其一若某条结果中出现不连续其后不再返回更多结果其二冗余路径被剔除若某条结果的EdgeSegment序列与先前结果完全一致则不再返回常见于交叉口两个候选点不同但路径边序列相同。Map Matcher Factory低成本创建与数据共享MapMatcherFactoryvalhalla/meili/map_matcher_factory.h用于便捷地创建地图匹配器。传入 Valhalla 配置和出行模式它会读取参数并为该模式创建一个MapMatcher。工厂同时维护一份GraphReader 实例与一份 CandidateQuery 实例并在其所有匹配器之间共享——正是由于这种数据共享从工厂创建匹配器非常廉价。注意工厂和匹配器都不是线程安全的需要调用方自行保证互斥。库 API 层面的用法详见 library-api.md构造工厂meili::MapMatcherFactory(const boost::property_tree::ptree config)传入合法的配置对象否则抛出std::invalid_argument创建匹配器meili::MapMatcherFactory::Create(const std::string mode_name)模式参数无效时同样可能抛std::invalid_argument离线匹配std::vectorMatchResult meili::MapMatcher::OfflineMatch(const std::vectorMeasurement sequence)返回与输入测量点序列一一对应的匹配结果序列MatchResult的关键访问器lnglat()匹配后的坐标、distance()测量点到匹配坐标的距离、edgeid()Valhalla 瓦片数据中标识边与节点的GraphId。工厂实例化一次即可但必须存活到其创建的所有匹配器被销毁之后。配置参数详解要启动 Meili 服务或实例化MapMatcherFactory都需要传入 Valhalla 配置文件Meili 的全部配置都位于配置的meili节点下。所有出行模式节点auto、pedestrian、bicycle、multimodal都可以持有自己的参数设置否则使用default节点中的设置。地图匹配参数以下参数控制匹配过程的精度与性能完整表格见 configuration.md参数说明默认值sigma_z非负值指定输入 GPS 序列的精度正态分布的方差同时用于加权测量点的发射代价4.07beta非负经验值用于加权两个连续候选点之间的转移代价3max_route_distance_factor非负值限制路由搜索范围到下一测量点的距离 × 该因子5max_route_time_factor非负值限制路由搜索范围到下一测量点的时间 × 该因子5breakage_distance非负值米。若两个连续测量点相距超过该值则二者之间的连通性不予考虑2000米interpolation_distance若两个连续测量点距离小于该值则后一个点被插值进匹配路线10米search_radius非负值米指定为每个测量点搜索道路候选点的半径50米max_search_radius指定search_radius的上界100米turn_penalty_factor非负值惩罚从一个路段转向下一个路段0米参数间的协同关系search_radius直接决定候选查询的扫描范围过小会漏掉可能的候选点过大则显著拖慢匹配sigma_z与beta分别决定发射与转移代价的权重形状直接影响 HMM 的似然量化interpolation_distance决定跳过多少近邻点max_route_distance_factor/max_route_time_factor是路由搜索的剪枝边界breakage_distance用于处理轨迹中的长间隙信号丢失turn_penalty_factor让匹配结果倾向于少转弯的路径。服务参数以下参数仅用于 Meili 服务HTTP API参数说明默认值mode指定默认出行模式multimodalcustomizable允许通过 URL 查询参数定制的参数列表[mode, search_radius]verbose控制用于调试的详细输出false服务 API 用法Meili 服务接受 POST 请求请求体为 GeoJSON 特征或几何对象类型为MultiPoint或LineString。URL 参数方面mode可选auto、bicycle、pedestrian、multimodal默认multimodalsearch_radius为[0, 100]内的数值服务默认 40。指定出行模式可以限制可匹配的道路类型如auto只考虑可行驶道路从而提升精度与速度模式未知时用默认multimodal考虑所有道路类型。当 GPS 精度未知时过大的search_radius会拖慢匹配过小又可能漏掉候选点。响应为 GeoJSONMultiLineStringfeature匹配坐标存放在属性matched_coordinates中未匹配到任何道路的测量点对应null。一个完整请求示例详见 service-api.mdcurl -X POST https://localhost:8002?search_radius35modeauto{ coordinates: [ [ 13.288925, 52.438512 ], [ 13.288938, 52.438938 ], [ 13.288904, 52.439169 ], [ 13.288821, 52.439398 ], [ 13.288824, 52.439491 ], [ 13.288824, 52.439563 ] ] }响应中每条输入坐标都会对应一个匹配后的坐标如matched_coordinates数组所示若匹配失败则为null。Thor 合约与工程边界index.md明确了 Meili 的定位边界Meili 本身没有对外 API曾经的独立 API 已被重构它通过 Valhalla 其余路由 API 被访问因此必须履行与 Thor 相同的合约——即一系列Location每个位置填入选中的候选点由MatchResult转换而来加上一条由PathInfo组成的路径表示路径上的边及其代价/时长。Meili 主入口OfflineMatch返回的MatchResults与EdgeSegments需要经过FormPath把EdgeSegment组装成PathInfo向量与TripLegBuilder::Build每段路线一次转换为 Thor 合约要求的输出格式。此外工程上最棘手的特殊情形是节点吸附候选node snapped candidates当测量点在图上最近的点恰是连接多条边的节点时既要避免为每条边都生成候选点会成倍放大 Viterbi 的路径组合数量因此路由器中用特殊逻辑将节点候选当作单一候选处理又要处理节点不指向边而MatchResult/EdgeSegment又必须引用边的歧义问题——例如轨迹切分点落在节点上时前一段结束在一条边、后一段开始于另一条边而同一个只存一条边引用的MatchResult会与其中一段冲突。结语源码阅读路线图将本文内容与源码对照阅读可沿此路径深入候选检索看 src/meili/candidate_search.ccHMM 代价模型看 src/meili/transition_cost_model.ccViterbi 搜索看 valhalla/meili/viterbi_search.h 与 src/meili/viterbi_search.cc路网最短路径看 src/meili/routing.cc门面与结果组装看 valhalla/meili/map_matcher.h、src/meili/map_matcher.cc、src/meili/match_route.cctop-k 备选路径见 src/meili/topk_search.cc。配套的测试用例可在 test/mapmatch.cc、test/map_matcher_factory.cc 与 test/viterbi_search.cc 中找到它们展示了上述各模块在实际数据上的行为验证。赞分享后端【免费下载链接】valhallaOpen Source Routing Engine for OpenStreetMap项目地址https://gitcode.com/gh_mirrors/va/valhalla点击查看免费下载相关推荐Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解Valhalla Meili 地图匹配算法解析从 HMM 建模到 Viterbi 与 Dijkstra 求解 本文以 Valhalla 仓库中 Meili 架后端Valhalla地图匹配技术详解Meili库如何实现GPS轨迹智能修正Valhalla地图匹配技术详解Meili库如何实现GPS轨迹智能修正 地图匹配技术是现代导航系统的核心功能之一它能将原始的GPS轨迹点智能地修正到实际的道后端Valhalla Loki 源码级解析从坐标到路由图的候选边关联引擎Valhalla Loki 源码级解析从坐标到路由图的候选边关联引擎 导读 本文以 Valhalla 官方架构文档 docs/docs/contributin后端上一篇Anaconda-mode源码解析Python后端脚本关键函数详解下一篇Frontend Masters Bootcamp 计算器项目HTML/CSS/JS综合实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考