Laide140 / CRTrainRoute

# CRTrainRoute · 中国铁路算路器
基于 OSM 铁路网几何，计算**任意两座火车站之间的最短走行线路**，返回走行里程、线路几何、途经车站，并附带一个高德地图可视化页面。
- 🚄 **最短路径** — A\* 算法，22.5 万节点 / 24.5 万边的全国铁路网
- 📏 **指定里程** — `km=2800` 可规划一条里程最接近 2800 km 的绕行线路
- 🚉 **途经车站** — 沿线路程升序，自动剔除同址异名的城际别名站
- ⛴ **跨海轮渡** — 琼州海峡按直线距离自动连通，海南全省可达
- 🗺️ **地图展示** — 内置网页，输入中文站名即可在地图上查看线路
- ⚡ **零第三方依赖** — 纯 Python 标准库，无需 pip install
---
## 快速开始
 [code] 
打开 即可使用网页版。
> 仓库已包含构建好的 `data/rail_graph.pkl` 与铁路 geojson，**无需重新构建**。
> 若需从头构建，见 重新构建数据。
### 环境要求
- Python 3.9+
- 无需安装任何第三方包（仅标准库 `http.server`、`urllib`、`heapq` 等）
---
## API
### `GET /api/v3/stationRoute`
| 参数 | 必填 | 说明 |
|---|---|---|
| `from` | ✅ | 起点车站，支持**中文站名**（`广州南`）或**电报码**（`IZQ`） |
| `to` | ✅ | 终点车站，同上 |
| `km` | ❌ | 指定目标里程（公里）。留空 = 最短路径 |
 [code] 
响应示例（节选）：
 [code] 
| 字段 | 说明 |
|---|---|
| `distance.meters` / `kilometers` | 最短走行距离 |
| `stations[]` | 途经车站，按沿线里程升序。`km` 为距起点里程，`offsetM` 为车站到线路的垂直距离 |
| `kmPlan` | 指定里程规划的详情，未指定时为 `null` |
| `ferry` | 跨海轮渡信息 |
| `warnings` | 数据提示（跨海、线路断链等） |
| `geometry` | 完整线路坐标 `[lng, lat]`，可直接作为 GeoJSON 使用 |
| `snapOffsetM` | 车站坐标到铁路网的吸附距离 |
### 指定里程（`km=`）
 [code] 
| 目标 | 实际 | 偏差 |
|---|---|---|
| 2200 km | 2200.2 km | +0.2 |
| 2300 km | 2299.9 km | −0.1 |
| 2800 km | 2799.9 km | −0.1 |
| 3200 km | 3200.3 km | +0.3 |
| 上海虹桥→广州南 2000 km | 2000.7 km | +0.7 |
目标里程**小于最短路**时直接返回最短路（`reached: false`）。
### 跨海轮渡
OSM 只记录轨道、不含轮渡航段，海南岛铁路因此自成孤立分量。建图时会自动为
含车站的孤立分量寻找距主网最近的点对，按**直线距离**建一条跨海边：
| 连接 | 距离 | 类型 |
|---|---|---|
| 徐闻 ↔ 海口（琼州海峡） | 21.06 km | 跨海轮渡 |
| 主网 ↔ 平潭（平潭海峡） | 15.10 km | 跨海轮渡 |
| 其余 11 处 | 0.01~3 km | 站场内断链，直接补齐 |
 [code] 
网页中用**青绿色虚线 + ⛴ 轮渡 21.1 km** 标签单独绘制该段。
### 其他端点
| 端点 | 说明 |
|---|---|
| `GET /api/v3/searchStation?q=广州&limit=10` | 站名联想，返回 `[{code, name}]` |
| `GET /health` | 服务健康检查 |
| `GET /` | 地图可视化页面 |
### 错误码
| 状态码 | 场景 |
|---|---|
| 400 | 缺少 `from`/`to`，或 `km` 非正数 |
| 404 | 车站不存在 |
| 422 | 两站在铁路网中不可达 |
| 500 | 内部错误 |
 [code] 
---
## 实现要点
### 数据来源
| 数据 | 来源 |
|---|---|
| 铁路线几何 | next.laide.net.cn 各省 `{省代码}.geojson`（OSM 数据） |
| 车站坐标 | `POST https://mobile.12306.cn/wxxcx/wechat/bigScreen/getStationAddress`（`stationCode` = 电报码） |
| 电报码 / 站名 | `https://www.12306.cn/index/script/core/common/station_name_new.js` |
### 图构建
1. **要素过滤** — 只保留 `fclass=rail`，排除地铁、有轨电车、单轨、轻轨（全国 25,674 个，占 7.9%）
2. **建图** — 解析 32 个省级 geojson，约 29.9 万要素、168 万坐标点，坐标量化去重
3. **骨架压缩** — 删除度数为 2 的中间点，压缩为 **19.7 万节点 / 24.5 万边**
4. **几何保留** — 每条骨架边记录原始折线中间点，查询时可还原完整走向
5. **连通分量** — 最大分量覆盖 94.6% 节点
6. **跨海补齐** — 见上文
### 寻路算法
- **A\*** — 启发式为到终点的大圆距离（可采纳且一致，保证最优）
- **CSR 扁平数组** — 邻接表压成 `head` / `edge_to` / `edge_w`，状态用数组而非字典
- **结果缓存** — 铁路网静态，同一节点对的几何与途经车站可复用
优化过程：
| 实现 | 广州南→北京西 |
|---|---|
| 字典邻接 + Dijkstra | 6.27 s |
| CSR 邻接 + A\* | 0.54 s |
| CSR + A\* + 结果缓存 | **0.04 s** |
### 指定里程算法
分两阶段逼近目标：
1. **全局绕行** — 迭代地对已选路径的全部边加惩罚再求解，里程单调增大，得到覆盖
 「最短路 → 最大绕行」的候选序列
2. **局部微调** — 把候选路径的若干区间替换为「避开原边」的次短路，增量通常仅
 几十公里，用于填补候选间的跳跃空隙
> 试过三种单一方法均不可行：边权重微扰（路网冗余度低，无效）、部分边惩罚
> （长边会被拆成短边绕过）、单纯整路径惩罚（离散跳跃，偏差 40~97 km）。
### 车站吸附
车站坐标吸附到图节点时，**只允许吸附到最大连通分量内的节点**。车站附近常存在
站内孤岛（站线未与干线互通），吸附到