5.3 网络分析与路径规划

5.3 网络分析与路径规划

本节摘要：道路、管线、河流都是网络。本节讲最短路径、服务区、最近设施等网络分析——解决"怎么走"的问题。

上手前先明确

阅读完本节，你应当能够：

1. 理解网络数据模型
2. 做最短路径分析
3. 做服务区和最近设施分析

概念脉络

一、网络数据模型

网络用图（Graph）建模：节点（Node）+ 边（Edge）。道路网里节点是路口，边是路段，边权是距离/时间/费用。

图 5-3 网络分析类型

二、最短路径算法

• Dijkstra：经典最短路径，非负权
• A*：带启发式，更快，导航常用
• Contraction Hierarchies：预处理加速，超快查询

三、pgRouting 网络分析

-- 最短路径
SELECT * FROM pgr_dijkstra(
  'SELECT id, source, target, cost FROM roads',
  100, 200, false
);

-- 服务区（10 分钟可达）
SELECT * FROM pgr_drivingDistance(
  'SELECT id, source, target, cost FROM roads',
  100, 600, false
);
​

pgRouting 是 PostGIS 网络分析扩展，支持最短路径、服务区、TSP、VRP 等。

四、网络数据准备

网络分析前要准备拓扑网络：

1. 路网拓扑：把线段连成网络，生成交叉口节点
2. 边权：距离/时间（考虑限速、转向限制）
3. 转向限制：禁止左转/掉头等
4. 单向边：单行道方向

-- 生成路网拓扑
SELECT pgr_createTopology('roads', 0.001, 'geom', 'id');
​

五、服务区分析

服务区是某点 N 分钟/N 公里可达范围，用于可达性分析：

• 学校 30 分钟可达范围
• 医院 15 分钟服务区
• 公交站点 500 米覆盖

六、最近设施

找距离某点最近的 N 个设施：

• 报警找最近派出所
• 故障找最近维修站
• 配送找最近仓库

七、VRP 车辆路径

VRP（Vehicle Routing Problem）是多车多点配送优化，比最短路径复杂得多，是组合优化问题，用启发式/元启发式算法（遗传、模拟退火）。

⚠️ 常见坑：网络分析前不做拓扑——线段没连成网络，路径算不通。先 pgr_createTopology 生成拓扑，再做分析。

💡 关键直觉：网络用图建模（节点+边），最短路径用 Dijkstra/A*，服务区是可达范围，最近设施找最近 N 个，VRP 多车配送。pgRouting 是 PostGIS 网络扩展。

七、Dijkstra 算法的工作过程

Dijkstra 是最短路径的经典算法，理解它有助于判断结果合理性。过程是：

1. 从起点开始，标记起点距离为 0，其余节点距离为无穷大。
2. 每次从未确定节点中选距离最小的节点，固定它的最短距离。
3. 松弛它的邻居：如果经当前节点到邻居更近，就更新邻居的距离和前驱。
4. 重复直到终点被固定。

朴素实现复杂度较高，用二叉堆优化后适合中等规模路网。A* 在 Dijkstra 基础上加启发式（到终点的估计距离），能大幅减少探索范围，导航引擎普遍采用。Contraction Hierarchies 则通过预处理把路网分层压缩，查询可在毫秒级完成，适合大范围实时导航。

-- pgRouting 返回路径节点和累计成本
SELECT seq, node, edge, cost, agg_cost
FROM pgr_dijkstra(
  'SELECT id, source, target, cost, reverse_cost FROM roads',
  100, 200, directed := true
);
​

注意 reverse_cost 字段：不填它默认双向可通行，填了才能表达单行道、禁止掉头等真实交通规则。

八、路网成本：距离还是时间

导航场景算的是时间而不是距离，成本字段要按限速换算。道路表里存长度和限速，查询时把 cost 定义为时间：

-- 用时间作成本（分钟）：长度/限速
ALTER TABLE roads ADD COLUMN cost_min float;
UPDATE roads SET cost_min = length_m / (speed_kmh * 1000.0 / 60.0);
-- 之后 pgRouting 查询用 cost_min 作为成本
​

还要考虑转向惩罚：左转可能比直行多等红灯。pgRouting 的 withPoints 系列函数支持转向成本，复杂路口建模时再深入。日常项目先做好"距离/时间 + 单双向"就够解决大部分问题。

九、服务区与最近设施的实践

服务区分析在应急和选址里很有用。比如消防站覆盖评估：对每个消防站算 15 分钟车程覆盖范围，再统计覆盖的人口：

-- 每个消防站 15 分钟（900 秒）可达的节点
SELECT * FROM pgr_drivingDistance(
  'SELECT id, source, target, cost FROM roads',
  5, 900, false
);
-- 再把这些节点关联到人口点图层，汇总覆盖人口
​

最近设施分析在 PostGIS 里也可以直接用空间函数做：ST_DWithin 找候选，再按距离排序取前 N。两者区别是"沿路网的最短路径"和"直线距离"，现实场景沿路网更准。

十、网络分析的常见坑

• 拓扑缺失：线段端点没合并，路径断成孤岛。先 pgr_createTopology，再检查节点度。
• 成本单位混乱：有的边用米、有的用秒，结果毫无意义。统一成本字段和单位。
• 有向图方向错：单向边方向反了，导航路线绕远。用真实路网数据时检查 direction 字段。
• 结果落不到网络上：起点/终点离路网太远，先做最近节点投影（ST_ClosestPoint 或 pgr 的 withPoints）。

核心回顾

• 网络模型：图（节点+边），边权是距离/时间/费用。
• 最短路径：Dijkstra/A*/CH，导航核心。
• pgRouting：PostGIS 网络分析扩展。
• 数据准备：路网拓扑、边权、转向限制、单向边。
• 服务区：N 分钟可达范围，可达性分析。
• 最近设施：找最近 N 个，应急响应。
• VRP：多车多点配送，组合优化。

第 5 章结束。下一章讲 GIS 工程实践。