跳至主要內容

GraphHopper-开源路径规划引擎

程序员李某某大约 37 分钟

GraphHopper-开源路径规划引擎

概述

功能

CH

CH 是一种 预处理加速技术，通过在数据导入后构建层级化的"捷径"网络，将路径计算复杂度从 O(n) 降至 O(√n)，极大提升实时路由查询速度。

Contraction Hierarchies算法即是在原始Graph先进行预处理，提前先算好一些点与点之间的最短路径距离(Shortcuts)，简化Graph的Edge个数，再利用改进的Bidirection Dijkstra找到最短路径。

技术实现细节

  1. 数据结构扩展
    • Shortcut Storage（捷径存储） 在预处理阶段，算法自动合并线性路径段，生成跨层级的虚拟快捷边（shortcuts），存储原始边的聚合权重（如时间/距离）。
    • 双向搜索逻辑 查询时同时从起点和终点出发，沿层级向上汇聚，避免遍历底层冗余节点。
  2. 基础图访问 通过 chGraph.getBaseGraph() 可获取原始路网数据（未压缩状态），用于：
    • 非加速路径计算（如需动态权重）
    • 底层路网分析（如提取特定道路属性）
  3. 支持高级功能

典型应用场景

场景是否推荐CH理由
实时导航（毫秒响应）✅ 强烈推荐查询速度提升10-100倍
动态权重计算🚫 不适用CH需固定权重预处理，动态规则（如实时交通）需关闭CH
大规模路网分析✅ 推荐内存效率高，但需权衡预处理时间（约耗时数小时/千万级节点）

限制与解决方案

问题原因解决方案
路径绕行不自然过度依赖高层级捷径调整 distance_influence（建议值50-150）平衡速度与路径连贯性
内存耗尽大规模路网CH存储需求高使用 graph.bytes_for_flags=4 降低标记位精度（牺牲5%速度换30%内存节省）
动态规则失效CH需固定预处理权重对实时性要求高的场景禁用CH："ch.disable": true

LM

地标算法核心原理

基础架构（ALT变种）

  • 算法本质：基于A*与三角不等式优化的预处理算法
  • 技术三要素：
    1. 地标点选取：预处理阶段选择分布式地标（如城市中心/交通枢纽）
    2. 距离预计算：存储每个节点到各地标的精确最短距离（正向/反向）
    3. 三角不等式：利用不等式 d(u,v) ≥ |d(l,u) - d(l,v)| 生成启发式估值

与CH算法对比

维度地标算法收缩层次结构（CH）
预处理时间快（仅需计算地标距离）慢（需全图收缩）
内存占用中（存储地标距离矩阵）高（存储大量快捷边）
跨大陆支持受限（2字节存储限制）全球适用
路径最优性ε-最优（可调节）严格最优

工程实现关键点

配置启用（config.yml）

profiles_lm:
  - profile: car_fast  # 应用地标算法的配置名
    weighting: fastest

⚠️ 必须显式声明启用，默认不激活

近似计算优化

// 关键代码逻辑（WeightApproximator接口）
double approxWeight = Math.max(
    fromLandmarkDist[landmark] - toLandmarkDist[landmark],
    toLandmarkDist[landmark] - fromLandmarkDist[landmark]
);

  • 精度控制：

    • epsilon=1：严格最优（默认）
    • epsilon<1：允许启发式加速（牺牲最优性）

  • 存储压缩：

    • 使用short类型（2字节）存储距离值 → 单地标全球内存占用约：

      \frac{2 \times 2 \times \text{节点数} \times \text{地标数}}{1024^3} \text{GB}

地理限制与解决方案

2字节距离限制

  • 技术约束：
    • 最大存储距离 = 32,767单位（约655km * 50km/h = 13小时车程）
    • 导致问题：欧/非/亚大陆间路径可能溢出
  • 临时方案： 自动禁用跨大陆请求的地标优化（回退到Dijkstra/A*）

小范围优化建议

profiles_lm:
  - profile: city_bike
    maximum_weight: 3600  # 显示设置最大值（秒），避免短距离精度损失

性能权衡策略

地标数量选择

地标数查询速度内存占用适用场景
16+40%0.5GB国家级路网
64+60%2GB大洲级路网
256+75%8GB超大城市精细路网
  • 选取逻辑： 系统自动选择拓扑分散的节点（需在预处理日志中确认分布）

精度-速度调节

# API请求示例：放宽最优性保证以获得更快响应
curl "localhost:8989/route?...&lm.epsilon=0.8"

典型问题排查指南

现象根本原因解决方案
跨大陆路线无加速自动禁用保护机制改用CH或关闭lm.disable
短路径绕行小距离差值精度丢失设置maximum_weight参数
预处理内存溢出地标数过多减至≤64或升级内存

进阶发展方向

  1. 混合索引方案： 结合CH与地标算法（如CH+LM），在预处理时生成分层地标距离
  2. 动态地标更新： 对频繁更新的路网区域实现增量式地标距离计算
  3. 存储优化： 测试VarInt压缩格式解决跨大陆距离存储问题

Subnetwork

子网配置（Subnetwork Configuration） 是 GraphHopper 用来 优化地图数据存储和路由计算 的核心机制。它通过将整个路网划分成多个逻辑子区域（Subnetwork），显著提升查询性能，尤其是对于大型地图（如国家级或全球数据）。

📌 核心作用

  1. 提升路由效率
  • GraphHopper 会 预先排除与连通性无关的道路（如死胡同、隔离路段），仅保留有效子网络，减少计算量。
  • 路由算法（如 Dijkstra、A*）只需在相关子网内搜索，避免全图遍历。
  1. 支持层级优化
  • 与 Contraction Hierarchies（CH） 结合时，子网划分能加速预处理过程。
  • 例如：高速公路和普通道路可以分属不同子网，优先计算高速路径。
  1. 隔离无效数据
  • 自动过滤无法通行的路段（如行人禁区、单向逆行道路）。
  • 确保生成的路线均实际可达。

配置文件

profiles

GraphHopper 允许您自定义在路线计算过程中如何对不同类型的道路进行优先级排序。

例如，当您开车长途旅行时，您通常希望使用高速公路以尽量减少旅行时间。但是，如果您骑自行车出行，您肯定不想使用高速公路，而是选择更短的路线，使用指定的自行车道等。

GraphHopper 提供内置车辆 profiles ，涵盖一些标准用例，可以通过 custom model 对其进行修改，以对 GraphHopper 的道路优先级进行细粒度控制，例如更改某些道路类型的行驶速度。

profile 由 custom model 及其 turn restrictions （转弯限制）定义。所有profile均在“profiles”部分中指定，config.yml并且必须至少有一个 profile 。以下是示例：

profiles:
  - name: car
    custom_model_files: [car.json]
  - name: my_bike
    custom_model_files: [bike_elevation.json]

通过选择 custom model 文件，GraphHopper 可以确定不同道路类型的可达性和默认行驶速度。

另一个重要的配置文件设置是turn_costs配置。使用它来为每个 profile 启用转弯限制：

profiles:
  - name: car
    turn_costs:
      vehicle_types: [motorcar, motor_vehicle]
    custom_model_files: [car.json]

custom_model

可以使用“custom_model”更详细地调整 GraphHopper 路线计算的成本函数。

profile 继承了内置基础模型的道路可达性规则和不同道路类型的默认速度。

但是，您可以指定一组规则来更改这些默认值。例如，您可以仅更改特定类型道路的速度等等：

profiles:
  - name: my_custom_profile
    vehicle: car
    custom_model: {
      "speed": [
        {
          "if": "road_class == MOTORWAY",  ## 高速公路
          "multiply_by": "0.8"
        }
      ]               
    }

除了 custom_model 条目，您还可以使用 custom_model_files（可选）属性来设置自定义模型文件的路径custom_models.directory

profiles:
  - name: car
    turn_costs:
      vehicle_types: [motorcar, motor_vehicle]
    custom_model_files: [car.json]

这在上面的示例中使用内部 custom_model 根据海拔变化修改速度bike_elevation.json。

您可以在文件夹中找到所有内部自定义模型 ，core/src/main/resources/com/graphhopper/custom_models例如hike.json、truck.json、bus.json 或car4wd.json``motorcycle.json``curvature.json

您可以将自定义模型留空custom_model: {}，或者用custom_model_files: []。

自定义模型

内置模型

racingbike            竞赛自行车
truck                 卡车
cargo _bike           货物_bike
foot                  徒步
hike                  远足
motorcycle            摩托车
mtb                   山地车
bike                  自行车
bus                   公交
car                   汽车
car4wd                汽车四驱车
foot_elevation        登高
curvature             曲率
bike_ elevation       自行车登高

核心概念

  1. 权重控制的两大维度

    • 速度（speed）：直接影响路径实际耗时和权重
    • 优先级（priority）：仅影响权重，不改变实际耗时。（优先/避让特定路段）

  2. 其他参数

    • distance_influence：平衡“最短时间”和“最短距离”的倾向性（默认为70）。

      { "distance_influence": 100 }  // 每额外1公里需节省100秒才考虑绕行

      计算逻辑： 若参考路径耗时T（秒）、距离D（公里），替代路径距离D+ΔD时： 可接受耗时 ≤ T - distance_influence × ΔD

    • areas可实现区域性限速或禁行（如市中心低优先级），结构同geojson

  3. 性能注意事项

    • 动态值（如max_speed * 0.9）会增加A-star算法的计算开销
    • 复杂模型建议禁用CH（ch.disable: true）

基础结构

{
  "custom_model": {
    "speed": [ /* 速度规则 */ ],
    "priority": [ /* 优先级规则 */ ],
    "distance_influence": 100,
    "areas": { /* 地理围栏定义 */ }
  }
}

规则操作符

操作符作用机理适用场景示例
multiply_by对当前值做乘法修正按比例调整速度/优先级{ "if": "road_class==MOTORWAY", "multiply_by": "0.5" } 高速路速度减半，0表示速度为0了，就是避让
limit_to强制限定极值设置最高速度或最低优先级阈值{ "if": "surface==GRAVEL", "limit_to": "60" } 砾石路面限速60km/h
do嵌套执行子规则集构建复杂条件逻辑分支见下文条件嵌套示例
if/else_if条件判断入口（必须按序声明）多条件分级处理{ "if": "condition1", ... }, { "else_if": "condition2", ... }
else最终兜底条件处理未被前述规则覆盖的情况{ "else": "", "multiply_by": "0.9" }

规则示例

速度调整

{
    "speed": [
      // 基础规则：高速公路速度降至默认值的50%
      { "if": "road_class == MOTORWAY", "multiply_by": "0.5" },

      // 复合规则：隧道内高速路额外限速80km/h
      { 
        "if": "road_environment == TUNNEL && road_class == MOTORWAY",
        "limit_to": "80" 
      },

      // 国家级特例：德国主干道降速20%
      { 
        "if": "country == DEU",
        "do": [
          { "if": "road_class == PRIMARY", "multiply_by": "0.8" }
        ]
      },
        // 无论路段的性质如何，所有路段的 速度都限制为90km/h
     {
          "if": "true",
          "limit_to": "90"
        }
    ]
}
  • 对于这种多个if的语句，从上到下依次执行，若"road_class == MOTORWAY且road_environment == TUNNEL的边，会命中两次，即multiply_by和limit_to同时生效，若两个都是multiply_by，那就需要乘以两次

优先级控制

对于具有数值的类别/编码值，max_width您不应使用==（等式）或!=（不等式）运算符，而应使用数值比较运算符“更大” >，“更大或等于” >=，“更小”<或“更小或等于” <=，例如：

{
    "priority": [
      // 彻底禁止通行区域（优先级归零）
      { "if": "in_construction_zone", "multiply_by": "0" },

      // 次级道路优先权重提升
      { "if": "road_class == SECONDARY", "multiply_by": "1.2" },

      // 动态优先级：基于车辆属性规避狭窄路段
      { 
        "if": "max_width < 2.5 || max_weight < 3.5", 
        "multiply_by": "0.1" 
      }
    ]
}

避让区域示例

{
  "priority": [
    {
      "if": "in_cottbus",
      "multiply_by": "0"
    }
  ],
  "areas": {
    "type": "FeatureCollection",
    "features": [
      {
        "type": "Feature",
        "id": "cottbus",
        "geometry": {
          "type": "Polygon",
          "coordinates": [
            [
              [14.31,51.75],
              [14.34,51.75],
              [14.34,51.77],
              [14.31,51.77],
              [14.31,51.75]
            ]
          ]
        }
      }
    ]
  }
}
  • priority配置优先级
    • if配置了in_表示在这个区域内
    • multiply_by配置了权重的系数，乘以0，表示避让这个区域
  • areas配置了要避让的区域
    • type、features等为固定格式，注意下面字段即可
    • id要和priority中if条件后的in_前缀后后面的字符匹配
    • geometry.type中Polygon表示区域，geometry.coordinates表示的坐标（经度、纬度）收尾必须相连

多条件避让

  • 组合条件：仅禁止特定道路类型的区域路段

    {
  "if": "in_downtown && road_class == MOTORWAY",
  "multiply_by": "0"
}

  • 多层绕行：通过多个 else_if 实现不同区域不同规避强度。

常见问题解决

问题现象可能原因解决方案
路径仍穿过禁区1. 多边形未闭合 2. 区域ID拼写错误1. 检查GeoJSON首尾点是否相同 2. 确保条件用 in_前缀
请求返回空路径区域过大导致无可行路线缩小区域范围或降低优先级（不归零）
性能显著下降动态优先级计算复杂添加 "ch.disable": true 关闭CH加速

条件嵌套高级用法

{
  "if": "country == US",
  "do": [
    { 
      "if": "state == CA", 
      "do": [
        { "if": "road_class == MOTORWAY", "limit_to": "105" },  // 加州高速放宽限速
        { "else": "", "multiply_by": "0.9" }
      ] 
    },
    { 
      "else_if": "state == TX",
      "limit_to": "80"  // 德州全域限速80
    }
  ]
}

代码示例

一些参数在Hits中添加，参考com.graphhopper.routing.Router

GHRequest request = new GHRequest()
  .setPoints(Arrays.asList(
             new GHPoint(24.565537, 121.019382),
             new GHPoint(24.316962, 120.921338)
     ))
     .setProfile("car")
     .setCustomModel(new CustomModel()
         .addToSpeed(
                 Statement.If("true", Statement.Op.LIMIT, String.valueOf(100)))
         .addToPriority(
                 Statement.If("road_class == TRACK", Statement.Op.MULTIPLY, String.valueOf(0)))
         .setDistanceInfluence(100d));

PMap pMap = request.getHints()
  .putObject("ch.disable", true);

GHResponse ghResponse = graphHopper.route(request);

GraphHopper Maps 提供了一个交互式文本编辑器，可用于轻松输入自定义模型。您可以按“自定义”按钮打开它。它将检查您的自定义模型的语法并用红色标记错误。您可以按 Ctrl+Space 或 Alt+Enter 来检索自动完成建议。按 Ctrl+Enter 将为您输入的自定义模型发送路由请求。

避让

JsonFeatureCollection areas = new JsonFeatureCollection();
Coordinate[] area_1_coordinates = new Coordinate[]{
        new Coordinate(48.019324184801185, 11.28021240234375),
        new Coordinate(48.019324184801185, 11.53564453125),
        new Coordinate(48.11843396091691, 11.53564453125),
        new Coordinate(48.11843396091691, 11.28021240234375),
        new Coordinate(48.019324184801185, 11.28021240234375),
};
areas.getFeatures().add(new JsonFeature("area_1",
        "Feature",
        null,
        new GeometryFactory().createPolygon(area_1_coordinates),
        new HashMap<>()));
CustomModel customModel = new CustomModel()
        .addToSpeed(Statement.If("road_class == MOTORWAY", Statement.Op.LIMIT, "80"))
        .addToPriority(Statement.If("surface == DIRT", Statement.Op.MULTIPLY, "0.7"))
        .addToPriority(Statement.If("surface == SAND", Statement.Op.MULTIPLY, "0.6"))
        .setDistanceInfluence(69d)
        .setHeadingPenalty(22)
        .setAreas(areas);
GHRequest req = new GHRequest(
            new GHPoint(42.509225, 1.534728), 
            new GHPoint(42.512602, 1.551558))
        .setCustomModel(customModel)
        .setProfile("car");

方向约束Heading

方向约束路由（Heading-Constrained Routing）

核心概念

  • 功能定位：通过设置航向角（0-360°，正北基准）约束路径起点/终点的行进方向
  • 底层原理：对非指定方向的出边施加时间惩罚（heading_penalty，默认120秒）
  • 特殊值：NaN表示无约束，非[0,360]数值会触发异常

方向定义规则

约束位置语义解释示例场景
起点出发方向路径初始行进方向heading=270 表示向西出发
终点到达方向路径末尾的进入方向的反向若需"从南方到达终点"，需设置 heading=0（北向）

实战示例（Andorra路网测试）

基础用例坐标

起点: 42.566757, 1.597751
终点: 42.567396, 1.597807
  1. 无方向约束（基准路径） ---- 路径选择完全基于最短时间
curl "localhost:8989/route?profile=car&point=42.566757,1.597751&point=42.567396,1.597807&type=json"
  1. 约束起点方向（西向270°） ---- 起点强制西行，绕过东向道路
curl "...&heading=270&ch.disable=true"
  1. 同时约束终点进入方向（表象南来→实际北向0°） ---- 终点必须从北方进入（需反向指定）
curl "...&heading=270&heading=0&ch.disable=true"
  1. 仅约束终点方向（跳过起点约束） ---- 终点必须从南方进入（指定180°）
curl "...&heading=NaN&heading=180&ch.disable=true"

关键参数解析

heading_penalty（单位：秒）

值效果适用场景
120默认惩罚值，明显规避非指定方向严格方向控制（如应急车辆调度）
10弱约束，当有更短路径时允许偏离方向温和引导（如旅游路线建议）
0等效于无约束测试方向逻辑的基准

技术限制

  1. CH模式兼容性 方向约束需禁用收缩层次结构（ch.disable=true），因CH预处理会固定边权重

    # 错误示例（CH模式不支持heading）
curl "...&heading=90"  # 返回400错误

  2. 多途经点约束 每个heading参数按顺序对应路径点，NaN占位表示跳过约束

    # 约束第1点和第3点方向
curl "...&point=A&point=B&point=C&heading=90&heading=NaN&heading=180"

底层实现逻辑

  1. 边遍历惩罚计算

    // 伪代码：出边方向筛选
double penalty = Math.abs(edgeAngle - desiredHeading) <= tolerance ? 
                0 : heading_penalty;
edgeWeight += penalty;

  2. 终点方向反向处理 因路由算法基于出边方向，终点约束需做反向映射：

    需求 "终点从南方进入" → 计算时转换为 "最后一段出边朝向北方（0°）"

  3. 权重动态调整 方向约束实际通过修改Weighting实现，与FastestWeighting等组合使用：

    # config.yml配置示例
profiles:
  - name: "car_heading"
    vehicle: car
    weighting: custom
    custom_model: {
      "speed": "default",
      "heading_penalty": 60  # 覆盖全局默认值
    }

典型错误排查

问题现象可能原因解决方案
方向约束完全失效未禁用CH模式添加&ch.disable=true
终点行为与预期相反混淆"进入方向"与"出边方向"对终点方向取相反值
返回400参数错误heading值超出[0,360]或非数字检查数值范围或替换NaN

API文档梳理

核心路由参数

参数默认值描述
point-必填，指定路由计算的多个坐标点(至少2个)，顺序敏感
localeen返回转向指令的语言 locale (如: pt_PT 表示葡萄牙语, de 表示德语)
instructionstrue是否计算并返回转向指令
profile-用于路由计算的出行模式(如: car, foot, bike等)
elevationfalse是否在返回结果中包含高程数据(第三维度)
points_encodedtrue坐标点是否使用编码字符串(节省带宽)而非原始数组格式
debugfalse是否格式化输出结果
calc_pointstrue是否计算路径点坐标(设为false仅返回距离和时间)
point_hint-道路名称提示，帮助改善GPS坐标点匹配精度
snap_prevention[tunnel, bridge, ferry]防止将坐标点"吸附"到特定道路类型(如桥梁、隧道等)
details-请求额外的路线详情(如: average_speed, street_name等)
curbsideany基于边缘的路由专用，指定车辆应在道路哪一侧(左/右/任意)
curbside_strictnessstrict严格程度(strict: 不满足条件时报错；soft: 宽松处理)
timeout_msinfinity请求超时时间(毫秒)

Hybrid混合模式参数

参数默认值描述
ch.disablefalse设为true启用混合模式(需服务端配置支持)
lm.active_landmarks4活动地标数(不建议修改)

Flexible灵活模式参数

参数默认值描述
ch.disabletrue必须设为true才能使用灵活模式特性
algorithmastarbi路由算法选项: dijkstra, astar, astarbi等
headingNaN指定起点/途经点的前进方向(0-360度, 基于正北顺时针)
heading_penalty300偏离指定方向的惩罚值(秒)
pass_throughfalse是否避免在途经点掉头
round_trip.distance10000环形路线模式的近似长度(米)
round_trip.seed0环形路线模式的随机种子
alternative_route.max_paths2备选路线最大数量
alternative_route.max_weight_factor1.4备选路线长度系数(相对于最优路线)
alternative_route.max_share_factor0.6备选路线共享路段最大比例

公共交通参数(profile=pt时专用)

参数默认值描述
pt.earliest_departure_time-最早出发时间(ISO-8601格式)
pt.arrive_byfalsetrue表示将earliest_departure_time作为最晚到达时间
pt.profilefalse是否执行行程方案范围查询
pt.profile_durationPT60M行程方案查询的时间范围(如: PT200S表示200秒)
pt.limit_street_timeunlimited进出公交系统的最大步行时间(如: PT30M)
pt.ignore_transfersfalse是否忽略换乘因素
pt.limit_solutionsunlimited最大返回的解决方案数量

JSON响应结构

{
  "paths": [
    {
      "distance": 2138.30,     // 总距离(米)
      "time": 129290,          // 总时间(毫秒)
      "ascend": 120.5,         // 总攀升高度(米)
      "descend": 115.2,        // 总下降高度(米)
      "points": "oxg_Iy...",   // 路径坐标(编码字符串)
      "points_encoded": true,  // 坐标是否编码
      "bbox": [13.36,52.46,13.38,52.47],  // 路径边界框
      "instructions": [        // 转向指令数组
        {
          "text": "直行A100",  // 指令描述
          "street_name": "A100", // 道路名称
          "distance": 1268.52, // 本段距离(米)
          "time": 65237,       // 本段耗时(毫秒)
          "interval": [0,10],  // 对应的路径点区间
          "sign": 0,           // 转向标志(见下方说明)
          "exit_number": 3     // 环岛出口编号(可选)
        }
      ],
      "details": {             // 额外详情
        "street_name": [[0,1,"主街"],[1,13,"D19E"]]
      }
    }
  ]
}

转向标志(sign)说明

值常量名说明
-7KEEP_LEFT保持左侧行驶
-3TURN_SHARP_LEFT向左急转
-2TURN_LEFT左转
-1TURN_SLIGHT_LEFT轻微左转
0CONTINUE_ON_STREET直行
1TURN_SLIGHT_RIGHT轻微右转
2TURN_RIGHT右转
3TURN_SHARP_RIGHT向右急转
4FINISH到达终点
5REACHED_VIA到达途经点
6USE_ROUNDABOUT使用环岛
7KEEP_RIGHT保持右侧行驶

区域信息服务(/info)

GET http://localhost:8989/info

响应示例：

{
  "build_date": "2023-02-21T16:52",
  "bbox": [13.072624,52.333508,13.763972,52.679616],
  "version": "8.0",
  "elevation": false,
  "profiles": [{
    "name": "foot",
    "features": { "elevation": false }
  }],
  "import_date": "2023-02-20T12:00:00Z"
}

等时线服务(/isochrone)

参数默认值描述
profile-出行模式(必填)
buckets1将时间/距离分段的数目(生成嵌套等时线)
reverse_flowfalse流向(false: 从点到多边形；true: 从多边形到点)
point-起点坐标"纬度,经度"(必填)
time_limit600行程时间上限(秒)
distance_limit-1行程距离上限(米)

错误响应

{
  "message": "无法找到坐标点2: 2248.224673, 3.867187",
  "hints": [{"message": "坐标点可能偏离道路太远"}]
}

HTTP错误代码

状态码原因
500服务器内部错误(建议将错误信息反馈给服务方)
501不支持指定的出行模式
400请求参数有误

整理说明：

  1. 对参数进行了分类组织，保持技术文档的专业性
  2. 关键参数标注了"必填"提示和中文说明
  3. 保留了原始技术术语但增加解释(如"吸附"snapping)
  4. JSON结构使用注释说明各字段含义
  5. 表格格式清晰展示枚举值和对应含义
  6. 强调注意点(如坐标编码需要特殊处理)

等时线

参数

@Data
public class LocationSelectorParam {
    /**
     * 中心点（经纬度）
     */
    private List<Double> point;

    /**
     * 出行方式
     */
    private String profileName;
    /**
     * 将时间/距离分段的数目(生成嵌套等时线)，1-20,默认1
     */
    private Integer buckets;
    /**
     * 流向(false: 从点到多边形；true: 从多边形到点)，默认 false
     */
    private Boolean reverseFlow;
    /**
     * 时间限制(必填)
     */
    private Long timeLimitInSeconds;
    /**
     * 距离限制，默认-1不限制
     */
    private Long distanceLimitInMeter;
    /**
     * 默认-1不限制
     */
    private Long weightLimit;
    /**
     * 返回类型，默认 geojson，可选 json
     */
    private ResponseType respType;
    /**
     * 容差，默认0米
     */
    private Double toleranceInMeter;
    /**
     * 默认 false
     */
    private Boolean fullGeometry;
    public enum ResponseType {json, geojson}
}

主要调用

/**
 * 等时线、等距线
 *
 * @author LiYuanhao
 * @date 2025年04月10日 11:01
 */
@Slf4j
@Component
public class LocationRegionalComputing {

    /**
     * 默认 1h
     */
    @Value("${graphhopper.default.timeLimitInSeconds:3600}")
    private long defaultTimeLimitInSeconds;

    /**
     * 默认 10km
     */
    @Value("${graphhopper.default.distanceLimitInMeter:10000}")
    private long defaultDistanceLimitInMeter;

    @Autowired
    private GraphHopper graphHopper;
    @Autowired
    private GraphHopperConfig graphHopperConfig;


    public Map<String, Object> location(LocationSelectorParam param) {

        log.info("******************* location start ************************");
        defaultValue(param);


        List<Double> point = param.getPoint();
        String profileName = param.getProfileName();
        Integer buckets = param.getBuckets();
        Boolean reverseFlow = param.getReverseFlow();
        Long timeLimitInSeconds = param.getTimeLimitInSeconds();
        Long distanceLimitInMeter = param.getDistanceLimitInMeter();
        Long weightLimit = param.getWeightLimit();
        LocationSelectorParam.ResponseType respType = param.getRespType();
        Double toleranceInMeter = param.getToleranceInMeter();
        Boolean fullGeometry = param.getFullGeometry();


        StopWatch sw = new StopWatch().start();
        PMap hintsMap = new PMap();
        hintsMap.putObject(Parameters.CH.DISABLE, true);
        hintsMap.putObject(Parameters.Landmark.DISABLE, true);

        PMap profileResolverHints = new PMap(hintsMap);
        profileResolverHints.putObject("profile", profileName);

        Profile profile = graphHopper.getProfile(profileName);
        if (profile == null)
            throw new IllegalArgumentException("出行方式【 '" + profileName + "'】不存在");
        LocationIndex locationIndex = graphHopper.getLocationIndex();
        BaseGraph graph = graphHopper.getBaseGraph();
        Weighting weighting = graphHopper.createWeighting(profile, hintsMap);
        BooleanEncodedValue inSubnetworkEnc = graphHopper.getEncodingManager().getBooleanEncodedValue(Subnetwork.key(profileName));
        Snap snap = locationIndex.findClosest(point.get(1), point.get(0), new DefaultSnapFilter(weighting, inSubnetworkEnc));
        if (!snap.isValid())
            throw new IllegalArgumentException("Point not found:" + point);
        QueryGraph queryGraph = QueryGraph.create(graph, snap);
        TraversalMode traversalMode = profile.hasTurnCosts() ? EDGE_BASED : NODE_BASED;
        ShortestPathTree shortestPathTree = new ShortestPathTree(queryGraph, queryGraph.wrapWeighting(weighting), reverseFlow, traversalMode);

        double limit;
        ToDoubleFunction<ShortestPathTree.IsoLabel> fz;
        if (weightLimit > 0) {
            limit = weightLimit;
            shortestPathTree.setWeightLimit(limit + Math.max(limit * 0.14, 200));
            fz = l -> l.weight;
        } else if (distanceLimitInMeter > 0) {
            limit = distanceLimitInMeter;
            shortestPathTree.setDistanceLimit(limit + Math.max(limit * 0.14, 2_000));
            fz = l -> l.distance;
        } else {
            limit = timeLimitInSeconds * 1000d;
            shortestPathTree.setTimeLimit(limit + Math.max(limit * 0.14, 200_000));
            fz = l -> l.time;
        }
        List<Double> zs = new ArrayList<>();
        double delta = limit / buckets;
        for (int i = 0; i < buckets; i++) {
            zs.add((i + 1) * delta);
        }

        Triangulator.Result result = new JTSTriangulator(graphHopper.getRouterConfig()).triangulate(snap, queryGraph, shortestPathTree, fz, degreesFromMeters(toleranceInMeter));

        ContourBuilder contourBuilder = new ContourBuilder(result.triangulation);
        List<Geometry> isochrones = new ArrayList<>();
        for (Double z : zs) {
            log.info("构建轮廓 z={}", z);
            MultiPolygon isochrone = contourBuilder.computeIsoline(z, result.seedEdges);
            if (fullGeometry) {
                isochrones.add(isochrone);
            } else {
                Polygon maxPolygon = heuristicallyFindMainConnectedComponent(isochrone, isochrone.getFactory().createPoint(new Coordinate(point.get(1), point.get(0))));
                isochrones.add(isochrone.getFactory().createPolygon(maxPolygon.getExteriorRing()));
            }
        }
        List<Map<String, Object>> features = new ArrayList<>();
        try {
            for (Geometry isochrone : isochrones) {
                StringWriter writer = new StringWriter();
                GeometryJSON g = new GeometryJSON();

                g.write(isochrone, writer);

                String geometry = writer.toString();

                Map<String, Object> feature = new HashMap<>();
//                feature.put("id", "some_id"); // 你可以根据需要设置id
                feature.put("type", "Feature");

                JSONObject geometryJson = JSON.parseObject(geometry);
                // 稀释坐标，貌似不好使
//                int count = 200;
//                JSONArray coordinates = (JSONArray) geometryJson.getJSONArray("coordinates").get(0);
//
//                int size = coordinates.size();
//                int step = (int) Math.floor((double) size / count);
//
//                List<Object> collect = IntStream.range(0, size)  // 生成从0到list.size()的索引流
//                        .filter(i -> i % step == 0)  // 只保留索引为i的整数倍的元素
//                        .mapToObj(coordinates::get)  // 将索引转换为对应的元素
//                        .collect(Collectors.toList());// 收集结果到一个列表
//                if (!collect.get(0).equals(collect.get(collect.size() - 1))) {
//                    collect.add(collect.get(0));
//                }
//                geometryJson.put("coordinates", collect);

                feature.put("geometry", geometryJson);

                // 设置properties
                Map<String, Object> properties = new HashMap<>();
                properties.put("bucket", features.size());
                if (respType == LocationSelectorParam.ResponseType.geojson) {
                    properties.put("copyrights", graphHopperConfig.getCopyrights());
                }
                feature.put("properties", properties);
                features.add(feature);
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        sw.stop();

        Map<String, Object> json = new HashMap<>();

        if (respType == LocationSelectorParam.ResponseType.geojson) {
            json.put("type", "FeatureCollection");
            json.put("features", features);  // 这里直接将 features 放入 Map 中
        } else {
            json.put("polygons", features);

            Map<String, Object> info = new HashMap<>();
            info.put("copyrights", graphHopperConfig.getCopyrights());
            info.put("took", Math.round((float) sw.getMillis()));
            json.put("info", info);
        }

        log.info("******************* location end ************************ took: {}, visited nodes:{}", sw.getSeconds(), shortestPathTree.getVisitedNodes());
        return json;

    }

    /**
     * 校验并填充默认值
     */
    public void defaultValue(LocationSelectorParam param) {
        List<Double> point = param.getPoint();
        if (point == null || point.size() != 2)
            throw new IllegalArgumentException("坐标无效");
        String profileName = param.getProfileName();
        if (StringUtils.isBlank(profileName))
            param.setProfileName("car");
        Integer buckets = param.getBuckets();
        if (buckets == null || buckets <= 0)
            param.setBuckets(1);
        Boolean reverseFlow = param.getReverseFlow();
        if (reverseFlow == null)
            param.setReverseFlow(false);
        Long timeLimitInSeconds = param.getTimeLimitInSeconds();
        if (timeLimitInSeconds == null || timeLimitInSeconds <= 0)
            param.setTimeLimitInSeconds(defaultTimeLimitInSeconds);
        Long distanceLimitInMeter = param.getDistanceLimitInMeter();
        if (distanceLimitInMeter == null || distanceLimitInMeter == 0)
            param.setDistanceLimitInMeter(defaultDistanceLimitInMeter);
        Long weightLimit = param.getWeightLimit();
        if (weightLimit == null || weightLimit == 0)
            param.setWeightLimit(-1L);
        LocationSelectorParam.ResponseType respType = param.getRespType();
        if (respType == null)
            param.setRespType(LocationSelectorParam.ResponseType.geojson);
        Double toleranceInMeter = param.getToleranceInMeter();
        if (toleranceInMeter == null)
            param.setToleranceInMeter(0d);
        Boolean fullGeometry = param.getFullGeometry();
        if (fullGeometry == null)
            param.setFullGeometry(false);
    }

    /**
     * 启发式查找主连通分量
     *
     * @param multiPolygon
     * @param point
     * @return
     */
    private Polygon heuristicallyFindMainConnectedComponent(MultiPolygon multiPolygon, Point point) {
        int maxPoints = 0;
        Polygon maxPolygon = null;
        for (int j = 0; j < multiPolygon.getNumGeometries(); j++) {
            Polygon polygon = (Polygon) multiPolygon.getGeometryN(j);
            if (polygon.contains(point)) {
                return polygon;
            }
            if (polygon.getNumPoints() > maxPoints) {
                maxPoints = polygon.getNumPoints();
                maxPolygon = polygon;
            }
        }
        return maxPolygon;
    }

    /**
     * 度转米
     * 我们想用 米 来指定一个容差，但我们需要在未投影的 经纬度 空间中指定它。这在世界的某些地区和某些方向比在其他地方更正确
     *
     * @param distanceInMeters distance in meters
     * @return "distance" in degrees
     */
    static double degreesFromMeters(double distanceInMeters) {
        return distanceInMeters / DistanceCalcEarth.METERS_PER_DEGREE;
    }
}

MVT切片

@Path("mvt")
public class MVTResource {

    private static final Logger logger = LoggerFactory.getLogger(MVTResource.class);
    private static final MediaType PBF = new MediaType("application", "x-protobuf");
    private final GraphHopper graphHopper;
    private final EncodingManager encodingManager;

    @Inject
    public MVTResource(GraphHopper graphHopper, EncodingManager encodingManager) {
        this.graphHopper = graphHopper;
        this.encodingManager = encodingManager;
    }

    @GET
    @Path("{z}/{x}/{y}.mvt")
    @Produces("application/x-protobuf")
    public Response doGetXyz(
            @Context HttpServletRequest httpReq,
            @Context UriInfo uriInfo,
            @PathParam("z") int zInfo,
            @PathParam("x") int xInfo,
            @PathParam("y") int yInfo,
            @QueryParam("render_all") @DefaultValue("false") Boolean renderAll) {

        if (zInfo <= 9) {
            byte[] bytes = new VectorTileEncoder().encode();
            return Response.fromResponse(Response.ok(bytes, PBF).build())
                    .header("X-GH-Took", "0")
                    .build();
        }

        StopWatch totalSW = new StopWatch().start();
        Coordinate nw = num2deg(xInfo, yInfo, zInfo);
        Coordinate se = num2deg(xInfo + 1, yInfo + 1, zInfo);
        LocationIndexTree locationIndex = (LocationIndexTree) graphHopper.getLocationIndex();
        final NodeAccess na = graphHopper.getBaseGraph().getNodeAccess();
        BBox bbox = new BBox(nw.x, se.x, se.y, nw.y);
        if (!bbox.isValid())
            throw new IllegalStateException("Invalid bbox " + bbox);

        final GeometryFactory geometryFactory = new GeometryFactory();
        if (!encodingManager.hasEncodedValue(RoadClass.KEY))
            throw new IllegalStateException("You need to configure GraphHopper to store road_class, e.g. graph.encoded_values: road_class,max_speed,... ");

        final EnumEncodedValue<RoadClass> roadClassEnc = encodingManager.getEnumEncodedValue(RoadClass.KEY, RoadClass.class);
        final AtomicInteger edgeCounter = new AtomicInteger(0);

        // 256x256 pixels per MVT. here we transform from the global coordinate system to the local one of the tile.
        AffineTransformation affineTransformation = new AffineTransformation();
        affineTransformation.translate(-nw.x, -se.y);
        affineTransformation.scale(
                256.0 / (se.x - nw.x),
                -256.0 / (nw.y - se.y)
        );
        affineTransformation.translate(0, 256);

        // if performance of the vector tile encoding becomes an issue it might be worth to get rid of the simplification
        // and clipping in the no.ecc code? https://github.com/graphhopper/graphhopper/commit/0f96c2deddb24efa97109e35e0c05f1c91221f59#r90830001
        VectorTileEncoder vectorTileEncoder = new VectorTileEncoder();
        locationIndex.query(bbox, edgeId -> {
            EdgeIteratorState edge = graphHopper.getBaseGraph().getEdgeIteratorStateForKey(edgeId * 2);
            LineString lineString;
            if (renderAll) {
                PointList pl = edge.fetchWayGeometry(FetchMode.ALL);
                lineString = pl.toLineString(false);
            } else {
                RoadClass rc = edge.get(roadClassEnc);
                if (zInfo >= 14) {
                    PointList pl = edge.fetchWayGeometry(FetchMode.ALL);
                    lineString = pl.toLineString(false);
                } else if (rc == RoadClass.MOTORWAY
                        || zInfo > 10 && (rc == RoadClass.PRIMARY || rc == RoadClass.TRUNK)
                        || zInfo > 11 && (rc == RoadClass.SECONDARY)
                        || zInfo > 12) {
                    double lat = na.getLat(edge.getBaseNode());
                    double lon = na.getLon(edge.getBaseNode());
                    double toLat = na.getLat(edge.getAdjNode());
                    double toLon = na.getLon(edge.getAdjNode());
                    lineString = geometryFactory.createLineString(new Coordinate[]{new Coordinate(lon, lat), new Coordinate(toLon, toLat)});
                } else {
                    // skip edge for certain zoom
                    return;
                }
            }

            edgeCounter.incrementAndGet();
            Map<String, Object> map = new LinkedHashMap<>();
            for (Map.Entry<String, KVStorage.KValue> e : edge.getKeyValues().entrySet()) {
                map.put(e.getKey(), e.getValue().toString());
            }
            map.put("edge_id", edge.getEdge());
            map.put("edge_key", edge.getEdgeKey());
            map.put("base_node", edge.getBaseNode());
            map.put("adj_node", edge.getAdjNode());
            map.put("distance", edge.getDistance());
            encodingManager.getEncodedValues().forEach(ev -> {
                if (ev instanceof EnumEncodedValue)
                    map.put(ev.getName(), edge.get((EnumEncodedValue) ev).toString() + (ev.isStoreTwoDirections() ? " | " + edge.getReverse((EnumEncodedValue) ev).toString() : ""));
                else if (ev instanceof DecimalEncodedValue)
                    map.put(ev.getName(), edge.get((DecimalEncodedValue) ev) + (ev.isStoreTwoDirections() ? " | " + edge.getReverse((DecimalEncodedValue) ev) : ""));
                else if (ev instanceof BooleanEncodedValue)
                    map.put(ev.getName(), edge.get((BooleanEncodedValue) ev) + (ev.isStoreTwoDirections() ? " | " + edge.getReverse((BooleanEncodedValue) ev) : ""));
                else if (ev instanceof IntEncodedValue)
                    map.put(ev.getName(), edge.get((IntEncodedValue) ev) + (ev.isStoreTwoDirections() ? " | " + edge.getReverse((IntEncodedValue) ev) : ""));
            });
            lineString.setUserData(map);

            Geometry g = affineTransformation.transform(lineString);
            vectorTileEncoder.addFeature("roads", map, g, edge.getEdge());
        });


        byte[] bytes = vectorTileEncoder.encode();
        totalSW.stop();
        logger.debug("took: " + totalSW.getMillis() + "ms, edges:" + edgeCounter.get());
        return Response.ok(bytes, PBF).header("X-GH-Took", "" + totalSW.getSeconds() * 1000)
                .build();
    }

    Coordinate num2deg(int xInfo, int yInfo, int zoom) {
        // inverse web mercator projection
        double n = Math.pow(2, zoom);
        double lonDeg = xInfo / n * 360.0 - 180.0;
        // unfortunately latitude numbers goes from north to south
        double latRad = Math.atan(Math.sinh(Math.PI * (1 - 2 * yInfo / n)));
        double latDeg = Math.toDegrees(latRad);
        return new Coordinate(lonDeg, latDeg);
    }
}

参考

路线计算原理

GraphHopper 最重要的功能之一是计算两个地点之间的“最佳”路线。

为此，GraphHopper 将整个道路网络细分为所谓的“边 edge”。每条边代表两个交叉口之间的特定路段。

因此，找到两个地点之间的最佳路线意味着找到连接这两个地点的最佳边序列。

GraphHopper 存储每个边的某些属性（所谓的“编码值”），并应用公式（所谓的“加权”）来计算每个边的数字“weight”。

最佳路线是总权重最小的路线。

在内部，GraphHopper 使用以下公式进行加权：

edge_weight = edge_distance / (speed * priority) + edge_distance * distance_influence

权重 = 距离 / （车辆速度 速度优先权重） + 距离 距离影响

  • 权重本质是时间

  • priority速度优先权重：不改变实际耗时，仅影响路径选择

    • priority=0，代表只关心距离
    • priority=1 时，不影响权重计算结果。
    • priority < 1：降低权重，使路段更具吸引力（更可能被选中）。
    • priority > 1：增加权重，使路段更可能被绕过。

  • distance_influence距离影响：平衡「时间最短」和「距离最短」

    • distance_influence=0：严格优先选择 最快路线，无论绕行距离多长。

    • distance_influence>0，数值越大，算法越倾向于 短距离路线，即使耗时稍长。

    • 临界计算示例：

      • 假设某基准路线耗时 T_ref（秒），距离 D_ref（公里）。

      • 当存在一条替代路线，距离为 D_ref + ΔD（公里），其可接受的耗时上限为：

      T_max = T_ref - distance_influence × ΔD

      • 数值示例：

        • distance_influence=30 时，若替代路线多绕行1公里（ΔD=1），其耗时须 ≤ T_ref - 30秒 才会被选中。
        • 若原路线参考值 T_ref=600秒，D_ref=10公里，那么一条 11公里 的替代路线需耗时 ≤ 570秒 才有优先级。

    • 实际应用场景：

      • 快递配送：distance_influence=0，追求绝对最短时间。
      • 电动车续航敏感场景：适当增加 distance_influence，减少总距离以节省电量。

边缘属性：编码值

GraphHopper 为每个路段存储不同的属性，即所谓的“encoded values”。一些常用的编码值如下（括号中给出了它们的一些可能值）：

  • road_class 道路类别：（OTHER 、MOTORWAY 、TRUNK 、PRIMARY 、SECONDARY 、TRACK 轨道、STEPS 台阶、CYCLEWAY 自行车道、FOOTWAY 人行道……）

    OTHER 其他,

    MOTORWAY 高速公路, TRUNK 主干道,

    PRIMARY 主要道路, SECONDARY 次要道路, TERTIARY 第三级,

    RESIDENTIAL 住宅, UNCLASSIFIED 未分类, SERVICE 服务,

    ROAD 路, TRACK 轨道, BRIDLEWAY 马道, STEPS 台阶, CYCLEWAY 自行车道, PATH 路径,

    LIVING_STREET 生活街道, FOOTWAY 人行道, PEDESTRIAN 行人, PLATFORM 平台, CORRIDOR 走廊;

  • road_environment 道路环境：（ROAD 道路、FERRY 渡轮、BRIDGE 桥梁、TUNNEL 隧道……）

  • road_access 道路通道：（DESTINATION 目的地、DELIVERY 送货、PRIVATE 私人、NO 禁行、...）

  • surface 表面：（PAVED 铺砌路面、DIRT 泥土路面、SAND 沙子路面、GRAVEL 砾石路面......）

  • smoothness 平滑度：（EXCELLENT 优秀、GOOD 良好、INTERMEDIATE 中等……）

  • toll 收费站：（MISSING 缺失、NO 无、HGV HGV、ALL 全部）

  • bike_network 自行车网络，foot_network 步行网络：（MISSING 缺失、INTERNATIONAL 国际、NATIONAL 国家、REGIONAL 地区、LOCAL 本地、OTHER 其他）

  • country 国家：（MISSING或以国家代码表示的国家，ISO3166-1:alpha3例如DEU）

  • state 州：（MISSING或以ISO3166-2代码表示的状态，如 US_CA）

  • hazmat 危险品：（YES, NO 是，否），hazmat_tunnel 危险品隧道：（A，B，..，E），hazmat_water 危险品水：（YES 是，PERMISSIVE 允许，NO 否）

  • hgv：（MISSING 缺失，YES 是，DESIGNATED 指定，...）

  • track_type 轨迹类型：（MISSING 缺失、GRADE1 等级 1、GRADE2 等级 2、...、GRADE5 等级 5）

  • urban_density 城市密度：（RURAL 农村，RESIDENTIAL 住宅，CITY 城市）

  • max_weight_except 最大重量除外：（NONE 无、DELIVERY 交货、DESTINATION 目的地、FORESTRY 林业）

要了解所有可用的编码值，您可以查询/info端点

{
  "bbox": [
    114.360051,
    10.372807,
    122.083943,
    28.084358
  ],
  "profiles": [
    {
      "name": "car"
    }
  ],
  "version": "9.0",
  "elevation": false,
  "encoded_values": {
    "car_access": [
      "true",
      "false"
    ],
    "car_average_speed": [
      ">number",
      "<number"
    ],
    "road_class": [
      "OTHER",
      "MOTORWAY",
      "TRUNK",
      "PRIMARY",
      "SECONDARY",
      "TERTIARY",
      "RESIDENTIAL",
      "UNCLASSIFIED",
      "SERVICE",
      "ROAD",
      "TRACK",
      "BRIDLEWAY",
      "STEPS",
      "CYCLEWAY",
      "PATH",
      "LIVING_STREET",
      "FOOTWAY",
      "PEDESTRIAN",
      "PLATFORM",
      "CORRIDOR"
    ],
    "road_environment": [
      "OTHER",
      "ROAD",
      "FERRY",
      "TUNNEL",
      "BRIDGE",
      "FORD"
    ],
    "roundabout": [
      "true",
      "false"
    ],
    "road_class_link": [
      "true",
      "false"
    ],
    "max_speed": [
      ">number",
      "<number"
    ],
    "ferry_speed": [
      ">number",
      "<number"
    ],
    "car_subnetwork": [
      "true",
      "false"
    ]
  },
  "import_date": "2025-04-02T03:02:01Z",
  "data_date": "2020-12-27T21:42:02Z"
}

除了这种可以采用多个不同字符串值的类别之外，还有一些类别表示布尔值（对于给定的道路段，它们为真或假），例如：

  • get_off_bike 下车
  • road_class_link 道路类别链接
  • roundabout 迂回
  • 后缀_access包含特定车辆的访问权限（布尔值）

还有一些采用数值形式，例如：

  • average_slope：表示 100 * elevation change 海拔变化/edge_distance 的路段；它会以相反的方向改变符号；参见 max_slope
  • curvature 曲率：beeline distance 直线距离/ edge_distance 边缘距离（0..1），例如弯曲的道路取小于1的值
  • hike_rating 徒步评级：OSM 中的 0 到 6 之间的数字sac_scale，例如 0 表示“missing 失踪”，1 表示“hiking 徒步”，2 表示“mountain_hiking 登山”，3 表示demanding_mountain_hiking 高难度登山，4 表示alpine_hiking 高山徒步，5 表示demanding_alpine_hiking高难度高山徒步，6 表示difficult_alpine_hiking 困难高山徒步
  • mtb_rating：OSM 中的 0 到 7 之间的数字mtb:scale，例如 0 表示“缺失”，1 表示mtb:scale=0，2 表示mtb:scale=1等等。前“+”或“-”字符将被忽略。
  • horse_rating：OSM 中的 0 到 6 之间的数字horse_scale，例如 0 表示“缺失”，1 表示“常见”，2 表示“要求高”，3 表示困难，4 表示危急，5 表示危险，6 表示不可能
  • lanes：车道数
  • max_slope：边的最大坡度（100 * elevation change 海拔变化/distance_i 距离_i”）的有符号小数sum(distance_i)=edge_distance。对于较长的路段来说很重要，因为路段的上坡（或下坡）可能比平均坡度大得多。
  • max_speed：标志上的速度限制（km/h）
  • max_height 最大高度（米）、max_width 最大宽度（米）、max_length 最大长度（米）
  • max_weight 最大重量（吨）、max_axle_load 最大车轴负载（吨）
  • 后缀_average_speed包含特定车辆的平均速度（km/h）
  • 后缀_priority包含道路偏好，但不改变特定车辆的速度（0..1）

基于边的收缩层次结构（Edge-based Contraction Hierarchies）

核心思想

在预处理阶段通过节点收缩构建层次化网络，与节点式CH（Node-based CH）的本质区别在于： 边式CH以原始边（Original Edges）为基本单元，需确保任意两个相邻边的转向关系在收缩后仍能保持原最短路径权重（含转向成本）。

传统节点式CH:
u → x → v 收缩为 u → v (忽略中间节点x)

边式CH进阶:
e(u→x) + f(x→v) 收缩为 shortcut(e→f) (需保留转向成本)

关键技术差异对比

维度节点式CH边式CH
基本单元节点（Nodes）原始边（Original Edges）
快捷边（Shortcut）连接邻居节点连接相邻边的转向关系
转向成本处理不支持通过原始边ID映射转向成本表
环路处理不存在需处理Loop Shortcuts（自环绕捷径）

实现流程分解

  1. 节点排序（Node Ordering）

    • 共同基础：与节点式CH使用相同的 PrepareContractionHierarchies 框架

    • 优先级计算差异

      // 边式CH专用优先级公式（基于以下因子加权）
priority = α·edgeQuotient + β·originalEdgeQuotient + γ·hierarchyDepth
      • edgeQuotient：类似节点式的边差异评估
      • originalEdgeQuotient：仅统计原始边数量（忽略快捷边）
      • hierarchyDepth：层次深度因子（调整收缩顺序）

  2. 节点收缩（Node Contraction）

    关键操作由 EdgeBasedNodeContractor 实现，核心步骤：

    1. 邻居边扫描 对目标节点 x 的所有相邻原始边进行配对检查

      示例拓扑:
  e1(u→x), e2(v→x)  // 入边
  f1(x→w), f2(x→y)  // 出边
需验证的转向对:
  e1→f1, e1→f2, e2→f1, e2→f2

    2. 见证路径搜索（Witness Path Search） 使用 WitnessPathSearcher 执行受限Dijkstra搜索：

      • 搜索终止条件：基于设定参数 sigmaFactor 动态限制已访问边数
      • 特殊标记：路径条目标记 isPathToCenter 判断是否经过待收缩节点

    3. 快捷边生成

      • 存储首末原始边ID以支持转向成本查询
      • 处理环路捷径（Loop Shortcuts）时生成嵌套快捷边

  3. 查询算法（CH Query）

    • 双向分层Dijkstra：正向/反向搜索仅访问更高层级节点，交汇时处理转向成本
    • A*优化：边式CH中因探索更多路径条目，A*启发式能更早体现收益
    • 无Stall-on-Demand：文献[3]表明A*在边式场景更有效（暂未实现该优化）

关键挑战与解决方案

转向成本存储优化

  • 问题：若快捷边直接存储转向成本，会导致表膨胀

  • 方案： 快捷边仅记录首尾原始边ID，运行时动态计算：

    // 示例：计算快捷边s(e→f)的转向成本
TurnCostTable.get(e.lastOrigEdge, f.firstOrigEdge);

环路捷径处理

  • 场景：当路径需多次穿越同一节点（如绕行禁转路口）

  • 方案：

    • 生成多级嵌套快捷边

      环路捷径嵌套结构:
原始路径: a→x→b→x→c
生成快捷边: 
  s1(a→x→c) [含嵌套s2(x→b→x)]

    • 在 EdgeBasedNodeContractorTest 中覆盖各类环路测试用例

见证搜索效率

  • 动态调整：通过 OnFlyStatisticsCalculator 实时监控搜索效率，动态优化 sigmaFactor
  • 权衡公式： sigmaFactor ↘ ⇒ 收缩加速但快捷边增多 ⇒ 查询变慢

性能影响因素

参数/配置影响方向调优建议
sigmaFactor收缩速度 vs 查询速度大型地图建议初始值=8
优先级公式权重(α,β,γ)快捷边数量分布默认权重经论文[2]验证
A*启发式权重查询速度推荐Euclidean距离乘以1.1-1.3

现存问题与改进方向

  1. 原始边比例突增 收缩后期 originalEdgeQuotient 主导优先级计算，可能导致过量快捷边
    • 可能方案：动态调整权重因子或引入截断阈值
  2. 双向快捷边复用 当前边式CH的快捷边仅单向存储，理论可复用反向边提升内存效率
    • 挑战：环路捷径会引入复杂依赖
  3. 混合索引策略 结合Landmark等预计算数据进一步加速查询

route源码分析

public GHResponse route(GHRequest request) {
    GHResponse ghRsp;
    try {
        // 检查遗留不在支持的参数：vehicle、weighting、turn_costs、edge_based --- 在 profile 中配置
        this.checkNoLegacyParameters(request);
        // 至少一个途经点检查
        this.checkAtLeastOnePoint(request);
        // 检查点是否在边界内 --- graphHopper.getBaseGraph().getBounds().contains(纬度，经度)
        this.checkIfPointsAreInBounds(request.getPoints());
        // 检查强制方向 --- Headings个数必须与Point数量一致，或者为0，且必须是方位角（0-360之间）
        this.checkHeadings(request);
        // 如果你传递 point_hint，你需要为每个点只传递一个提示，空提示将被忽略
        this.checkPointHints(request);
        // 如果你通过路边，你需要为每个点恰好通过一个路边，空的路边将被忽略
        this.checkCurbsides(request);
        // Hits不再支持 'block_area' 参数。请改用带有 'areas' 的自定义模型
        this.checkNoBlockArea(request);
        // 创建求解器 - CH、LM、混合
        Solver solver = this.createSolver(request);
        solver.checkRequest();
        // 检查并初始化 ---  如果使用 request.Curbsides 必须配置 profile.TurnCosts
        solver.init();
        if ("round_trip".equalsIgnoreCase(request.getAlgorithm())) {
            if (!(solver instanceof FlexSolver)) {
                throw new IllegalArgumentException("algorithm=round_trip only works with a flexible algorithm");
            } else {
                return this.routeRoundTrip(request, (FlexSolver)solver);
            }
        } else {
            return "alternative_route".equalsIgnoreCase(request.getAlgorithm()) ? this.routeAlt(request, solver) : this.routeVia(request, solver);
        }
    } catch (MultiplePointsNotFoundException var6) {
        MultiplePointsNotFoundException ex = var6;
        ghRsp = new GHResponse();
        Iterator var4 = ex.getPointsNotFound().iterator();

        while(var4.hasNext()) {
            IntCursor p = (IntCursor)var4.next();
            int var10003 = p.value;
            ghRsp.addError(new PointNotFoundException("Cannot find point " + var10003 + ": " + request.getPoints().get(p.value), p.value));
        }

        return ghRsp;
    } catch (IllegalArgumentException var7) {
        IllegalArgumentException ex = var7;
        ghRsp = new GHResponse();
        ghRsp.addError(ex);
        return ghRsp;
    }
}

参数

Hits

參考com.graphhopper.util.Parameters.Routing

  • 公共

    • algorithm ---- 參考com.graphhopper.util.Parameters.Algorithms

    • edge_based

    • turn_costs

    • u_turn_costs

    • max_visited_nodes

    • max_visited_nodes

    • timeout_ms

    • instructions

    • calc_points

    • way_point_max_distance

    • elevation_way_point_max_distance

    • pass_through

    • point_hint

    • curbside

    • force_curbside

    • snap_prevention

  • 备选路径

    • alternative_route.max_paths
    • alternative_route.max_weight_factor
    • alternative_route.max_share_factor

  • 往返路径

    • round_trip.distance
    • round_trip.seed
    • round_trip.points
    • round_trip.max_retries

  • astar

    • astar.epsilon

  • astarbi

    • astarbi.epsilon
Parameters.Routing.MAX_VISITED_NODES max_visited_nodes 最大访问节点数  routerConfig也可配置
Parameters.Routing.U_TURN_COSTS   u_turn_costs  转弯花费   profile也可配置

request参数

algorithm 算法 
- round_trip 往返路线 --- 只能使用混合算法
- alternative_route 备选路线 ---不支持CH
- dijkstra  Dijkstra --- 不支持CH
- dijkstrabi  双向 Dijkstra
- dijkstra_one_to_many --- 一对多 Dijkstra（尚未适用于基于边缘的 #394，尚不适用于 CH）
- astar 单向A* --- 不支持CH
- astarbi 双向A*

instructions 为true则显示转弯指示
calc_points 为true则显示路径点列表
way_point_max_distance 配置返回点列表的简化

  • algorithm

    • round_trip

      • 往返路线，用于生成闭环路线的算法，适合需要 固定距离/时间往返 的场景
      • 只能使用混合算法
      • 入参坐标点只能是一个
      • 距离通过equest.getHints()设置putObject("round_trip.distance",1000d)
      • RoundTrip.DISTANCE 默认 10_000（10公里）
      • RoundTrip.POINTS（round_trip. points）坐标点数，默认 Math.min(20, distance/50000+2)

    • alternative_route

  • pathDetails ----- com.graphhopper.util.Parameters.Details

routerConfig

  • 读路径文件

    • datareader.file ---- 指定输入的 OSM 地图文件路径（如 .pbf 或 .osm）
    • datareader.date_range_parser_day
    • datareader.worker_threads ---- 读数据线程数，默认2
    • datareader.instructions ---- 解析道路名称，默认true
    • datareader.preferred_language ---- 首选语言

  • 自定义

    • custom_areas.directory ---- 自定义区域目录
    • custom_models.directory 或 custom_model_folder ---- 自定义模型目录

  • 高程数据处理

    • graph.elevation.edge_smoothing ---- 高程平滑算法（moving_average 或 ramer）
    • graph.elevation.edge_smoothing.moving_average.window_size
    • graph.elevation.edge_smoothing.ramer.max_elevation
    • graph.elevation.long_edge_sampling_distance ---- 长距离边缘采样间隔（米）
    • graph.elevation.way_point_max_distance ---- 路径点间最大高程插值距离（米）

  • 优化

    • prepare.min_network_size ---- 子网的最小节点数（小于此值的子网被丢弃），默认200，过大会导致路径不连续
    • prepare.subnetworks.threads ---- 子网线程，默认1
    • prepare.ch.threads ----
    • prepare.lm.threads
    • prepare. lm. landmarks ---- 默认16
    • prepare. lm.log_details ---- 默认false
    • prepare. lm.min_network_size ---- 默认-1
    • prepare. lm.suggestions_location ---- 建议位置，逗号分割
    • prepare. lm.split_area_location

  • index

    • index.high_resolution ---- 索引分辨率，默认300
    • index.max_region_search --- 最大区域搜索，默认4单元，用于搜索坐标点最近的段（snap）

  • 城市密度

    • graph.urban_density.residential_radius ---- 住宅区半径，默认400
    • graph.urban_density.residential_sensitivity ---- 住宅区敏感性，默认6000
    • graph.urban_density.city_radius ---- 城市区域半径，默认1500
    • graph.urban_density.city_sensitivity ---- 城市区域敏感性，默认1000
    • graph.urban_density.threads ---- 城市密度计算线程，默认0

  • 路径规划

    • routing. max_visited_nodes ---- 最大访问量节点，默认Integer.MAX_VALUE，可设置小点，防止超时

    • routing. timeout_ms ---- 超时时间，默认Long.MAX_VALUE

    • routing. round_trip. max_retries ---- 往返规划最大重试次数，默认3

    • routing. non_ch. max_waypoint_distance ---- 默认Integer.MAX_VALUE，设置太小会抛异常

      throw new PointDistanceExceededException("Point " + i + " is too far from Point " + (i - 1) + ": " + point, detailMap);

    • routing. instructions ---- 是否生成导航指令，默认true

    • routing. lm. active_landmarks ---- 地标算法中地标加速计数默认值，Math.min(8, lmPreparationHandler.getLandmarks())

    • routing. way_point_max_distance ---- 路径点最大距离，用于调整规划的路径点坐标密度，默认0.5

  • graph其他

    • graph.dataaccess.segment_size ---- 内存分块大小（影响 I/O 性能），默认-1
    • graph.dataaccess.default_type 或 graph.dataaccess ---- 数据存储类型（RAM_STORE、MMAP、UNSAFE），默认RAM_STORE，详情查看com.graphhopper.storage.DAType
    • graph.calc_checksums ---- 计算检查，默认false
    • graph.location ---- 图数据存储目录（如果为空，自动从 OSM 文件名派生 --- xxx-gh）
    • graph.remove_zipped ---- 是否在加载后删除zip压缩文件，默认true
    • graph.encoded_values ----
    • graph.locktype ---- 文件锁类型（native 或 simple）,默认native

  • 其他

    • max_speed_calculator.enabled ---- 最大速度计算器，默认false，开启状态会读core模块下的com/graphhopper/routing/util/legal_default_speeds.json

    • import.osm.ignored_highways ---- 忽略的 OSM 道路类型（逗号分隔）

      • 您不应将 import.osm.ignored_highways=footway 或 =path 与 pedestrian profiles（行人配置） 结合使用。这可能是您的配置中的错误
      • 您不应将 import.osm.ignored_highways=cycleway 或 =path 与 bicycle profiles（自行车配置文件）结合使用。这可能是您的配置中的错误

    • country_rules.enabled ---- 默认false

  • profiles

  • profiles_ch

不再支持

  • routing.ch.disabling_allowed
  • routing.lm.disabling_allowed
  • osmreader.osm -> datareader.file
  • spatial_rules.location -> custom_areas.directory
  • spatial_rules.borders_directory -> custom_areas.directory
  • spatial_rules.max_bbox -> 没有替换，将考虑所有自定义区域。
  • graph.vehicles -> turn_costs 、custom_model 参考文档docs/migration/config-migration-08-09.md
  • graph.flag_encoders ->
  • graph.elevation.smoothing -> graph.elevation.edge_smoothing: moving_average 或 graph.elevation.edge_smoothing: ramer'. See #2634

其他

上次编辑于:
贡献者: 李元昊
Copyright © 2025 程序员李某某