LegalFarePlan：非累加票价规则下票价透明的城市铁路路径规划的标签设置框架

# LegalFarePlan：面向非可加性票价规则下票价透明化城市轨道交通路径规划的标号设定框架
来源：https://arxiv.org/html/2607.09755

###### 摘要

城市轨道交通票价体系可能具有非可加性：从起点到终点的单次付费行程的票价，可能与多个合法分离行程段的票价之和不同。本文提出*LegalFarePlan*，一个票价透明化的路径规划框架，将合法出站再进站操作建模为显式、可审计的约束。给定交通网络、票价函数、换乘规则、车站级出站/再进站成本、额外时间预算以及分割次数限制，规划器可计算包含付费行程段的可解释路径方案。该工件实现了Dijkstra最短时间路径规划器基线、直接路径规划器基线、贪心分割启发式、有界精确标号设定以及帕累托前沿搜索。评估使用了受控合成数据以及一个包含57个车站、360个OD对的半合成基准。在半合成基准上，有界精确搜索在45分钟额外时间预算下，对71.11%的OD对识别出正面建模票价降低，平均降低3.78个合成票价单位，最大降低9.0个合成票价单位。这些结果展示了方法的行为和可复现性；并非关于港铁或任何交通运营商的实证结论。

数据和合法性范围。本文中的所有出站再进站策略均建模为合法行为：乘客通过正常闸机出站，通过正常闸机重新进站，并为每个付费行程段支付公布票价。该工件不模拟逃票、车票滥用、系统篡改、闸机操作或法规规避。包含的数据集是合成的或半合成的，仅用于算法验证和可复现性。

## I 引言

交通路径规划通常被表述为最短路径或多标准路由问题，其中规划器优化旅行时间、换乘、步行、可靠性或广义成本。票价常被处理为静态的OD属性。这种简化对于具有非可加性票价规则的交通系统来说是不够的。在这类系统中，从车站\(o\)到车站\(d\)的一次连续付费行程的票价，可能与将行程分割成多个合法付费行程段获得的总票价不同。乘客可以在中间车站合法出站并重新进站，但这一操作具有时间、不便以及有时是金钱成本。

本研究研究以下路径规划问题：

> 给定一个铁路网络、一个非可加性票价表、明确的换乘规则、合法出站/再进站成本以及用户约束，计算一个最小化总付费票价的路径方案，同时报告时间、换乘次数、出站/再进站操作次数以及人类可读的解释。

这个问题不能简化为物理最短路径。规划器必须结合两层：物理路由层，用于检查每个行程段是否可通过网络行驶；以及票价层，用于为每个合法付费行程定价。这种分离对可复现性很重要：物理网络数据、票价表、换乘规则和合法出站假设都可以独立审计。

贡献如下：

1. 1. 对具有合法出站再进站操作的非可加性交通票价规则下票价感知路径规划的形式化定义。
2. 2. 一个可复现的CSV模式，涵盖车站、物理连边、票价、换乘规则、出站/再进站惩罚以及OD基准。
3. 3. 一个标准库Python工件，包含Dijkstra最短时间、直接路径规划器、贪心、有界精确标号设定和帕累托前沿模式。
4. 4. 一个受控的8车站合成基准和一个更大的57车站半合成基准，用于在许可的真实数据不可用时进行可复现的评估。
5. 5. 实验脚本、测试、表格和图表，使所有报告的建模票价降低结果可追溯到程序输出。

## II 相关工作

物理路由组件建立在最短路径搜索之上，从Dijkstra算法开始[1 (https://arxiv.org/html/2607.09755#bib.bib1)]。现代公共交通行程规划器将最短路径扩展到时刻表、换乘和多模态约束[2 (https://arxiv.org/html/2607.09755#bib.bib2),3 (https://arxiv.org/html/2607.09755#bib.bib3),4 (https://arxiv.org/html/2607.09755#bib.bib4)]。所提出的票价感知问题也与多标准最短路径相关，其中标签在多个目标上维护，并修剪被支配的标签[5 (https://arxiv.org/html/2607.09755#bib.bib5)]。然而，票价感知的出站再进站规划不同于标准的多标准路由，因为目标是在*付费行程段*上计算，而不仅仅是在物理连边上。

交通网络分析也与分配模型相关。Wardrop均衡原理为路径选择建模提供了早期基础[6 (https://arxiv.org/html/2607.09755#bib.bib6)]，而Spiess和Florian则在服务不确定性下提出了公共交通分配的最优策略公式[7 (https://arxiv.org/html/2607.09755#bib.bib7)]。本文不解决系统级分配问题，但借鉴了面向乘客的计划应通过显式广义成本和操作约束进行评估的观点。

票价感知路由进一步依赖于票务和票价数据。智能卡和自动售票收集数据已被广泛研究用于OD推断和公共交通分析[8 (https://arxiv.org/html/2607.09755#bib.bib8),9 (https://arxiv.org/html/2607.09755#bib.bib9),10 (https://arxiv.org/html/2607.09755#bib.bib10),11 (https://arxiv.org/html/2607.09755#bib.bib11)]。这些研究激发了对仔细数据溯源和票价产品解释的需求。LegalFarePlan与需求估计工作不同，它将票价表视为明确的算法输入，并专注于法律上可解释的路径方案。

该工件也与可复现计算研究相关。它不报告没有可审计证据的运营商特定结论，而是分离数据模式、验证、算法和生成的输出。这一点至关重要，因为交通票价表依赖于政策、车票产品并随时间变化。工件审查和徽章实践同样强调可重用计算证据的重要性[12 (https://arxiv.org/html/2607.09755#bib.bib12)]。

## III 动机示例

受控合成基准包含一个紧凑的城市铁路网络，有三条线路和八个车站。从Alder Central (A) 到 Harbor Expo (H) 的直接合成票价为18.0。从A到Elm Park (E) 的合法付费行程段成本为8.0，从E到H的合法付费行程段成本为5.0。如果乘客在E处出站并重新进站，总付费票价为13.0。物理行程仍然有效，模型添加了一个特定车站的出站/再进站时间惩罚。

优化器报告在Elm Park (E) 处有一个合法分割，建模票价降低5.0，相对于直接方案的额外建模时间为2.0分钟。这个例子说明了核心建模问题：路径在物理上可能相似，但其付费行程分解改变了票价。因此，规划器必须同时推理网络路径和票价行程段序列。

## IV 问题形式化

设\(G=(V,E)\)为一个城市铁路网络。每个车站\(v \in V\)具有元数据，包括一个标志位，指示模型是否允许在\(v\)处合法出站再进站。每个物理连边\(e=(u,v,\ell)\)具有线路标识符\(\ell\)和旅行时间\(t(e)\)。换乘规则定义是否允许在车站\(v\)处从线路\(\ell_i\)换乘到线路\(\ell_j\)，并指定相应的换乘时间。

设\(\mathsf{fare}(o,d)\)为从车站\(o\)到车站\(d\)的一次付费行程的票价函数。该函数可能具有非可加性：

\[
\mathsf{fare}(o,d) \neq \mathsf{fare}(o,x) + \mathsf{fare}(x,d).
\]

设\(X \subseteq V\)为模型允许合法出站再进站的车站集合。每个\(x \in X\)有时间惩罚\(\mathsf{penalty}^{\mathrm{time}}(x)\)和可选的金钱惩罚\(\mathsf{penalty}^{\mathrm{money}}(x)\)。

对于OD对\((o,d)\)的一个票价感知路径方案是一个序列

\[
P = (s_0 = o, s_1, \ldots, s_m = d),
\]

其中每个中间车站\(s_i\)（对于\(1 \le i < m\)）是一个合法出站再进站车站。每对连续\((s_i, s_{i+1})\)是一个付费行程段。总金钱成本为

\[
C(P) = \sum_{i=0}^{m-1} \mathsf{fare}(s_i, s_{i+1}) + \sum_{i=1}^{m-1} \mathsf{penalty}^{\mathrm{money}}(s_i),
\]

总建模时间为

\[
T(P) = \sum_{i=0}^{m-1} \mathsf{shortestTime}_G(s_i, s_{i+1}) + \sum_{i=1}^{m-1} \mathsf{penalty}^{\mathrm{time}}(s_i).
\]

函数\(\mathsf{shortestTime}_G\)是在带有换乘规则的物理网络上计算的。

优化问题为：

\[
\begin{aligned}
\min_{P} \quad & C(P) \\
\text{s.t.} \quad & m-1 \le K, \\
& T(P) \le T(P_{\mathrm{direct}}) + \Delta, \\
& s_i \in X \quad \forall i \in \{1, \ldots, m-1\}, \\
& \mathsf{fare}(s_i, s_{i+1}) \text{ 已定义} \quad \forall i, \\
& \mathsf{shortestTime}_G(s_i, s_{i+1}) < \infty \quad \forall i.
\end{aligned}
\]

主要目标是最小化金钱成本。打破平局时考虑更短的旅行时间、更少的出站次数、更少的换乘次数和更简单的解释。

### IV-A 假设与非目标

该形式化有意将优化与政策解释分离。首先，票价表假定为对于固定票种定义了付费行程段的金钱成本。其次，只有当车站级数据明确允许时，才允许出站再进站操作，并且每次分割都会创建一个新的付费行程段。第三，旅行时间是确定性的连边时间和换乘时间；时刻表效应、发车间隔、拥挤和中断不在当前模型范围内。最后，规划器是咨询性的：它报告建模的法律假设，并不取代运营商规则、乘客条件或当地法规。

## V 算法

### V-A 物理路由

物理层在车站-线路状态\((v,\ell)\)上运行Dijkstra式搜索。沿着一条连边移动会增加车内时间。在车站\(v\)处从线路\(\ell_i\)切换到线路\(\ell_j\)仅在存在明确换乘规则且标记为有效时才被允许。这种设计避免了基于名称的换乘推断，这对于可复现的交通路由来说是不安全的。

### V-B 基线

直接票价基线。直接基线返回一次付费行程\((o,d)\)，如果\(\mathsf{fare}(o,d)\)存在且物理路由可行。

最短时间基线。最短时间基线计算物理上最短的路由而不插入付费行程段分割。在当前工件中，直接基线和最短时间基线共享相同的付费行程段结构，但在概念上有所不同：一个定义了票价比较点，另一个定义了物理时间参考。

### V-C 付费行程段搜索空间

票价层可以看作一个有向辅助图，其节点为车站，弧为合法付费行程段。只有当票价条目\(\mathsf{fare}(u,v)\)可用且物理路由层可以找到从\(u\)到\(v\)的可行路径时，弧\((u,v)\)才存在。因此，一条方案路径是该辅助图中的一条路径，中间节点被限制为合法出站再进站车站。这种观点使非可加性票价规则变得显式：成本附加在付费行程段弧上，而不是物理轨道连边上。

### V-D 贪心分割启发式

贪心启发式从直接方案开始，反复在当前序列中插入一个合法分割车站。对于每个插入位置和候选车站，规划器检查票价行程段可用性、物理可达性、分割次数和额外时间可行性。它接受最佳改进的插入，并在没有插入能改进方案或已使用\(K\)次分割时停止。

### V-E 有界精确标号设定搜索

精确搜索将合法付费行程段视为转移。状态为\((v,k)\)，其中\(v\)是当前车站，\(k\)是已使用的出站再进站操作次数。一个标签存储票价、时间、分割次数和车站序列。标签\(a\)支配标签\(b\)（记为\(a \preceq b\)），如果\(a\)在票价、时间和分割次数上都不比\(b\)差，并且至少在其中一个方面严格更好。

搜索初始化直接方案作为当前最佳解，设置时间上限为\(T(P_{\mathrm{direct}}) + \Delta\)，并按照票价递增的顺序扩展标签。从位于车站\(v\)的标签开始，它测试每个车站\(x\)，要么作为终点，要么作为合法分割车站。只有当付费行程段\((v,x)\)有票价条目、物理路径可行、分割次数不超过\(K\)且累计时间在限制内时，转移才被接受。终点标签更新当前最佳解；中间标签仅当在相同车站-分割状态下不被支配时才被插入。

###### 命题1（有界最优性）。

对于固定的OD对、分割次数限制\(K\)、额外时间预算\(\Delta\)、票价表、物理图、换乘规则和出站/再进站惩罚表，精确搜索返回一个在所有满足约束的合法付费行程段序列中具有最小金钱成本的可行方案，假设没有可行的被支配标签被丢弃。

*草图*。搜索枚举所有可行的合法付费行程段转移，最多\(K\)次分割和时间限制。一个被丢弃的标签被相同状态下的另一个标签所支配，该标签在票价、时间或分割次数上都不更大，因此在非负行程段成本和惩罚下，扩展被支配标签不能产生更好的可行方案。因此，修剪被支配标签保留了每个潜在最优延续的至少一个代表。

###### 命题2（直接上界）。

如果直接方案可行且包含在候选集合中，精确优化器返回的金钱成本不大于直接票价。

*草图*。算法使用直接方案初始化当前最佳解。它仅用字典序更好的可行方案替换当前最佳解。因此，最终方案不可能具有比直接方案更高的金钱成本。

### V-F 帕累托前沿搜索

帕累托模式返回关于票价、旅行时间、出站惩罚、分割次数和换乘次数的非支配可行方案。当决策者希望检查票价-时间权衡而非接受单个标量化结果时，此模式很有用。

### V-G 复杂度

设\(n=|V|\)，\(K\)为分割次数限制，\(L\)为每个车站-分割状态保留的非支配标签数量，\(R\)为一次物理最短路径查询的成本。如果不缓存，在搜索期间检查所有候选付费行程段可能代价高昂。因此，LegalFarePlan缓存物理路径和付费行程段可行性；每个不同的OD行程段在车站-线路图上最多求解一次。有界票价层搜索最多有\(O(nKL)\)个保留标签，每个标签考虑最多\(O(n)\)个出站付费行程段候选，因此在路径缓存后给出\(O(n^2KL)\)次票价层转移检查。路径缓存构建的上界为\(O(n^2R)\)。