前不久看到了一个视频《我国有哪些距离很近且不在同一线路上的火车站？》，很好奇在这些地理位置相近的车站间进行转移，若只能采用铁路换乘的形式，在理论上的最优路径是什么？尝试了下12306的换乘查询，但不出所料给出的几乎都是包含同城换乘的方案。其它工具更是倾向于都是综合来看最优的方案，但并不符合我这个要求。于是我在 NAS 上挂了个任务，爬取了全国铁路列车的时刻表。

对于这个问题。我们可以定义这样一个模型

一个铁路网络被定义为一个元组 $G=(S, C)$，其中：$S$ 是一个有限的车站 (Station)集合。$C$ 是一个连接的集合。每个连接$c \in C$代表一个每日在固定时刻开行的车次，其形式为$c = (u, v, t_{d}^{\text{mod}}, \Delta t)$，其中：$u, v \in S$ 分别是出发站和到达站。 $t_{d}^{\text{mod}} \in [0, 1440)$ 是该服务的出发时刻，代表以分钟计的当天相对时间。$\Delta t \in \mathbb{R}^+$ 是该服务的行程耗时。一条路径$P$是一个由$k$个已乘坐连接组成的有序序列$ P = (\hat{c}_1, \hat{c}_2, \ldots, \hat{c}_k)$。每个“已乘坐连接” $\hat{c}_i$ 是一个元组 $\hat{c}_i = (c_i, T_{d,i}, T_{a,i})$，其中：$c_i = (u_i, v_i, t_{d,i}^{\text{mod}}, \Delta t_i) \in C$ 是时刻表中的一个连接。$T_{d,i} \in \mathbb{R}$ 是本次乘坐的绝对出发时间。$T_{a,i} \in \mathbb{R}$ 是本次乘坐的绝对到达时间。这些值必须遵循以下的规则：首段行程$\hat{c}_1$ 的绝对出发时间 $T_{d,1}$ 是在某个出发日期 $D \in \mathbb{Z}$ 时该服务的出发时刻，即 $T_{d,1} = D \times 1440 + t_{d,1}^{\text{mod}}$。其到达时间为 $T_{a,1} = T_{d,1} + \Delta t_1$。后续行程对于所有 $i \in [1, k-1]$，$\hat{c}_{i+1}$ 必须满足：$v_i = u_{i+1}$。其绝对出发时间 $T_{d,i+1}$ 是旅客在时刻 $T_{a,i}$ 到达车站 $v_i$ 后，所能乘坐的最早一班 $c_{i+1}$ 服务。

目标函数是总行程时长，这是一个非累加性的目标函数。单源最短路算法的正确性依赖于边的权值可以累加并且满足最优子结构。但目前这种情况一条路径的总成本无法通过其子路径的成本简单推导得出。

很显然，不能简单地在以物理车站为节点的图上跑最短路。于是我们可以定义以当前路径的到达时间，整个旅程的初始出发时间和当前所在的车站为一个状态，然后按照状态的经由时间维护优先队列跑 Dijkstra ，问题就解决了。

但是似乎这样效率并不高，想了下如果目标只是求最优的一个解，可以直接舍弃掉那些到达晚于已有状态且出发早于已有状态的状态。不过问题是这样并无法求出前 K 个最优路径，但作为寻找可行的解是足够了。于是就有了CRTransfer这个项目。