Metropolitan Routing Algorithm

全球 60 座城市的街道网络可视化，以及基于真实地图数据的路由算法研究平台。

---

这是什么

两件事，互相服务：

第一件：看城市。 把世界上最有意思的城市街道网络渲染成深橙色霓虹风格的高清地图——芝加哥的方格网、东京的环状超密度、巴西利亚的飞机轮廓、威尼斯的运河迷宫。每座城市的路网都是一张独特的"城市指纹"。

第二件：跑算法。 同一份 OpenStreetMap 数据在渲染地图的同时，被保存为结构化的图数据（节点 + 边），供后续在真实城市路网上运行 A*、Dijkstra 等路由算法，测试性能和寻路效果。

---

城市列表

共 60 座城市，分三个梯队：

梯队	选城标准	数量
第一梯队	视觉冲击力强的经典城市	15
第二梯队	全球地理覆盖	35
第三梯队	路网形态奇特（飞机轮廓、全运河、完美45°旋转网格…）	10

详见 map/TIER3_奇特路网城市.md 和 map/TIER1_2_城市路网分类.md。

---

目录结构

Metropolitan-Routing-Algorithm/
│
├── map/                          ← 地图渲染模块
│   ├── render.py                 ← 主渲染脚本
│   ├── cities.py                 ← 60 座城市列表
│   ├── style.py                  ← 颜色方案和线宽常量
│   │
│   ├── gallery/                  ← 渲染输出（4K JPG，60 张）
│   │   ├── Chicago.jpg
│   │   └── ...
│   │
│   ├── graphs/                   ← 路网原始数据（供算法使用）
│   │   ├── Chicago_nodes.parquet
│   │   ├── Chicago_edges.parquet
│   │   └── ...
│   │
│   └── 数据格式说明.md
│
└── algorithm/                    ← 路由算法模块
    ├── main.py                   ← 主调度器（多核并行跑所有城市×算法）
    ├── endpoints.py              ← 最远端点对计算（双轮 Dijkstra 近似）
    ├── algo/                     ← 8 种算法实现（各自独立文件，含中文注释）
    │   ├── bfs.py                ← BFS 广度优先
    │   ├── dfs.py                ← DFS 深度优先
    │   ├── dijkstra.py           ← Dijkstra
    │   ├── bellman_ford.py       ← Bellman-Ford（仅小图）
    │   ├── astar.py              ← A*（单向）
    │   ├── greedy_bfs.py         ← 贪婪最佳优先
    │   ├── bidir_dijkstra.py     ← 双向 Dijkstra
    │   └── bidir_astar.py        ← 双向 A*
    ├── viz/
    │   ├── renderer.py           ← 帧渲染（numpy + Pillow，不逐帧调 matplotlib）
    │   ├── gif_maker.py          ← 50 帧采样 + 末尾停留 → GIF
    │   └── style.py              ← 蓝色系配色 + 自动检测中文字体
    ├── results/                  ← 算法输出（GIF、JSON 指标、最终静图）
    ├── algorithm_review.ipynb    ← 结果查看（每算法一个 2×2 四城市网格）
    └── ALGORITHM_PRD.md

---

快速开始

环境要求

pip install osmnx matplotlib numpy scipy pillow geopandas

渲染单张城市地图（测试）

cd map
python render.py 0 1    # 只渲染 Chicago

渲染全部 60 座城市

cd map
tmux new-session -s citymap
python render.py 2>&1 | tee render.log

预计总耗时 3–5 小时，已完成的城市在重启后自动跳过。

读取路网数据

import geopandas as gpd
import osmnx as ox

nodes = gpd.read_parquet('map/graphs/Chicago_nodes.parquet')
edges = gpd.read_parquet('map/graphs/Chicago_edges.parquet')

# 还原为 NetworkX 图，直接跑算法
edges = edges.set_index(['u', 'v', 'key'])
G = ox.graph_from_gdfs(nodes, edges)

---

数据来源

全部数据来自 OpenStreetMap，通过 osmnx 下载。ODbL 协议，学术和非商业用途免费使用。

---

技术说明

地图渲染

• 数据来源：OpenStreetMap → osmnx 下载后投影至本地 UTM 坐标系
• 渲染引擎：matplotlib LineCollection（向量绘制，支持百万级边）
• 光晕效果：对主干道额外绘制 5× 宽度、7% 透明度的同色宽线模拟发光
• 输出：4K JPG（quality=92），单张约 3–10 MB

为什么下载的 JSON 很小，存下来的数据却很大？

OSM 原始格式是高度压缩的引用结构：节点坐标只存一次，道路只记录"经过哪些节点 ID"，多条路共用同一个节点也不会重复存坐标。

原始 JSON：
  节点 12345: {lat: 41.8781, lon: -87.6298}   ← 坐标存一次
  道路 A:     [12345 → 12346 → 12347]          ← 只存 ID

osmnx 处理后，三件事同时发生：

1. 坐标从引用变内嵌 — 每条边都把完整折线坐标复制进去，不再共用
2. 双向路拆成两条边 — 一条路 = 两条有向边，数据量直接翻倍
3. 追加大量计算列 — 投影坐标（x/y 米制）、length、speed、travel_time……原始 JSON 里没有，全是算出来塞进去的

处理后：
  边 (12345→12346): geometry=LineString([坐标1, 坐标2]) + length + highway + ...
  边 (12346→12345): ← 反向再存一条

纽约 137 万条边，每条带着完整坐标串和十几列属性，体积自然上去了。Parquet + zstd 是在展开后的数据上重新压缩，能小很多，但永远比原始引用结构大。

图数据存储

从 graphml（XML 纯文本，数百 MB）改为 Parquet + zstd 压缩：

格式	大小（纽约，137万条边）	读取速度
GraphML	~800 MB	慢
GraphML.gz	~80 MB	慢
Parquet + zstd	~20–40 MB	极快

每座城市存两个文件：<城市>_nodes.parquet（路口坐标）+ <城市>_edges.parquet（路段属性），渲染时一并生成，复用同一份 GeoDataFrame，不重复计算。

节点关键字段：osmid / x / y / lon / lat 边关键字段：u / v / length / highway / maxspeed / oneway

详细字段说明见 map/数据格式说明.md。

---

算法模块

测试场景

在四座城市的路网中选取最远端点对（路径距离最长的两个路口）作为起终点——搜索空间被迫覆盖整个城市，是对算法最极端的压测。

城市	节点数	边数
Hong Kong, China	176,069	452,067
Seoul, South Korea	171,490	~400,000
Lahore, Pakistan	172,146	~380,000
Washington D.C., USA	109,425	~280,000

最远端点对用双轮 Dijkstra 近似法计算（误差 < 5%），结果缓存到 results/<城市>/endpoints.json，不重复计算。

8 种算法

算法	类型	保证最优解	参与 GIF 对比
BFS 广度优先	盲目搜索	仅最短跳数	✅
DFS 深度优先	盲目搜索	❌	—
Dijkstra	经典最短路径	✅	✅
Bellman-Ford	最短路径（支持负权重边）	✅	仅小子图
A*（单向）	启发式搜索	✅	✅
贪婪最佳优先	启发式搜索	❌	✅
双向 Dijkstra	双向搜索	✅	✅
双向 A*	双向 + 启发式	✅	✅

A* 的启发函数使用 UTM 投影坐标下的欧几里得直线距离（单位米），满足可采纳性（admissible），保证最优解。

预期加速比（vs Dijkstra 基准）

算法	扩散节点量（估算）	速度提升
Dijkstra	~全图（基准）	1×
A*（单向）	~1/8	~8×
贪婪最佳优先	~1/20（不保证最优）	~20×
双向 Dijkstra	~1/16	~16×
双向 A*	~1/30	~30×

可视化

每种算法生成一个 GIF 动画：

• 50 帧均匀采样扩散过程，最后 3 秒停留在路径找到的最终状态
• 蓝色系叠加在城市路网底图上（深色越早访问，亮色越晚）
• 双向算法正向/反向用两种色调区分

快速开始（算法）

cd algorithm

# 全部 4 城市 × 6 算法，多核并行
python main.py

# 只跑单城市或单算法
python main.py --city Hong_Kong --alg astar

# 只计算最远端点，不跑算法
python main.py --endpoints-only

# 查看结果（每个算法一个 2×2 四城市网格）
jupyter notebook algorithm_review.ipynb